java - 为什么返回 (h = key.hashCode()) ^ (h >>> 16) 而不是 key.hashcode？

Question

我没有看到这种避免碰撞的方法。我认为如果key.hashcode大于table.length，就会发生碰撞。

更新: 实际上我引用了 JDK 1.8 中的 HashMap#hash，并且对将高位向下传播的好处感到有点困惑。 现在，我想借助这个 link 我很清楚了，好处是:

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

对于碰撞，如果key的个数大于表的长度，那么不管用什么hash方法都会发生碰撞。

Answer 1

假设您使用

天真地索引到哈希表中

int index = hashcode % table.length;

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