JAVA基础--集合相关

List(顺序、可重复、单元素)

ArrayList

• 底层：数组Object[] elementData
• 构造
  • 无参
    • 默认容量空，0；
  • 指定容量
• 添加
  • 添加先判断容量，所需容量为size+1；
  • 初始为0取max(10,size+1)；
  • 初始不为0取size+1；
  • 大于当前size就grow();
  • elementData[size++] = e;

• 扩容grow()X1.5

  • newCapacity = ole +( old>>1);
  • elementData[] = Arrays.copyOf(elementData(T[]),newcapacity(int));

    Vector

• 底层：数组

• 构造
  • 无参
    • 10
  • 指定大小
• 添加
  • elementCount+1 - length>0;
  • grow();

• 扩容X2

  • new = old +(增量(默认0可指定)>0？增量：old);

    LinkedArrayList

• 底层：数组+双向链表:Node;

  • Node next;Node prev;
  • Node first; Node last;
• 构造：
• 添加：newNode;
• 删除（默认删第一个）

• 扩容：不需要

  Set（无序、不可重复、单元素）

  HashSet（放入无序，取出有序固定（不是添加的顺序））

• HashSet底层就是基于HashMap，值为key,value为虚拟对象Object PRESENT

• 添加
  • put(new String(“xxx))
  • put(new String(“xxx)) //添加失败，因String重写了hash和equals方法。
  • hashmap key转换为hash值转换为索引；
    • hash = (key==0)? 0 : (h = key.hashCode()) ^ (h>>>16);
    • 右移16为避免碰撞，尽量每一位都参与计算。
  • 若索引有元素，直接添加；
  • 若有元素，调用equals比较；相同不添加；不同添加到链表。
• 树化：冲突>=8-1
  • 条件1：冲突>=8-1
  • 条件2：table>=63（!table<64）
• 去重
  • 先hashcode判断，没有相等的就假设无重复存。
  • 若相等，equals()看是否碰撞。不等不存。
• 为什么重写equals必须重写hash
  

  hashCode()的默认⾏为是对堆上的对象产⽣独特值。如果没有重写 hashCode()，则该 class 的两个 对象⽆论如何都不会相等（即使这两个对象指向相同的数据）。 k1, k2;//引用类型，值相等。 map.put(K1,v1); map.get(K2)//失败因hash(k1)!=hash(k2) hash()没重写，是Object的，对应的是k1k2在堆的hash

@Data
public class Key{
    private Integer id;
    @Override
    public boolean equals(Object o){
       // if(o == null || !(o instanceof Key)){
       //     return false;
       // }else{
       //     return this.getId().equals((Key)o.getId());
       // }
        if(o intanceof Key){
            return this.getId().equals((Key)o.getId());
        }
        return false;
    }
    @Override
    public int hashCode(){
        return id.hashCode();
    }
}

• equals方法必须要满足以下几个特性
• 1.自反性：x.equals(x) == true,自己和自己比较相等
• 2.对称性：x.equals(y) == y.equals(x),两个对象调用equals的的结果应该一样
• 3.传递性：如果x.equals(y) == true y.equals(z) == true 则 x.equals(z) == true,x和y相等，y和z相等，则x和z相等

• 4.一致性 : 如果x对象和y对象有成员变量num1和num2，其中重写的equals方法只有num1参加了运算，则修改num2不影响x.equals(y)的值

  LinkedHashSet（extend HashSet）

• 底层：LinkedHashMap; 数组 + 双向链表

• 构造：无参（）:super(16, .75f, true); HashSet(16,.75f,true);
• 添加：newNode;
• 顺序：双向列表保证有序。
• 删除（默认删第一个）

Map（键值对）

HashMap（k可为一个null）

• 底层：数组Node[] table
  • 最大值：table<= 1 << 30(2);容量必须2的次幂。
  • 负载因子：0.75(默认)，泊松分布；随机hash下，节点分布符合泊松分布。
  • 无序：索引来自key的hash。
• 构造方法
  • 无参：空
  • 指定初始值
• 扩容：
  • 第一次：1<<4 =16
  • 之后： new = old <<1 (2倍)
• 冲突：
  • 链表；
  • 当binCount >= 8-1:树化

• 树化：

  • table < 64; resize() 后添加；第一次16>32 添加，第二次 32>64添加；

    LinkedHashMap

• 底层

  • Entry extends HashMap.Node {
  • Entry before, after;}

    HashTable（kV不可为null，否则NPE）

    TreeMap

工具类Collections