转载

HashMap源码解析系列(一)之HashMap#hash(Object key)方法

1.什么是哈希碰撞 2.为什么会有哈希碰撞 3.HashMap如何解决哈希碰撞 4.HashMap的hashCode为什么要右移16位先来说说理论的东西也就是1和2的问题， 两个不同的值在取哈希值的时候相同称之为哈希碰撞 这句话就概括了1和2的问题那HashMap如何解决哈希碰撞我们先来看一个例子0011 1000 和 0001 1000 在对 0000 1111（等于15 假设现在HashMap的容量为16）进行按位与运算后的结果 注：（^）异或运算就是两个都为1的时候为1否则为0

//0011 1000对0000 1111做异或运算
0011 1000
0000 1111 ^
0000 1000 //运算结果
复制代码

//0011 1000对0000 1111做异或运算
0001 1000
0000 1111 ^
0000 1000 //运算结果
复制代码

两个不相同的值对数组长度-1进行按位与运算后得到的结果相同这就发生了哈希碰撞，而HashMap对hashCode进行了右移16为如：

0111 1111 1111 1111 1111 1111 1111 1111
0000 0000 0000 0000 0011 1111 1111 1111 >>> 16
复制代码

就是将原数据的高16位都变成0而低16位替换成原先数据的高16位，那为什么要这么做呢，其实就是要进行扰动计算，防止不同hashCode的高位不同但低位相同导致的hash冲突。简单点说，就是为了把高位的特征和低位的特征组合起来，降低哈希冲突的概率，也就是说，尽量做到任何一位的变化都能对最终得到的结果产生影响。说这个之前我么就得先了解HashMap中根据key获取数组索引的另外一个算法**根据hash算出的code对数组长度进行与运算（取摸）**这代码在1.8之后在putVal方法中的第630行

if ((p = tab[i = (n - 1) & hash]) == null)
复制代码

其中 i = (n - 1) & hash 就是根据key的值来确定Node在table中的索引。如果我们直接使用key的hashCode对数组长度-1进行取摸的话比如：以初始长度16为例，16-1=15 。二进制表示是00000000 00000000 00001111

1010 0101 1100 0100 0010 0101
0000 0000 0000 0000 0000 1111   &
-----------------------------------
0000 0000 0000 0000 0000 0101    //高位全部归零，只保留末四位
复制代码

但这时候问题就来了，这样就算我的散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。更要命的是如果散列本身做得不好，分布上成等差数列的漏洞，恰好使最后几个低位呈现规律性重复，就会出现严重的哈希碰撞，其带来的结果就是在table容器中某个索引的链表特别长，而有些索引根本就没有几个甚至都没有数据的情况，这时候哈希值向右移16为的价值就体现出来了先来了解位异或运算（^）运算规则是：两个数转为二进制，然后从高位开始比较，如果相同则为0，不相同则为1。位与运算符（&）运算规则：两个数都转为二进制，然后从高位开始比较，如果两个数都为1则为1，否则为0。

1111 1111 1111 1111 1111 0000 1110 1010
0000 0000 0000 0000 1111 1111 1111 1111  >>> 16 //右移16位
-------------------------------------------------------------
1111 1111 1111 1111 0000 1111 0001 0101  ^ //位异或运算的结果
0000 0000 0000 0000 0000 0000 0000 1111 &  // //对15进行取摸（位与运算运算）
-------------------------------------------------------------
0000 0000 0000 0000 0000 0000 0000 0101 //其10进制5
复制代码

右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。那么，为什么可以使用位运算(&)来实现取模运算(%)呢？

这实现的原理如下：
X % 2^n = X & (2^n – 1)
2^n表示2的n次方，也就是说，一个数对2^n取模 == 一个数和(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，也就是余数。
复制代码

而这也就解释了上一篇中HashMap#tableSizeFor()中的初始值长度threshold为什么要算出是2的次方数，初始值是16，之后每次扩充为原来的2倍。因为只要保证length的长度是 2^n 的话，就可以实现取模运算了，当然这只是一个用法，其实初始值长度threshold=2的次方数在之后的HashMap#resize()方法（初始化容器、扩容）也有一些奇妙的运用，我们下一篇章再分析吧

原文 https://juejin.im/post/5efea690e51d4534714aa670

正文到此结束