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

回答