乐趣区

关于面试:HashMap中的取模和扩容算法推导

jiezi

为什么 HashMap 容量 capacity 大小是 2 的 n 次幂？
为什么应用 e.hash & (capacity – 1) 位运算作取模公式？
为什么扩容时应用 e.hash & oldCap 来计算扩容后的数组索引？
本文通过推导 HashMap 中的取模和扩容算法以答复上述问题。

  • 1. 按位与 (&) 运算的了解

  • 2. 取模运算

    • 2.1 当 e.hash 为负数

    • 2.2 当 e.hash 为正数

      • 正数取模怎么算

        • 整数除法取整
        • 取模怎么算

  • 3. 扩容运算

    • 3.1 推导 e.hash & oldCap = 0 时，y = x
    • 3.1 推导 e.hash & oldCap = 1 时，y = x + oldCap
  • 4. 总结

1. 按位与 (&) 运算的了解

位运算的运算规定如下：

两个二进制的数按位与，如 A & B，当 B 中某一位为 1，则保留 A 上对应位上的数。
假如 B = 1000(二进制)，第四位为 1。
当 A = 1001(二进制)，A & B 获得第四位为 1，失去 A & B = 1000(二进制)；
当 A = 0110(二进制)，A & B 获得第四位为 0，失去 A & B = 0000(二进制)；

了解了按位与的这一层含意之后，再来看 HashMap 中的取模和扩容算法。

2. 取模运算

HashMap 的取模公式为 e.hash & (capacity – 1)。

这里 capacity 是 HashMap 数组构造的大小，约定为 2 的 n 次幂，即 capacity = 2 ^ n。
对于节点 e，它的哈希值用 e.hash 示意。

失常来说，取模公式为 e.hash % capacity，为什么 HashMap 中能够用位运算来代替呢？

2.1 当 e.hash 为负数

从二进制角度来看，e.hash / capacity = e.hash / 2^n = e.hash >>> n，即把 e.hash 右移 n 位，此时失去了 e.hash / 2^n 的商。
而被移掉的局部 (低 n 位)，则是 e.hash % 2^n，也就是 余数。

如何获得 e.hash 的低 n 位呢？

已知 2^n 的二进制模式为 1 前面跟着 n 个 0，则 2^n – 1 的二进制模式为 n 个 1。
如 8 = 2 ^ 3，其二进制模式为 1000，7 = 2 ^ 3 – 1，其二进制模式为 111。

依据对按位与 (&) 操作的了解，e.hash & (2^n – 1) 就是获得 e.hash 的低 n 位，同样是 余数。

因而咱们能够推导出 e.hash & (capacity – 1) = e.hash % capacity。

验证：

// e.hash = 7，n = 2，capacity = 2^n = 4
System.out.println(7 % 4);// 3
System.out.println(7 & 3);// 3

2.2 当 e.hash 为正数

当 e.hash 为正数时，如 -7，若 n = 2，此时 e.hash & (capacity – 1) 失去的后果与 e.hash % capacity 不同，是不是翻车了呢？

// e.hash = -7，n = 2，capacity = 2^n = 4
System.out.println(-7 % 4);// -3
System.out.println(-7 & 3);// 1

其实不然，咱们来看下百度对于 -7 mod 4 的计算结果：

其实 -7 mod 4 失去 -3 或 1 都是正确的后果。取决于计算机采纳的运算规定。

来看下正数取模的问题。以下内容来自《正数取模怎么算》

正数取模怎么算

整数除法取整

思考这样一个计算题：18 除以 5，要失去一个整数后果，到底应该是 3 还是 4？这就是一个问题了。计算机上有几种对于后果取整的办法：

  • 向上取整，向 +∞方向取最靠近准确值的整数，也就是取比理论后果稍大的最小整数，> 也叫 Ceiling 取整。这种取整形式下，17 / 10 == 2，5 / 2 == 3, -9 / 4 == -2。
  • 向下取整，向 -∞方向取最靠近准确值的整数，也就是取比理论后果稍小的最大整数，也叫 Floor 取整。这种取整形式下，17 / 10 == 1，5 / 2 == 2, -9 / 4 == -3。
  • 向零取整，向 0 方向取最靠近准确值的整数，换言之就是舍去小数局部，因而又称截断取整（Truncate）。这种取整形式下，17 / 10 == 1，5 / 2 == 2, -9 / 4 == -2。

