HashMap 每次扩容时，为什么都必须是 2 的 N 次方?

最近有粉丝问壹哥，为什么 HashMap 每次扩容时，都必须是 2 的 N 次方？

其实要想弄明白这个问题，我们就必须知道 HashMap 的底层源码结构。接下来壹哥就带各位来分析一下 HashMap 的底层设计。

我们知道，HashMap 的底层是通过数组+链表+红黑树的数据结构来存放数据的。当新添加元素的 key 值出现了 hash 碰撞，就会在同一 个 bucket 中形成链表或者红黑树。 当键值对的数量超过阈值时就会扩容，将以前处于同一个链表或者红黑树上的元素打散，在新数组的 bucket 上进行重新分布。

当 HashMap 在初始化没有指定容量的情况下，首次添加元素时，数组的容量为 16；当超出阈值，数组容量为扩容为之前的 2 倍。

那么问题来了，为什么 HashMap 会将首次初始化容量设置为 16，而后续每次扩容都是之前的 2 倍？而不是像 ArrayList 首次为 10，后续为 1.5 倍呢？这可是我们在面试时的一个高频考点哦！壹哥提醒各位，一定要搞清楚这一点哦。

对应源码分析

其实要想回答出上面提出的问题，我们可以从 HashMap 的源码里找到答案，如下图所示：

其中 n 为数组的长度，n - 1 为数组的最大索引值 。 （n - 1）& hash 的意思是将每个元素 key 的 hash 值 ， 与最大索引值进行相与 操作。 然后判断对应的 bucket 位置是否有元素，如果没有元素则在对应的 bucket 位置直接添加；如果有元素，则形成链表或者红黑树。

深入分析

各位看官，你现在可能对上面的内容还是有点云里雾里，别急，让我们再来看一组数据：

当数组初始长度为 16 的时候，每次扩容都为之前的 2 倍，那么就保证了每次扩容之后新数组的最大索引值对应的二进制数为全 1 。 根据 2.1 小节中，图片标识的 (n - 1) & hash，那么就能保证添加到 HashMap 中 key 的 hash 值与最大索引相与时，能够最大化的分散到 HashMap 所有的 bucket 中，进而最大化避免出现 hash 碰撞而形成链表或者红黑树。

壹哥再反向地跟各位看官论证一下。假如说 HashMap 的初始化长度是 10，那么最大索引值为 9，而 9 对应的二进制数是 1001。那么 key 的 hash 值与 9 相与，结果只可能为 0、1、8、9，那么新增的数据永远只能放到数组索引为 0、1、8、9 这四个位置，这就大大增加了出现链表和红黑树转换的概率。

所以初始化为 16，每次扩容是之前的 2 倍，这就大大降低了链表和红黑树转换的概率，自然也就提高了 HashMap 的性能。 现在你明白了吗？

作者：一一哥 Sun

链接：https://juejin.cn/post/7177982041089605693

来源：稀土掘金