了解奇怪的Java哈希函数

Question

以下是中的哈希函数的源代码java.util.HashMap。这些评论很好地解释了它的成就。但是如何？-什么是^和>>>运营商在做什么？有人可以解释的代码实际上是如何做的评论有什么说的？

/**

 * Applies a supplemental hash function to a given hashCode, which

 * defends against poor quality hash functions.  This is critical

 * because HashMap uses power-of-two length hash tables, that

 * otherwise encounter collisions for hashCodes that do not differ

 * in lower bits. Note: Null keys always map to hash 0, thus index 0.

 */

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);

}

Answer 1

这是一篇讨论整数散列函数及其设计注意事项的文章。它不是很详细，但是要点是：操作必须使用一系列计算来实现雪崩。雪崩意味着输入中的一位差异将使大约1/2的输出位不同。基本上，目标是使用补充哈希函数删除输入中的任何规则，因为这些规则可能导致哈希表退化。