【2021-07-01】为什么 HashMap 的初始化容量要设计成 2 的等幂？

每日一题 /

请移步至：每日一题查看更多的题目～

答：

我们知道，自 JDK 1.8 起，HashMap 的底层设计为 “数组 + 链表 + 红黑树”。

所谓的 HashMap 的容量指的就是底层哈希桶数组的长度。默认的情况下，HashMap 初始化容量为 16。

当我们向 HashMap 中添加一个元素时，我们首先需要知道该元素应该放入到哪个哈希桶中。最直观的想法就是，调用该对象的 hashCode 方法，该方法会返回一个整数，然后使用这个数对 HashMap 的容量取模即可知道该元素在哈希桶数组中对应的位置。实际上 JDK 的处理方式和这个思路差不多~

在 JDK 1.7 ，HashMap 会先使用 hash 函数（方法）获取一个 hash 值。hash 方法传入元素的 key 的 hashCode，返回一个 int 值，然后调用 indexFor 方法，indexFor 方法传入 hash 值和容器容量，计算出元素在哈希桶的数组中存放的位置。

JDK 1.7
hash 方法将 key.hashCode 转换成一大串数字
indexFor 方法将 hash 方法生成的一大串数字转换成哈希桶数组的下标

需要说明的是在 JDK 1.8 以后，就没有 indexFor 方法了，不过探究 JDK 1.7 的 indexFor 方法会更直观一些，因为 JDK 以后的版本中虽然没有 indexFor 这样一个单独的方法，但是只是将这个操作直接写进了其他方法中。本质上查询哈希桶数组的下标的算法实现是一样的。

我们来看下 JDK 1.7 的源码：

hash

static int hash(int h) {
    return h ^ (h >>> 7) ^ (h >>> 4);
}

indexFor

static int indexFor(int h, int length) {
    return h & (length-1);
}

indexFor 方法只做了一个操作：

h & (length-1)

这个操作的本质就是：取模运算！前提条件是 length 为 2 的幂

举个栗子：

已知，length = pow(2,n) ，n = 3,h = 6

h & (length - 1) 的结果为 0110 & 0111 = 0110 = 6，

而 h % length 的结果为 6 % 8 = 6，

二者相等。

关于这个位运算的技巧，我们并不需要了解它是如何成立的，毕竟这是一个数学问题，我们只需要记住这样一个结论即可。设计者使用位运算代替取模的原因在于，位运算的效率比取模运算高的多，考虑到 HashMap 的性能，所以就这么设计了。这个位运算成立的前提是 length 为 2 的幂。

至于 HashMap 默认的初始容量为何设置为 16，第一点是 16 这个数字满足 2 的幂这一要求；另外 16 作为初始化容量是一个效率与内存之间权衡考虑的结果，这个值既不能设计的太大，又不能设计的太小，而 16 这个值则刚刚好。

本文章首发在 LearnKu.com 网站上。