字典如何快速查找

Question

我正在查看Item[TKey]Dictionary<TKey,TValue>的来源，试图了解字典中的存储/检索机制，以及为什么它比逐个检查每个条目更快。

在哪里我感到困惑是buckets领域的素数和Entry<TKey,TValue>.next的相互作用的用户。

有人可以向我解释逻辑，或指向一个参考，我可以理解它。

谢谢。

Answer 1

见Hash Tables，并可能this article about using prime numbers in hash table implementations.

Answer 2

查找到哈希码，它们允许词典 '桶' 键：

http://msdn.microsoft.com/en-us/library/4yh14awz%28VS.80%29.aspx

科林·E.

Answer 3

看看这个维基百科文章在： Hashtable

字典只是一种强类型d实现一个散列表。它有一些“桶”，它把物品和钥匙放在一起。

将项目添加到哈希表时，它使用密钥的哈希码来决定将要放入哪个存储桶（通常这是一个非常快速的操作，只需调用GetHashCode并对其应用模数）。一旦它具有存储桶（这是某种列表），它会检查存储桶是否已经包含具有相同密钥的项目，如果不是这种情况，则会添加它。这也很快，因为每个存储桶只包含哈希表中所有项目的一小部分。

如果您想根据密钥检索项目，它会根据密钥的哈希码确定存储桶，并在存储桶中查找包含此密钥的项目。

当然，这是一个非常简单的描述...请参阅维基百科文章以获取更多详细信息。