HashMap 高低位异或与

HashMap 高低位异或与

philo-尼可 288 2021-01-19

HashMap 的容量始终是 2 的次幂,是为了将取模运算转为位运算,提高性能。

2^1 = 10          2^1 -1 = 01 
2^2 = 100         2^2 -1 = 011 
2^3 = 1000        2^3 -1 = 0111
2^n = 1(n个零)     2^n -1 = 0(n个1) 

2n = 1(n个零) 2n 的二进制特点
2n -1 = 0(n个1) 2n-1 的二进制特点

可以发现当 length = 2^n 时,h & (length-1) 的结果正好位于 0 到 length-1 之间,就相当于取模运算。所以下面的等式是成立的。

h % length = h & (length-1)

转为位运算后,length-1 就相当于一个低位掩码,在按位与时,它会把原散列值的高位 (设)置为0,这就导致散列值只在掩码的小范围内变化,显然增大了冲突几率。为了减少冲突,HashMap 在设计散列算法时,使用高低位异或,变相的让键的高位也参与了运算
static final int hash(Object key) { // JDK8
int h;
// h = key.hashCode() 1. 取hashCode值
// h (h >>> 16) 2. 高16位与低16位异或,变相保留高位的比特位
return (key == null) ? 0 : (h = key.hashCode())
(h >>> 16);
}
高位的移位异或,既能保证有效的利用键的高低位信息,又能减少系统开销,这样设计是对速度、效率和质量之间的权衡。


# HashMap # 数据结构