哈希表 - 重新散列

Question

有人告诉我，.NET 中的 Hashtable 使用重新哈希（rehashing）来减少/避免冲突。

即，“重新哈希的工作方式如下：假设我们有一组不同的哈希函数 H1…Hn，在向哈希表插入或检索项时，最初使用 H1 哈希函数。如果这导致冲突，则尝试使用 H2，以此类推，直到使用 Hn 避免 Hashtable 中的冲突。”

假设：我们有一个具有 n（其中 n < 无穷大）个元素的哈希表，渐进时间复杂度为 o(1)；我们（CLR）在应用某种哈希函数（Hn-1 哈希函数，其中 n>1）时实现了这一点。

问题： 当我们寻找（检索）任何元素（如果使用不同的哈希函数）时，可以有人解释一下 CLR 如何将键映射到哈希码？CLR 如何跟踪（如果有的话）任何活动对象（哈希表）的哈希函数？

提前感谢

- s_nair

---

侧边栏：您是否需要使用 Hashtable 是因为要使用 .NET 1.1（直接或通过库）？如果不是，您应该考虑使用 System.Collections.Generic.Dictionary<TKey, TValue>。 - Anthony Pegram

@Anthony Pegram：我认为在哈希表数据结构优化方面，Hashtable和Dictionary类的低级实现应该没有任何区别。据我所知，主要区别在于Dictionary提供了泛型类型参数，这使得使用值类型对象更加高效，有效地排除了装箱/拆箱操作。 - sll

我查看了Dictionary<TKey, TValue>的代码，所以我知道它不使用多个哈希函数，只是使用单个哈希函数object.GetHashCode()，并根据表大小（这是一个质数）的模放置在插槽中。 - Qwertie

@Anthony Pegram: 我们有一个使用Hashtable的代码库。因此，我们想知道哈希在哈希表底层是如何工作的。不管怎样，感谢您的评论。 - s_nair

@sll：感谢你对Universal Hashing的闪现式创意。然而，我必须在这里评论你的观点。据我所知，Hashtable在发生冲突时使用再散列/双哈希。但是，当涉及到Dictionary时，它使用链接以避免冲突。我目前能想到的唯一相似之处是，Dictionary是Hashtable的通用实现。 - s_nair

@s_nair：你有MSDN的参考资料吗？我记得看到过类似的内容，但具体细节想不起来了，看起来你是对的。 - sll

Answer 1

随机选择哈希函数被称为通用哈希方法。据我所知，哈希函数仅在某些初始化过程中选择一次，因此在单个哈希表的范围内使用多个哈希函数并不是真实情况。 编辑：更多细节

刚回家，打开T. Cormen的《算法导论》一书，在11.3.3通用哈希部分找到以下内容：

通用哈希的主要思想是在执行开始时从精心设计的函数类中随机选择哈希函数

您可以通过在 Google Books 网站 此处 预览该书籍，了解更多信息。

- sll