---

🟢 Junior Level

1. Architectural Essence

The HashSet class (java.util.HashSet) does not implement its own low-level data structure for storing elements. Instead, it is an elegant, lightweight adapter wrapper built directly around HashMap:

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    private transient HashMap<E, Object> map;
    
    // Shared dummy sentinel object representing the value for every key:
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }
}

All elements added to a HashSet are stored as the keys of the underlying HashMap. Because HashMap guarantees key uniqueness, HashSet inherently inherits the property of element uniqueness.

For the value slot associated with each key, HashSet uses a single, shared static dummy sentinel object: PRESENT (new Object()).

HashSet: ["Apple", "Banana", "Cherry"]
  │
  ▼
HashMap (Internal Representation):
  ┌──────────┬─────────────────┐
  │   Key    │      Value      │
  ├──────────┼─────────────────┤
  │ "Apple"  │ ──► PRESENT     │
  │ "Banana" │ ──► PRESENT     │
  │ "Cherry" │ ──► PRESENT     │
  └──────────┴─────────────────┘

---

2. Core Operations & Delegation

All public methods in HashSet simply delegate their execution to the underlying HashMap instance:

// Adding an element:
// put() returns null if the key was newly inserted, or the previous value (PRESENT) if it already existed.
public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

// Checking element presence:
public boolean contains(Object o) {
    return map.containsKey(o);
}

// Removing an element:
// remove() returns the previous value (PRESENT) if found, or null if the key was absent.
public boolean remove(Object o) {
    return map.remove(o) == PRESENT;
}

// Size and clearing:
public int size() {
    return map.size();
}

public void clear() {
    map.clear();
}

Time Complexity of Core Operations

Operation	Average Case	Worst Case (Pathological Collisions)	Notes
add(E e)	$O(1)$	$O(\log N)$ / $O(N)$	$O(\log N)$ via Red-Black Tree treeification in Java 8+
contains(Object o)	$O(1)$	$O(\log N)$ / $O(N)$	Governed by uniform distribution of hashCode()
remove(Object o)	$O(1)$	$O(\log N)$ / $O(N)$	Fast hash lookup followed by node unlinking
Iteration	$O(\text{capacity} + N)$	$O(\text{capacity} + N)$	Must inspect every bucket slot in table[], including nulls

---

🟡 Middle Level

1. Bucket Index Calculation & Collision Handling

When set.add(e) is called, the underlying HashMap performs the following steps:

1. Perturbation Function (Bit Spreading):

   static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }
   

   Shifting 16 bits to the right and XORing blends the high-order bits of the hash code into the lower bits. This prevents excessive collisions when the table capacity is small (e.g., 16) and keys differ only in their upper bits.

2. Bucket Index Resolution:

   index = (table.length - 1) & hash;
   

   Because the table capacity is always enforced as a power of two ($2^k$), the expensive modulo division % is replaced by a single-cycle bitwise AND (&).

3. Collision Search & Equality Evaluation: When locating an entry inside a populated bucket, HashMap applies a fast multi-tiered equality check:

   if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
   

   • First, it compares primitive 32-bit hash integers (1 CPU cycle).
   • If hashes match, it performs reference equality p.key == key (avoiding method invocation).
   • Only if reference equality fails does it dispatch the virtual method .equals().

---

2. Collision Treeification in Java 8+

Prior to Java 8, collisions within a bucket were stored strictly as a singly-linked list (Node<K,V>). Under hash collision attacks (Hash DoS) or poor hashCode() implementations, lookups degraded to $O(N)$.

Java 8 introduced dynamic Treeification:

• Conversion Threshold: If collisions in a single bucket reach $\ge 8$ elements (TREEIFY_THRESHOLD = 8) AND the total array capacity is $\ge 64$ (MIN_TREEIFY_CAPACITY = 64), the bucket list transforms into a balanced Red-Black Tree (TreeNode<K,V>).
• Capacity Priority: If a bucket reaches 8 collisions but total table capacity is $< 64$, the table is resized (resize()), doubling capacity rather than converting to a tree.
• Complexity Bound: Treeification guarantees that worst-case search, insertion, and deletion complexity is bounded at $O(\log N)$.
• Untreeification: If deletions or table resizing reduce the number of nodes in a tree bucket to $\le 6$ (UNTREEIFY_THRESHOLD = 6), the tree converts back into a singly-linked list to reduce pointer and memory overhead.

Bucket Collision Lifecycle:
[0..7 elements]: Node -> Node -> Node (Singly-Linked List, O(N))
[>= 8 elements + capacity >= 64]: TreeNode (Red-Black Tree, O(log N))
[<= 6 elements after deletion/resize]: Converts back to Singly-Linked List (O(N))

---

3. The Mutable Element “Lost Object” Hazard

Because HashSet uses elements as keys in a hash table, elements must be immutable, or at least their fields participating in hashCode() and equals() must never change while stored in the set:

