Are sets actually implemented as maps?

Question

Everywhere on StackOverflow, I see the response:

A Set is just a Map, except that it's Key is it's Value. This is why both Set and Map cannot have duplicates, as it violates the unique Key principle.

But then I see (for example) that Set does not involve itself with Map at all. Infact, Map isn't even part of Collections while Set is. But to me, this doesn't make sense because most likely the implementation of HashSet in the JDK is very similar to the implementation of HashMap, besides the fact that both come from different interfaces.

What is the relationship between Set and Map in this regard?

Answer 1

The Set and Map interfaces are not related (except of the keySet() and entrySet() methods of the Map interface that return Sets backed by the Map).

However, several Set implementations use a backing Map implementation to store their data (the elements of the Set become keys in the underlying Map, and the values of the underlying Map are just dummy objects). This is true for HashSet and TreeSet.

This is mentioned in the Javadoc :

public class HashSet
extends AbstractSet
implements Set, Cloneable, Serializable

This class implements the Set interface, backed by a hash table (actually a HashMap instance).

And :

public class TreeSet
extends AbstractSet
implements NavigableSet, Cloneable, Serializable

A NavigableSet implementation based on a TreeMap.

Answer 2

Actually Set interface is not backed by Map or anything. However, HashSet is implemented using Hashmap as actual data structure.

Set is not said to be having Map in javadoc

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.

However, as per javadoc Hashset is using HashMap intertally to make sure unique data is maintained.

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element.

It keeps the value added to Set inside the Map as key, not in value. It adds same constant single object in values for all the entries.

  public boolean More ...add(E e) {
     return map.put(e, PRESENT)==null;
}

Here, PRESENT is static value dummy object to be kept in backign Map.

  private static final Object PRESENT = new Object();

Backing Map object gets created when we invoke various construtors of HashSet :-

  public More ...HashSet() {
    map = new HashMap<E,Object>();
   }

public More ...HashSet(Collection c) { map = new HashMap(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); }

public More ...HashSet(int initialCapacity, float loadFactor) { map = new HashMap(initialCapacity, loadFactor); }

All the source can be seen at this link

Refer javadocs for other Set implementations backed by Map.