任何人都可以解释一下java设计HashMap的hash()函数吗？
|
参见英文答案 >
Explanation of HashMap#hash(int) method2个
在我阅读JDK的源代码之后,我发现HashMap的hash()函数看起来很有趣.它的官方代码如下： static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
参数h是来自Objects的hashCode,它放在HashMap中.这种方法如何工作？为什么？为什么这个方法可以抵御糟糕的hashCode函数？ 解决方法
Hashtable使用素数的“经典”方法：获取值的“索引”,获取键的哈希值并根据大小执行模数.将素数作为大小,通常会在索引上给出一个很好的分布(当然也取决于哈希值).
HashMap使用“2的幂”方法,意味着大小是2的幂.原因是它应该比素数计算更快.但是,由于2的幂不是素数,因此会有更多的冲突,特别是对于具有相同低位的散列值. 为什么？对于获得(桶/槽)索引的大小执行的模数简单地通过以下方式计算：hash& (size-1)(这正是HashMap中用来获取索引的内容！).这基本上是“二次幂”方法的问题：如果长度有限,例如在图16中,HashMap的默认值,仅使用最后的位,因此具有相同较低位的散列值将导致相同(桶)索引.在16的情况下,仅使用最后4位来计算索引. 这就是计算额外散列的原因,基本上它正在移动较高位值,并使用较低位值对它们进行操作.数字20,12,7和4的原因,我真的不知道.它们使用的是不同的(在Java 1.5左右,哈希函数差别不大).我想有更多的高级文献可供选择.您可能会发现有关他们为何使用他们在各种与算法相关的文献中使用的数字的更多信息,例如： http://en.wikipedia.org/wiki/The_Art_of_Computer_Programming http://mitpress.mit.edu/books/introduction-algorithms http://burtleburtle.net/bob/hash/evahash.html#lookup根据长度使用不同的算法(这是有道理的). http://www.javaspecialists.eu/archive/Issue054.html也许很有意思.检查Joshua Bloch在文章底部附近的反应：“替换二级哈希函数(我在计算机的帮助下开发)具有强大的统计特性,几乎可以保证良好的桶分布.”)所以,如果你问我,这些数字来自Josh本人进行的某种分析,可能是谁知道谁的帮助. 所以：2的幂可以提供更快的计算,但是需要额外的哈希计算才能在插槽/存储桶上有一个很好的扩展. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |