performance - 为什么要遍历哈希图 O(c/n)？

Question

有很多链接告诉我哈希图的大 O 是：

get   O(1)
add   O(1)
contains O(1)
next item O(c / n)    c = table capacity (number of buckets) n = size

为什么 get/add/contains 是 O(1) 有点明显，但我想知道为什么迭代是 O(c/n)。

当我在做的时候，我很想知道为什么大 O 是 ConcurrentHashmap、TreeMap 等的。

谁有好的链接？

score 2 · Accepted Answer

链接的论文没有说迭代是O(c/n). 它说“下一个条目”是O(c/n). 迭代是每个 n 的“下一个条目”。

首先，请注意这c (capacity) > n (entries)是一个不变量 - 并且 c 是 n - so O(c/n)>的某个函数O(1/n)。（注意：根据评论，我并不完全确定我关于 HashMap 实现中的不变量的断言，该实现使用链来解决冲突。）

因此，这实际上说明的是，在标准 HashMap 中，在执行“下一个条目”时查看的一些存储桶是空的，必须被跳过。因此，“下一个条目”的界限是“超过O(1/n)”。但是，在阅读此边界时要小心，因为它并不意味着迭代越快越快n——它只是根据总n条目来描述“下一个条目”的边界。

由于迭代实际上只是所有 n 的“下一个条目”，因此对于 HashMap 的迭代：

O(1/n * n) -> O(n)
O(c/n * n) -> c*O(n) -> ~O(n)

（因为它c是一个函数，在不同的情况下将它作为一个常数拉n出来可能会有点误导；因此是曲线。）

1 回答 1