爲什麼迭代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功能它可以有點不同的情況來誤導把它拉出來作爲一個常數;因此，波形曲線。）