JDK1.8中关于hash值的计算方式

JDK1.8中关于hash值的计算方式

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

key的hash值和自己的高16位进行异或运算，得到一个更加散列（随机）的值。因为这个值要和数组的长度进行&运算，所以一定要得到一个更加随机的值
JDK1.8中计算索引位的方式

image.png

即

tab[i = (n - 1) & hash]

所以完整的计算hash存储索引位的代码应是

i = (n - 1)&(h = key.hashCode()) ^ (h >>> 16)  

更简化一些是

散列表数组长度 & (h = key.hashCode()) ^ (h >>> 16)

1.为什么是h >>> 16

先来看看如果直接拿hash值进行运算是什么结果

那么上面的计算公式变成

散列表数组长度 & (h = key.hashCode())

因为数组长度一般都是65536的（即 2^16），所以&运算，所以如果直接将hashCode和数组长度&运算，那么一直都是hash值的低16位和数组进行运算
比如一个key的hash值是78897121，数组长度为7那么他们之间的&运算如下：

    0000 0100 1011 0011 1101 1111 1110 0001
 &  0000 0000 0000 0000 0000 0000 0000 0111    
    0000 0000 0000 0000 0000 0000 0000 0001    

这样来看如果数组长度小于65536，即 0001 0000 0000 0000 0000，那么一直都是hash值的低16位和数组长度进行&运算
而上面的例子的计算结果，其实就是其第三位和数组长度进行&运算。
当length=8时 下标运算结果取决于哈希值的低三位
当length=16时 下标运算结果取决于哈希值的低四位
当length=32时 下标运算结果取决于哈希值的低五位
当length=2的N次方， 下标运算结果取决于哈希值的低N位。

得出结论这个计算结果取决于哈希值的低log₂ⁿ的影响（这里的n是数组长度）

通过上面可以看出：
hash值由于和（length-1）运算，length 绝大多数情况小于2的16次方。所以始终是hashcode 的低16位（甚至更低）参与运算。这样的结果会让得出的索引位过于集中，都集中于某几个索引位上，不够随机。
所以为了计算得出的索引位更加的随机，尽量防止散列碰撞，需要在计算hash值这上面动手脚，让这个hash值的低16位更加随机，那么得出的索引位也就更加的散列。
而JDK在计算hash值的时候，都不是简单的直接拿自己的高16位和数组长度进行计算，而是先让hash右移16位后，在将该值和hash值进行^运算，得出一个更加随机的hash值。

  0000 0100 1011 0011 1101 1111 1110 0001   (78897121)
^ 0000 0000 0000 0000 0000 0100 1011 0011  （右移16位后的数据）

  0000 0100 1011 0011 1101 1011 0101 0010  (78895954)

所以JDK1.8中为了得到一个更加散列的索引，先通过key的hash值和该hash值的高16位进行^计算后再和数组长度&运算。

2.为什么用^而不用&和|

这里不能是& 或者|运算，因为这两种结果都使得结果趋向于0或者1，不够随机，所以用^。从这里可以看出JDK1.8真是为了得出一个随机的值，在所有该有花的地方都进行了优化。

3.相关知识补充

(1) >>>

' >>>' 表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0,如果是正数则和>>的结果相同。
右移多少位，O>>>N 等价于 O/2ⁿ

(2) 为什么上面正数都是32位

因为在java中int的取值范围
-2^31——231-1，即-2147483648——2147483647

2147483647换算成二进制即

0111 1111 1111 1111 1111 1111 1111 1111

(3).位移运算符

&

& 是所有的2进制位数“与”出的最终结果，“与”的规则是两者都为1时才得1，否则就得0
例子：
7 & 6=？
7的2进制是：1 1 1
6的2进制是：1 1 0
结果： 1 1 0
得到结果为110，2进制转换为10进制110=6
所以：7 & 6 = 6

|

是所有的2进制位数“或”出的最终结果，“或”的规则是两者之一有一个1就得1，否则就得0
例子：
7 | 6 =？
7的2进制是：1 1 1
6的2进制是：1 1 0
结果： 1 1 1
得到结果为111，2进制转换为10进制111=7
所以：7 | 6 = 7

^(亦或运算)

针对二进制，相同的为0，不同的为1
例子
2 =======>0010
3 =======>0011
2^3就为0001，结果就是1