我对哈希表的概念相当陌生，而且我一直在阅读不同类型的哈希表查找和插入技术。
我想知道线性探测、链接和二次探测的时间复杂度之间有什么区别？
我主要对哈希表中节点的插入、删除和搜索感兴趣。因此，如果我将每个进程的系统时间（插入/搜索/删除进程）与进程号绘制成图表，这些图表会有什么不同？
我猜测： - 二次探测将是最坏情况 O(nlogn) 或 O(logn) 进行搜索 - 线性探测将是最坏情况 O(n) 进行搜索 - 不确定但我认为 O(n^2 ) 用于链接
有人可以证实这一点吗？谢谢！
问问题
3707 次
1 回答
8
由于各种原因，准确分析所有这些不同的散列方案实际上非常困难。首先，除非你对你的散列函数做出非常强的假设，否则很难准确地分析这些散列方案的行为，因为不同类型的散列函数会导致不同的性能。其次，与处理器缓存的交互意味着某些在理论上稍差的哈希表实际上可以胜过理论上稍好一些的哈希表，因为它们的访问模式更好。
如果您假设您的散列函数看起来像一个真正的随机函数，并且如果您将散列表中的负载因子保持在最多一个常数，那么所有这些散列方案都需要 O(1) 的查找时间。换句话说，每个方案，按照预期，只需要您执行恒定数量的查找来找到任何特定元素。
从理论上讲，线性探测比二次散列和链式散列要差一些，因为除非散列函数具有强大的理论特性，否则元素往往会聚集在彼此附近。然而，在实践中，由于引用的局部性，它可能非常快：所有查找往往彼此接近，因此发生的缓存未命中率较低。二次探测具有较少的碰撞，但没有那么好的局部性。链式哈希往往具有极少的冲突，但往往具有较差的引用局部性，因为链式元素通常不是连续存储的。
在最坏的情况下，所有这些数据结构都可能需要 O(n) 时间来进行查找。这种情况发生的可能性极小。在线性探测中，这将要求所有元素连续存储而没有间隙，并且您必须查找第一个元素中的一个。使用二次散列，你必须有一组看起来很奇怪的桶才能获得这种行为。使用链式哈希，您的哈希函数必须将每个元素转储到同一个桶中，以获得绝对最坏情况的行为。所有这些都是指数级不可能的。
简而言之，如果你选择这些数据结构中的任何一个，除非你有一个非常糟糕的哈希函数，否则你不太可能被严重烧毁。我建议使用链式哈希作为默认值，因为它具有良好的性能并且不会经常遇到最坏情况的行为。如果你知道你有一个很好的哈希函数，或者有一个小的哈希表，那么线性探测可能是一个不错的选择。
希望这可以帮助！
于 2013-03-24T21:02:48.177 回答