为什么HashMap的hash值要右移16位?

前言

一时兴起，去看了看 HashMap 的源码，越过大段的注释后，第一个方法就给我难住了。为什么这么计算出的 hash 值可以更加分散呢？

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

概念介绍

<<: 左移运算符，num << 1,相当于 num 乘以 2 低位补 0
举例：3 << 2
将数字 3 左移 2 位，将 3 转换为二进制数字:0000 0000 0000 0000 0000 0000 0000 0011，然后把该数字高位(左侧)的两个零移出，其他的数字都朝左平移 2 位，最后在低位(右侧)的两个空位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 1100，则转换为十进制是 12。
>>: 右移运算符
举例：11 >> 2
则是将数字 11 右移 2 位，11 的二进制形式为:0000 0000 0000 0000 0000 0000 0000 1011，然后把低位的最后两个数字移出，因为该数字是正数，所以在高位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 0010。转换为十进制是 3。
>>>: 无符号右移，忽略符号位，空位都以 0 补齐
按二进制形式把所有的数字向右移动对应位数，低位移出(舍弃)，高位的空位补零。对于正数来说和带符号右移相同，对于负数来说不同。其他结构和>>相似。
% : 模运算取余
简单的求余运算
^ : 位异或第一个操作数的的第 n 位于第二个操作数的第 n 位相反，那么结果的第 n 为也为 1，否则为 0
1
0^0=0， 1^0=1， 0^1=1， 1^1=0
& : 与运算第一个操作数的的第 n 位于第二个操作数的第 n 位如果都是 1，那么结果的第 n 为也为 1，否则为 0
1
0&0=0， 0&1=0， 1&0=0， 1&1=1
| : 或运算第一个操作数的的第 n 位于第二个操作数的第 n 位只要有一个是 1，那么结果的第 n 为也为 1，否则为 0
1
0|0=0， 0|1=1， 1|0=1， 1|1=1
~ : 非运算操作数的第 n 位为 1，那么结果的第 n 位为 0，反之，也就是取反运算（一元操作符：只操作一个数）
1
~1=0， ~0=1

HashMap 中元素的位置

HashMap 中put()方法源码如下，可以看到是调用putVal()方法。

1
2
3

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

而在putVal()方法中，HashMap 中定位到桶的位置是根据 Key 的 hash 值与数组的长度取模来计算的。即i = (n - 1) & hash;

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    ...
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    ...

在绝大多数情况下，length 一般都小于 2^16 即小于 65536。所以i始终是 hash的低16位 与(length-1)进行&运算的结果。

例：假设 length 为 8。HashMap 的默认初始容量为 16

length = 8; （length-1） = 7；转换二进制为 111；

假设一个 key 的 hashCode = 78897121 转换二进制为：100101100111101111111100001，

（length-1）& 78897121运算如下:

0000 0100 1011 0011 1101 1111 1110 0001
&运算
0000 0000 0000 0000 0000 0000 0000 0111
=
0000 0000 0000 0000 0000 0000 0000 0001 （就是十进制1，所以下标为1）

推导得出：

当 length=8 时，下标运算结果取决于哈希值的低三位
当 length=16 时，下标运算结果取决于哈希值的低四位
当 length=32 时，下标运算结果取决于哈希值的低五位
当 length=2 的 N 次方，下标运算结果取决于哈希值的低 N 位

其实，这个算法就是取模。Java 之所以使用位运算(&)来代替取模运算(%)，最主要的考虑就是效率。

位运算(&)效率要比代替取模运算(%)高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。

位运算符代替取模运算的原理如下：

1	X % 2^n = X & (2^n – 1)

假设 n 为 3，则 2^3 = 8，表示成 2 进制就是 1000。2^3 -1 = 7 ，即 0111。

此时 X & (2^3 – 1) 就相当于取 X 的 2 进制的最后三位数。

从 2 进制角度来看，X / 8 相当于 X >> 3，即把 X 右移 3 位，此时得到了 X / 8 的商，而被移掉的部分(后三位)，则是 X % 8，也就是余数。

例：

1
2
3

6 % 8 = 6 ，6 & 7 = 6

10 % 8 = 2 ，10 & 7 = 2

所以, (n-1) & hash只要保证 n 的长度是 2^n 的话，就可以实现取模运算了。

所以，因为位运算直接对内存数据进行操作，不需要转成十进制，所以位运算要比取模运算的效率更高，所以 HashMap 在计算元素要存放在数组中的 index 的时候，使用位运算代替了取模运算。之所以可以做等价代替，前提是要求 HashMap 的容量一定要是 2^n 。

根据为什么 HashMap 的默认容量设置成 16的说法，16 是一个经验值，是效率和内存之间的权衡结果。

总结

综上所诉：在大部分情况下：因为length < 2^16，所以只有 hashCode 的低十六位（或者更低）参与运算。

假设有一种情况，对象 A 的 hashCode 为 1000010001110001000001111000000，对象 B 的 hashCode 为 0111011100111000101000010100000。

如果数组长度是 16，也就是 15 与运算这两个数（前面说的 hashCode & （length - 1）），你会发现结果都是 0。这样的散列算法明显不能达到要求。

所以在hash(Object key)方法中对 key 的 hashCode 进行扰动计算，防止不同 hashCode 的高位不同但低位相似导致的 hash 冲突。即将 key 的 hashCode 与所得 hashCode 的高十六位进行^运算，让 hashCode 高十六位也加入到了运算中，把高位的特征和低位的特征组合起来，降低哈希冲突的概率，也就是说，尽量做到任何一位的变化都能对最终得到的结果产生影响。

为什么用^而不用&和|:
因为&和|都会使得结果偏向 0 或者 1，并不是均匀的概念，所以用^。

为什么HashMap的hash值要右移16位?

概念介绍

HashMap 中元素的位置

总结

参考