java - Java哈希表中的哈希

Question

我一直在挖掘哈希表源代码。并发现哈希是如何发生的:

int index = (hash & 0x7FFFFFFF) % tab.length;

我不明白为什么这里使用按位AND？

如果我们将 0x7FFFFFFF 转换为二进制，我们会得到 = 111 1111 1111 1111 1111 1111 1111 1111

据我所知，如果第一个数字和第二个数字=1，按位AND将给出1因此，如果我们得到一些对象哈希码，例如 2314539 将其转换为二进制并执行 & 操作，我们实际上得到相同的数字:

2314539 = 10 0011 0101 0001 0010 1011

10 0011 0101 0001 0010 1011
&
 11 1111 1111 1111 1111 1111‬
=
 10 0011 0101 0001 0010 1011

10 0011 0101 0001 0010 1011 = 2314539

如您所见，此操作没有进行任何更改。那么这里有什么意义呢？

Answer 1

让我们从Java中余数(%)的含义开始。根据JLS 15.17.3 :

The remainder operation for operands that are integers after binary numeric promotion (§5.6.2) produces a result value such that (a/b)*b+(a%b) is equal to a.

It follows from this rule that the result of the remainder operation can be negative only if the dividend is negative, and can be positive only if the dividend is positive. Moreover, the magnitude of the result is always less than the magnitude of the divisor.

假设index计算为index = hash % tab.length。如果是这样，hash 的负值(除数)将导致 index 的负值。

但是我们将使用 index 为 tab 下标，因此它必须位于 0 和 tab.length.

相反，实际计算首先通过屏蔽符号位将 hash 映射到非负数。然后执行余数运算。

So what's a point here?

1. 您的工作示例是针对正哈希值。 & 确实对负散列 值产生影响。
2. 重点是避免负hash值给出负index值，这将导致ArrayIndexOutOfBoundsException。