0

谁能解释一下这个哈希函数背后的逻辑？

static int hash(int h) {
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

我将 传递key.hashCode()给这个函数，它给了我哈希值。根据这个值和数组大小，我计算数组的索引。我只是不了解此方法中使用的运算符。

  1. 在这种情况下，此运算符在此处做什么^。它是否检查！=
  2. 无符号右移 >>> 做什么？我们在 Java 中没有 Unsigned int 对吗？
  3. 如何为此函数选择值 20、12、7 和 4？它是预定义的还是用户定义的？

key.hashCode()传递给此哈希函数的是79847235. 任何人都可以解释内部发生的事情以返回最终的哈希值。

4

2 回答 2

3

看看下面的内容：

Bitwise and Bit Shift Operators

~       Unary bitwise complement
<<      Signed left shift
>>      Signed right shift
>>>     Unsigned right shift
&       Bitwise AND
^       Bitwise exclusive OR
|       Bitwise inclusive OR

相关unsigned right shift见：Java中的无符号右移'>>>'运算符

另外，对于 >>> 我认为：

>>> 运算符将表达式 1 的位右移表达式 2 中指定的位数。零从左边开始填充。右移的数字被丢弃。所以这种转变不尊重标志。

那么这个函数有什么作用...

  • (h >>> 20) 将 h 除以 2 的 20 次方。（向右移动 20 次）。此外，这意味着如果您的数字为负数，它将不会继续如此。
  • (h >>> 12) 将 h 除以 2 的 12 次方。（它向右移动 12 次）...再次与负数相同。
  • 然后将这两个结果进行异或，然后再次与原始 H 进行异或。
  • 接下来，更多的 XORing 继续计算最终的哈希值。

编辑：注意到这已在接受的答案中进行了广泛分析：了解奇怪的 Java 哈希函数

于 2013-09-25T23:38:28.903 回答
1

无符号右移 ( >>>) 与有符号右移( ) 不同>>，它将在执行右移操作之前将负数转换为正数，以确保结果返回无符号正整数。例如，右移h >>> 20本质上意味着返回 的下限整数h/Math.pow(2,20)。
例如对于您的输入79847235，因为它是一个正数，所以无符号右移和有符号右移都将返回一个正整数。 79847235>>>20将因此 preform:
Math.floor(79847235/Math.pow(2,20))which 返回76.
接下来h >>> 12是79847235：
Math.floor(79847235/Math.pow(2,12))which 返回19493
（它更大，因为我们除以一个较小的数字）。
现在我们执行一个exclusive ORon76和19493。
例如1^0is1
1^1如果0
我们想要包含 AND，我们必须使用包含 OR，即 |
因此1|1is 1
1|0is 0
etc is the binary representation

1001100of 76
100110000100101is the binary representation of 19493
an operationexclusive OR看起来 像这样

000000001001100：: 这与: 填写我们的值is : is重要的是要记住我们的新值现在是 下一行: is76
10011000010010119493
---------------
10011000110100119561



h ^= (h >>> 20) ^ (h >>> 12);

h ^= 19561


h = h^19561

h79847235
79847235^1956179827754
h = 79827754
h 79827754



return h ^ (h >>> 7) ^ (h >>> 4);

h>>>7Math.floor(79827754/Math.pow(2,7))哪个返回623654
h>>>4就是Math.floor(79827754/Math.pow(2,4))哪个返回4989234

现在括号已经不碍事了：
return h ^ 623654 ^ 4989234;
从左到右执行这个很重要。
填写h并重新组合：
return (79827754 ^ 623654) ^ 4989234;



79827754 ^ 623654is:
100110000100001001100101010( 79827754in binary)
000000010011000010000100110( 623654in binary)
---------------------------
100110010111001011100001100( 80451340in binary)

最后我们有：
return 80451340 ^ 4989234;

80451340 ^ 4989234is:
100110010111001011100001100( 80451340in binary)
000010011000010000100110010( 4989234in binary)
---------------------------
100100001111011011000111110( 76002878in binary)

因此我们的最终结果是：
return 76002878;

随意检查我的答案，我已经仔细检查了我的工作。
由于按位异或的性质，很难预测散列函数的结果是大于还是小于我们的参数。例如：
11^2is 9(小于我们的参数 11)
17^2is 19(大于我们的参数 17)

于 2013-09-26T00:49:39.207 回答