HashSet Internals

TL;DR

• The internal workings of a HashSet are entirely delegated to a HashMap.
• A HashSet stores your elements as the keys in a backing HashMap.
• It uses a constant, dummy Object as the value for every key in that map.

Concept

Because a HashMap strictly enforces that keys must be unique, building a Set on top of a Map is incredibly easy. Sun Microsystems (the creators of Java) did exactly this to avoid writing redundant code.

When you look at the source code for java.util.HashSet, you will see:

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

When you call hashSet.add(element), it simply executes:

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

Performance Characteristics

Because it is just a wrapper around HashMap, its performance characteristics, memory footprint, load factors, initial capacity, and collision handling (linked lists turning into trees) are identical to HashMap Internals.

Examples

import java.util.HashSet;

public class HashSetInternalsExample {
    public static void main(String[] args) {
        HashSet<String> mySet = new HashSet<>();
        
        // This line:
        mySet.add("Java");
        
        // Is conceptually equivalent to doing this:
        // internalMap.put("Java", new Object());
        
        // Trying to add it again:
        boolean result = mySet.add("Java"); 
        
        // Conceptual equivalent:
        // Object previousValue = internalMap.put("Java", new Object());
        // return previousValue == null; 
        
        // Since "Java" already existed, put() returns the old dummy object (not null).
        // Therefore, result is false.
        System.out.println(result); // false
    }
}

Interview Questions

Q: Does a HashSet consume more memory than necessary?
A: Yes, arguably. Because it is backed by a HashMap, every element you insert into a HashSet creates a Map Node (which holds a hash, a key reference, a value reference, and a next-node reference). The value reference always points to the dummy PRESENT object. While the PRESENT object itself only consumes memory once, the pointer to it in every node adds overhead compared to a custom, array-backed set implementation.

Q: If LinkedHashSet extends HashSet, what map does it use internally?
A: Instead of a HashMap, the constructor of LinkedHashSet initializes its internal map field as a LinkedHashMap. This gives it the exact same dummy-value wrapper logic, but leverages the doubly-linked list ordering of the LinkedHashMap.