HashSet in Java: How It Works and When to Use It

Ask a candidate "how does HashSet work internally?" and most will say "it uses hashing". That answer scores zero. The answer that scores is: "it wraps a HashMap, elements become keys, and the whole equals/hashCode machinery of HashMap does the duplicate detection." This page takes you from the first answer to the second, with code you can run to prove each claim.

HashSet is the default implementation of the Set interface — read that page first if you want the HashSet vs LinkedHashSet vs TreeSet decision framework.

The secret: HashSet is a HashMap in disguise

Open the JDK source for HashSet and the core of it fits on a slide:

public class HashSet<E> extends AbstractSet<E> implements Set<E> {
    private transient HashMap<E, Object> map;

    // Dummy value shared by every entry in the backing map
    private static final Object PRESENT = new Object();

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

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }
}

Every element you add becomes a key in the internal map, and the value is always the same shared PRESENT object. map.put returns the previous value for that key — null means the key was new, so add returns true; non-null means it already existed, so add returns false and the set is unchanged. Duplicate rejection is not extra logic in HashSet at all; it is HashMap's key-uniqueness doing the work.

This means everything you learn about how HashMap works internally — buckets, hashing, collisions, resizing, treeification — applies to HashSet verbatim.

What happens on add(): buckets, hashing, collisions

When you call set.add("Java"), the backing map does four things:

1. Calls "Java".hashCode() and spreads the bits (XOR of high and low 16 bits) to reduce collisions.
2. Maps that hash to a bucket index: (capacity - 1) & hash. Capacity is always a power of two, so this is a fast bitwise AND, not a modulo.
3. If the bucket is empty, stores a new entry there. Done — O(1).
4. If the bucket has entries (a collision), walks them comparing hashes and calling equals. A match means duplicate → rejected. No match → append to the bucket.

Since Java 8, a bucket that accumulates 8+ colliding entries (with table size ≥ 64) converts its linked list into a red-black tree, turning worst-case O(n) lookups in that bucket into O(log n).

Time complexity you can quote

The average case assumes a reasonable hashCode that distributes elements across buckets. The whole point of using HashSet is that membership checking costs O(1) instead of the O(n) scan an ArrayList needs. Here is that difference made concrete:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ContainsShowdown {
    public static void main(String[] args) {
        int n = 200_000;
        List<Integer> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) { list.add(i); set.add(i); }

        long t1 = System.nanoTime();
        int hits = 0;
        for (int i = 0; i < 10_000; i++) {
            if (list.contains(n - 1 - i)) hits++;   // O(n) each
        }
        long listMs = (System.nanoTime() - t1) / 1_000_000;

        long t2 = System.nanoTime();
        for (int i = 0; i < 10_000; i++) {
            if (set.contains(n - 1 - i)) hits++;    // O(1) each
        }
        long setMs = (System.nanoTime() - t2) / 1_000_000;

        System.out.println("ArrayList.contains x10k: " + listMs + " ms");
        System.out.println("HashSet.contains   x10k: " + setMs + " ms (hits=" + hits + ")");
    }
}

On a typical laptop the list side takes seconds-scale time while the set side finishes in single-digit milliseconds — 10,000 linear scans versus 10,000 hash lookups. Whenever you write list.contains(...) inside a loop, that is a signal to switch to a HashSet.

Pro tip: Deduplicating a list is a one-liner that exploits this: new ArrayList<>(new LinkedHashSet<>(list)) removes duplicates in O(n) while keeping the original order. Using new HashSet<>(list) is fine when order does not matter.

The equals/hashCode contract — where HashSet breaks

HashSet's correctness rests on one rule: objects that are equal must have equal hash codes. Violate it and the set malfunctions silently:

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

class Voucher {
    final String code;
    Voucher(String code) { this.code = code; }

    @Override public boolean equals(Object o) {
        return o instanceof Voucher v && code.equals(v.code);
    }
    // BUG: hashCode() not overridden — falls back to identity hash
}

public class BrokenSet {
    public static void main(String[] args) {
        Set<Voucher> used = new HashSet<>();
        used.add(new Voucher("WELCOME50"));

        // Same logical voucher, different object:
        System.out.println(used.contains(new Voucher("WELCOME50"))); // false!
        used.add(new Voucher("WELCOME50"));
        System.out.println(used.size());  // 2 — duplicate accepted
    }
}

The two Voucher objects are equals-equal, but default hashCode gives them different values, so they hash to different buckets and never meet for the equals comparison. Fix: @Override public int hashCode() { return code.hashCode(); } — or use a record, which generates both methods correctly for free.

Common mistake: A common mistake beginners make is mutating an object after adding it to a HashSet, when the mutated field participates in hashCode. The element is now filed in the wrong bucket: contains returns false and remove fails, yet iteration still shows the object. Prefer immutable fields for anything used in hashing.

Capacity, load factor and resizing

HashSet inherits HashMap's sizing model: a default initial capacity of 16 buckets and a default load factor of 0.75. When size > capacity × 0.75, the table doubles and every element is rehashed into the new table — an O(n) operation.

Practical consequences:

• Bulk-loading a known number of elements? Pre-size it: new HashSet<>((int) (expected / 0.75f) + 1) avoids every intermediate rehash.
• Iteration cost scales with capacity, not just size — a set that once held a million elements but now holds ten still iterates over the full-size bucket table.
• Resizing is also why iteration order can change over the life of a HashSet.

Nulls, ordering and thread safety

Three quick facts that decide edge cases:

• One null allowed. null hashes to bucket 0. TreeSet, by contrast, throws on null.
• No ordering guarantee. Iteration order depends on hash values and capacity. Need order? LinkedHashSet (insertion) or TreeSet (sorted) — the comparison table is on the Set interface page linked above.
• Not thread-safe. Concurrent writers can corrupt the table. Use ConcurrentHashMap.newKeySet() for a concurrent set, or Collections.synchronizedSet(...) with manual synchronization during iteration.

Interview note: "Why does HashSet not have a get() method?" is a favorite curveball. The answer: a set only answers membership — you already have the element you are asking about, so there is nothing to retrieve. If you need to look up an object by a key, that is a HashMap use case, not a Set use case.

When to use HashSet — and when not to

Reach for HashSet when:

• Uniqueness is a rule of the domain: user IDs, voucher codes, visited URLs.
• You do frequent contains checks — O(1) beats every list.
• You need fast union/intersection/difference via addAll/retainAll/removeAll.

Avoid it when:

• Order matters (LinkedHashSet/TreeSet) or you need index access (ArrayList).
• Elements are mutable in their hash-relevant fields.
• You need range queries like "all values between 50 and 70" — TreeSet's O(log n) navigation wins there.

HashSet questions — internal working, the equals/hashCode contract, HashSet vs HashMap — appear in nearly every Java collections interview. If you can explain the PRESENT dummy-value trick and the broken-voucher example above from memory, you are ahead of most candidates. To build that fluency across the whole framework with structured practice, see our Java Full Stack course.