How do HashSets in Java work? [duplicate]

Question

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?

Answer 1

A HashSet is actually a HashMap where the value is always the same.

The way a HashMap works 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 HashSet simply contains the keys, so .contains(..) is O(1). That and remove(..) are the only operations a HashSet is faster than an ArrayList (which is O(n)). Iteration is the same, addition is the same.

Answer 2

First, HashSet, unlike ArrayList is a Set: It cannot contain duplicates while ArrayList can - so they are built for different purposes. It also does not guarantee ordering - again, unlike a list.

Second - a HashSet is built on the hash table data structure, that allows O(1) seek time for an element.

Note that many times, a HashSet is slower then an ArrayList - if you want to iterate on elements for example - usually doing it in an ArrayList will be faster then in a HashSet [because of bad cache performance of hash, among other reasons]