Java中的HashSets如何工作？

可能重复：
Java hashmap如何工作？

有人可以向我解释一下java中的HashSets是如何工作的以及为什么它们比使用ArrayLists更快？

Answer 1

首先，与ArrayList不同， HashSet是一个Set ：它不能包含重复项，而ArrayList可以 – 因此它们是为不同目的而构建的。 它也不保证订购 – 再次，不像列表。

第二 – HashSet构建在哈希表数据结构上，允许O(1)寻找元素的时间。

请注意，很多时候， HashSet 比 ArrayList 慢 – 如果你想在元素上迭代 – 通常在一个ArrayList执行它会比在HashSet更快[因为哈希的缓存性能不好，以及其他原因]

Answer 2

HashSet实际上是一个HashMap ，其值始终相同。

HashMap工作方式在很多地方都有描述（它也被称为“哈希表”）。 简而言之：它生成键（对象）的哈希值并将它们放入表中。 然后，每次查找密钥时，都会计算其哈希值，并直接引用表中的桶。 这意味着您只需一个操作（最佳情况）即可访问地图。

HashSet只包含键，因此.contains(..)是O(1) 。 那和remove(..)是HashSet比ArrayList （O（n））更快的唯一操作。 迭代是一样的，加法是一样的。

Answer 3

这些是两种不同的数据结构。

HashSet背后的概念是关键探测。
即，您使用输入键的转换来获取数组中值的位置的索引。
这是一个常数O(1)操作，因为数组允许随机访问。

arraylist也是O(1)访问操作，因为它也由数组支持。 但仅限随机访问和插入。

搜索虽然是arraylist的O(N)操作，因为您必须搜索列表中的所有元素以获取值，而不像HashSet ，您只需转换键并访问数组。 在HashSet搜索是O(1)

Answer 4

事实上，例如迭代和附加到ArrayList更快。

而且，你甚至无法对 HashSet进行排序 。

但最快的是NoOp。 没有任何东西像NoOp一样快。 当然，它没有做太多，NoOp。 但它真的很快！

你需要更精确地考虑“比”更快。