java.util.HashSet和java.util.TreeSet使用什麼算法在其結構中存儲唯一值？

Question

我遇到過多種算法，例如Flajolet-Martin算法，HyperLogLog以從元素列表中找出獨特元素，並突然對Java如何計算它感到好奇？每種情況下存儲和查找唯一值的時間複雜度是多少？

Answer 1

HashSet類型使用散列表（通常使用封閉尋址）跟蹤其元素，而TreeSet類型使用二叉搜索樹來跟蹤其元素。這些數據結構給出了這個問題的確切答案：「這裏是這個元素嗎？」對於需要100％確定地知道以前是否看到過某些內容的情況，以及它們的內存使用情況通常與目前爲止所看到的元素總數成正比的情況非常有用。

另一方面，像HyperLogLog這樣的基數估計器可以很好地回答「存在多少個不同的元素，給出還是佔用幾個百分比？」這樣的問題。如果您需要粗略估計您已經看到了多少不同的東西，那麼將這些東西放在散列表或二叉搜索樹中的方法會佔用太多內存（例如，如果您因爲他們使用的內存量通常是你能夠接受的東西，因爲它是一個Google Web服務器，並且你希望統計訪問你的不同IP地址。但是，他們不允許你回答「我在之前看過這個確切的東西嗎？因此不能用作任何java.util.Set子類型的實現。

簡而言之，這裏的數據結構旨在解決不同的問題。傳統的BST和哈希表用於確切查詢，以確定您是否已經看到某件事是目標，並且希望能夠對所見的所有元素進行迭代。基數估計是很好的，你只關心有多少個完全不同的元素，你不關心它們是什麼，也不需要確切的答案。

Answer 2

Flajolet-Martin和HyperLogLog算法大約與O(N)時間和適度的內存使用情況（比O(N)好得多）N元流中的一個通得到不同元件（所述count-distinct problem）的近似計數。

Map API的實現不需要「計數不同」問題的解決方案。

（旁白：TreeMap和HashMap已經保持條目數的預計算的計數在地圖，即Map.size()前提是你不進入線程安全問題的結果是準確的（不是。近似）調用size()的成本是O(1)，維護它的費用是O(U)其中U是進行地圖的添加和刪除操作的次數）。

更一般地，Flajolet馬丁算法或HyperLogLog不/不能形成的基礎10數據結構。他們沒有解決dictionary problem。

HashMap和TreeMap所使用的算法分別是散列表和二叉樹算法。在各自的javadoc中有更多的細節，完整的源代碼（帶註釋）隨時可供您查看。 （Google爲"java.util.HashMap" source ...爲例。）

---

^{1 - 有趣的是，ConcurrentHashMap不以這種方式工作......因爲更新size領域將是一個併發的瓶頸。相反，size()操作是O(N)。}