HashMap中的hash算法中的几个疑问

Java基础

浏览数:77

2019-9-18

AD:资源代下载服务

HashMap中哈希算法的关键代码

//重新计算哈希值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//key如果是null 新hashcode是0 否则 计算新的hashcode
}
//计算数组槽位
 (n - 1) & hash

HashMap的细节我们不谈,只看这个哈希算法的细节(h = key.hashCode()) ^ (h >>> 16)

^按位异或运算,只要位不同结果为1,不然结果为0;
>>> 无符号右移:右边补0

为什么要无符号右移16位后做异或运算

根据上面的说明我们做一个简单演练

将h无符号右移16为相当于将高区16位移动到了低区的16位,再与原hashcode做异或运算,可以将高低位二进制特征混合起来

从上文可知高区的16位与原hashcode相比没有发生变化,低区的16位发生了变化

我们可知通过上面(h = key.hashCode()) ^ (h >>> 16)进行运算可以把高区与低区的二进制特征混合到低区,那么为什么要这么做呢?

我们都知道重新计算出的新哈希值在后面将会参与hashmap中数组槽位的计算,计算公式:(n – 1) & hash,假如这时数组槽位有16个,则槽位计算如下:

仔细观察上文不难发现,高区的16位很有可能会被数组槽位数的二进制码锁屏蔽,如果我们不做刚才移位异或运算,那么在计算槽位时将丢失高区特征

也许你可能会说,即使丢失了高区特征不同hashcode也可以计算出不同的槽位来,但是细想当两个哈希码很接近时,那么这高区的一点点差异就可能导致一次哈希碰撞,所以这也是将性能做到极致的一种体现

使用异或运算的原因

 异或运算能更好的保留各部分的特征,如果采用&运算计算出来的值会向1靠拢,采用|运算计算出来的值会向0靠拢

为什么槽位数必须使用2^n

1、为了让哈希后的结果更加均匀

这个原因我们继续用上面的例子来说明

假如槽位数不是16,而是17,则槽位计算公式变成:(17 – 1) & hash

从上文可以看出,计算结果将会大大趋同,hashcode参加&运算后被更多位的0屏蔽,计算结果只剩下两种0和16,这对于hashmap来说是一种灾难

2、可以通过位运算e.hash & (newCap – 1)来计算,a % (2^n) 等价于 a & (2^n – 1)  ,位运算的运算效率高于算术运算,原因是算术运算还是会被转化为位运算

说了这么多点,上面提到的所有问题,最终目的还是为了让哈希后的结果更均匀的分部,减少哈希碰撞,提升hashmap的运行效率

 

作者:沉默的背影