Keys Must Not Change

Every map operation that takes a key (get, containsKey, remove, and the search inside put) finds the right entry by comparing the given key against the stored keys with equals. So far we have assumed that a stored key gives the same result under equals as it did when we put it in.

Suppose the key is a mutable object rather than a String. Say a Username whose equals compares its name field:

Username u = new Username("ann");
Map<Username, String> accounts = new LinkedMap<>();
accounts.put(u, "x7");          // store the password under "ann"

u.setName("bob");               // mutate the very object we used as the key

The map still holds one entry. The entry stores a reference to u, so changing u changes what equals reports for the stored key, without touching the map:

after put(u, "x7") — u and the entry's key reference the same object
u ────────────────────────────────┐
                                  ▼
          ┌──────────┐     ┌──────────────┐
head ───▶ │ key  ●───┼───▶ │ name = "ann" │
          │ value x7 │     └──────────────┘
          └──────────┘

after u.setName("bob") — the entry is untouched; only u's field changed
u ────────────────────────────────┐
                                  ▼
          ┌──────────┐     ┌──────────────┐
head ───▶ │ key  ●───┼───▶ │ name = "bob" │
          │ value x7 │     └──────────────┘
          └──────────┘

Now look up either name:

accounts.get(new Username("ann"));  // null — no stored key equals "ann" anymore
accounts.get(new Username("bob"));  // "x7" — found under the wrong name

Nothing was removed, and no exception is thrown. The map just gives wrong answers.

The rule is that a key must not change, after it is stored, in any way that affects how it compares. For our maps that means equals. A map that keeps its keys sorted also compares them with compareTo, and the hash-based maps of a later chapter also use hashCode.

The easiest way to guarantee that is to use immutable keys, objects that cannot change after they are created. This is why String and wrapper classes like Integer are the usual keys: they are immutable. A value has no such requirement. The map never searches by value, so you can change a value whenever you like, and put is built to replace one.

The same rule applies to a set. A set’s add, contains, and remove also find an element by equals. A set element is a key with no value attached.