java.util.HashMap源码阅读---Java 8 HashMap的resize策略

[ZxYuan]

源码版本：openjdk 8-b132

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/HashMap.java?av=f#665

当键值对数量超过既定阈值时，HashMap需要扩容，同时完成重哈希。Java 8以前采用较为简单的策略，即遍历所有键值对，新索引位置=hash&(新的数组容量-1)；Java 8中的HashMap不仅采用拉链法解决哈希碰撞，当每条链的键值对数量大于阈值TREEIFY_THRESHOLD（源码中为8）时，将采用红黑树代替链表存储，以减小复杂度。

需要注意的是，每次扩容后的容量都是2的幂次倍（源码中初始默认容量为16）。

resize函数处理HashMap的扩容和重哈希操作，函数中新建一个散列表数组，容量为旧表的2的幂次倍，接着需要把旧表的键值对迁移到新表，这里分三种情况，这里详细说明第三种情况：

1. 表项只有一个键值对时，针对新表计算新的索引位置并插入键值对
2. 表项节点是红黑树节点时（说明这个bin元素较多已经转成红黑树了），split这个bin。
3. 表项节点包含多个键值对组成的链表时（这里与以往版本不同）：

把链表上的键值对按hash值分成lo和hi两串，lo串的新索引位置与原先相同[原先位置j]，hi串的新索引位置为[原先位置j+oldCap]；

第3种情况的解释：链表的键值对加入lo还是hi串取决于 判断条件if ((e.hash & oldCap) == 0)，因为capacity是2的幂，所以oldCap为10...0的二进制形式，若判断条件为真，意味着oldCap为1的那位对应的hash位为0，对新索引的计算没有影响（新索引=hash&(newCap-1)，newCap=oldCap<<2）；若判断条件为假，则 oldCap为1的那位对应的hash位为1，
即新索引=hash&( newCap-1 )= hash&( (oldCap<<2) - 1)，相当于多了10...0，即oldCap

例子：
旧容量=16，二进制10000；新容量=32，二进制100000
旧索引的计算：
hash = xxxx xxxx xxxy xxxx
旧容量-1= 1111
&运算 xxxx
新索引的计算：
hash = xxxx xxxx xxxy xxxx
新容量-1= 1 1111
&运算 y xxxx

新索引 = 旧索引 + y0000，若判断条件为真，则y=0(lo串索引不变)，否则y=1(hi串索引=旧索引+旧容量10000)