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代表对应最高位不为零,需要移动到高位索引。
网友评论