Java中HashCode算法详解
Java中的集合，比如HashMap/HashSet/HashTable在实现上都用到了hashCode算法，用来计算元素在数组中的位置。hashCode是Object类中的一个方法，所以，所有的Java类都有这个方法，只是一些类对这个方法进行了覆写，下面以String类的实现为例进行说明：
public int hashCode() {
int h =hash;
if (h ==0 &&value.length >0) {
char val[] =value;
for (int i =0; i < value.length; i++) {
h =31 * h + val[i];
}
hash = h;
}
return h;
}
其实这个算法的实现很简单，以“hangzhou”这个字符串为例，计算过程如下：
第一步：int ‘h’
第二步：31 * （第一步结果） + int ‘a’
第三步：31 * （第二部结果） + int ‘n’
第四步：31 * （第三步结果） + int ‘g’
第五步：31 * （第四步结果） + int ‘z’
第六步：31 * （第五步结果） + int ‘h’
第七步：31 * （第六步结果） + int ‘o’
第八步： 31 * （第七步结果） + int ‘u’
可以得到“hangzhou”的hashcode为4740586。
为什么HashMap中的&位必须位奇数（length-1）
从key映射到HashMap数组的对应位置需要一个Hash函数：
index = Hash("hangzhou")
如何实现一个尽量分布均匀的hash函数呢？我们使用key的hashcode做某种运算：
index = hashCode("hangzhou") & (Length - 1) 其中，Length为HashMap的长度，下面来演示整个过程：
1、“hangzhou”的hashcode为4740586，二进制表示为100 1000 0101 0101 1110 1010
2、假定HashMap的长度为默认的16，则Length - 1为15，也就是二进制的1111
3、把以上两个结果做与运算，得到的结果为1010，也就是index为10
可以说，Hash算法最终得到的index结果完全取决于hashCode的最后几位。
假设，HashMap的长度为10，则Length - 1为9，也就是二进制的1001，通过Hash算法得到的最终index为8，当只有一个元素的时候这没问题。但是我们再来试一个hashCode：100 1000 0101 0101 1110 1110时，通过Hash算法得到的最终的index也是8，另外还有100 1000 0101 0101 1110 1000得到的index也是8。也就是说，即使我们把倒数第二、三位的0、1变换，得到的index仍旧是8，说明有些index结果出现的几率变大！！而有些index结果永远不会出现，比如二进制0000.
这样，显然不符合Hash算法均匀分布的要求。
反观，长度16或其他2的幂次方，Length - 1的值的二进制所有的位均为1，这种情况下，Index的结果等于hashCode的最后几位。只要输入的hashCode本身符合均匀分布，Hash算法的结果就是均匀的。
一句话，HashMap的长度为2的幂次方的原因是为了减少Hash碰撞，尽量使Hash算法的结果均匀分布。
网友评论