取模怎么算

取模运算实际上是计算两数相除当前的余数。假如 q 是 a、b 相除产生的商 (quotient)，r 是相应的余数(remainder)，那么在简直所有的计算零碎中，都满足：
a = b x q + r，其中 |r|<|a|。
因而 r 有两个抉择，一个为正，一个为负；相应的，q 也有两个抉择。如果 a、b 都是负数的话，那么个别的编程语言中，r 为负数；如果 a、b 都是正数的话，个别 r 为正数。然而如果 a、b 一正一负的话，不同的语言则会依据除法的不同后果而使得 r 的后果也不同，然而个别 r 的计算方法都会满足：
r = a – (a / b) x b

回到咱们的例子，可知：

/**
 * Truncate 法：* r = (-7)-(-7/4)x4 = (-7)-(-1)x4 = -3
 * Ceiling 法：* r = (-7)-(-7/4)x4 = (-7)-(-1)x4 = -3
 * Floor 法：* r = (-7)-(-7/4)x4 = (-7)-(-2)x4 = 1
 */
System.out.println(-7 % 4);// -3
System.out.println(-7 & 3);// 1

Java 语言中的取模运算采纳了 truncate 法失去的 -3，与 Floor 法失去的 1 同样都是 -7 mod 4 的后果。
从狭义上来说，当 e.hash 为正数，e.hash & (capacity – 1) = e.hash % capacity 仍旧是成立的。

3. 扩容运算

定义 HashMap 中扩容之前的旧数组容量为 oldCap，其中 oldCap = 2^n，扩容之后的新数组容量为 2oldCap。

在扩容的时候，对于节点 e，计算 e.hash & oldCap。
当 e.hash & oldCap = 0，则节点在新数组中的索引值与旧索引值雷同。
当 e.hash & oldCap = 1，则节点在新数组中的索引值为旧索引值 + 旧数组容量。

设：扩容前，节点 e 在旧数组索引值为 x；扩容后，节点 e 在新数组的索引值为 y.

3.1 推导 e.hash & oldCap = 0 时，y = x

在旧数组中，取模公式为 e.hash & (oldCap – 1) = x，因为 oldCap = 2^n，可知 oldCap – 1 的二进制模式为 n 个 1。
依据对按位与 (&) 操作的了解，e.hash & (oldCap – 1) 相当于取 e.hash 的低 n 位的值，该值为 x。

在新数组中，取模公式为 e.hash & (2oldCap – 1) = y，因为 oldCap = 2^n，可知 2oldCap – 1 的二进制模式为 n + 1 个 1。
依据对按位与 (&) 操作的了解，e.hash & (2oldCap – 1) 相当于取 e.hash 的低 n + 1 位的值，该值为 y。

同理当 e.hash & oldCap = e.hash & 2^n = 0 时，阐明 e.hash 的第 n + 1 位为 0，
此时低 n + 1 位的值与低 n 位的值是相等的，即 y = x，命题得证。

3.1 推导 e.hash & oldCap = 1 时，y = x + oldCap

当 e.hash & oldCap = e.hash & 2^n = 1 时，阐明 e.hash 的第 n + 1 位为 1。
对于一个二进制数，其第 n + 1 位为 1，其余 n 位为 0，该二进制数的值为 2^n，也就是 oldCap。
当 e.hash 的第 n + 1 位为 1，且低 n + 1 位的值为 y，低 n 位的值为 x，此时 y = x + oldCap，命题得证。

4. 总结

推导可知，当 HashMap 容量 capacity 大小是 2 的 n 次幂时，取模公式和扩容公式都能够用按位与运算来替换取模运算，极大地晋升了运算效率。

然而，按位与运算理论是取 hash 值的低位，舍弃了高位会使得 hash 运算后果不平均，HashMap 是通过引入扰动运算来防止这个问题的。

退出移动版