c# - 哈希表在调整大小时如何跟踪现有的键索引？

Question

我想知道哈希表在增加容量时如何找到正确的索引。例如，假设我有一个默认容量为 10 的哈希表。现在我们必须添加 (key,value) 对[14,"你好 1"]

我们将使用下面的索引机制为上面的键“14”获得的索引是“4”。所以哈希表将把这个(键，值)对保存在索引 4 中。

int index = key.GetHashCode() % 10

现在我们继续向哈希表中添加项目，它达到了负载因子。所以是时候调整大小了。假设 hastable resize 为 20。

现在我要在这个哈希表中搜索我的旧 key “14”。根据索引机制，现在我将获得此键的索引为 14。因此我将从索引 14 开始搜索哈希表，但理想情况下它在索引 4 中。

所以我的问题是哈希表在调整大小时如何跟踪现有的键索引？还是哈希表在调整大小时重新散列所有现有键？

Answer 1

您可能想继续阅读 hash tables ，但我认为您缺少的概念是:

• 对于给定的 key ，比如“asdf”，有一个给定的 32 位 int 散列码。
• 要获得索引存储中的位置，您应用 hashCode % length 的模数 (%) -- 因此，如果您将表从 10 增加到 20，则结果更改为新索引。实现当然会去确保每个现有条目都在新表的正确存储桶中。