散列过程如何在Dictionary 中工作
散列过程如何在Dictionary中工作？ 我读到使用字典提供更快的查找。 但是不明白怎么了？ 散列和映射到索引的方式如何？ 找不到任何好的参考。
编辑：如何从散列函数的结果中获取存储对象的实际内存位置？
字典中的散列过程使用一种被称为链接的技术。 通过链接，利用辅助数据结构来保持任何冲突。 具体来说，Dictionary中的每个插槽都有一个映射到存储桶的元素数组。 如果发生碰撞，碰撞元素将被添加到桶的列表中。
有关详细信息，请参阅MSDN上的这篇文章。
哈希表或字典是存储键值对的数据结构。 哈希表的优点是，给定一个密钥查找，相应的值非常快。 简化，在哈希表中查找键值对的时间不依赖于表的大小。 将其与列表或数组中的键值对进行比较。 要查找键值对，您必须从头开始搜索列表，直到找到匹配的键。 列表越长，找到键值对所需的时间就越多。 使用big-O表示法可以说在哈希表中查找键是O（1）的顺序，而使用线性搜索查找列表中的键是O（N）（简化）的顺序。
要在哈希表中插入键值对，首先必须计算键的哈希码。 在.NET中，所有对象都有一个名为GetHashCode的方法，该方法返回该特定对象的哈希码（32位整数）。 重要的是，相等的对象返回相同的哈希码，但如果不同的对象返回不同的哈希码，则非常有用。 要注意错误的观念，即不同的对象不能返回相同的哈希码 – 它们可以，但它会导致冲突 （见下文）。
举个例子，考虑两个字符串的哈希码：
“嘘”0x598FD95A “Foo”0x598FD8DE
即使字符串非常相似，它们也有不同的哈希码。
我在这里简化了一些事情，专注于哈希表的重要方面，所以现在让我们说内部Dictionary将键值对存储在一个数组中。 要在此数组中找到存储键值对的索引，您必须计算以数组大小为模的键的哈希码。 假设数组的大小为5：
索引（“Boo”）= 0x598FD95A％5 = 4 索引（“Foo”）= 0x598FD8DE％5 = 0
这导致了这个内部哈希表数组：
+ - + --------- + | 0 | “Foo”| + - + --------- + | 1 | （空）| + - + --------- + | 2 | （空）| + - + --------- + | 3 | （空）| + - + --------- + | 4 | “嘘”| + - + --------- +
查找哈希表中的条目非常快。 您只需计算以内部数组大小为模的密钥的哈希码，并检索该索引处的字符串。
现在考虑关键的“动物园”：
索引（“Zoo”）= 0x598FDC62％5 = 0
它与键“Boo”具有相同的索引。 这导致所谓的碰撞 。 哈希表的正确实现必须处理冲突，并且有不同的策略来执行此操作 。 此外，随着内部arrays填满，arrays中的空元素将越来越少，导致冲突数量增加。 负载系数是内部数组中已使用元素与总元素之间的比率。 在上面的例子中，负载系数是2/5 = 0.4。 当负载因子超过某个阈值时，大多数哈希表实现将增加内部数组的大小。
如果您想进一步了解其中一些概念，您将需要学习其他答案中链接的一些更全面的资源。
通过使用称为哈希映射的计算机科学概念。 这比搜索列表更快。 这通过使搜索不需要遍历列表直到找到匹配为止。 相反，键是“ 哈希 ”，并用作列表的索引。 这种散列函数几乎总是比搜索列表更快（迭代多次比较）。
通常，通过采用哈希值％数组大小，这可能会产生冲突。
字典使用散列键进行查找，因为我试图在我对你的另一个问题的答案中解释。 因此，如果您将自定义对象类型作为键，则一切都取决于您的自定义对象的GetHashCode()实现。