首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >哈希表碰撞重散列-如何读取值?

问哈希表碰撞重散列-如何读取值?
EN

Stack Overflow用户
提问于 2012-02-06 20:49:32
回答 2查看 5.6K关注 0票数 10

我试图了解Hashtable在C#中是如何工作的。我阅读了MSDN文章,我了解到C#哈希表在冲突中使用'rehashing‘,也就是说,如果我试图在哈希表中插入一个键/值对,如果使用HashFunction H1会导致冲突,那么它将尝试HashFunction H2、H3等,直到没有发现冲突为止。

MSDN引用:

Hashtable类使用了另一种称为重哈希的技术。(一些消息来源称重散列为双哈希。) 重散列的工作方式如下:有一组不同的哈希函数,H1 .在从哈希表插入或检索项时,首先使用H1哈希函数。如果这导致了碰撞,则尝试使用H2,如果需要,则继续使用Hn。上一节只显示了一个哈希函数,即初始哈希函数(H1)。其他哈希函数非常类似于这个函数,只是通过一个乘法因子进行微分。一般而言,散列函数Hk定义为: Hk(key) = GetHash(key) +k* (1 +(GetHash(Key) >> 5) + 1) % (hashsize -1))% hashsize )

但是,以MSDN site1中的示例为例:

代码语言:javascript
复制
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?有单独的地图吗?谢谢。

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2012-02-06 21:02:42

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

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

现在困扰我们的问题是,当值不在表中时,会发生什么?嗯,这可能很难看:当你在表中碰到一个缺失的条目时,或者更糟糕的是,当你遍历了存储在表中的条目时,你可以确定条目不在那里--但在最坏的情况下,这可能需要“一段时间”。

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

票数 3
EN

Stack Overflow用户

发布于 2012-02-06 20:52:43

它将首先尝试H1。如果找不到匹配,它将使用H2。诸若此类。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/9167045

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档