Returning the Stored Entries

Suppose we want to print each username together with its password:

for (String user : accounts) {
  String pw = accounts.get(user);
  System.out.println(user + " -> " + pw);
}

This is $O(n^2)$: each get is an $O(n)$ search, and the loop calls it once per key.

The traversal already passes through every entry, and each entry holds its value next to its key. So we add the separate method for the pairs that we put off when we made the keys the default, entries(), and get each value without a second search.

public interface Map<K, V> extends Iterable<K> {
  // ... put, get, remove, containsKey, size as before ...
  Iterable<...> entries();  // a separate traversal, over the key–value pairs
}

At each step, the traversal has to hand back an object that holds one key and its value. Where do those objects come from? We could build a fresh object on every step, but we do not have to: each map already stores its pairs as objects.

ArrayMap keeps an Entry in every filled slot of its backing array:

// inside ArrayMap
private static class Entry<K, V> {
  K key;
  V value;
  // ...
}

And LinkedMap keeps a Node per pair:

// inside LinkedMap
private static class Node<K, V> {
  K key;
  V value;
  Node<K, V> next;
  // ...
}

The cheapest traversal returns those stored objects. The iterator already visits each one, so returning it allocates nothing: $O(1)$ auxiliary space, the same as the key traversal.

To return them, entries() needs a return type that callers can name. Entry and Node are private nested classes, so callers cannot name them. We would have to make the class public, and its fields public, so the caller can read the key and value:

public static class Entry<K, V> {  // promoted from private to public
  public K key;
  public V value;
  // ...
}

Then ArrayMap could return Iterable<Entry<K, V>>, and the caller could read e.key and e.value, in one traversal.

But making the storage class public causes two problems.

The first is that the two maps store different classes: ArrayMap.Entry and LinkedMap.Node. A caller writing against the Map interface, not knowing which implementation they hold, could not name one type that works for both.