HashMap

JDK1.7 数组+链表

JDK1.8 数组+链表，链表长度>8 --> 红黑树

1.7

根据hash计算index，一般index= hash % length, 让键值对均匀分配在数组中

插入元素时可能产生 哈希冲突，所以产生了链表

链表的缺陷： 查询O（N）

为什么需要指数次幂？

负载因子：0.75

initialCapacity数组的初始长度：2的指数次幂

如果自己定义的不是，在put时在inflateTable里改成大于这个数的第一个2的指数次幂

提高效率：取模运算在底层需要换算成2进制，计算效率：加>×>除>mod，所以用h&(length-1)代替

当length是2的指数次幂，才会相等。

这样保证求出的index在length范围之内，不会越界

加载因子为什么是0.75

loadfactor=1，可以最大化利用空间

loadfactor=0.5，可以尽量避免哈希冲突，查询效率高，节省时间，当用到一半就扩容

为什么链表长度是8

产生hash碰撞的时候，放在一个桶里面，放在链表后面的概率符合泊松分布

泊松分布：负载因子0.75时，随着链表里节点的增加，定位到同一个桶的概率越来越小，产生红黑树的概率所以也不大，所以jdk8比7提高了8-10%的性能

扩容

jdk7

put时，addEntry，如果size大于阈值且当前桶不为空，就会扩容resize

resize: 扩容需要转移数组transfer

多线程时会出现环

transfer的作用

问题：会产生死锁，因为会颠倒链表中的位置

jdk8

首先，定义了4个新的变量：

• loHead, loTail

• hiHead, hiTail

当前hashcode & oldCap（eg.16）

• 结果要么0000全是0，要么是16

（如果本身的hashcode<16,则&的结果为0，如果hashcode>=16，则&的结果为16

如果&的结果是0，则是低位，否则是高位

迁移过程

loTail断掉，loHead在新数组下标相同的位置

hiTail断掉，hiHead在新数组下标原下标+原数组长度

好处：

用高低位避免了死锁，

没有重新进行hash计算，

几乎算是均匀的拆分，

避免了链表环的产生，

这也是为什么要2的指数次幂的原因