Java中的HashSets如何工作？

可能重複：
How does Java hashmap work?Java中的HashSets如何工作？

有人能向我解釋如何在Java工作HashSets，爲什麼他們是不是使用的ArrayList快？

2012-02-02 madCode

是否更快取決於您使用它的方式。例如，HashMap 永遠不會比索引ArrayList 更快地查找索引。它可以更快速地處理集合，但即使這樣也取決於添加東西的方式。 – cHao 2012-02-02 20:55:03

拿起一本關於數據結構和算法的好書，比如* Introduction to Algorithms *，並閱讀哈希表。 – 2012-02-02 20:55:09

http://docs.oracle.com/javase/tutorial/collections/ – JSager 2012-02-02 20:55:45

首先，HashSet，不像ArrayList是Set：它不能包含重複項，而ArrayList可以 - 因此它們是爲不同目的而構建的。它也不保證排序 - 再次，不像列表。

其次-a HashSet建立在hash table數據結構上，它允許O(1)尋道時間的元素。

注意，很多時候，一個HashSet是慢那麼ArrayList - 如果你想在例如元素迭代 - 通常做在ArrayList會更快然後在惡劣高速緩存性能HashSet [因爲的哈希值，其他的原因]

2012-02-02 20:56:32 amit

A HashSet實際上是一個HashMap其中值始終相同。

在很多地方（它也被稱爲「哈希表」）描述了一個HashMap工作的方式。簡而言之：它會生成密鑰（對象）的哈希值並將它們放入一個表中。然後，每次查找密鑰時，都會計算其哈希值，並直接引用表中的存儲桶。這意味着你只有一個操作（最好的情況）來訪問地圖。

HashSet只是包含密鑰，所以.contains(..)是O(1)。那和remove(..)是唯一的操作HashSet比ArrayList（它是O（n））更快。迭代是一樣的，加法是一樣的。

2012-02-02 20:56:03 Bozho

只是爲了增加描述性的答案，迭代應該是O（n），並且應該是O（1）時間複雜度，就像HashMap一樣。要檢查的一個很好的概念是重新散列，在數據結構中要存儲更多數據（使用加載因子檢查），因此需要爲相同的表創建更大的表，從而導致平均插入時間增加。 – 2014-09-30 17:19:00

作爲事實上，例如超過迭代和附加到ArrayList更快之間。

而且，你甚至不能排序一個HashSet。

但是最快的是NoOp。沒有任何東西可以像NoOp一樣快。當然，NoOp並沒有太大的作用。但它真的很快！

你需要在你認爲比「快於」更精確。

2012-02-02 21:01:59

這些是2種不同的數據結構。

HashSet背後的概念是關鍵探索。
I.e.您使用輸入鍵的轉換來獲取數組中值的位置的索引。
這是一個常量O(1)操作，因爲數組允許隨機訪問。

ArrayList也是O(1)操作訪問，因爲它也支持一個數組。但僅限於隨機訪問和插入。

的搜索雖然是一個ArrayList O(N)操作，因爲你必須通過在列表中的所有elemements搜索去不像HashSet值，你只變換密鑰和訪問陣列。在HashSet中搜索的結果是O(1)

2012-02-02 21:03:45 Cratylus

回答