algorithm - 对于哈希表，如何得出 n=O(m) 的结论，其中 n 是表中的元素数，m 是槽数？

Question

在 CLRS 的第 260 页上，它说，

如果哈希表槽的数量至少与表中元素的数量成正比，我们有 n = O(m)，因此，a = n/m = O(m)/m = O(1) . 因此，搜索平均花费恒定的时间。

如何得出 n = O(m) 的结论？n（表中元素的总数）如何被 m（槽数）限制？不应该是 m = O(n) 吗？

Answer 1

O(m) 指的是槽数的最坏情况限制，即n，即哈希表中的项目数。这方面的一个例子是直接地址表。