jdk1.8 HashMap中hash值计算源码
/**
* 扰动函数
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 其中的key.hashCode调用的是底层的native方法。
public native int hashCode();- Q: 为什么不直接使用key的hashCode值呢?
如果直接使用key的hashCode()函数的时候,将hash值作下标访问Map的数组的话,由于2进制的取值范围是[-2^31,2^31),加起来大于有40亿的映射空间。只要hash函数散列的比较松散，那么久很难出现碰撞。当然,40亿的数据，内存也是放不下的。所以不能直接拿key的hashCode。
- Q: 为什么要进行
h = key.hashCode()) ^ (h >>> 16)这个运算呢？
这个问题就要从计算出的hash值的作用上来切入了,hashMap计算这个hash值就是为了什么? 增删改查的时候确定元素在数组中的位置。那么hashMap是怎么确定位置的呢? 我们知道HashMap中的数组是tab字段。根据tab找到，在final HashMap.Node<K,V> getNode(int hash, Object key)方法中,有这么tab[(n - 1) & hash]使用。 n是数组的长度.
这里n-1相当于一个低位掩码,和hash进行与操作的结果就是散列值的高位全部归零,保留低位,用来做下标访问. 这么看，就算我们的hash散列分布再松散，冲突也会很严重。以默认长度16为例。
11111111 11111111 11110000 11101010 # native方法 HashCode()
& 00000000 00000000 00000000 00001111 # 默认初始长度 15 = 16 -1
-------------------------------------
00000000 00000000 00000000 00001010 # 进行&操作，计算出的下标为10我们看下使用扰动函数计算后的结果:
# 扰动函数计算过程:
h=hashCode(): 11111111 11111111 11110000 11101010 # native方法 HashCode()
-------------------------------------------------------------------------------
h: 11111111 11111111 11110000 11101010 # native方法 HashCode()计算出的值。
^ h>>>16: 00000000 00000000 11111111 11111111 # hashCode左移16位=>高16位变低位
-----------------------------------------------------------------------------------
hash=h^(h>>>16): 11111111 11111111 00001111 00010101 # 扰动函数计算出的值
# 与掩码做&运算=>计算数组下标
hash=h^(h>>>16): 11111111 11111111 00001111 00010101 # 扰动函数计算出的值
& : 00000000 00000000 00000000 00001111 # 低位掩码=> hashMap中数组的长度
-----------------------------------------------------------------------------------
.... 00101 # =>计算出的下标为5.Peter Lawley的一篇专栏文章《An introduction to optimising a hashing strategy》里的的一个实验
结果显示，当HashMap数组长度为512的时候，也就是用掩码取低9位的时候，在没有扰动函数的情况下，发生了103次碰撞，接近30%。而在使用了扰动函数之后只有92次碰撞。碰撞减少了将近10%。看来扰动函数确实还是有功效的。
JDK7中的HashMap计算hash的方式
参考文章
最后
期望与你一起遇见更好的自己
