c - C 中哈希表的时间复杂度

Question

我对哈希表的概念相当陌生，而且我一直在阅读不同类型的哈希表查找和插入技术。

我想知道线性探测、链接和二次探测的时间复杂度之间有什么区别？

我主要对哈希表中节点的插入、删除和查找感兴趣。因此，如果我绘制每个进程(插入/搜索/删除进程)的系统时间与进程号的关系图，这些图会有何不同？

我猜:- 二次探测是最坏情况下的 O(nlogn) 或 O(logn) 搜索- 线性探测对于搜索来说是最坏情况下的 O(n)- 不确定，但我认为 O(n^2) 用于链接

有人可以证实这一点吗？谢谢!

Answer 1

由于各种原因，令人惊讶地实际上很难准确分析所有这些不同的哈希方案。首先，除非你对你的哈希函数做出非常强的假设，否则很难准确地分析这些哈希方案的行为，因为不同类型的哈希函数会导致不同的性能。其次，与处理器缓存的交互意味着某些类型的理论上稍差的哈希表实际上可以胜过理论上稍好一些的哈希表，因为它们的访问模式更好。

如果您假设您的哈希函数看起来像一个真正的随机函数，并且如果您将哈希表中的负载因子保持为至多一个常数，则所有这些哈希方案的查找时间都为 O(1)。换句话说，根据预期，每个方案只需要您进行固定次数的查找以找到任何特定元素。

从理论上讲，线性探测比二次哈希和链式哈希要差一些，因为除非哈希函数具有很强的理论属性，否则元素往往会彼此靠近聚集。然而，在实践中，由于引用的局部性，它可能非常快:所有查找往往彼此接近，因此发生缓存未命中的情况更少。二次探测具有较少的碰撞，但没有那么好的局部性。链式哈希倾向于极少发生冲突，但往往具有较差的引用局部性，因为链式元素通常不是连续存储的。

在最坏的情况下，所有这些数据结构都可能需要 O(n) 的时间来进行查找。这种情况极不可能发生。在线性探测中，这将要求所有元素连续存储而没有间隙，并且您必须查找第一个元素之一。使用二次散列，您必须有一组非常奇怪的桶才能获得此行为。使用链式哈希，您的哈希函数必须将每个元素转储到同一个桶中以获得绝对最坏情况的行为。所有这些都不太可能发生。

简而言之，如果你选择这些数据结构中的任何一个，除非你有一个非常糟糕的哈希函数，否则你不太可能被严重烧毁。我建议使用链式哈希作为默认值，因为它具有良好的性能并且不会经常遇到最坏情况的行为。如果您知道自己有一个很好的哈希函数，或者有一个小的哈希表，那么线性探测可能是一个不错的选择。

希望这对您有所帮助!