>假设我们有一个大小为 m 的哈希表，在每个存储桶中我们存储一个大小为 p 的哈希表。最坏情况/平均案例搜索复杂度是多少？
我倾向于说，由于计算哈希函数仍然是原子的，唯一最坏的情况是如果值位于大小为 p 的哈希表中链表的末尾，那么 O（n）？
我不知道如何计算这种情况的平均情况，并希望得到任何指示！
是的，在最坏的情况下，如果通过添加到链表来解决冲突，它仍然是线性的。第一级有 n 个槽，第二级有 p 个槽的两级哈希表与具有np槽的单级哈希表相同。您添加的所有元素最终都可能位于同一二级槽，全部添加到同一链表中，等等。基于这一观察结果，平均情况复杂度与具有np槽的单级哈希表相同，后者使用链表来解决冲突。