ZxYuan/zxyuan.me

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

Opened this issue · 0 comments

源码版本: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)