为什么哈希/扰动函数能降hash碰撞？

为什么哈希/扰动函数能降hash碰撞？

因为key.hashCode()函数调用的是键值类型自带的哈希函数，返回一个int类型的散列值。int类型的取值范围是-2147483648到2147483647，大约40亿个可能的映射空间。

尽管哈希函数能够将键值映射得相对均匀松散，使得碰撞的概率很小，但问题是一个长度为40亿的数组是无法放入内存中的。

假设HashMap数组的初始大小为16，为了访问数组的下标，需要对散列值进行模运算，取得的余数才能用作数组下标。

在源码中，模运算是通过将散列值与数组长度减1进行"与&"操作来实现的。位运算比取余运算更快速，因此被用于计算数组下标。

bucketIndex = indexFor(hash, table.length);

static int indexFor(int h, int length) {
     return h & (length-1);
}

顺便说一下，这也正好解释了为什么 HashMap 的数组长度要取 2 的整数幂。因为这样（数组长度 - 1）正好相当于一个 “低位掩码”。与 操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度 16 为例，16-1=15。2 进制表示是 0000 0000 0000 0000 0000 0000 0000 1111。和某个散列值做 与 操作如下，结果就是截取了最低的四位值。

这样是要快捷一些，但是新的问题来了，就算散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。如果散列本身做得不好，分布上成等差数列的漏洞，如果正好让最后几个低位呈现规律性重复，那就更难搞了。

这时候 扰动函数 的价值就体现出来了，看一下扰动函数的示意图：

右移 16 位，正好是 32bit 的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。