JDK1.8 的 HashMap 在很多方面都做了优化改进, 其中扩容时引入了高低位机制, table 数组中某个位置的链表或者红黑树中的节点在扩容时, 不需要重新按照以前的方式计算索引位置, 而只要计算 hash 值在旧容量最高位对应的二进制是 1 还是 0, 是 1 泽回移动到高位索引 (原索引位置 + 原容量), 是零则在低位索引也就是原位置.
举例如下:
hash 值 h 二进制为
0010 1100 1111 0001 1110 1110
旧容量为 length=16, 二进制为
- 0001 0000
- length-1=0000 1111
那么扩容前索引位置为
h&(length-1)=1110=14
扩容后, 容量为 32, 对应二进制为
0010 0000
新 length-1=0001 1111
hash 值对新容量计算索引时, 可以看出最后四位二进制是不变的, 与原容量时计算一致, 唯一变化的是倒数第五位的二进制值, 本例中 hash 对应新索引不变还是 14, 因为 hash 的倒数第五位为 0
如果 hash 为 0100 0001 0010, 旧容量中索引为 0010=2, 新容量下索引为 0001 0010=18=2+16.
结论
可见在扩容后, 索引位置要嘛不变, 要嘛移动旧容量个位置.
而判断的依据就是 hash 值在扩容后容量 - 1 的最高位对应的值, 而扩容后容量 - 1 的最高位其实就是扩容前容量的最高位.
因此可以通过 h&oldcap 来判断,=0 代表对应最高位为零, 不移动位置;>0 代表对应最高位不为零, 需要移动到高位索引.
来源: http://www.jianshu.com/p/a69d88b2d1f0