美文网首页后台开发笔记
JDK1.8中HashMap的高低位索引机制

JDK1.8中HashMap的高低位索引机制

作者: 山东大葱哥 | 来源:发表于2020-01-23 10:01 被阅读0次

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

    相关文章

      网友评论

        本文标题:JDK1.8中HashMap的高低位索引机制

        本文链接:https://www.haomeiwen.com/subject/uuhnzctx.html