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

喜欢ヅ旅行 2021-09-18 07:46 376阅读 0赞

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中计算索引位的方式

![18721752-afa205b145628d42.png][]

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的取值范围  
\-231——231-1，即-2147483648——2147483647

2147483647换算成二进制即

0111 1111 1111 1111 1111 1111 1111 1111

### (3).位移运算符 ###

#### & ####