首页 > 代码库 > 关于hashMap中 计算hashCode的逻辑推理(二)

关于hashMap中 计算hashCode的逻辑推理(二)

hashMap中,为了使元素在数组中尽量均匀的分布,所以使用取模的算法来决定元素的位置.如下:

1 //方法一:
2 static final int hash(Object key){//jdk1.8
3   int h;
4   return (key == null) ? 0 : h = key.hashCode() ^ (h >>> 16);
5 }
6 //方法二:
7 static int indexFor(int h,int length){//低版本的源码
8   return h & (length - 1);//第三步,取模运算
9 }

方法一是我当前使用jdk版本的源码,

方法二是在网上查到的低版本的源码,

首先确认:当length总是2的n次方时,  h & (length - 1)   等价于   hash对length取模      ,但是&比%具有更高的效率;(这一点我暂时无法证明).

 

其次,方法一和方法二的原理是一样的,

在JDK1.8的实现中,优化了高位运算的算法,通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),

主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销。

 

 

-----------------------------------

另开头:

为什么数组大小为2的幂时hashmap访问性能最高?

我在网上查了一些博文,好多都”举例说明“,来以事实说话,

其实我感觉这有取巧的嫌疑,

以下为我个人理解:

为什么取length-1(奇数)?  而不是 length-0(偶数)?

在进行&(逻辑与)运算时(例:a & b),只有当 a =true and b =true 时,结果才是 1,否则都是0;

所以,当 hash & 偶数  时,  二进制结果 就总会是偶数,这就导致 数组的偶数位被浪费,数组的奇数位的冲突概率 增高.

 

基于以上,所以  存储位置index = h & (length - 1);   中length取偶数 使得  hashMap具有更高的性能.

 

至于为什么选择 为2的幂?    接触尚短,我暂时还没想到,待后续.

关于hashMap中 计算hashCode的逻辑推理(二)