理解 Java 中奇怪的哈希函数

Question

理解 Java 中奇怪的哈希函数

34

以下是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);
}

- calebds

它们是位运算，也可以参见：http://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html - Brian Roach

6个回答

6

>>>是一个带有零填充的位移操作符。

^是一个异或操作符。

XOR也被称为“异或”——它是一种数学运算符，用于结合两个数字。请参见http://en.wikipedia.org/wiki/Exclusive_or

右移n位就像从数字中删除n个最低位一样。所以如果数字是00010111，并且您将其向右移动1位，您会得到00001011。

- StilesCrisis

5

这里有一篇文章讨论了整数哈希函数及其设计考虑的一些方面，具体请参见此处。虽然文章不是很详细，但主要观点如下:

操作必须使用一系列计算来实现avalanche。 avalanche的意思是，输入中的一个位的不同会使约1/2的输出位不同。

基本上，补充哈希函数的目标是消除输入中的任何规律，因为这些规律可能导致哈希表退化。

- Michael Borgwardt

1

^ 是按位异或运算符, >>> 是位移运算符。

- penartur

有人能解释一下代码实际上是如何做到评论所说的吗？http://cstheory.stackexchange.com/ 更适合这种类型的问题。 - penartur

0

>>> 看起来是无符号右移位操作，^ 是按位异或。

http://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html

- Dan Passaro

-1

这是一种按位异或和无符号右移的组合。

点击此处了解更多解释：http://www.roseindia.net/java/master-java/bitwise-bitshift-operators.shtml

- ahillman3

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- philwb · Accepted Answer

这里有一些代码和样例输出：

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个或多个位。因此，您可以插入一些随机性到底部位中，利用可能分布更好的高位。然后通过异或应用于原始值，将该随机性添加到较低位。第二次移位的7位异或4位的移位创建一个掩码，可以翻转0个或多个底部28位，这再次为较低位和一些重要的位带来了一些随机性，通过利用先前的异或已经处理了一些底部位的分布。最终结果是通过哈希值平稳分布的位数。

由于Java中的HashMap通过将哈希与所需桶的数量相结合来计算桶索引，因此需要对哈希值的较低位进行均匀分布，以便将条目均匀地分散到每个桶中。

至于证明这个语句限制了冲突数量，我没有任何意见。此外，请参见此处了解有关构建哈希函数的一些良好信息以及关于为什么两个数字的异或趋向于在结果中分布随机位的一些细节。