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 theHashSet
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.