首页 > 代码库 > 关于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的逻辑推理(二)