---

🟢 Junior Level

30-Second Summary

If you mutate an object that is already stored as a key in a HashMap, that entry becomes permanently unlocatable (“Ghost / Zombie Entry”):

• Calling map.get(key) returns null.
• Calling map.containsKey(key) returns false.
• Calling map.remove(key) fails to delete the entry and returns null.

However, the entry remains physically pinned in JVM heap memory inside the internal Node<K, V>[] table array. The map’s size() does not decrease, the Garbage Collector cannot reclaim the objects, and the application suffers a silent Logical Memory Leak.

---

Real-World Analogy: Airport Luggage Lockers

Think of an automated baggage locker system:

• You store a blue suitcase. The automated system computes a locker number based on the color: “Blue $\to$ Locker #5” and locks it there.
• Overnight, someone repaints the suitcase red while inside the locker.
• In the morning, you ask the terminal for your “Red suitcase”. The system calculates: “Red $\to$ Locker #12”, opens locker #12, finds it completely empty, and reports: “Luggage Not Found”. Your suitcase remains trapped in locker #5 forever.

---

Code Example: Breaking HashMap with a Mutable Key

// ❌ DANGEROUS ANTI-PATTERN: Using a mutable ArrayList as a Map key
List<String> keyList = new ArrayList<>();
keyList.add("USER");

Map<List<String>, String> permissions = new HashMap<>();
permissions.put(keyList, "READ_ACCESS");

// Before mutation: Lookup succeeds
System.out.println(permissions.get(keyList)); // Prints "READ_ACCESS"

// 💥 CATASTROPHE: Mutate the key in place:
keyList.add("ADMIN");

// After mutation: The entry is lost!
System.out.println(permissions.get(keyList));         // ❌ Returns null!
System.out.println(permissions.containsKey(keyList)); // ❌ Returns false!
System.out.println(permissions.size());              // ⚠️ Returns 1 (Pinned in memory!)

---

🟡 Middle Level

The Dual Point of Failure in HashMap.getNode()

To understand why HashMap cannot locate the mutated key, examine the source code of HashMap.getNode() in OpenJDK:

final Node<K,V> getNode(Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = hash(key))]) != null) { // 1. Target Bucket Index
        
        // 2. Hash & Equality Verification:
        if (first.hash == hash && 
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        
        // Chained linked list / Red-Black tree traversal...
    }
    return null;
}

When a key’s fields are modified, lookup fails on two successive layers:

1. Level 1 Failure: Bucket Index Mismatch

• During put(key), hash $H_1$ was calculated, and the entry was stored in table[5].
• During get(key), the mutated fields produce a new hash $H_2$. The formula (n - 1) & hash routes lookup to table[12]. Slot #12 is empty, so getNode() immediately returns null in $O(1)$ time.

2. Level 2 Failure: Cached Node Hash Mismatch (Even on Hash Collisions)

Even if $H_2$ coincidentally resolves to the exact same bucket index (table[5]):

• The entry node Node<K, V> stores an immutable cached hash field: final int hash, computed during insertion ($H_1$).
• The lookup condition first.hash == hash evaluates $H_1 == H_2$, which returns false.
• Due to Java’s boolean short-circuit evaluation (&&), the JVM does not even evaluate first.key == key or key.equals(first.key)! The node is immediately rejected.

---

The HashSet Duplication Hazard

Because HashSet is backed internally by a HashMap<E, Object>, mutating a set element violates the mathematical set uniqueness contract:

Set<List<String>> set = new HashSet<>();
List<String> list = new ArrayList<>(List.of("A"));
set.add(list);

list.add("B"); // Mutate key element
set.add(list); // 💥 Successfully inserts the exact same instance a second time!

System.out.println(set.size()); // Prints 2 (Duplicate instances inside a Set!)

---

🔴 Senior Level

Memory Leak Mechanics & The resize() Trap

1. Logical Memory Leak (Zombie Entries):
   • The orphaned Node<K, V> maintains strong references to both the key and value instances.
   • The Garbage Collector cannot collect either object, even if all external application references are dropped.
2. What Happens During resize():
   • When entry counts exceed the capacity threshold, HashMap doubles the table capacity.
   • During rehashing, HashMap NEVER re-evaluates key.hashCode()! It reads the cached node.hash:

     if ((e.hash & oldCap) == 0) // Uses original cached hash!
     

   • The zombie node is migrated to a new bucket index based strictly on its old, original hash.
   • resize() cements the entry’s unlocatable status rather than correcting it.

---

Recovering or Removing the Orphaned Entry

Once a key has mutated, retrieval via standard key lookup is impossible. The only recovery mechanism is a linear $O(N)$ scan through entrySet():

