The Map.Entry Interface

One interface fixes both problems, the writable fields and the two different storage classes. It describes only what a caller may do with a pair: read its key and its value.

interface Entry<K, V> {
  K key();
  V value();
}

A type whose only operations are key() and value() cannot be used to overwrite a key, replace a value, or change a next link.

Where the interface is declared

A pair only makes sense as part of a map, so we declare this interface inside Map, the same way each storage class is nested inside its map. A type nested in an interface is automatically public and static.

Nesting it there gives the interface the name Map.Entry<K, V>. Java names its own java.util.Map.Entry the same way.

public interface Map<K, V> extends Iterable<K> {
  // ... put, get, remove, containsKey, size as before ...

  Iterable<Map.Entry<K, V>> entries();

  interface Entry<K, V> {
    K key();
    V value();
  }
}

Using Map.Entry in a loop

A caller uses it like this:

for (Map.Entry<String, String> e : accounts.entries()) {
  System.out.println(e.key() + " -> " + e.value());
}

Map.Entry stops the caller from replacing the stored key, but it does not make the key object immutable. If the key is a mutable object, like the Username from earlier, the caller can still change it through e.key(). The entry then stays in the map, but lookups compare keys with equals, so it is no longer found under its old key. That is why keys must still not change, and why immutable keys like String are the usual choice.

The same loop works whether accounts is an ArrayMap or a LinkedMap, because both hand back a Map.Entry.