How HashSet, LinkedHashSet and TreeSet work

For this lesson, we'll focus on how the three main set implementations work in Java 21, why their equality rules differ, and which one I would choose in common interview scenarios: unique product names, sign-up order for unique user IDs, sorted unique student IDs, and enum roles. Interviewers ask this because sets look small from the API, but they reveal whether you understand maps, equality, ordering and mutation.

01Picture it first: three guest lists

Think of sets as three guest lists at an event. HashSet is the bouncer's stamp book: it answers "have I seen this person?" without caring about the line order. LinkedHashSet is the same stamp book plus a clipboard that records the first arrival order. TreeSet is a sorted register that keeps names in alphabetical or numeric order as people arrive.

The first picture shows the key trick behind HashSet: it is a map wearing a set-shaped jacket.

Fig. 1

A HashSet stores each element as a key in an internal HashMap, and every key points to the same dummy PRESENT value

Now compare iteration order. Add the same five numbers to each set and ask what a for loop sees.

Fig. 2

HashSet, LinkedHashSet and TreeSet receive the same inserted values, then iterate in unspecified hash order, insertion order and sorted order

Notice three things:

• HashSet optimizes membership, not human-readable order.
• LinkedHashSet gives deterministic insertion order without sorting.
• TreeSet gives sorted order and range queries, but pays O(log n) per update.

02HashSet under the hood

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

public class UniqueProductNames {
    public static void main(String[] args) {
        Set<String> names = new HashSet<>();

        System.out.println(names.add("keyboard"));
        System.out.println(names.add("mouse"));
        System.out.println(names.add("keyboard"));
        System.out.println(names);
    }
}

The first two calls print true; the third prints false. The set already contains an equal key, so the structure is unchanged. The final order is deliberately not promised, so do not write a test that expects [keyboard, mouse].

OpenJDK's HashSet has this shape:

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

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

That line is the whole idea. A HashMap already knows how to store unique keys, spread hashes, handle collisions, resize and treeify crowded bins. HashSet reuses all of that and ignores the map value.

Notice the interaction:

• contains(e) delegates to map.containsKey(e).
• remove(e) removes the map key and returns whether the dummy value was present.
• The element's hashCode() picks the bucket, then equals() confirms the match inside the bucket.
• Expected add, remove and contains are O(1); under severe collisions, Java 8+ tree bins can make a crowded bucket O(log n) once the table is large enough.

This is why the usual product-name question is a HashSet question. If the requirement is "store unique product names and test membership", HashSet<String> is the default. If the requirement also says "print them in the order first seen", use LinkedHashSet<String> instead.

The equals and hashCode contract

Hash-based sets depend on one contract: equal objects must have equal hash codes. Unequal objects may collide, but equal objects cannot be sent to different buckets. If equals() says two users are the same email but hashCode() uses a database id, your set will behave like it is haunted.

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

final class ProductId {
    private final String value;

    ProductId(String value) {
        this.value = value;
    }

    @Override public boolean equals(Object other) {
        return other instanceof ProductId id && Objects.equals(value, id.value);
    }

    @Override public int hashCode() {
        return Objects.hash(value);
    }
}

public class ProductIdSet {
    public static void main(String[] args) {
        Set<ProductId> seen = new HashSet<>();
        seen.add(new ProductId("SKU-7"));
        System.out.println(seen.contains(new ProductId("SKU-7"))); // true
    }
}

Records are often the cleanest way to make set elements because they generate consistent equals() and hashCode() from final components. We cover the contract more deeply in The equals() and hashCode() contracts.

The mutable-key bug