HashMap源码分析hash函数（扰动函数）

JDK1.7的hash()方法(扰动函数)：

final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
           

JDK1.8的hash()方法：

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

其中key.hashCode()是操作系统自带的哈希函数，返回int类型的散列值。int的范围是**-2147483648到2147483648**，虽然这样很难出现哈希碰撞，但是hashMap的初始容量才16，所以直接使用散列值是不合理的。用之前还要先做对数组的长度取余运算，得到的余数才能用来访问数组下标。JDK1.7的源码中使用indexFor()函数来完成，JDK1.8对index的计算放在了putVal()函数里面。

indexFor代码如下：

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

这里使用到了散列值和数组length-1进行与运算，为什么可以这么做？

• 取余(%)操作中如果除数是2的幂次则等价于与其除数减⼀的与(&)操作 （也就是说 hash%length==hash&(length-1)的前提是数组的length 是2的 n 次⽅；）。并且采⽤⼆进制位操作 &，相对于%能够提⾼运算效率

​ 下面解释为什么数组的长度是2的n次方。

​ 看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！（参考：http://www.iteye.com/topic/539465）

但是这样又会有新的问题。这样就算我的散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。

这时候“扰动函数”的价值就体现出来了。如下图：

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