In Java, hash-based collections (like HashMap and HashSet) rely on the hash code of an object to locate its bucket. If an object is inserted as a key, and then one of its fields used in hashCode() calculation is mutated, the object's hash code changes. This leaves the object "trapped" in its old bucket, making it impossible to find or remove.

In this guide, we will walk through a code trace where mutating a key field breaks set containment and prevents object removal.

Illustration representing bucket hash lookup failures due to key mutations
Real-World Analogy: The Relocated Mailbox

Imagine a school mail sorter room:

  • You receive a letter labeled for **Mailbox 2**. The sorter places it in slot 2.
  • While no one is looking, a student changes the label on the envelope to read **Mailbox 1** (mutating a field).
  • Later, you want to retrieve the envelope. The sorter checks the label, sees it says Mailbox 1, and goes to **Slot 1** to look for it.
  • Because Slot 1 is empty, the sorter returns and says: "Sorry, your letter doesn't exist!" even though it is still sitting inside Slot 2. It is lost forever.

1. The Mutability Code Scenario

Let's look at this implementation using a helper class KeyMaster:

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

class KeyMaster {
    public int i;

    public KeyMaster(int i) {
        this.i = i;
    }

    public boolean equals(Object o) {
        return i == ((KeyMaster) o).i;
    }

    public int hashCode() {
        return i; // Hash code depends directly on mutable field 'i'
    }
}

2. Tracing the Execution

Now let's trace the main method operations step by step:

public static void main(String[] args) {
    Set<KeyMaster> set = new HashSet<>();
    KeyMaster k1 = new KeyMaster(1);
    KeyMaster k2 = new KeyMaster(2);

    set.add(k1);
    set.add(k1); // Duplicate addition is ignored
    set.add(k2);
    set.add(k2); // Duplicate addition is ignored

    System.out.print(set.size() + ":"); // PRINTS: 2:
    
    // TRAP: Mutate k2's comparison field!
    k2.i = 1; 
    
    System.out.print(set.size() + ":"); // PRINTS: 2: (Set size is unchanged)
    
    set.remove(k1);
    System.out.print(set.size() + ":"); // PRINTS: 1: (k1 is successfully removed)
    
    set.remove(k2);
    System.out.print(set.size());       // PRINTS: 1 (k2 CANNOT be found or removed!)
}
Why did set.remove(k2) fail?

When k2 was added, it had i = 2, so its hash code was 2. HashSet stored it inside bucket index 2. When we did k2.i = 1;, its hash code became 1. When we called set.remove(k2), HashSet evaluated its current hash code (1) and checked bucket index 1. Because bucket index 1 was empty (we already removed `k1`), the HashSet concluded k2 wasn't in the collection and did nothing. `k2` remains stuck in bucket index 2!

Conclusion

To avoid this collection trap:

  • Always design your Map keys and Set elements to be **immutable** (use final fields).
  • If you must modify properties of an element inside a Set or Map, remove the object first, mutate the field, and re-add it.