我最近接受了几次关于 Hashtables 的采访，以及什么时候需要覆盖 GetHashCode()。讨论越来越深入，直到我认输。

我现在正在做一些研究，以涵盖为下次准备的所有内容。

我发现了这篇很棒的文章，我想分享一下:
http://msdn.microsoft.com/en-us/library/ms379571(VS.80).aspx#datastructures20_2_topic5

1) 我觉得不太舒服的是，字典是基于哈希的，但列表显然不是。这是否仅意味着在 List<> 和 Array[] 中搜索是线性的，而在字典或哈希表中搜索是常数，因此速度更快？这就是全部吗？

2) 如果我使用一个类作为字典中的键，我需要根据任何必需的标识字段覆盖该类上的 GetHashcode() 以使实例唯一。但是，仍然可能发生两个 ID 字段相等并且会生成相同的哈希码的情况？如果是这种情况，在具有相同哈希码的两个实例发生冲突时会发生什么？

3) 如何解决冲突？我在文章中读到了关于在 Hashtable 和 Chaining for the Dictionary 发生冲突的情况下重新散列方法的文章。但我仍然不确定它是如何工作的，因为我不是数学天才。 :-\谁能更好地解释它是如何工作的？

非常感谢，
凯夫

请您参考如下方法:

1) 一般来说，是的，Dictionary<T>或 HashSet<T>有恒定的时间访问。在未排序的 List<T> 中定位项目或 Array 必须线性完成。排序集合让您可以进行二进制搜索，从而提供 O(log n) 访问时间。

2) 如果您覆盖 GetHashCode在 .NET 中，您还应该覆盖 Equals方法。在.NET中Dictionary和 HashSet ，您不能插入相等的项目。在一般情况下，散列冲突是不可避免的(除非您已经计算出一个完美的散列)。有几种方法可以解决冲突。

3) 有关冲突解决的更多信息，请参阅 http://en.wikipedia.org/wiki/Hash_table .