The ArrayMap Class

Here is the class, with its entry type, fields, and constructor:

public class ArrayMap<K, V> implements Map<K, V> {

  private Entry<K, V>[] arr;  // the backing array
  private int size;           // how many pairs the map holds

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

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

  @SuppressWarnings("unchecked")
  public ArrayMap() {
    arr = (Entry<K, V>[]) new Entry[10];  // start with room for 10 pairs
    size = 0;                             // the map starts empty
  }

  // ... the operations will go here
}

The constructor creates an Entry[], not an Object[]. Recall from SortedArray that we create an array of whatever the element type erases to, because the JVM checks the cast against that type. SortedArray needed a Comparable[]. Here the element type Entry<K, V> erases to Entry, so (Entry<K, V>[]) new Object[10] would throw a ClassCastException. Writing Entry without its type arguments is called a raw type.

The size operation reads the field directly:

@Override
public int size() {
  return size;
}

Every remaining operation has to locate an entry by its key, so we write that search once, as a private helper:

private int indexOf(K key) {
  for (int i = 0; i < size; i++) {
    if (arr[i].key.equals(key)) {
      return i;
    }
  }
  return -1;
}

It is the same search as ArraySet’s indexOf, except that it compares keys.