List(顺序、可重复、单元素)
ArrayList
- 底层:数组Object[] elementData
- 构造
- 无参
- 默认容量空,0;
- 指定容量
- 无参
- 添加
- 添加先判断容量,所需容量为size+1;
- 初始为0取max(10,size+1);
- 初始不为0取size+1;
- 大于当前size就grow();
- elementData[size++] = e;
扩容grow()X1.5
底层:数组
- 构造
- 无参
- 10
- 指定大小
- 无参
- 添加
- elementCount+1 - length>0;
- grow();
扩容X2
底层:数组+双向链表: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:树化
树化:
底层