hashmap为什么采用两倍扩容
我们先来看看源码中官方是怎么解释的红线标注意思大概就是：以二次幂展开，容器的元素要么保持原来的索引，要么以二次幂的偏移量出现在新表中。也就是说hashmap采用2倍扩容，可以尽可能的减少元素位置的移动。看下图（不考虑链表的情况）可以看出，数组初始长度为2的幂次方，随后以2倍扩容的方式扩容，元素在新表中的位置要么不动，要么有规律的出现在新表中（二的幂次方偏移量），这样会使扩容的效率大大提高。另外，h
我们先来看看源码中官方是怎么解释的
红线标注意思大概就是：以二次幂展开，容器的元素要么保持原来的索引，要么以二次幂的偏移量出现在新表中。也就是说hashmap采用2倍扩容，可以尽可能的减少元素位置的移动。
看下图（不考虑链表的情况）
可以看出，数组初始长度为2的幂次方，随后以2倍扩容的方式扩容，元素在新表中的位置要么不动，要么有规律的出现在新表中（二的幂次方偏移量），这样会使扩容的效率大大提高。
另外，hashmap采用二倍扩容还有另外一个好处：可以使元素均匀的散布hashmap中，减少hash碰撞。
要分析这个问题，我们就要看一下hashmap是怎么确定元素下标的。其实就是这么一段
(n-1) 与 hash 进行位运算。
n若是2的幂次方，则n-1的二进制就是11111***111这样的形式，那么(n-1)与hash进行位运算不仅效率很高，而且能均匀的散列，这个说起来很空洞，我们画图位运算一下。
就拿上边的数组长度为4来说，4-1的二进制为011
这个图例参考 HashMap为什么两倍扩容 这篇文章，里边画的更清楚一点，有情趣的可以跳转查看。
hashmap为什么采用2倍扩容
总结：
1、尽可能的减少元素位置的移动。
2、使元素均匀的散布hashmap中，减少hash碰撞。
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
14
0- 0
已为社区贡献1条内容
所有评论(0)