HashMap 的 hash 方法原理

HashMap 中的 hash 方法

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

上面这段代码叫扰动函数( Perturbation function )

理论上散列值是一个 int 型,如果直接用这个散列值作为下标访问 HashMap 主数组的话,考虑到2进制32位带符号的 int 范围从-2^31~2^31-1,大概有40亿的映射空间,可以肯定哈希比较松散,很难出现碰撞,但是这么大的空间内存不能存放,所以散列值不能直接拿来用。使用之前会进行取模运算,余数用来访问数组下标。

...
bucketIndex = indexFor(hash, table.length);
...

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

散列值和数组长度做 “与” 运算,这很好的解释了为什么数组长度要取2的幂指数,这样 len-1 相当于一个低位掩码。”与” 操作的结果:所有的高位都变味0,只保留低位,用来访问数组下标

len=16为例

       0010  1101  0111  1100  1000  0101
&      0000  0000  0000  0000  0000  1111
------------------------------------------
       0000  0000  0000  0000  0000  0101

这里有个问题,即使散列值再松散,只取后几位依然会碰撞严重。如果散列本身做的不好,在分布上导致后几位形成规律性重复就会有很大问题。这个时候扰动函数的价值就体现出来了。

    1111 1111 1111 1111 1111 0000 1110 1010     hashCode()
    0000 0000 0000 0000 1111 1111 1111 1111     h >>> 16
    1111 1111 1111 1111 0000 1111 0001 0101     h ^ h>>>16
    0000 0000 0000 0000 0000 0000 0000 1111     len-1
    0000 0000 0000 0000 0000 0000 0000 0101     hash & (len -1)

首先自己的高半区和低半区做异或,增大低位的随机性,同时低位混合了高位的特性。

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

5 × 3 =