散列过程如何在Dictionary <TKey,TValue>中工作

Question

散列过程如何在Dictionary中工作？我读到使用字典提供更快的查找.但是不明白怎么了？散列和映射到索引的方式如何？找不到任何好的参考.

编辑:如何从散列函数的结果中获取存储对象的实际内存位置？

Answer 1

哈希表或字典是存储键值对的数据结构.哈希表的优点是,给定一个密钥查找,相应的值非常快.简化,在哈希表中查找键值对的时间不依赖于表的大小.将其与列表或数组中的键值对进行比较.要查找键值对,您必须从头开始搜索列表,直到找到匹配的键.列表越长,找到键值对所需的时间就越多.使用big-O表示法可以说在哈希表中查找键是O(1)的顺序,而使用线性搜索在列表中查找键是O(N)(简化).

要在哈希表中插入键值对,首先必须计算键的哈希码.在.NET中,所有对象都有一个名为的方法GetHashCode,该方法返回该特定对象的哈希码(32位整数).重要的是,相等的对象返回相同的哈希码,但如果不同的对象返回不同的哈希码,则非常有用.要注意错误的观念,即不同的对象不能返回相同的哈希码 - 它们可以,但它会导致冲突(见下文).

例如,考虑两个字符串的哈希码:

"Boo" 0x598FD95A
"Foo" 0x598FD8DE

即使字符串非常相似,它们也有不同的哈希码.

我在这里简化了一些事情,专注于哈希表的重要方面,所以现在让我们说内部Dictionary<TKey, TValue>存储键值对在数组中.要在此数组中找到存储键值对的索引,您必须计算以数组大小为模的键的哈希码.假设数组的大小为5:

Index("Boo") = 0x598FD95A % 5 = 4
Index("Foo") = 0x598FD8DE % 5 = 0

这导致了这个内部哈希表数组:

+---+---------+
| 0 | "Foo"   |
+---+---------+
| 1 | (empty) |
+---+---------+
| 2 | (empty) |
+---+---------+
| 3 | (empty) |
+---+---------+
| 4 | "Boo"   |
+---+---------+

查找哈希表中的条目非常快.您只需计算以内部数组大小为模的密钥的哈希码,并检索该索引处的字符串.

现在考虑关键的"动物园":

Index("Zoo") = 0x598FDC62 % 5 = 0

它与键"Boo"具有相同的索引.这导致所谓的碰撞.哈希表的正确实现必须处理冲突,并且有不同的策略来执行此操作.此外,随着内部阵列填满,阵列中的空元素将越来越少,从而导致越来越多的冲突.所述负载因素是使用的元件和内部阵列中的总元素之间的比率.在上面的例子中,负载系数是2/5 = 0.4.当负载因子超过某个阈值时,大多数哈希表实现将增加内部数组的大小.

如果您想进一步了解其中一些概念,您将需要学习其他答案中链接的一些更全面的资源.

Answer 2

字典中的散列过程使用一种被称为链接的技术.通过链接,利用辅助数据结构来保持任何冲突.具体来说,Dictionary中的每个插槽都有一个映射到存储桶的元素数组.如果发生碰撞,碰撞元素将被添加到桶的列表中.

有关详细信息,请参阅MSDN上的这篇文章.