How Does HashSet Use HashMap Under the Hood?

A HashSet does not have its own storage. Internally it holds a HashMap whose keys are the elements you add and whose values are a single shared dummy object. That is the whole trick, and it explains most of the behaviour people find surprising about sets.

Because the elements are the map's keys, membership is decided by equals and hashCode. Adding an element you have already added does not create a second entry, because the map's put finds an existing key that is equal to it. That is why the add method returns a boolean: true if the element was new, false if it was already there. No set implementation could offer that API without the same trick.

It also explains the ordering guarantees. A plain HashSet inherits the HashMap's lack of ordering, so iteration order depends on the hash codes. A LinkedHashSet wraps a LinkedHashMap, which keeps the buckets in insertion order. And a TreeSet is a different animal entirely — it uses a TreeMap, so it keeps its elements sorted rather than hashed, and it is the only one of the three whose membership test is O(log n) rather than O(1).

Two more consequences follow from the design. A HashSet permits exactly one null element, because a HashMap permits exactly one null key. And because the dummy value is shared, iterating a HashSet gives you the keys, not the values — there is no value to give you.

Every operation is delegated to the backing HashMap. add calls put with the element as the key and the shared dummy as the value; if the key was already present, the map replaces the value and put returns the old dummy, which the set translates into false. remove returns whether an element was actually present. contains is a plain map lookup and is therefore O(1) on average.

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        System.out.println("add new   : " + set.add("apple"));
        System.out.println("add again : " + set.add("apple"));
        set.add("banana");

        System.out.println("size      : " + set.size());
        System.out.println("contains  : " + set.contains("apple"));
        System.out.println("remove    : " + set.remove("apple"));
        System.out.println("remove 2nd: " + set.remove("apple"));
        System.out.println("after     : " + set);

        // A set of objects uses their equals and hashCode.
        Set<Point> points = new HashSet<>();
        points.add(new Point(1, 2));
        points.add(new Point(1, 2));
        System.out.println("points    : " + points.size());
    }
}

class Point {
    final int x, y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        return o instanceof Point && ((Point) o).x == x && ((Point) o).y == y;
    }

    @Override
    public int hashCode() {
        return java.util.Objects.hash(x, y);
    }

    @Override
    public String toString() {
        return "(" + x + "," + y + ")";
    }
}

The output shows the semantics precisely. Adding a new element returns true; adding the same element again returns false and the size stays at one. Removing an element that is present returns true, and removing it again returns false. And the two Point objects, which are equal by value, collapse into a single entry because Point overrides equals and hashCode consistently.

The last case is the one that catches people. If you put objects into a set without overriding equals and hashCode, the set uses identity, so two points with the same coordinates count as two elements and the set's uniqueness guarantee is useless to you. That is a bug in your class, not in the set.

A HashSet is backed by a HashMap, and a HashMap allows one null key and any number of null values. A HashSet stores its elements as keys, so it inherits exactly that: one null element is permitted. Set semantics make sense for it, because null is just another value and the set's job is to say whether that value is present.

ConcurrentHashMap rejects null keys and null values, and therefore a concurrent set built on it rejects null elements too. The reason is concurrency-specific. The classic implementation of putIfAbsent or get-then-put uses a null return to mean "not found". Under concurrency, a null return is ambiguous: it could mean the key genuinely is absent, or it could mean the value was concurrently set to null and then removed. There is no way to distinguish those without a lock over the whole operation, which is exactly the cost the concurrent map exists to avoid.

The second question — what breaks if you put null in a HashMap key position — is about a different thing. A null key works, but it is a special case that the map has to handle on every operation: a null key cannot be hashed, so it is parked in a dedicated slot. The performance impact is small, but the design guidance is that null keys are a smell, and most well-designed classes reject them explicitly.

The practical advice for interviews: prefer a sentinel value or Optional over null in domain code, choose the collection implementation based on whether you need concurrency, and do not mix the two worlds — a HashSet that permits null and a concurrent one that does not is a difference worth knowing when you swap an implementation out.