Java哈希表中的哈希算法

Question

我一直在研究哈希表源代码。发现哈希发生的过程如下：

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

我不理解为什么要在此处使用位与运算符？

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

我知道按位与运算将在第一位和第二位都为1时给出 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（二进制转十进制）

正如您所看到的，这个操作并没有进行任何更改。那么这里的重点是什么呢？

- Skyglar

---

这个位运算 AND 会将 hash 中的负数转换为正数（清除符号比特位），但不会改变其他值。 - Eran

Answer 1

让我们从Java中余数（%）的含义开始。根据JLS 15.17.3：

在二进制数字提升（§5.6.2）后，对于整数操作数的余数运算产生一个结果值，使得(a/b)*b+(a%b)等于a。

由此规则可以得出，余数运算的结果只有在被除数为负数时才可能为负数，并且只有在被除数为正数时才可能为正数。此外，结果的大小始终小于除数的大小。

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

但我们将使用index来下标tab，因此它必须位于0和tab.length之间。

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

所以这里的要点是什么？

你的示例适用于正hash值。对于负hash值，&确实有所不同。

关键是避免负hash值导致负index值，从而导致ArrayIndexOutOfBoundsException。

- Stephen C