How do HashSets in Java work?

java hashset
madCode picture madCode · Feb 2, 2012 · Viewed 38.7k times · Source

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

Bozho picture Bozho · Feb 2, 2012

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.

Related questions

How to initialize HashSet values by construction?

I need to create a Set with initial values. Set<String> h = new HashSet<String>(); h.add("a"); h.add("b"); Is there a way to do this in one line of code? For instance, it's …

Read More
How to Iterate over a Set/HashSet without an Iterator?

How can I iterate over a Set/HashSet without the following? Iterator iter = set.iterator(); while (iter.hasNext()) { System.out.println(iter.next()); }

Read More
Hashset vs Treeset

I've always loved trees, that nice O(n*log(n)) and the tidiness of them. However, every software engineer I've ever known has asked me pointedly why I would use a TreeSet. From a CS background, I don't think it …

Read More