为什么 return (h = key.hashCode()) ^ (h >>> 16) 而不是 key.hashcode ？

Question

我不认为这种方法可以避免碰撞。我认为如果key.hashcode大于table.length，就会发生冲突。

更新内容： 实际上，我参考了 JDK 1.8 中的

HashMap#hash

，并且对向下扩展高位的好处有点困惑。 现在，我想在这个link的帮助下我已经清楚了，好处是：

• 我们不需要进行%计算，而是使用更快的方式——位移位。

对于碰撞来说，如果key的数量大于表的长度，那么无论使用什么哈希方法都会发生碰撞。

Answer 1

假设您天真地使用

索引到哈希表中

int index = hashcode % table.length;

这可能会在某些常见用例中导致许多冲突。例如，假设 table.length 是 2 的小幂（如 32 或 64）。在这种情况下，只有哈希码的低位才能确定索引。如果对象的哈希码仅高位不同，这将导致大量冲突。位移位允许哈希码的高位也影响计算的索引。

Answer 2

原因在评论中：

计算 key.hashCode() 并将散列的高位扩展到低位。由于该表使用二次方掩码，因此仅在当前掩码上方的位上变化的哈希集将始终发生冲突。 （已知的例子包括在小表中保存连续整数的 Float 键集。）

用简单的话来说，

Key#hashcode

（我们关心的最后一位）对于实际上不同的键来说是相同的。这会产生冲突，因为这些条目最终会出现在同一个存储桶中。

条目的去向取决于现有存储桶的数量或最后 n 位，正如您已经看到的：

int index = (n - 1) & hash

如果 hashmap 不会再次重新散列 - 这意味着最后几位没有不同的条目最终会出现在同一个存储桶中，搜索时间 == 会更慢。

使用

XOR

的原因 - 因为它具有 50/50% 的

1

和

0

分布（而不是

|

或

&

具有 75/25 或 25/75）。

并且使用

&

操作代替

%

，不仅仅是为了速度，而是因为哈希码是

int

并且可以为负数。负数的模将是负数 - 意味着负数桶...因此使用

&

将生成正索引。

Answer 3

使用

h ^ (h > > > 16)

将 hashCode 中的高阶位向右移动，并使用 XOR 运算将效果传播到较低位，以便这些位真正参与索引计算逻辑，最终有助于避免冲突。
此链接中通过示例清楚地解释了这一点： https://jvmaware.com/hashcode-calculation/

Answer 4

这是我对这个话题的理解。

入场指数计算如下

(n - 1) & (hash = hash(key))

而不是天真

(hash = hash(key)) % n

(n - 1) & hash

严格只生成+ve索引

n 是存储桶数组的大小，始终为 2 的幂。

由于表/桶数组的大小是 2 的幂（16、32、64...），因此它最终只会考虑较小掩码的哈希的低位（这里掩码表示 n-1）。

因此

该表使用二次幂掩码，仅在当前掩码以上的位上变化的哈希集将始终发生冲突

简单地说，从 0000100000 到 1111100000 的哈希值将落入同一个桶中。

为了确保这些数字的更好分布，较低位与较高位进行异或。

(h = key.hashCode()) ^ (h >>> 16);

为了获得最终索引，它被表大小掩盖，即

n-1

因此

int index = (n - 1) & ((h = key.hashCode()) ^ (h >>> 16));