在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周期。
XOR
我在发行说明中唯一看到的是从链接列表到平衡树的更改,以存储碰撞键(我认为这可能已经改变了计算一个好的哈希值所花费的时间),我特别感兴趣此更改对大型哈希图是否有预期的性能影响。是否有关于此更改的任何信息,还是对哈希函数有更好了解的人是否知道此更改的含义(如果有的话,也许我只是误解了代码)以及是否需要生成哈希迁移到Java 8时以不同的方式维护性能的代码?
如您所述:HashMap如JEP-180中所述,Java 8中的性能有了显着提高。基本上,如果哈希链超过一定大小,HashMap则将(如果可能)将其替换为平衡的二叉树。这将导致各种操作的“最坏情况”行为,O(log N)而不是O(N)。
HashMap
O(log N)
O(N)
这并不能直接说明对的更改hash。但是,我 假设 JEP-180中的优化意味着散列函数分布不均对性能造成的影响不那么重要,并且该方法的成本效益分析hash有所变化。即,较复杂的版本 平均而言 受益较少。(束缚地说,当密钥类型的hashcode方法生成高质量的代码时,那么复杂hash方法中的体操将浪费时间。)
hash
hashcode
但这只是一个理论。进行hash更改的真正理由很可能是Oracle机密。