hashtable - 在哈希表中搜索哈希表的复杂性？

Question

假设我们有一个大小为 m 的哈希表，并且在每个桶中我们存储一个大小为 p 的哈希表。最坏情况/平均情况搜索复杂度是多少？

我倾向于说，由于计算哈希函数仍然是原子的，唯一最坏的情况是如果值位于大小为 p 的哈希表中链表的末尾，那么 O(n)？

我不知道如何计算这种情况的平均情况，并希望得到任何指点！

Answer 1

是的，如果通过添加到链表来解决冲突，在最坏的情况下它仍然是线性的。n在第一级和第二级具有插槽的两级p哈希表与具有插槽的单级哈希表相同np。您添加的所有元素最终都可能在同一个二级槽中，都被添加到同一个链表中，等等。根据这一观察，平均情况复杂度与具有使用np槽的单级哈希表相同链表来解决冲突。