一尘不染

更改为Java 8中的HashMap哈希函数

java

在Java 8
java.util.Hashmap中,我注意到来自的更改:

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

从代码中可以看出,新功能是XOR低16位的简单形式,而高16位则保持了高16位不变,这与先前实现中的几种不同移位相反,并且从注释中可以看出,这在分配上不太有效散列函数的结果,其中低位对不同的存储区具有大量冲突,但由于必须执行较少的操作,因此节省了CPU周期。

我在发行说明中唯一看到的是从链接列表到平衡树的更改,以存储碰撞键(我认为这可能已经改变了计算一个好的哈希值所花费的时间),我特别感兴趣此更改对大型哈希图是否有预期的性能影响。是否有关于此更改的任何信息,还是对哈希函数有更好了解的人是否知道此更改的含义(如果有的话,也许我只是误解了代码)以及是否需要生成哈希迁移到Java
8时以不同的方式维护性能的代码?


阅读 214

收藏
2020-12-03

共1个答案

一尘不染

如您所述:HashMapJEP-180中所述,Java
8中的性能有了显着提高。基本上,如果哈希链超过一定大小,HashMap则将(如果可能)将其替换为平衡的二叉树。这将导致各种操作的“最坏情况”行为,O(log N)而不是O(N)

这并不能直接说明对的更改hash。但是,我 假设
JEP-180中的优化意味着散列函数分布不均对性能造成的影响不那么重要,并且该方法的成本效益分析hash有所变化。即,较复杂的版本 平均而言
受益较少。(束缚地说,当密钥类型的hashcode方法生成高质量的代码时,那么复杂hash方法中的体操将浪费时间。)

但这只是一个理论。进行hash更改的真正理由很可能是Oracle机密。

2020-12-03