.net - 为什么 .Net 基于哈希的集合在选择素数时会避免 101 和 101*N+1？

Question

我正在浏览.Net的Dictionary和HashSet的源代码，它们基本上是作为哈希表实现的。

他们总是选择素数作为表格的内部大小。我认为这是因为这些集合使用的哈希值通常随机性很差(例如，整数的哈希码只是相同的整数)，这有助于它们在存储遵循某种模式的键时减少冲突。 (这不是主要主题，但如果您认为有必要，请随时发表评论。我只是在这里提及它，以防它对主要问题很重要。)

选择素数的代码可以在 on GitHub 找到。我惊讶地发现他们预先计算的素数列表避免了 101 以及所有后续 101*N+1 类型的素数。换句话说，该表没有列出 101、607、809、1213 等。

即使在离开预先计算的表并计算新素数时，在接受它之前，它们也会专门检查 (i - 1) % HashPrime != 0 (HashPrime是 101)。

我的问题是:为什么？那个特定的素数家族有什么不好呢？我正在寻找这些数字可能导致的问题的示例。

Answer 1

正如@GuruStron 评论的那样，Hashtable.InitHash提供了一些线索。 Hashtable 是一个较旧的、非通用的哈希表实现，源自 .Net Framework 1.0，我认为没有人会再使用它。

它使用了 double hashing 的形式。真正的双重散列将使用从 key 对象派生的两个不同的散列函数。第二个哈希用于计算在发生冲突时寻找替代存储桶时的步骤。这意味着，在第一个哈希函数发生冲突的情况下，对于不同的键，替代存储桶仍应有所不同。不幸的是，.Net 对象标准上仅支持一种哈希函数。因此，Hashtable 不使用真正的双重哈希，而是根据第一个哈希计算第二个哈希。使用的函数基本上只是 SecondHash = FirstHash * SomePrime + 1。

他们选择的素数是 101。因此，如果他们允许 101 + 1 的倍数作为表大小，他们可能会得到等于表大小的步长。这意味着该键的下一个存储桶将与主存储桶相同，这将再次失败并导致无限循环。

至少这是我能理解的一种失败场景，也许还有更多。无论如何，新的哈希表实现不引用 101 常量，因此这似乎不再是一个限制。我认为他们仍然避免使用 101*N+1 只是出于历史原因。