详解 HashMap 中的 Hash 算法（扰动函数）

发表于 | 阅读次数：

面试中经常会问 HashMap 的源码，因为 HashMap 不仅是日常开发中最常用到的类，还因为里面还包括了很多巧妙的算法。

HashMap 里对 Key 取 Hash 和通过 Hash 找到在数组中的位置需要调用下面两段代码：

1
2
3
4
5
6
7
8
9
10
// 以下来源 JDK8 源码：

// 找到元素在数组中的位置，n 为数组长度。
i = (n - 1) & hash

// 计算 Key 的 Hash 值 
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

为什么 HashMap 数组的长度要是 2 的整数幂？

我们希望理想的情况是：任意一个 Key 落在数组中的位置是足够散列的，这样可以减少 Hash 碰撞的概率。

假设计算出的 Hash 值是足够散列的，由于 Hash 值是一个 int 类型的值，大部分情况下 HashMap 数组是不会那么长的。所以在有限的数组长度内，当然是取 Hash 值的低几位算是比较理想的散列方式。

正因为此，而任何 2 的整数幂，减一得到的二进制位全部是一。如：16-1=15，二进制表示为：1111；32-1=31，二进制表示为：11111。所以让 Hash 值与（&）上 n-1 后得到的就是低位 Hash 值，如：

1
2
3
4
    00100100 10100101 11000100 00100101    // Hash 值 
&   00000000 00000000 00000000 00001111    // 16 - 1 = 15
----------------------------------
    00000000 00000000 00000000 00000101    // 高位全部归零，只保留末四位。

Hash 算法（扰动函数）

接着上面的理解，所以我们需要一个 Hash 函数得到足够散列的 Hash 值。

而任何一个 Object 类型的 hashCode 方法得到的 Hash 值是一个 int 型，Java 中 int 型是 4*8=32 位的。显然很少有 HashMap 的数组有 40 亿这么长。如果只是取低几位的 Hash 值的话，那么那些低位相同，高位不同的 Hash 值就碰撞了，如：

1
2
3
// Hash 碰撞示例：
H1: 00000000 00000000 00000000 00000101 & 1111 = 0101
H2: 00000000 11111111 00000000 00000101 & 1111 = 0101

为了解决这类问题，HashMap 想了一种办法（ 扰动 ）：将 Hash 值的高 16 位右移并与原 Hash 值取异或运算（^），混合高 16 位和低 16 位的值，得到一个更加散列的低 16 位的 Hash 值。如：

1
2
3
4
5
6
7
00000000 00000000 00000000 00000101 // H1
00000000 00000000 00000000 00000000 // H1 >>> 16
00000000 00000000 00000000 00000101 // hash = H1 ^ (H1 >>> 16) = 5

00000000 11111111 00000000 00000101 // H2
00000000 00000000 00000000 11111111 // H2 >>> 16
00000000 00000000 00000000 11111010 // hash = H2 ^ (H2 >>> 16) = 250

最终：

1
2
3
// 没有 Hash 碰撞 
index1 = (n - 1) & H1 = (16 - 1) & 5 = 5
index2 = (n - 1) & H2 = (16 - 1) & 250 = 10

再加上在程序中位运算是很快的，所以这算是一种非常巧妙并且高效的 Hash 函数。

相关文章