HashSet in Java is backed by a HashMap instance

TIL that a HashSet in Java is backed by aHashMap instance.

The first line of the Java 8 HashSet API states

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

The first constructor of the HashSet class looks like:

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * default initial capacity (16) and load factor (0.75).
 */
public HashSet() {
    map = new HashMap<>();
}

Why?

I was wondering why a HashSet is backed by a HashMap instance. Despite the fact that his question is asked a couple of times on Stack Overflow, I could not find an official source that answers my question. If I combine the answers I found on the internet, I would come up with an explanation like the following:

Both HashSet and HashMap are using hashing for their data structure. There is no explicit reason, why the authors of Java should reinvent the wheel and use redundant code, if they can re-use a HashMap key as HashSet value. There are only two requirements:

  • The values of a HashSet must be unique—and they will be unique
  • We need a value for the map, which can be any dummy object, because we will not refer to it—there is a dummy object in the HashSet class:
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

All implementations

In fact, almost all implementations of the Set interface in Java are based on a Map instance.

SHARE THIS ARTICLE