我最近在几次关于Hashtables的访谈中进行了深入研究,并且何时需要覆盖GetHashCode().讨论一直在深入和深入,直到我全身心投入.
我现在正在做一些研究,以涵盖下一次准备好的一切.
我找到了这篇我想分享的优秀文章:http: //msdn.microsoft.com/en-us/library/ms379571(VS80).aspx #datastructures20_2_topic5
1)我感觉不太舒服的事实是字典是基于哈希的,但列表显然不是.这只是意味着在List <>和Array []中搜索是线性的,而在字典或散列表中搜索是不变的,因此更快？这都是它的全部吗？
2)如果我使用类作为字典中的键,我需要根据任何必需的标识字段覆盖该类的GetHashcode()以使实例唯一.但是,仍然可能发生两个ID字段相等并且将生成相同的哈希码？如果这是两个实例与相同哈希码冲突期间发生的情况？
3)如何解决碰撞？我在文章中读到了关于Hashtable和Chaining for the Dictionary的碰撞情况下的rehashing方法.但我仍然不确定它是如何工作的,因为我不是数学天才.: - \任何人都可以更好地解释它是如何工作的？
非常感谢,Kave
1) 一般来说，是的，aDictionary<T>或HashSet<T>具有恒定时间访问。在未排序或数组中定位项目List<T>必须线性完成。排序集合允许您进行二分搜索，从而提供 O(log n) 访问时间。
2) 如果你GetHashCode在.NET中重写，你也应该重写该Equals方法。在 .NETDictionary和.NET 中HashSet，您无法插入相等的项目。在一般情况下，哈希冲突是不可避免的（除非您计算出完美的哈希）。有多种方法可以解决冲突。
3) 有关冲突解决的更多信息，请参阅http://en.wikipedia.org/wiki/Hash_table。