HashMap 计算 Hash 值的扰动函数
计算过程
以下代码叫做 “扰动函数”
//java 8 中的散列值优化函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
理论上 hash 散列是一个 int 值,如果直接拿出来作为下标访问 hashmap 的话,考虑到二进制 32 位,取值范围在-2147483648 ~ 2147483647。大概有 40 亿个 key , 只要哈希函数映射比较均匀松散,一般很难出现碰撞。
一个客观的问题:要存下 40 亿长度的数组,服务器内存是不能放下的。通常咱们 HashMap 的默认长度为 16 。所以这个 hashCode , (key.hashCode ) 是不能直接来使用的。使用之前先做对数组长度的与运算,得到的值才能用来访问数组下标。
代码如下:
// n = hashmap 的长度
p = tab[i = (n - 1) & hash])
这里为什么要使用 n -1 ,来进行与运算,这里详单与是一个”低位掩码”, 以默认长度 16 为例子。和某个数进行与运算,结果的大小是 < 16 的。如下所示:
10000000 00100000 00001001
& 00000000 00000000 00001111
------------------------------
00000000 00000000 00001001 // 高位全部归 0, 只保留后四位
这个时候会有一个问题,如果本身的散列值分布松散,只要是取后面几位的话,碰撞也会非常严重。还有如果散列本身做得不好的话,分布上成等差数列的漏洞,可能出现最后几位出现规律性的重复。
这个时候“扰动函数”的价值就体现出来了。如下所示:
在 hash 函数中有这样的一段代码:(h = key.hashCode()) ^ (h >>> 16)
右位移 16 位, 正好是32bit 的一半,与自己的高半区做成异或,就是为了混合原始的哈希码的高位和低位,以此来加大低位的随机性。并且混合后的低位掺杂了高位的部分特征,这样高位的信息变相保存下来。其实按照开发经验来说绝大多数情况使用的时候 HashMap 的长度不会超过 1000,所以提升低位的随机性可以提升可以减少 hash 冲突,提升程序性能。
如果感兴趣的小伙伴可以浏览下一下 Peter Lawlay 的专栏《An introduction to optimising a hashing strategy》的一个实验:他随机选取了 352 个字符串,在散列值完全没有冲突的前提下,对低位做掩码,取数组下标。
结果显示, 当 hashmap 的数组长度为 512 的时候,也就是采用低位掩码取低 9 位的时候,在没有扰动函数的情况下,发生了 103 次碰撞,接近 30%。而在使用扰动函数之后只有 92 次碰撞。碰撞减少了将近10%。说明扰动函数确实有功效的。
但是明显 Java 8 觉得扰动做一次就够用了,做 4 次的话,可能边际效用也不大, 为了效率考虑就改成了一次。
代码演示
import java.lang.reflect.Field;
import java.util.HashMap;
/**
* HashMap 计算 hashKey
* <p>
* 演示:扰动函数
*
* @see HashMap#hash(Object)
*/
public class HashKeyTest {
public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
HashMap<String, String> map = new HashMap<>();
String k = "王羲之";
String v = "大书法家";
map.put(k, v);
Field field = map.getClass().getDeclaredField("table");
field.setAccessible(Boolean.TRUE);
Object[] nodes = (Object[]) field.get(map);
int h = k.hashCode();
System.out.println(" h=" + h);
System.out.println();
// 调用 hashCode 结果
System.out.println(" h=hashCode() " + num0x(h) + " 调用 hashCode");
// 无符号右移 16
System.out.println(" h>>>16 " + num0x(h >>> 16));
System.out.println("--------------------------------------------------");
// 计算 hash
System.out.println(" hash=h^(h>>>16) " + num0x(h ^ (h >>> 16)) + " 计算 hash");
System.out.println("--------------------------------------------------");
// 计算下标
System.out.println(" (n-1)&hash " + num0x(15 & (h ^ (h >>> 16))) + " 计算下标");
System.out.println();
int idx = (15 & (h ^ (h >>> 16)));
// 输出下标
System.out.println(" 下标: " + idx);
// 在下标中去获取数据
System.out.println(" 查询结果:" + nodes[idx]);
}
/**
* 输入 int 转换为 二进制字符串
*
* @param num 数字
* @return 二进制字符串
*/
static String num0x(int num) {
String num0x = "";
for (int i = 31; i >= 0; i--) {
num0x += (num & 1 << i) == 0 ? "0" : "1";
}
return num0x;
}
}
运行结果如下:
参考资料:https://www.zhihu.com/question/20733617
相关文章
- 数字城市+物联网+云计算+人工智能,打造智慧城市
- pytorch交叉熵损失函数计算_pytorch loss不下降
- Excel函数学习-计算各职务的人数
- Java对象的字节大小计算详解编程语言
- 函数MySQL中实现完美日期计算的函数(mysql日期)
- MySQL计算函数:让数据处理更简单(mysql计算函数)
- 微软Azure云计算将开通中国新数据中心 位于河北省由世纪互联运营
- Oracle中强大的差函数: 提升计算效率(oracle差函数)
- Oracle中实现快速用时计算的函数(oracle用时函数)
- 值Linux系统快速计算Hash值(linux计算hash)
- 使用Oracle的函数计算生日日期(oracle计算生日)
- 使用日期函数在 Oracle 中进行时间格式化和计算(日期函数oracle)
- MySQL中使用week函数进行时间计算(mysql中week函数)
- MySQL中avg函数计算平均数(mysql中avg)
- C语言与MySQL实训现代计算之旅(c mysql实训作业)
- 函数Oracle中灵活使用MIN函数,轻松解决数据计算困难(oracle中的min)
- Oracle中实现日期计算的方法(oracle中日期的计算)
- 轻松实现Redis Hash计算(redis计算hash)
- 关于PHP的相似度计算函数:levenshtein的使用介绍
- php计算几分钟前、几小时前、几天前的几个函数、类分享
- php计算2个日期的差值函数分享