详解 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 函数。