Java 中的 HashSet 是如何工作的？
可能的重复：
Java hashmap 是如何工作的？
有人可以向我解释一下 Java 中的 HashSet 是如何工作的以及为什么吗？它们比使用 ArrayList 更快吗？
Possible Duplicate:
How does Java hashmap work?
Can someone explain to me how HashSets in java work and why they are faster than using ArrayLists?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
HashSet实际上是一个HashMap，其中值始终相同。HashMap的工作方式在很多地方都有描述（它也称为“哈希表”）。简而言之：它生成键（对象）的哈希值并将它们放入表中。然后，每次查找键时，都会计算其哈希值并直接引用表中的存储桶。这意味着您只需一项操作（最好的情况）即可访问地图。HashSet仅包含键，因此.contains(..)的时间复杂度为O(1)。该操作和remove(..)是HashSet唯一比ArrayList（时间复杂度为 O(n)）更快的操作。迭代相同，加法相同。A
HashSetis actually aHashMapwhere the value is always the same.The way a
HashMapworks is described in many places (it is referred to as "hashtable" as well). In short: it generates hashes of keys (objects) and positions them into a table. Then each time you look for a key, its hash is computed and the bucket in the table is referenced directly. This means you have just one operation (best case) to access the map.The
HashSetsimply contains the keys, so.contains(..)isO(1). That andremove(..)are the only operations aHashSetis faster than anArrayList(which is O(n)). Iteration is the same, addition is the same.首先，
HashSet与ArrayList不同，它是一个 Set：它不能包含重复项，而 ArrayList 可以 - 因此它们是为不同目的而构建的。与列表不同，它也不保证排序。其次 -
HashSet构建在 哈希表 数据结构之上，即允许O(1)查找元素的时间。请注意，很多时候，
HashSet比ArrayList慢 - 例如，如果您想迭代元素- 通常在ArrayList中执行会比在HashSet中执行得更快[因为散列的缓存性能较差，以及其他原因]First,
HashSet, unlikeArrayListis a Set: It cannot contain duplicates whileArrayListcan - so they are built for different purposes. It also does not guarantee ordering - again, unlike a list.Second - a
HashSetis built on the hash table data structure, that allowsO(1)seek time for an element.Note that many times, a
HashSetis slower then anArrayList- if you want to iterate on elements for example - usually doing it in anArrayListwill be faster then in aHashSet[because of bad cache performance of hash, among other reasons]这是两种不同的数据结构。
HashSet背后的概念是键探测。即，您使用输入键的转换来获取数组中值的位置索引。
这是一个常数
O(1)操作，因为数组允许随机访问。数组列表也是
O(1)访问操作，因为它也由数组支持。但仅适用于随机访问和插入。
不过，对于数组列表来说，搜索是
O(N)操作，因为与HashSet<不同，您必须搜索列表中的所有元素才能获取值。 /code> 您只需转换密钥并访问数组。在HashSet中搜索的时间为O(1)These are 2 different data structures.
The concept behind
HashSetis key probing.I.e. you use a transformation of the input key to get an index of the location of the value in an array.
This is a constant
O(1)operation since an array allows random access.The arraylist is also
O(1)operation for access since it is also backed by an array.But only for random access and insertion.
The search though is
O(N)operation for an arraylist since you have to search through all the elemements in the list to get to the value unlike theHashSetwhere you just transform the key and access the array. Search in aHashSetisO(1)事实上，例如，对 ArrayList 进行迭代和追加到 ArrayList 的速度更快。
哎呀，你甚至无法对 HashSet 进行排序。
但其中最快的是 NoOp。没有什么比 NoOp 更快的了。当然，NoOp 的作用并不大。但它确实很快！
您需要更精确地确定您认为“快于”的内容。
As a matter of fact, for example iterating over and appending to an ArrayList is faster.
And heck, you cannot even sort a HashSet.
But the fastest of all is the NoOp. There is nothing just remotely as fast as the NoOp. Granted, it doesn't do much, the NoOp. But it's really fast at that!
You need to be more precise in what you consider to be "faster than".