Iterating a Map

In the iterator chapter we made a set work in an enhanced for loop. We want to write for (... : map) and visit its contents one at a time, for example to print every registered username. But a map entry is two things, a key and a value, so before we can iterate a map we have to decide what the loop variable holds.

There are three options. The loop variable could be a key, a value, or a pair, a key and its value together. I will make the keys the default. A map’s keys are what we most often need to iterate over. A value is not a good default, because the map cannot look anything up from a value. A pair would work, but iterating the pairs needs a type for a pair that a caller can use, and we do not have one yet. Designing that type takes some work, so I want to do it on its own. Once we have it, we will add a separate method for the pairs. A type can be Iterable over only one element type, so any traversal other than the default needs its own method.

To make the keys the default, we have the Map interface extend Iterable<K>:

public interface Map<K, V> extends Iterable<K> {
  // Same methods as before
}

Now every class implementing Map must supply an iterator() that returns an Iterator<K>.

Each key iterator is the set’s iterator from the iterator chapter with one change: it returns the key of the entry or node it is on. In ArrayMap, that is arr[cursor].key:

@Override
public Iterator<K> iterator() {
  return new KeyIterator();
}

private class KeyIterator implements Iterator<K> {
  private int cursor = 0;  // index of the entry whose key comes next

  @Override
  public boolean hasNext() {
    return cursor < size;
  }

  @Override
  public K next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    return arr[cursor++].key;
  }
}

In LinkedMap, it is current.key. As in the set’s linked iterator, next() saves the key before it advances current:

@Override
public Iterator<K> iterator() {
  return new KeyIterator();
}

private class KeyIterator implements Iterator<K> {
  private Node<K, V> current = head;  // node whose key comes next

  @Override
  public boolean hasNext() {
    return current != null;
  }

  @Override
  public K next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    K key = current.key;
    current = current.next;
    return key;
  }
}

The costs are the same as for the set: $O(1)$ per call, $O(n)$ for a full traversal, and $O(1)$ auxiliary space. With that, the default traversal works:

Map<String, String> accounts = new ArrayMap<>();
// put some username -> password pairs

for (String user : accounts) {
  System.out.println(user);
}