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

绝地灬酷狼 2024-04-01 18:23 78阅读 0赞

## 一. 背景介绍 ##

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

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

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

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

![edaee5a4fc2f41a7a81fe5e27d48ed1f.png][]

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

## 二. 问题解答 ##

### 2.1 对应源码分析 ###

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

![ed6619846a654a96905b863a8b5b9818.png][]

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

### 2.2 深入分析 ###

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

**当数组初始长度为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的性能。**现在你明白了吗？

[edaee5a4fc2f41a7a81fe5e27d48ed1f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/31c15412c8484002bd587ba2055ee0c2.png
[ed6619846a654a96905b863a8b5b9818.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d7a0ef35123c45e4a4bafd890fd7e76f.png