在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保密.