与Hashtable和Dictionary相关的面试问题
与Hashtable和Dictionary相关的面试问题
我最近在几次面试中被问到Hashtables以及何时需要重写GetHashCode()。讨论越来越深入，直到我束手无策。现在我正在进行一些研究，以便下次准备好应对一切。\n我找到了这篇很棒的文章，我想分享一下：\nhttp://msdn.microsoft.com/en-us/library/ms379571(VS.80).aspx#datastructures20_2_topic5\n1) 我觉得不太舒服的是字典是基于哈希的，但列表显然不是。这只是意味着在List<>和Array[]中搜索是线性的，而在字典或哈希表中搜索是常数的，因此更快吗？就是这样吗？\n2) 如果我在字典中使用一个类作为键，我需要根据任何必要的标识字段来重写该类的GetHashCode()方法，以使实例唯一。然而，仍然可能发生两个ID字段相等并生成相同哈希码的情况？如果是这样的话，两个具有相同哈希码的实例发生冲突时会发生什么？\n3) 如何解决冲突？我在文章中读到了关于Hashtable冲突时的重新哈希方法和Dictionary的链接方法。但我仍然不确定它的工作原理，因为我不是数学天才。:-\\ 有人能更好地解释一下它的工作原理吗？\n非常感谢，\nKave
哈希表是一种数据结构，用于存储键值对。哈希表的查找速度取决于哈希函数的质量以及解决冲突的策略。以下是关于哈希表和字典的一些面试问题以及相关的讨论。
1) 默认情况下，列表的搜索是线性的，需要遍历所有元素。如果哈希表存在冲突，查找速度会变慢。完美的哈希函数可以在最坏情况下实现常数时间的查找。
2) 当对大量可能的键进行哈希时，哈希冲突是不可避免的。因此，大多数哈希表实现都有一些解决冲突的策略。.NET的Hashtable实现似乎使用双重哈希。
3) 只要提供适当的哈希码，就不需要担心哈希冲突。如果感兴趣，可以阅读维基百科关于哈希表的文章，其中解释了几种技术。
最近更新的讨论中提到，Hashtable和Dictionary在处理冲突时有一些差异。Hashtable已过时，推荐使用Dictionary或HashSet。
在面试中，某些情况下是否需要自己处理哈希冲突。实际上，只要提供适当的哈希码，.NET会自动处理冲突。可能是面试官想要听到关于内部使用双重哈希的信息。
如果数据库的主键类型是int，并且字典只包含该类型的对象，那么哈希冲突的机会几乎为零。只需在GetHashCode函数中返回主键字段即可。但大多数情况下，需要一个好的哈希函数。
关于处理冲突，只是需要了解为什么一个尽可能唯一的哈希函数很重要。
如果哈希表的负载因子达到指定的负载因子，字典中的桶数量会自动增加到大于当前字典桶数两倍的最小质数。使用来自数据库的主键（int类型）将得到一个最优的哈希函数。
Hashtable和Dictionary是常见的数据结构，用于存储键值对。在使用这些数据结构时，会遇到一些问题和挑战。下面是一些与Hashtable和Dictionary相关的面试问题，我们来看一下问题的出现原因以及解决方法。
问题1：通常情况下，使用Dictionary或HashSet可以实现常数时间的访问。而在未排序的List或Array中查找项必须线性地进行。排序集合可以使用二分搜索，从而实现O(log n)的访问时间。
问题2：如果在.NET中重写了GetHashCode方法，也应该重写Equals方法。在.NET的Dictionary和HashSet中，不能插入相等的项。在一般情况下，哈希冲突是不可避免的（除非使用了完美哈希）。解决哈希冲突的方法有几种。
问题3：关于冲突解决的更多信息，可以参考维基百科的哈希表相关页面。在.NET中，冲突通常通过将链表附加到桶上来解决。
回答者提到了完美哈希，问题的提问者进一步追问了如何实现完美哈希以及哈希冲突是否由开发人员负责。
问题的回答者解释了完美哈希的概念。假设数据库中有1,000个唯一键，而哈希表只能容纳其中的任意100个键。您创建的哈希码将被哈希表映射到这100个插槽中的一个。因此，即使哈希码是唯一的，哈希表中仍然可能发生冲突。只有在哈希码与哈希表中的插槽一一映射时，最小完美哈希才能正常工作。定义一个给出合理均匀分布的哈希函数是开发人员的责任，但解决冲突是哈希表实现的责任。
以上是对Hashtable和Dictionary相关问题的解答和讨论。在使用这些数据结构时，我们需要理解哈希冲突的问题，并根据需要选择适当的解决方法。