16

我正在阅读 Java 1.6 API 提供的 HashMap 类的代码，无法完全理解以下操作的需要（在 put 和 get 方法的主体中找到）：

int hash = hash(key.hashCode());

该方法hash()具有以下主体：

 private static int hash(int h) {
         h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

这通过对提供的哈希码执行位操作来有效地重新计算哈希。即使 API 声明如下，我也无法理解这样做的必要性：

这很关键，因为 HashMap 使用长度为二的幂的哈希表，否则会遇到低位没有差异的 hashCode 的冲突。

我确实理解键值解析存储在数据结构数组中，并且该数组中项目的索引位置由其哈希确定。我不明白的是这个函数如何为哈希分布增加任何价值。

4

4 回答 4

25

正如 Helper 所写，它的存在是为了以防关键对象的现有散列函数出现故障，并且在混合低位方面做得不够好。根据pgras 引用的消息来源，

 /**
  * Returns index for hash code h.
  */
 static int indexFor(int h, int length) {
     return h & (length-1);
 }

哈希以 2 的幂长度进行与运算（因此，length-1保证为 1 的序列）。由于这种与运算，只使用了 的低位h。其余的h被忽略。想象一下，无论出于何种原因，原始哈希仅返回可被 2 整除的数字。如果直接使用它，则永远不会使用哈希图的奇数位置，从而导致碰撞次数增加 x2。在一个真正病态的情况下，一个糟糕的哈希函数会使哈希图表现得更像一个列表，而不是一个 O(1) 容器。

Sun 工程师必须运行测试表明太多的散列函数在其低位中不够随机，并且许多散列图不够大而不能使用高位。在这些情况下，HashMap 中的位操作hash(int h)可以提供对大多数预期用例的净改进（由于较低的冲突率），即使需要额外的计算。

于 2010-03-29T15:04:01.733 回答
2

我在某处读到这样做是为了确保良好的分发，即使您的 hashCode 实现，嗯，错误，很糟糕。

于 2010-03-29T13:42:49.760 回答
2

正如你所知道的哈希图，底层实现是一个哈希表，特别是一个封闭的桶哈希表。负载因子决定了集合中合适的对象数量/桶的总数。

假设您不断添加更多元素。每次你这样做时，它不是更新，它运行对象的 hashcode 方法，并使用带模运算符的桶数来决定对象应该进入哪个桶。

随着 n（集合中的元素数）/m（桶数）变大，您的读写性能会越来越差。

假设您的哈希码算法很棒，性能仍然取决于这个比较 n/m。

重新散列也用于更改存储桶的数量，并且仍然保持与构建集合相同的负载因子。

请记住，任何散列实现的主要好处是读取和写入的理想 O(1) 性能。

于 2011-02-18T16:25:27.213 回答
1

如您所知，object.hashCode() 可以被用户覆盖，所以一个非常糟糕的实现会抛出非随机的较低级别的位。这往往会挤满一些桶，并会留下许多桶未装满。

我刚刚创建了他们在哈希中尝试做的事情的可视化地图。似乎 hash(int h) 方法只是通过进行位级操作来创建一个随机数，以便生成的数字更加随机（因此更均匀地进入存储桶）分布。

每个位都重新映射到不同的位，如下所示：

        h1 = h1 ^ h13 ^ h21 ^ h9 ^ h6     
        h2 = h2 ^ h14 ^ h22 ^ h10 ^ h7
        h3 = h3 ^ h15 ^ h23 ^ h11 ^ h8
        h4 = h4 ^ h16 ^ h24 ^ h12 ^ h9
        h5 = h5 ^ h17 ^ h25 ^ h13 ^ h10

. . . .

直到h12。

正如你所看到的，h 的每一位都会离它自己那么远。所以这将是非常随机的，不会挤满任何特定的桶。希望这有帮助。如果您需要完整的视觉效果，请给我发送电子邮件。

于 2011-09-21T14:02:57.050 回答