c# - Dictionary 的 Key Hashcode 与存储值的桶索引之间的关系

Question

Wiki 说(据我所知)每当我向字典添加项目时，系统都会计算哈希码(通过调用 GetHashCode)。然后系统使用哈希码找到一个存储桶，我的值(value)将被保存。

请向我解释在桶数组中查找哈希码和索引之间关系的逻辑，我的值将由字典存储在桶数组中。

想象一下当我创建一个 Dictiornary 并向其添加一个 GetHashCode 返回值 1000000 的对象时的情况。

这是否意味着在 Dictionary 内部将创建一个包含 1000000 个元素的数组并将我的对象存储在索引 999999999 处？

如果这个假设是正确的，那么用这么大的数组来存储一个值有什么意义。

Answer 1

幸运的是，您的假设不正确。如果是，它们实际上就不是桶，而只是一个索引可访问的对象数组。如果您的散列码保证是唯一的，那么这对于 O(1) 查找可能没问题，但事实并非如此 - 事实上，散列码保证不是是唯一的。您无法将 Int64 的每个可能值映射到唯一的 Int32 哈希码。这不是哈希码的用途。

相反，字典会初始化一个较小的桶数组，然后使用简单的模运算来查找桶。 (来自.NET Reference Source)

 int targetBucket = hashCode % buckets.Length;

这意味着如果有 10 个桶，例如，它将得到哈希码除以 10 的余数。如果您的哈希算法运行良好，则意味着哈希码遵循标准分布，这意味着任何 < em>n 个项目，对于足够大的 n，可能会在桶之间平均分配。

至于有多少桶被初始化，这个数字将是第一个大于 ctor 中传递的容量的素数，或者 0 ( See here )。如果这导致过多的哈希冲突，它会自动扩展，每次都跳到下一个质数，直到稳定。