// O(N) linear recovery via entrySet iterator:
for (Iterator<Map.Entry<List<String>, String>> it = map.entrySet().iterator(); it.hasNext(); ) {
    Map.Entry<List<String>, String> entry = it.next();
    if (entry.getKey() == keyList) { // Reference equality check!
        System.out.println("Recovered value: " + entry.getValue());
        it.remove(); // Safely purges the zombie node from the internal table array!
    }
}

---

3 Architectural Remedies

Pattern	Implementation	Production Suitability
Immutable Records	public record OrderKey(String tenant, UUID id) {}	🟢 Industry Standard (Prevents mutation entirely)
Remove $\to$ Mutate $\to$ Put	val = map.remove(k); k.modify(); map.put(k, val);	🟡 Legacy compatibility pattern
IdentityHashMap	Compares keys via == and System.identityHashCode(k)	🟢 Framework caches (Bypasses field-based hashing)

---

4 Tricky Questions

1. Can a value be extracted from a HashMap after its key was mutated without clearing the entire map with map.clear()?

Answer: Yes, but only in $O(N)$ time via an explicit linear scan of entrySet() or values(). Because map.get(key) calculates a new bucket index and misses the original node, direct lookup is broken. The application must iterate over map.entrySet() using an Iterator, checking for reference equality (entry.getKey() == mutatedKey). Once found, calling iterator.remove() safely deletes the orphaned node from memory.

---

2. What happens to a mutated key during a resize() operation in HashMap? Is key.hashCode() re-evaluated?

Answer: No! During table resizing, HashMap never re-invokes key.hashCode(). In the OpenJDK implementation of resize(), the method reuses e.hash (the integer calculated and cached in the Node structure during initial insertion):

if ((e.hash & oldCap) == 0) { ... }

The node is relocated to a new bucket index based purely on its old cached hash. As a result, resizing does not fix the bucket alignment; it permanently preserves the node in a bucket determined by the outdated hash code.

---

3. Why does the condition first.key == key fail to match in getNode() if the key’s new hash happens to target the exact same bucket?

Answer: In getNode(), the matching condition uses the short-circuiting logical AND (&&) operator:

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

The integer comparison first.hash == hash is evaluated first as a fast rejection filter. Because first.hash stores the original pre-mutation hash ($H_1$) and the local variable hash contains the new post-mutation hash ($H_2$), first.hash == hash returns false. Due to short-circuit evaluation, the second operand (first.key == key) is never evaluated by the CPU, and the node is discarded immediately.

---

4. What happens if you mutate an element stored inside a HashSet and subsequently call set.contains() or set.add() with that same element?

Answer:

• set.contains(element): Evaluates to false because lookup calculates the new hash code, searching an empty or unrelated bucket.
• set.add(element): Successfully inserts the identical object a second time! The method calculates the new hash, routes to the bucket corresponding to the new hash, finds no collision, and inserts a second entry. This violates the fundamental contract of the Set interface: the collection now contains two entries pointing to the exact same heap reference, and size() increments to 2.

---

🎯 Interview Cheat Sheet

Summary: What Happens When a Key Mutates

• get(key) / remove(key): Returns null (Searches the wrong bucket).
• Logical Memory Leak: Orphaned entry is retained in table[bucket] indefinitely (Zombie Entry).
• resize() Trap: Repositions nodes using the old cached hash, cementing the unlocatable status.
• HashSet Breakdown: Set uniqueness breaks down, permitting duplicate object entries.
• Data Recovery: Can only be found and purged via full $O(N)$ linear traversal over map.entrySet().

---

How to Prevent Key Mutation Hazards

1. Enforce Immutability: Use strictly immutable keys (String, UUID, Long, record).
2. Remove $\to$ Mutate $\to$ Put Pattern: Remove the key under its old hash before mutating, then re-insert under the new hash.
3. Use IdentityHashMap: When identity by memory address (==) is explicitly desired over logical equality.

---

Red Flags to Avoid

• ❌ “HashMap automatically shifts entries to new buckets when key fields change.” (False; HashMap has no listeners and cannot detect object mutations).
• ❌ “The Garbage Collector automatically frees orphaned keys in HashMap.” (False; strong references in the internal array prevent garbage collection).
• ❌ “If the new hash targets the same bucket, HashMap will match the key by reference k == first.key.” (False; first.hash == hash evaluates to false first, short-circuiting the check).

---

Related Topics

• Can You Use Immutable Objects as Keys in HashMap — Safe map keys
• What is Record and How Does It Help Create Immutable Classes — Immutable records
• What Are the Advantages of Immutable Objects for Caching — Caching stability
• What Happens If You Override Getter in Subclass of Immutable Class — Invariant corruption