为什么迭代HashMap O（c/n）？

Question

有很多的链接，告诉我，大O的一个HashMap是：

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

这是还挺显而易见的，为什么得到/添加/包含的O（1），但我想知道为什么迭代是O（c/n）。

虽然我在的话，我很想知道为什么大O的是，他们是什么样的ConcurrentHashMap，TreeMap的等

任何人有一个很好的链接？

Answer 1

链接文件不是说迭代为O(c/n)。它说“下一个条目”是O(c/n)。迭代是每个n的“下一个条目”。

首先，请注意c (capacity) > n (entries)是一个不变量 - 而c是n的一些函数 - 所以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功能它可以有点不同的情况来误导把它拉出来作为一个常数;因此，波形曲线。）