C中哈希表的时间复杂度

Question

我对哈希表的概念相当新,我一直在阅读不同类型的哈希表查找和插入技术.

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

我主要对哈希表中节点的插入,删除和搜索感兴趣.因此,如果我将每个流程的系统时间(插入/搜索/删除流程)与流程编号进行对比,那么图表将如何不同？

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

有人能证实吗？谢谢!

Answer 1

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

如果您假设您的哈希函数看起来像一个真正的随机函数,并且如果您将哈希表中的加载因子保持为最多为常量,则所有这些哈希方案都预期会有O(1)查找时间.换句话说,每个方案,在期望中,只需要您执行恒定数量的查找以查找任何特定元素.

理论上,线性探测比二次散列和链式散列稍差,因为除非散列函数具有强大的理论属性,否则元素倾向于彼此聚集.但是,实际上由于引用的局部性,它可能非常快:所有查找往往彼此接近,因此发生的缓存未命中次数较少.二次探测具有较少的碰撞,但没有那么好的局部性.链式散列往往具有极少的冲突,但往往具有较差的引用局部性,因为链式元素通常不是连续存储的.

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

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

希望这可以帮助!