java - 了解奇怪的 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

这是一些代码和示例输出:

public static void main ( String[] args ) {
    int h = 0xffffffff;
    int h1 = h >>> 20;
    int h2 = h >>> 12;
    int h3 = h1 ^ h2;
    int h4 = h ^ h3;
    int h5 = h4 >>> 7;
    int h6 = h4 >>> 4;
    int h7 = h5 ^ h6;
    int h8 = h4 ^ h7;

    printBin ( h );
    printBin ( h1 );
    printBin ( h2 );
    printBin ( h3 );
    printBin ( h4 );
    printBin ( h5 );
    printBin ( h6 );
    printBin ( h7 );
    printBin ( h8 );

}

static void printBin ( int h ) {
    System.out.println ( String.format ( "%32s", 
        Integer.toBinaryString ( h ) ).replace ( ' ', '0' ) );
}

哪些打印:

11111111111111111111111111111111
00000000000000000000111111111111
00000000000011111111111111111111
00000000000011111111000000000000
11111111111100000000111111111111
00000001111111111110000000011111
00001111111111110000000011111111
00001110000000001110000011100000
11110001111100001110111100011111

因此，代码将哈希函数分解为多个步骤，以便您可以看到正在发生的事情。 20 个位置的第一次移位与 12 个位置的第二次移位创建一个掩码，该掩码可以翻转 int 的底部 20 位中的 0 个或更多位。因此，您可以在底部位中插入一些随机性，以利用可能更好分布的较高位。然后通过 xor 将其应用于原始值，以将随机性添加到低位。 7 个位置的第二次移位 x 或 4 个位置的移位创建了一个掩码，该掩码可以翻转底部 28 位中的 0 个或更多位，这通过利用先前的 xor 再次为低位和一些更重要的位带来一些随机性这已经解决了低位的一些分布。最终结果是通过哈希值更平滑地分布比特。

由于 java 中的 hashmap 通过将哈希与桶数相结合来计算桶索引，因此您需要均匀分布哈希值的低位，以便将条目均匀地分布到每个桶中。

关于证明这限制了碰撞次数的声明，我没有任何输入。另见 here了解有关构建散列函数的一些有用信息以及有关为什么两个数字的异或倾向于在结果中随机分布位的一些详细信息。