为什么HashMap要重新哈希？ [已关闭]

Question

Java 中的 HashMap 使用单独的链接来处理冲突，这就是为什么您可以毫无问题地进行任意次数的插入。

我不明白的是HashMap需要重新散列的原因。

当哈希表中的条目数超过 负载因子和当前容量，哈希表被重新哈希 （即重建内部数据结构）使得哈希 表的桶数量大约是桶的两倍

HashMap 被扩展了，为什么？

这只是经典的单独链接的优化，以限制每个桶可以拥有的键的数量吗？ （因为这些键具有相同的哈希值。）

Answer 1

这只是经典分离链接的优化，以限制每个桶可以拥有的键的数量（因为这些键具有相同的哈希值）？

这或多或少是正确的¹。

Java

HashMap ^{查找工作原理的}简化版本

2

如下：

1. 调用

   key.hashCode()

   来获取 32 位哈希码。
2. 32位哈希码被简化为更小的整数，可以用作哈希桶数组的索引。
3. 在选定的哈希桶中搜索其键等于我们正在查找的键的条目。
4. 返回条目中存储的值。如果没有匹配，则返回

   null

   。

假设地图中共有

N

个条目，当前有

B

个存储桶。

如果我们假设现有键的映射条目均匀分布在存储桶中，则意味着每个存储桶中大约有

L(N, B) = N / B

条目。

现在步骤 1、2 和 4 相对于

N

和

B

是恒定的。然而，搜索哈希桶的成本取决于桶中元素的数量。

在简单的实现中³，搜索成本将是

O(L)

。具体来说，您需要检查平均

L / 2

条目是否密钥在地图中，如果不在地图中，则需要检查

L

。

但正如我们之前所说，

L

实际上是桶

B

数量的函数。事实上，如果我们增加数量

B

，我们就会减少

L(N, B)

。

简而言之，重新哈希会增加存储桶的数量

B

，从而降低搜索哈希存储桶的平均成本，从而平均实现更快的查找。

---

^{1 - 你说：“因为这些键具有相同的哈希值”。这是不正确的。按键不一定具有相同的}

hashCode

。哈希冲突发生在reduction步骤之后。
2 - 例如，这忽略了这样一个事实：对于链太长的任何哈希桶，Java 都会切换到红黑树表示。仅当存储桶中的键分布（显着）不均匀时才会发生这种情况。这与重新哈希无关，因此我们不需要在这里考虑它。
3 - 即忽略红黑树。事实上，这些不应该改变最终的结果。如果你愿意的话可以自己检查一下。

Answer 2

当“桶”太满而影响查找时间、冲突和其他基于

initial capacity

 和 

load factor

 的哈希图参数（在 

HashMap 的 JavaDoc 中对此进行了解释）的因素时，需要对 Hashmap 进行重新哈希处理。

想象一下，您以列表的形式散列到

16

存储桶。那么索引将类似于 hashCode mod

16

。但是每个桶在链表中都可以有

1000's

的条目，因此仍然可以进行线性搜索来找到给定键的正确值。如果列表扩展到

256

个存储桶，那么索引现在将是 hashCode mod

256

（对于更多数量的存储桶，索引可能会更高）。但现在现有元素对于新列表大小来说位于错误的存储桶中，因此所有内容都需要重新哈希。这种重新散列会减少每个存储桶中的项目数量，但会消耗一些额外的内存。理想情况下，这种情况不会经常发生，并且可以根据数据的先验知识来设置初始大小和负载系数。

有几点需要注意：

• hashCode 不一定是唯一的，这意味着无论上述模数如何，多个对象都可以散列到同一个存储桶。或者，如果模数发生变化，那么当重新哈希发生时，同一存储桶中的两个值现在可能位于不同的存储桶中。例如，如果哈希码是

  1234

  和

  1334

  并且模数是

  100

  ，则它们将具有相同的索引

  (34)

  并且位于同一个存储桶中。如果模数为

  1000

  ，它们将具有不同的索引

  (234, 334)

  ，并最终位于不同的桶中。

• 不同的是实现哈希图。上述解释没有考虑其他可能进一步减少开销的方法。