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

Question

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

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

int index = key.GetHashCode() % 10

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

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

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

Answer 1

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

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