对于使用N个键和M个列表(地址)的单独链的哈希表，其时间复杂度为:
Insert: O(1)
Search: O(N/M)
Remove: O(N/M)
我认为以上应该是对的。
但是我不喜欢分析开放寻址的时间复杂度。假设负载系数仍然是N/M，谁能告诉我如何处理它的时间复杂度，也许还可以比较一下两种实现。谢谢!
编辑:我对这里的线性探测特别感兴趣。
线性探测的分析实际上实质上比最初看起来要复杂得多。线性探测的"经典"分析是在(非常不现实的)假设下进行的，即用于在表中分布元素的哈希函数表现得像一个完全随机的函数。不幸的是，对于大多数哈希函数来说，这真的不是一个公平的假设，因为大多数哈希函数以一种合理的非随机方式分布元素。要选择一个用于线性探测的哈希函数，它具有上面给出的(预期的)时间限制，通常需要选择一种称为5-wise独立哈希函数的哈希函数类型。这个分析并不简单，但如果你很好奇，你可能会想看看"线性探测与恒定独立性"这篇论文。本文还对线性探测哈希表进行了分析，假设您正在使用较弱类型的哈希函数来说明为什么上述时间限制在这种情况下不成立。
希望这对你有帮助!