javaHashMap

java.util.HashMap类提供了静态的hash方法和indexFor方法：

/**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions. This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
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);
}

/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}

看hash方法的javadoc可以了解其目的：为了防止低质量的hash方法带来的过多冲突而增加的这个静态的hash方法。核心代码：

h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);

非常的晕，不是吗？还好总有一些牛人走在我们前面进行了分析：

http://nbqwcnm.iteye.com/blog/1126938

（我的理解）简单点说，就是通过上面代码把原本由低质量的hash方法产生的h进行再次hash而得到一个新的整数，这个整数的产生依赖于对原h的每个字节（共8个）按照一定算法进行^处理，从而保证冲突的尽量避免。

每个字节的处理过程如下：

8=8 
7=7^8 
6=6^7^8 
5=5^8^7^6 
4=4^7^6^5^8 
3=3^8^6^5^8^4^7 
2=2^7^5^4^7^3^8^6 
1=1^6^4^3^8^6^2^7^5 
结果中的1、2、3三位出现重复位^运算 
3=3^8^6^5^8^4^7     ->   3^6^5^4^7 
2=2^7^5^4^7^3^8^6   ->   2^5^4^3^8^6 
1=1^6^4^3^8^6^2^7^5 ->   1^4^3^8^2^7^5 

 

再来看看indexFor方法

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

通过hash值h（由HashMap.hash方法确定的）和hash表长度length来确定当前hash值在hash表中的位置。

照理说我们最常见的做法应该是h%length就可以了,而这里为什么要h&(length-1)呢？其实还是从性能的角度考虑的。我们知道如果Hash表长度是2的平方的话h&(length-1)与h%length是等价的，而前者的性能要高很多。

http://nbqwcnm.iteye.com/blog/1126988