algorithm - 了解 CLRS 上的通用哈希章节

Question

您好，我正在阅读有关 CLRS 通用哈希的章节。

第 234 页

推论 11.4

Using universal hashing and collision resolution by chaining in a table with m slots, it takes expected time Theta(n) to handle any sequence of n INSERT, SEARCH and DELETE operations containing O(m) INSERT operations.

我有点明白了，但我很难理解这个英文句子。结尾“包含O(m)个INSERT操作”是什么意思？

这是否意味着 n = O(m) 插入已经执行。然后，....我不知道。我无法解析这句话。 1st INSERT 和 2nd INSERT 有什么区别？

我想听听你的意见。

谢谢!

Answer 1

我认为 n 个插入、搜索和删除操作只有一个序列，但是参数 m 用于限制允许在这 n 个操作中放入的插入操作的数量。假设您有一个大小为 10 的表，因此 m=10，然后您设置 n=1 000 000，前 500 000 次操作插入，接下来的 500 000 次搜索不在表中的项目。那么性能会很差，因为该表将有大约 100 000 个项目长的链。

所以如果你有一个有 m 个槽的表，这个定理只允许你进行大约 m 个插入操作，所以这个表永远不会容纳超过大约 m 个项目，并且链不会变得太长，而且所有的操作都是几乎是 O(1) - 在上面的示例中，您只能进行大约 10 次插入操作，因此其他 999 990 次操作必须是搜索或删除。