散列 java 散列 table

Question

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

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?

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

散列 java 散列 table

Hashing in java hash table

java

hash

hashtable