class User {
    private String name;
    public User(String name) { this.name = name; }
    public void setName(String name) { this.name = name; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User u)) return false;
        return Objects.equals(name, u.name);
    }

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

Set<User> users = new HashSet<>();
User ivan = new User("Ivan");
users.add(ivan);

// Mutate hash-dependent field while resident in the Set:
ivan.setName("Peter");

// CATASTROPHIC STATE:
System.out.println(users.contains(ivan)); // false!
System.out.println(users.remove(ivan));   // false! (Cannot remove!)
System.out.println(users.size());         // 1 (Zombie object stuck in heap!)

Under the Hood:

1. Upon insertion, ivan was placed into bucket index $B_1$ calculated from hash("Ivan").
2. After mutating the name to "Peter", hashCode() changes.
3. Invoking contains(ivan) computes bucket index $B_2$ from hash("Peter"). Bucket $B_2$ is empty or contains other keys, returning false.
4. The object remains orphaned in bucket $B_1$, producing a silent memory leak.

---

🔴 Senior Level

1. Memory Footprint & GC Allocation Analysis

HashSet incurs significant memory overhead due to the object layout of HashMap.Node:

On a 64-bit JVM with Compressed OOPs (-XX:+UseCompressedOops, active by default for heaps $< 32\text{ GB}$):

• Node Object Header: 12 bytes (8-byte Mark Word + 4-byte compressed Klass pointer).
• Node Fields:
  • int hash: 4 bytes.
  • K key reference: 4 bytes.
  • V value reference (PRESENT): 4 bytes.
  • Node<K,V> next reference: 4 bytes.
• 8-Byte Alignment Padding: 4 bytes.
• Total Node Instance Size: 32 bytes.
• Bucket Array Slot (table[i]): 4 bytes per reference. With a load factor of 0.75, this accounts for $\approx 5.33\text{ bytes}$ per element.

Total structural overhead per HashSet element:
  ~32 bytes (HashMap.Node) + ~5.33 bytes (table array slot) = ~37.33 bytes.
The payload element (e.g., java.lang.Long) requires an additional 24 bytes (16-byte header + 8-byte value).

Comparison: Storing 10,000,000 long Values

• HashSet<Long>: Requires $\approx 610\text{ MB}$ of heap and creates 20,000,000 discrete objects (10 million Long instances + 10 million HashMap.Node instances), imposing massive garbage collection pause overhead.
• Primitive Open-Addressing Set (fastutil LongOpenHashSet): Stores keys in a contiguous, flat long[] array without nodes or wrapper objects. Requires $\approx 80\text{ MB}$ ($\approx 7.5\times$ less memory) and creates 0 GC-tracked objects.

---

2. Custom Serialization Architecture: Why map is transient

In HashSet, the internal map field is explicitly declared with the transient modifier:

private transient HashMap<E, Object> map;

The Architectural Problem: Hash tables rely heavily on hash distribution and internal memory addresses (such as System.identityHashCode). Different JVM versions, architectures (x86 vs. ARM64), or patch levels may evaluate hash codes or table layouts differently. If the raw Node[] table array were serialized, deserializing it on another JVM could cause elements to land in invalid buckets, corrupting lookup semantics.

The Solution: Streamlined Serialization Protocols: HashSet implements custom writeObject and readObject routines:

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
    s.defaultWriteObject();
    s.writeInt(map.capacity());
    s.writeFloat(map.loadFactor());
    s.writeInt(map.size());

    // Serialize ONLY the raw element payloads, skipping nodes and bucket layouts!
    for (E e : map.keySet())
        s.writeObject(e);
}

private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();
    int capacity = s.readInt();
    float loadFactor = s.readFloat();
    map = new HashMap<>(capacity, loadFactor);

    int size = s.readInt();
    // Reinsert each element via map.put(), reconstructing the table cleanly:
    for (int i = 0; i < size; i++) {
        @SuppressWarnings("unchecked")
        E e = (E) s.readObject();
        map.put(e, PRESENT);
    }
}

---

3. The Hidden Package-Private Constructor for LinkedHashSet

Inside OpenJDK’s HashSet source code exists an obscure package-private constructor:

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

The dummy boolean argument exists solely to differentiate this constructor’s signature from the public HashSet(int, float) constructor. This design allows LinkedHashSet to simply inherit the entire HashSet codebase without duplicating code, merely passing true to this hidden constructor to substitute the internal HashMap backing instance with a LinkedHashMap.

---

4 Tricky Questions

1. Why does HashSet not provide a get(Object o) method?

Answer: By mathematical definition, a set is a collection representing membership (contains(o)), not key-value associations. If an application already possesses an instance equal to the desired object (o.equals(target)), calling get() would redundantly return an object that the caller already holds. If the use case requires key-to-instance canonicalization (such as object interning or cache mapping where two equal objects hold distinct metadata), a Map<K, V> or ConcurrentMap.putIfAbsent() must be used instead.

