hashMap

数据结构

数组+链表/红黑树

是否允许空键空值

key只允许有一个,多了会覆盖.value可以多个.

重要参数

1.初始容量:16.

2.负载因子,0.75.

3.hash的计算:

h=h^(h>>>16),高位与低16位异或运算.增大随机性.比如map的length=8,添加一串数字,9,17,25直接取模都会放到tale[1],但是进行异或后,就不会都在一个位置了.

h&(length-1),取模确定数组的槽位.

PUT流程

hashmap的底层长度为何总数2的n次方

现象:在初始化hashmap的时候,hashmap总数会无符号右移和位运算,计算出来一个大于传入的值的2次幂.

原因1:在根据hash计算数组槽位的时候,一般取模用的公式: h%length 正好可以由h&(length-1)替代.将十进制的计算替换为速度更快的位运算.

原因2:减少hash冲突,使key均匀分布.

对于length如果是奇数的话,比如17,length-1就是偶数16,二进制是10000,h&10000,最后一位都是0,因此数组的偶数位都会空着.

对于length如果是偶数的话,比如16,length-1的二进制是1111,h&1111,最后一位数可以取决于h,减少了hash冲突.

1.8的hashmap做了哪些优化

1.结构由数组+链表变为了数组加链表/红黑树.

2.链表的增加方式由头插法变为了尾插法.

原因:在多线程情况下,触发扩容的时候,map的put和扩容都采用头插法,改变了链表中node的顺序,会形成环.

1.8的时候采用了尾插法,这个在扩容时不会改变node的顺序,从而避免环.

hashMap都会有线程安全问题

1.7的hashmap会形成环.

1.8的hashmap会发生数据覆盖.

1.8的扩容为什么会更简单

1.7的扩容会进行rehash,重新计算hash值.

1.8的扩容不会重新计算hash,只看mask最高位是0还是1,是1的话,就原位置+oldCap.