
面试中经常会问 HashMap 的源码,因为 HashMap 不仅是日常开发中最常用到的类,还因为里面还包括了很多巧妙的算法。
HashMap 里对 Key 取 Hash 和通过 Hash 找到在数组中的位置需要调用下面两段代码:
1 | // 以下来源 JDK8 源码: |
为什么 HashMap 数组的长度要是 2 的整数幂?
我们希望理想的情况是:任意一个 Key 落在数组中的位置是足够散列的,这样可以减少 Hash 碰撞的概率。
假设计算出的 Hash 值是足够散列的,由于 Hash 值是一个 int 类型的值,大部分情况下 HashMap 数组是不会那么长的。所以在有限的数组长度内,当然是取 Hash 值的低几位算是比较理想的散列方式。
正因为此,而任何 2 的整数幂,减一得到的二进制位全部是一。如:16-1=15,二进制表示为:1111
;32-1=31,二进制表示为:11111
。所以让 Hash 值与(&)上 n-1 后得到的就是低位 Hash 值,如:
1 | 00100100 10100101 11000100 00100101 // Hash 值 |
Hash 算法(扰动函数)
接着上面的理解,所以我们需要一个 Hash 函数得到足够散列的 Hash 值。
而任何一个 Object 类型的 hashCode 方法得到的 Hash 值是一个 int 型,Java 中 int 型是 4*8=32 位的。显然很少有 HashMap 的数组有 40 亿这么长。如果只是取低几位的 Hash 值的话,那么那些低位相同,高位不同的 Hash 值就碰撞了,如:
1 | // Hash 碰撞示例: |
为了解决这类问题,HashMap 想了一种办法( 扰动 ):将 Hash 值的高 16 位右移并与原 Hash 值取异或运算(^),混合高 16 位和低 16 位的值,得到一个更加散列的低 16 位的 Hash 值。如:
1 | 00000000 00000000 00000000 00000101 // H1 |
最终:
1 | // 没有 Hash 碰撞 |
再加上在程序中位运算是很快的,所以这算是一种非常巧妙并且高效的 Hash 函数。