hashMap默认的负载因子是0.75,即如果hashmap中的元素个数超过了总容量75%,则会触发扩容,扩容分为两个步骤:
- 第1步是对哈希表长度的扩展(2倍)
- 第2步是将旧哈希表中的数据放到新的哈希表中。
因为我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。
如我们从16扩展为32时,具体的变化如下所示:
![图片[1]-HashMap的扩容机制-编程社](https://cos.bianchengshe.com/wp-content/uploads/2024/04/image-9.png?imageMogr2/format/webp/interlace/1/quality/100)
rehash 因此元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:
![图片[2]-HashMap的扩容机制-编程社](https://cos.bianchengshe.com/wp-content/uploads/2024/04/image-10.png?imageMogr2/format/webp/interlace/1/quality/100)
resize 因此,我们在扩充HashMap的时候,不需要重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。
可以看看下图为16扩充为32的resize示意图:
![图片[3]-HashMap的扩容机制-编程社](https://cos.bianchengshe.com/wp-content/uploads/2024/04/image-11.png?imageMogr2/format/webp/interlace/1/quality/100)
resize16-32 这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END
暂无评论内容