Iterating Key–Value Pairs

Here is the Map interface. A map is iterable over its keys:

public interface Map<K, V> extends Iterable<K> {
  boolean put(K key, V value);  // stores value under key, replacing any old value;
                                // returns true if the key was not present before
  V get(K key);                 // returns the value stored under key, or null if key is absent
  boolean remove(K key);        // removes key and its value if key is present;
                                // returns true if the map changed
  boolean containsKey(K key);   // returns true if key is in the map
  int size();                   // returns the number of key-value pairs in the map
}

LinkedMap<K, V> implements Map<K, V> with a singly linked list, one node per pair.

public class LinkedMap<K, V> implements Map<K, V> {
  private Node<K, V> head;  // the first node, or null when empty
  private int size;         // how many pairs the map holds

  private static class Node<K, V> {
    K key;
    V value;
    Node<K, V> next;
  }

  // the Map operations and the key iterator are already implemented
}

ArrayMap<K, V> also implements Map<K, V>. It stores each pair in a private nested Entry<K, V> class with fields key and value, and keeps the entries in a backing array.

Exercise

accounts is a LinkedMap<String, String> that holds $n$ pairs. What is the time complexity of this loop? Explain.

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

Solution

$O (n^{2})$ . The loop runs once per key, $n$ times, and each get is a linear search, $O (n)$ .

Solution

A class can provide only one iterator() method, so it can be Iterable over only one type. Map already uses that on its keys. The entries() method returns a separate object that is Iterable over the pairs.

Solution

The caller holds the map’s own nodes, so every write changes the map. They can overwrite key, so the entry can no longer be found under its key and may be found under another one. They can overwrite value without going through put, for example with null, which put would reject. Then get returns null for a key that is present, so a null from get no longer means the key is absent. They can overwrite next, which cuts off or rearranges the rest of the list.

Solution

The two maps hand back different classes, LinkedMap.Node and ArrayMap.Entry. A caller who holds a Map<K, V> and does not know which implementation is behind it cannot name one type for the loop variable, and Map cannot declare one return type for entries() that fits both.

Solution

An interface with two accessors and nothing else, nested in Map so that callers name it Map.Entry<K, V>. LinkedMap’s Node and ArrayMap’s Entry each implement it and stay private:

public interface Map<K, V> extends Iterable<K> {
  // the five operations as before

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

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