c# - Hashtable - 重新散列

Question

我被告知Hashtable在.NET使用重新散列以减少/避免碰撞。

IE。“重新哈希的工作方式如下：假设我们有一组不同的哈希函数，H1 ... Hn，并且在从哈希表中插入或检索项目时，最初使用 H1 哈希函数。如果这导致冲突，则尝试 H2 并向前直到 Hn 以避免 Hashtable 中的冲突。”</p>

假设：我们有一个带有 n（其中 n < Infinity）元素的哈希表，其中渐近时间复杂度为 o(1)；我们（CLR）在应用一些散列函数（Hn-1 散列函数，其中 n>1）时实现了这一点。

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

提前致谢

Answer 1

散列函数的随机选择被称为通用散列方法。AFAIK 每个初始化过程都会选择一次哈希函数，因此当在单个哈希表的范围内使用多个哈希函数时，这不是真实的情况。

编辑：更多细节

刚回到家，打开 T. Cormen 的“算法简介”一书，在第11.3.3 节 Universal Hashing中找到以下内容：

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

您可以通过在此处的 Google 图书网站上预览这本书来阅读更多内容