哈希表中哈希表的搜索复杂性？

Question

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

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

我不知道如何计算这种情况的平均情况，并感谢任何人的指点！

Answer 1

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