HashMap的扩容机制

hashMap默认的负载因子是0.75,即如果hashmap中的元素个数超过了总容量75%,则会触发扩容,扩容分为两个步骤:

  • 第1步是对哈希表长度的扩展(2倍)
  • 第2步是将旧哈希表中的数据放到新的哈希表中。

因为我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。

如我们从16扩展为32时,具体的变化如下所示:

图片[1]-HashMap的扩容机制-编程社

rehash 因此元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:

图片[2]-HashMap的扩容机制-编程社

resize 因此,我们在扩充HashMap的时候,不需要重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。

可以看看下图为16扩充为32的resize示意图:

图片[3]-HashMap的扩容机制-编程社

resize16-32 这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。

© 版权声明
THE END
喜欢就支持一下吧
点赞8赞赏 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容