Hashtable碰撞重组 - 如何读取值？

Question

我试图了解Hashtables如何在C#中工作.我阅读了MSDN文章,我理解C#Hashtables使用'rehashing'进行冲突,即如果我尝试将键/值对插入哈希表,如果使用HashFunction H1导致冲突,那么它将尝试HashFunction H2,H3等,直到找不到碰撞.

MSDN报价:

Hashtable类使用称为rehasing的不同技术.(有些消息来源称重新散列为双重散列.)

Rehashing的工作方式如下:有一组哈希不同的函数,H1 ... Hn,当从哈希表中插入或检索项时,最初使用H1哈希函数.如果这会导致碰撞,则尝试使用H2,如果需要,则转到Hn.上一节仅显示了一个哈希函数,即初始哈希函数(H1).其他散列函数与此函数非常相似,仅通过乘法因子进行区分.通常,散列函数Hk定义为:

Hk(key)= [GetHash(key)+ k*(1 +(((GetHash(key)>> 5)+ 1)%(hashsize - 1)))]%hashsize

但是,从MSDN site1获取示例:

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？有没有单独的映射？谢谢.

Answer 1

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

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

现在令人烦恼的问题是，当表中没有该值时会发生什么？好吧，这可能相当难看：当您遇到表中丢失的条目时，或者更糟糕的是，当您迭代了表中存储的尽可能多的条目时，您可以确定该条目是不存在——但在最坏的情况下这可能需要“一段时间”。

请记住，由于一个键只能与一个值关联，因此一旦找到该键，也就找到了该值。哈希表能做的最糟糕的事情就是必须对哈希表本身中的所有值进行相当于缓存不友好的线性搜索......但最终，它会找到该值（如果存在），因为它将存储的键与请求的密钥来测试它是否存在。封闭哈希表唯一的优化是先看哪里——在本例中，哈希函数 1 表示，然后是 2，然后是 3...