在 java 8 java.util.Hashmap 中我注意到一个变化from http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/HashMap.java#HashMap.hash%28int%29:
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
to http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132/java/util/HashMap.java#HashMap.hash%28java.lang.Object%29:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
从代码来看,新函数更加简单XOR
将低 16 位与高 16 位混合,保持高 16 位不变,这与之前实现中的几个不同的移位相反,并且从评论来看,这在分配具有大量冲突的哈希函数的结果时效率较低。将较低位分配给不同的存储桶,但通过执行更少的操作来节省 CPU 周期。
我在发行说明中唯一看到的是change http://openjdk.java.net/jeps/180从链接列表到平衡树来存储冲突键(我认为这可能会改变计算良好哈希值所花费的时间),我特别感兴趣的是看看这种变化是否会对大型设备产生任何预期的性能影响哈希映射。是否有关于此更改的任何信息,或者对哈希函数有更好了解的人是否知道此更改可能会产生什么影响(如果有的话,也许我只是误解了代码)以及是否需要生成哈希迁移到 Java 8 时以不同的方式编写代码以保持性能?
正如您所指出的:性能显着提高HashMap
在 Java 8 中,如所述JEP-180 http://openjdk.java.net/jeps/180。基本上,如果哈希链超过一定大小,HashMap
将(在可能的情况下)用平衡二叉树替换它。这使得各种操作的“最坏情况”行为O(log N)
代替O(N)
.
这并不能直接解释这一变化hash
。不过,我愿意假设JEP-180 中的优化意味着由于分布不均的哈希函数而造成的性能影响不太重要,并且对hash
方法改变;即越复杂的版本好处越少一般。 (请记住,当按键类型hashcode
方法生成高质量的代码,然后在复杂版本中进行体操hash
方法都是浪费时间。)
但这只是一个理论。真正的理由是hash
更改很可能是 Oracle 机密。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)