嗨，我正在阅读关于 CLRS 上的通用散列的章节。
在第 234 页
推论 11.4
通过在具有 m 个槽的表中链接使用通用散列和冲突解决方案，需要预期时间 Theta(n) 来处理包含 O(m) 个 INSERT 操作的 n 个 INSERT、SEARCH 和 DELETE 操作序列。
我有点明白这个想法，但我很难理解这个英文句子。结尾“包含 O (m) INSERT 操作”是什么意思？
这是否意味着已经执行了 n = O(m) 插入。然后，....我不知道。我无法解析这句话。第一次插入和第二次插入有什么区别？
我想听听你的意见。
谢谢！
我认为只有 n 个插入、搜索和删除操作的序列，但是参数 m 用于限制允许在这 n 个操作中放入的插入操作的数量。假设您有一个大小为 10 的表，因此 m=10，然后您设置 n=1 000 000，前 500 000 次操作插入，接下来的 500 000 次搜索不在表中的项目。那么性能会很差，因为该表将有大约 100 000 个项目长的链。
所以如果你有一个有m个槽的表，这个定理只允许你大约m个插入操作，所以这个表永远不会超过大约m个项目，链也不会变得太长，所有的操作几乎都是O (1) - 在上面的示例中，您只能进行大约 10 个插入操作，因此其他 999 990 个操作必须是搜索或删除。
说“O(m)”INSERT 操作意味着C*m+B序列中有 INSERT 操作，其中 m 是槽数。
您在具有 m 个插槽的表上有一系列 n 操作。INSERT 操作的数量与槽的数量成正比（无论序列的长度如何），而不是与操作的数量成正比。
换句话说，只有当插入次数不是 n 的某个函数（例如，序列中的一半操作是插入）而是槽数的线性函数时，预期时间才是 theta(n)，并且它不会随着序列的长度而增长。