首页 > 代码库 > hashCode相关性能优化

hashCode相关性能优化

学习下hashMap中用到的关于hashCode性能优化技巧,作为笔记,为之后并发深入作基础。

1.关于提高性能的hash算法

在被模的位数为2的n次方时,用位与代替效率低下的模运算。位与效率相比模运算效率更高。
例:15%4=3,代替为 15 & 3=1111 & 0011=0011=3

hashmap中在求得某个key后,需要找到在哪个Entry数组下标的运算如下:

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

例:
两个key,调用Object的hash方法后值分别为:
32,64,然后entry数组大小为:16,即在调用indexFor时参数分别为[32,15],[64,14],
这时分别对它们调用indexFor方法:
32计算过程:
  100000 & 1111 =>  000000 =>0
64计算过程如下:
 1000000 & 1111 =>  000000 =>0

可以看到indexFor在Entry数组大小不是很大时只会对低位进行与运算操作,高位值不参与运算(如果Entry大小为32,则只会与低5位进行与操作),很容易发生hash冲突。

这里,32与64这两个hash值,都被存储在Entry数组0的位置上。


为了解决这个问题,HashMap在做indexFor操作前,需要调用hash方法,使hash值的位值在高低位上尽量分布均匀,hash方法:
static int hash(int h) {  
    // 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);  
}

还是按前面的key,经过Object的hash方法后,分别为32,64来进行运算:
32调用hash运算过程如下:
   原始h为32的二进制:
        100000
        h>>>20:  
        000000
    h>>>12:
        000000
    
接着运算 h^(h>>>20)^(h>>>12):
    结果:    100000

然后运算: h^(h>>>7)^(h>>>4),
过程如下:
    h>>>7:    000000
    h>>>4:    000010
最后运算: h^(h>>>7)^(h>>>4),
    结果:    100010,即十进制34
    
    调用indexFor方法:
        100010 & 1111 => 2,即存放在Entry数组下标2的位置上
------------------------------------

64的运算结果为:1000100,十进制值为68
    调用indexfor方法:
        1000100 & 1111 => 4,即存放在Entry数组下标4的位置上

可以看到经过hash方法后,再调用indexFor方法,这样可以减少冲突。