哈希表冲突重新哈希-如何读取值

本文关键字：读取 何读取 冲突 新哈希 哈希表 | 更新日期: 2023-09-27 18:22:39

我正在努力了解哈希表在C#中是如何工作的。我读了MSDN的文章，我知道C#哈希表对冲突使用"rehashing"，即如果我试图在哈希表中插入一个键/值对，如果使用HashFunction H1导致冲突，那么它将尝试HashFunction H2、H3等，直到没有发现冲突。

MSDN报价：

Hashtable类使用一种不同的技术，称为重新安置。（一些消息来源称重新散列为双重散列。）

Rehashing的工作原理如下：有一组hash不同函数，H1。。。Hn，以及从中插入或检索项目时哈希表，最初使用H1哈希函数。如果这导致对于碰撞，尝试H2，如果需要，则继续到Hn。上一节只显示了一个散列函数，它是初始散列函数（H1）。其他散列函数非常相似对于这个函数，只通过乘法因子进行微分。在里面一般来说，散列函数Hk定义为：

Hk（密钥）=[GetHash（密钥）+k*（1+（（GetHash）（密钥）>>5）+1）%（hashsize–1））]%hashsize

但是，以MSDN站点1:为例

private static Hashtable employees = new Hashtable();
public static void Main()
{
    // Add some values to the Hashtable, indexed by a string key
    employees.Add("111-22-3333", "Scott");
    employees.Add("222-33-4444", "Sam");
}

假设添加第二个关键帧将导致冲突，因此必须使用H2。然而，当我给员工打电话["222-33-4444"]时，哈希表是如何知道使用H2的？有单独的映射吗？谢谢

哈希表冲突重新哈希-如何读取值

我认为你误解了重新哈希。只有一个散列函数：虚拟object.GetHashCode()（或者，如果您提供IHashCodeProvider或IEqualityComparer，它会使用该对象来计算散列代码）。当哈希表已满时，它会扩展其容量，并在新的、更大的数组上重新分配元素。执行此操作的私有方法称为Rehash()，但它不重新计算哈希代码

校正

重新哈希不使用新函数，而是对哈希代码的前一个值进行操作；这具有搜索后续槽的效果，直到找到一个空槽（用于插入/设置），或者直到检查了具有相同（初始）哈希码的所有键是否与索引键相等（用于检索）。

编辑

直接回答您的问题：

假设添加第二个关键帧将导致冲突，因此必须使用H2。然而，当我给员工打电话["222-33-4444"]时，哈希表是如何知道使用H2的？有单独的映射吗？谢谢

  1. 根据传递的密钥的哈希代码计算正确的bucket
  2. 如果那个桶是空的，就失败
  3. 如果bucket的密钥与传递的密钥匹配，则返回bucket的值
  4. 如果哈希冲突计数为零，则失败
  5. 根据当前哈希代码计算下一个哈希代码
  6. 根据新的哈希代码计算正确的bucket
  7. 转至步骤2

哈希表将键和值存储在哈希表本身中。这样，以后在诸如哈希表查找之类的操作中，可以保证找到的值与用于查找的索引匹配。哈希表使用一种简单的"尝试查找直到成功的基本方法"方法。在这种情况下，查找的方法是"使用哈希函数X"，其中X在失败时发生变化。

在其他方案中，查找的方法是"查看表条目X"（由哈希函数确定），其中X在每次失败时仅以包装方式增加一。

现在恼人的问题是，当值不在表中时会发生什么？好吧，这可能相当丑陋：当你找到表中丢失的条目时，或者更糟糕的是，当你迭代了表中存储的尽可能多的条目后，你可以确定该条目不在那里——但在最坏的情况下，这可能需要"一段时间"。

请记住，由于只有一个值可以与一个键相关联，因此一旦找到了键，就找到了值。哈希表所能做的最糟糕的事情就是必须对哈希表本身的所有值进行相当于缓存不友好的线性搜索。。。但最终，如果它在那里，它会找到值，因为它将存储的密钥与请求的密钥进行比较，以测试它是否在那里。封闭哈希表唯一的优化是首先查找位置——在这种情况下，哈希函数1表示，然后是2，然后是3…

它将首先尝试H1。如果它没有找到匹配项，它将使用H2。等等。

相关文章：