【面试必杀题】HashMap 扩容时，可以不是2的N次方吗

开启掘金成长之旅！这是我参与「掘金日新计划 · 2 月更文挑战」的第 2 天，点击查看活动详情

大家好，我是车辙。根据我的面试经历，很多面试官经常会将HashMap作为面试基础题，这主要还是因为它里面涉及到的知识点太多了。有次在组内的分享中，我们就交流了相关问题，比如：HashMap扩容时，可以不是2的N次方吗？

很多小伙伴乍一看，脑子里立马涌现出了答案，可不就是2的N次方嘛，还有其他选项？如果你回答不出来，往下看。

唠叨的老余

刚代码敲的起劲，老余的唠叨就把我打断了：“现在来面试的程序员水平也太差了，连这么简单的问题都不了解，还不如新来的几个应届生呢”。

我抬起头：“不至于，工作几年后更多的关注点可能在项目上，有些题目不了解也正常，你以为人人都像你那么牛逼呢，话说你问了什么刁钻的问题呀”。

老余：“和HashMap扩容有关的，HashMap扩容时，可以不是2的N次方吗，基本上能完完全全回答出来的很少，要不你来试下”

我：“又来了，怎么受伤的总是我。不过答案我还是知道的。”

先来结论：HashMap 的扩容倍数可以不是2的N次方。

注意！本次代码涉及 Java 版本为 JDK8，并且假设你对源码有一定了解。

什么是 HashMap 扩容

我们知道，HashMap的底层是通过数组+链表+红黑树来实现的。在没有手动设置的情况下，HashMap默认数组长度为16，而它进行扩容的阈值是 16 * 0.75 = 12。为了减少Hash冲突，让数据分布的更加均匀，当HashMap上存放的值超过了阈值后，就需要对HashMap进行扩容。

有哪些 Hash 算法

老余：好小子，八股文比你背的6的人真不多了。刚才你说了扩容是为了减少 Hash 冲突，让数据分布的更加均匀。那你能说下，有哪些 Hash 算法吗？

我：Hash算法又称散列算法，它的作用可以简单理解为将较大的数据转化为小的数字，并且相同的入参每次执行得到的出参也应该是相同的。所以在我看来并没有什么固定的Hash算法，只要能达到要求即可。

比如最基础的取模算法，被人称作是现代密码学的根基。可以将无限大的数转化为一定范围的数。例如：

(10000 % 8) => 最后得到值一定小于8

但是这种算法相对来说很好被破解，破解者只要将批量数据执行一遍就能得出结论：所有结果都是小于8，很容易就猜出来这个算法。

后来，有人在此基础上做了点增强，比如说与、或、非、异或等操作，让产生的数据不再具有很强的规律性。例如：

((10000 % 8) | 8) 

有些人还是觉得不再安全，又加了一步移位运算。例如：

((10000 % 8) | 8) << 2

这其实就是很多Hash算法的来源了，比如MD4,MD5,SHA-256这些，本质算法就是如此，只不过会加入更多的循环和计算，来加强散列函数的可靠性。

我也不是特别的了解算法的具体细节，关于这部分看看就好

HashMap 的 Hash 算法是怎么做的

我们来看看HashMap 在Hash算法这方面是如何做的？ 首先获取Key的HashCode值，接着做位运算和异或处理，获取对应的 Hash 值。

随后将该Hash值与n-1做与运算。通过(n - 1) & hash，就能得出最终的数组下标值。然后判断该数组下标中的bucket是否有值，如果没有直接添加。如果有，说明存在Hash冲突，形成链表。

注意这边的 n-1，n 指的是数组的长度，因为数组下标是从0开始的，所以 n-1 为数组的最大下标值

为什么是 & 而不是 |

老余：你说的这些太基础了，还没有答到点子上。比如我问你，它为什么要用位运算? 我：当然是因为速度快呗。 老余：那它为什么要用位运算中的与&，为什么不用或| 我：因为通过与运算，能保证位运算后的最大值不会大于两者中的最小值。例如13的二进制数为1101，另一个数是1111=15，两者进行与运算后，最终的值是1101，依然是13。如下图所示：

而如果使用或，可能会出现超过数组长度的现象。假设数组长度为14，Hash值为 11，那么 n-1=13,这时候11=1011 和 13=1101进行或运算，最终的结果是15，超过了两个数中的最大值，不就下标越界了。

这也就是HashMap为什么使用与的原因了。

使用 n - 1 也正是由于这个因素，能够防止下标越界。

扩容可以不是2的N次方吗

我：当然可以，只要能保证数组长度的增加，甚至是3的N次方也行，只不过会存在效率问题。

之前我们提过，为了保证速度，HashMap 必须得使用位运算。在此基础上，为了防止下标越界，使用数组长度的 n-1 作为其中一个值。但你想想，为什么不用 n-2，n-3呢?

老余：你问我干嘛，是我在问你诶?

我：因为Hash算法的主要目的是保证数据散列均匀。假如说 HashMap的数组长度是8，那么n-3 = 5，而5对应的二进制数是 101。那么key的hash值和5进行与运算，结果只可能为 000,100，001,101，所以新增的数据只能放到数组的0、1、4、5 位置上，剩下的位置只能剩余。不仅如此，这还会大大的增加Hash冲突的概率，最后导致HashMap的时间复杂度上去了，空间复杂度也不低。

而如果是 n-1=7，它对应的二进制数是 111。那么key的hash值和7进行与运算，会有8种可能，刚刚好填充完整个数组，让HashMap 的时间复杂度最大程度的接近于O(1)，空间也完美利用。

所以从中我们可以得出结论，只要让那个与运算的值=2^y-1，就是最佳方案。而在这种条件下，扩容是2的N次方与n-1结合在一起，则是最优解。

还没看明白的小伙伴可以直接看总结

如果哪一天，写 JDK 的开发人员把n-1写成了n-2，应该会造成一大堆面试惨案吧。

碎碎叨

老余：好小子，回答的真不赖，我压根没你想的那么深。

我：JDK 内部的源码确实是博大精深，我也参考过其他文章，很多都这样写：因为是 n-1 的值去进行位运算，所以为了让散列均匀，扩容必须是2的N次方。但是忽略了一个问题：他们全是在 n-1 成为既定事实的情况下去理解的这个问题，没有往更深层次去想为什么是n-1。

老余：emmm，我还是赶紧去看下源码理解下吧，免得被求职者吊打。

总结

1. 为了保证HashMap的使用效率， HashMap使用了位运算作为 Hash 算法。
2. 而为了保证不发生下标越界的情况，HashMap使用了&的同时，进行位运算的值必须小于 n，也就是n-x。
3. 与此同时，为了保证分布均匀，那个值最好是 2^y-1。

在上述三个条件的条件约束下，由此得出关系式：n-x=2^y-1。所以此时，最优解 x 的值为1，y 是任意正整数。

回到我们的问题，HashMap 扩容时，可以不是2的N次方。但是为了提高效率，使用 n-1 进行位运算 以及 扩容数量是2的N次方才是最优解。 如果不是n-1，HashMap扩容后的数量就应该根据数组长度进行动态计算，并且一定会存在空间资源的浪费。

如果这篇文章对您有所帮助，可以关注我的公众号《车辙的编程学习圈》，也可以在我的博客网站扫码关注 我的博客网站。

我是车辙，掘金小册《SkyWalking》作者，一名常被HR调侃为XX杨洋的互联网打工人