Java Collections – Difference Between HashSet and HashMap

collectionshashmaphashsetjava

Apart from the fact that HashSet does not allow duplicate values, what is the difference between HashMap and HashSet in their implementation?

It's a little bit vague because both use hash tables to store values.

HashSet is a set, e.g. {1,2,3,4,5}

HashMap is a key -> value (key to value) map, e.g. {a -> 1, b -> 2, c -> 2, d -> 1}

Notice in my example above that in the HashMap there must not be duplicate keys, but it may have duplicate values.

In the HashSet, there must be no duplicate elements.

ArrayList

contains() is O(n) but you have fully control over the order of the entries.

                      get  add  contains next remove(0) iterator.remove
ArrayList             O(1) O(1) O(n)     O(1) O(1)      O(1)

Not thread safe and to make it thread safe you have to use Collections.synchronizedList(...)

Gives you an O(1) contains() method but doesn't preserve order.

                      add      contains next     notes
HashSet               O(1)     O(1)     O(h/n)   h is the table

Not thread safe and to make it thread safe you have to use Collections.synchronizedSet(...)