Iterating the Entries

First, ArrayMap’s storage class has to be a Map.Entry. It implements the interface by adding the two accessors:

private static class Entry<K, V> implements Map.Entry<K, V> {
  K key;
  V value;

  Entry(K key, V value) {
    this.key = key;
    this.value = value;
  }

  @Override
  public K key() {
    return key;
  }

  @Override
  public V value() {
    return value;
  }
}

The class stays private, and only the Map.Entry interface it implements is public. Every filled slot now holds a Map.Entry, so the iterator can return the stored entry directly.

entries() must return an Iterable. A map is already Iterable over its keys, so entries() cannot return the map itself. It returns an Entries object instead. Entries is a private inner class whose only job is to be that Iterable: its iterator() creates an EntryIterator.

@Override
public Iterable<Map.Entry<K, V>> entries() {
  return new Entries();
}

private class Entries implements Iterable<Map.Entry<K, V>> {
  @Override
  public Iterator<Map.Entry<K, V>> iterator() {
    return new EntryIterator();
  }
}

private class EntryIterator implements Iterator<Map.Entry<K, V>> {
  private int cursor = 0;  // index of the entry that comes next

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

  @Override
  public Map.Entry<K, V> next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    return arr[cursor++];
  }
}

EntryIterator is the key iterator from earlier with one change: next() returns the whole entry, arr[cursor], instead of arr[cursor].key.

LinkedMap does the same. Node implements Map.Entry with the same two accessors:

private static class Node<K, V> implements Map.Entry<K, V> {
  K key;
  V value;
  Node<K, V> next;

  Node(K key, V value) {
    this.key = key;
    this.value = value;
  }

  @Override
  public K key() {
    return key;
  }

  @Override
  public V value() {
    return value;
  }
}

entries() and Entries are the same as in ArrayMap. The EntryIterator is the linked key iterator with one change: next() returns the node instead of its key.

private class EntryIterator implements Iterator<Map.Entry<K, V>> {
  private Node<K, V> current = head;  // node that comes next

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

  @Override
  public Map.Entry<K, V> next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    Node<K, V> node = current;
    current = current.next;
    return node;
  }
}