How Java HashSet Works Under the Hood: Building a Set via Composition

Suppose you are building a newsletter email campaign platform.

Before sending out 2,000,000 promotional emails, your backend ingests subscriber lists from multiple marketing databases. Many users exist on multiple lists.

Sending duplicate emails to the same subscriber violates anti-spam regulations and doubles email provider billing costs. You need a data structure that guarantees every email address appears exactly once.

If you store email strings in an ArrayList and check list.contains(email) before every insert, deduplicating 2,000,000 emails takes hours because contains() runs in $O(N)$ linear time.

This problem demands a Set. A Set guarantees element uniqueness and checks membership in $O(1)$ constant time.

---

Why You Need This in Real Life

Instead of building hash distribution, collision chaining, and table expansion algorithms from scratch for sets, the JDK architects used object composition.

HashSet wraps an internal HashMap instance, reusing map key uniqueness guarantees.

---

Composition Over Inheritance

A set stores individual elements (E), whereas a map stores key-value pairs (K, V).

Because map keys must be unique, any element added to a set can serve as a key in an internal map.

MyHashSet<E> Object
  |
  +---> backingMap: MyHashMap<E, Object>
           |
           +---> Key: Element "[email protected]" ===> Value: PRESENT (dummy object)
           +---> Key: Element "[email protected]" ===> Value: PRESENT (dummy object)

The value associated with each key in the internal map is a single static dummy Object reference named PRESENT.

---

Static Dummy Object Memory Saver

Why do we use a single static final Object PRESENT reference instead of instantiating new Object() on every insert?

private static final Object PRESENT = new Object();

Creating a new dummy object on every add() call allocates 16 bytes of heap memory per element.

Using a single static reference reuses the exact same heap address pointer across all set entries, spending zero extra memory on dummy values.

---

Complete MyHashSet<E> Implementation

Here is our custom set implementation:

import java.util.Iterator;

public class MyHashSet<E> implements Iterable<E> {
    private final MyHashMap<E, Object> map;
    private static final Object PRESENT = new Object();

    public MyHashSet() {
        this.map = new MyHashMap<>();
    }

    public boolean add(E element) {
        // map.put returns null if key was NOT present previously
        return map.put(element, PRESENT) == null;
    }

    public boolean remove(E element) {
        // map.remove returns PRESENT if element was in the map
        return map.remove(element) == PRESENT;
    }

    public boolean contains(E element) {
        return map.containsKey(element);
    }

    public int size() {
        return map.size();
    }

    public boolean isEmpty() {
        return map.size() == 0;
    }

    @Override
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }
}

---

Unordered Element Storage Trap

Because HashSet delegates to HashMap, element order depends entirely on hash bucket index assignments.

MyHashSet<String> set = new MyHashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Cherry");

Iterating over set does not guarantee elements return in insertion order.

If bucket indices calculate to Cherry (index 2), Apple (index 5), Banana (index 11), iteration yields: Cherry, Apple, Banana.

If your application requires both uniqueness AND predictable iteration order, use LinkedHashSet.

---

Quick Summary

• HashSet wraps HashMap via composition instead of duplicating code.
• Set elements store as map keys; map values point to a shared static PRESENT dummy reference.
• HashSet inherits $O(1)$ add, remove, and lookup performance from HashMap.

References & Further Reading

1. OpenJDK Repository. OpenJDK 21 Source Code: java.util.HashSet & java.util.TreeSet. GitHub.
2. Bloch, J. (2018). Effective Java (3rd Edition) — Item 18: Favor Composition Over Inheritance. Addison-Wesley.
3. Oracle Corporation. Java SE 21 API Documentation: java.util.Set Interface. Oracle Docs.

---