学习下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,15]，
这时分别对它们调用indexFor方法：
32计算过程：
? 100000 & 1111 =>? 000000 =>0
64计算步骤例如以下：
?1000000 & 1111 =>? 000000 =>0
能够看到indexFor在Entry数组大小不是非常大时仅仅会对低位进行与运算操作，高位值不參与运算（假设Entry大小为32，则仅仅会与低5位进行与操作），非常easy发生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方法，这样能够降低冲突。