---

2. What happens if an element’s class does not implement Comparable, but more than 8 collisions occur in a single bucket?

Answer: If the bucket size reaches 8 and capacity is $\ge 64$, HashMap converts the bucket into a Red-Black Tree (TreeNode). During tree operations, HashMap attempts to order nodes using Comparable.compareTo(). If the keys do not implement Comparable (or if their classes differ), HashMap falls back to its internal tieBreakOrder(Object a, Object b) method:

1. It compares their class names via a.getClass().getName().compareTo(b.getClass().getName()).
2. If class names are identical, it compares their JVM identity hash codes via System.identityHashCode(a). The Red-Black Tree is successfully constructed and remains balanced, though key comparisons incur a minor performance penalty compared to native Comparable instances.

---

3. Why can allocating new HashSet<>(1_000_000) without adding elements severely degrade application performance?

Answer: Allocating new HashSet<>(1_000_000) allocates an underlying Node<K,V>[] array of size $2^{20} = 1\,048\,576$ slots ($\approx 4\text{ MB}$ of memory references). The critical hazard occurs during iteration:

• A HashSet iterator has a time complexity of $O(\text{capacity} + \text{size})$.
• To iterate over a set containing 0 (or only a handful) of elements, the iterator must linearly inspect all 1,048,576 slots in the table looking for non-null heads.
• This creates millions of CPU cache misses, stalling the processor pipeline and wasting tens of milliseconds of CPU time.

---

4. How does HashSet achieve thread safety in concurrent environments?

Answer: HashSet is completely unsynchronized and not thread-safe. Concurrent modifications can cause lost updates, corrupted linked node chains, or stale reads. To use a hash-based set safely in concurrent architectures:

• ConcurrentHashMap.newKeySet(): The modern, high-performance recommendation. Backed by ConcurrentHashMap, it uses lock-free CAS operations and synchronized bucket heads for fine-grained striping without coarse table locks.
• Collections.synchronizedSet(new HashSet<>()): A legacy wrapper that synchronizes every single operation on a shared mutex (mutex), causing severe lock contention under high concurrency.
• CopyOnWriteArraySet: Appropriate strictly for read-heavy, write-rare workloads (e.g., event listener registries).

---

🎯 Interview Cheat Sheet

30-Second Elevator Pitch

“HashSet is an adapter wrapper around HashMap, where elements serve as keys and a static singleton PRESENT = new Object() acts as the dummy value. It provides average $O(1)$ complexity for add, remove, and contains. In Java 8+, if collisions in a single bucket reach $\ge 8$ and total capacity is $\ge 64$, the bucket transforms from a singly-linked list to a Red-Black Tree, bounding worst-case lookup time to $O(\log N)$. To prevent severe cache misses and memory waste, elements in a HashSet must be strictly immutable, and large capacity allocations should be avoided if element counts are small.”

High-Impact Architectural Facts

• Memory Footprint: Each HashSet element costs $\approx 37\text{ bytes}$ of structural overhead ($\approx 32\text{ bytes}$ for HashMap.Node + $\approx 5.33\text{ bytes}$ bucket slot), making primitive wrapper sets (HashSet<Long>) $7-8\times$ heavier than open-addressing primitive sets.
• Equality Evaluation Pipeline: p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))). Primitive hash equality is evaluated first, then reference equality ==, and .equals() only as a final fallback.
• Serialization Strategy: The map field is transient. HashSet serializes only capacity, load factor, size, and raw element references, rebuilding bucket distributions cleanly during deserialization.
• Subclass Reuse: LinkedHashSet is constructed via a hidden package-private constructor HashSet(int, float, boolean dummy) that initializes an internal LinkedHashMap.

Common Pitfalls & Red Flags

• ❌ Mutating an element after insertion: Mutating fields involved in hashCode() changes the target bucket, causing contains() to fail and stranding the object as an uncollectible memory leak.
• ❌ Assuming HashSet preserves insertion order: Order is non-deterministic and shifts across resizes; only LinkedHashSet preserves insertion order.
• ❌ Using HashSet<Long> for high-volume primitive storage: Creates millions of GC-tracked objects and bloated memory; use specialized primitive collections like fastutil’s LongOpenHashSet.
• ❌ Believing HashSet is thread-safe: Requires ConcurrentHashMap.newKeySet() in multi-threaded environments.

---

Related Topics

• What is the difference between HashSet, LinkedHashSet and TreeSet — Comprehensive Set taxonomy
• What is TreeSet and how does it work — Red-Black tree mechanics
• What is Map and what implementations exist — Core map architecture
• What is the difference between HashMap, LinkedHashMap and TreeMap — Map hierarchy deep dive
• How does ConcurrentHashMap ensure thread-safety — Lock-free CAS and bucket synchronization