Solution: Adding a Pair: put

If the key is present, put replaces its value and returns false. If the key is absent, it has to go at its insertion point, so the later keys have to shift one slot right to open a gap. The later values have to shift with them. If we shifted only the keys, every value after the gap would end up paired with the key that comes before its own key.

@Override
public boolean put(K key, V value) {
  if (key == null || value == null) {
    throw new IllegalArgumentException();
  }
  int i = insertionPoint(key);
  if (i < size && keys[i].equals(key)) {
    values[i] = value;  // key present; replace its value
    return false;
  }
  if (size == keys.length) {
    grow();
  }
  for (int j = size; j > i; j--) {  // shift later keys and values right
    keys[j] = keys[j - 1];
    values[j] = values[j - 1];
  }
  keys[i] = key;
  values[i] = value;
  size++;
  return true;
}

Here is put("banana", 4) on the map from the problem. The insertion point of "banana" is 1, between "apple" and "fig". The loop moves "pear" and then "fig" one slot right, each with its value:

before put("banana", 4)

keys    ┌─────────┬───────┬────────┬───┐
        │ "apple" │ "fig" │ "pear" │   │
        └─────────┴───────┴────────┴───┘
values  ┌─────────┬───────┬────────┬───┐
        │    5    │   2   │   3    │   │
        └─────────┴───────┴────────┴───┘
size 3

after put("banana", 4)

keys    ┌─────────┬──────────┬───────┬────────┐
        │ "apple" │ "banana" │ "fig" │ "pear" │
        └─────────┴──────────┴───────┴────────┘
values  ┌─────────┬──────────┬───────┬────────┐
        │    5    │    4     │   2   │   3    │
        └─────────┴──────────┴───────┴────────┘
size 4

"fig" still has 2, and "pear" still has 3. The search is $O(\log n)$, but the shift can move all $n$ pairs, so put is $O(n)$.

grow doubles both arrays and copies the pairs across at the same indices:

@SuppressWarnings("unchecked")
private void grow() {
  K[] biggerKeys = (K[]) new Comparable[keys.length * 2];
  V[] biggerValues = (V[]) new Object[values.length * 2];
  for (int i = 0; i < size; i++) {
    biggerKeys[i] = keys[i];
    biggerValues[i] = values[i];
  }
  keys = biggerKeys;
  values = biggerValues;
}