7

看了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是从中放入的hashCode。这种方法是如何工作的，为什么？为什么这种方法可以防御较差的hashCode函数？ObjectsHashMap

4

1 回答 1

14

Hashtable 使用素数的“经典”方法：要获得一个值的“索引”，您需要对键进行哈希处理，然后对大小进行取模。以素数为大小，（通常）在索引上给出了很好的分布（当然也取决于散列）。

HashMap 使用“二的幂”方法，这意味着大小是二的幂。原因是它应该比素数计算更快。但是，由于 2 的幂不是素数，因此会有更多的冲突，尤其是对于具有相同低位的哈希值。

为什么？为获得（bucket/slot）索引的大小执行的模数简单地计算为： hash & (size-1) （这正是 HashMap 中用来获取索引的内容！）。这基本上是“二次幂”方法的问题：如果长度受到限制，例如 HashMap 的默认值 16，则仅使用最后一位，因此，具有相同低位的哈希值将导致相同的（桶）索引。在 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 的反应：“替代二级哈希函数（我在计算机的帮助下开发）具有强大的统计特性，几乎可以保证良好的桶分布。”）所以，如果你问我，这些数字来自乔希本人进行的某种分析，可能得到了谁知道谁的帮助。

因此：2 的幂可以提供更快的计算速度，但需要额外的哈希计算才能在插槽/存储桶上进行良好的分布。

于 2013-01-23T12:38:24.293 回答