algorithm - 带有链接的散列的预期运行时间，但每个列表都按排序顺序

Question

这是来自 CLRS 第 261 页 (11.2-3) 的问题。

假设我们用链式实现了一个哈希表，并保持每个列表的排序。假设简单的统一散列，插入、删除、成功搜索和不成功搜索的预期运行时间是多少？

它在这里说这两种搜索都成为 theta(1+log(alpha)) 的预期运行时间。插入和删除保持 theta(1+alpha)，因为插入或删除排序列表的时间是线性的。

（注意 alpha 表示负载因子，或存储的总键数除以表槽数）

问题： 在我看来，插入和删除平均需要 1+log(alpha) 时间。1 用于计算哈希函数。log(alpha)，因为 slot 中的每个链表都有预期的 alpha 长度，我们可以分而治之，在 log(alpha) 时间内找到插入的位置。但是，答案是 theta(1+alpha)。

然后我想，也许答案是假设你不分而治之，只是线性搜索列表。但是后来我不明白为什么不成功的搜索需要 theta(1+log(alpha)) 时间，因为如果我们必须线性搜索，那么时间与列表的大小 alpha 成正比，所以搜索时间应该是 theta(1+alpha)。与不涉及排序的链式散列相比，这并没有提供任何改进。

我在这里有什么误解？

标签： algorithm

Answer 1

如果每个插槽都有一个排序数组列表而不是链表，那么给出的复杂性是正确的——在列表中搜索需要 O(log n) 时间，但插入或删除需要 O(n)，因为它需要将所有插入/删除后的元素指向上或下。

如果使用链表，那么搜索、插入和删除都需要 O(n) 时间，因为没有随机访问就无法进行二分搜索。