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

Question

在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时以不同的方式维护性能的代码？

Answer 1

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

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

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