对于使用具有 N 个键和 M 个列表（地址）的单独链接的哈希表，其时间复杂度为：
Insert: O(1)
Search: O(N/M)
Remove: O(N/M)
以上我认为应该是对的。
但我对分析开放寻址的时间复杂度感到不舒服。假设负载因子仍然是 N/M，有人可以阐明如何处理它的时间复杂度，也许还可以对两种实现进行一些比较。谢谢！
编辑：我对这里的线性探测特别感兴趣。
问问题
7590 次
1 回答
0
线性探测的分析实际上比最初看起来要复杂得多。线性探测的“经典”分析在（非常不切实际的）假设下工作，即用于在表中分布元素的散列函数表现得像一个完全随机的函数。不幸的是，对于大多数散列函数来说，这确实不是一个公平的假设，因为大多数散列函数以合理的非随机方式分布元素。要选择一个用于线性探测的散列函数，它具有您上面给出的（预期）时间界限，您通常需要选择一种称为5-wise Independent hash function 的散列函数。这个分析并不简单，但如果你好奇你可能想看看论文“具有恒定独立性的线性探测”。本文还对线性探测哈希表进行了分析，假设您使用的是较弱类型的哈希函数，以说明为什么上述时间限制在这种情况下不成立。
希望这可以帮助！
于 2013-04-07T23:13:08.777 回答