Untitled

Mark an empty space into an array without using null
K[] keys;
V[] values;

class Node {
    K key;
    V value;
}

Node[] nodes;

private static final Object BLANK = new Object();

K[] keys;
V[] values;
boolean[] hasValue;

private boolean isNullMapped = false;
private V nullValue = null;

public put(K key, V value)
{
  if (key == null) { nullValue = value; }
  ...
}

private static class KeyWrapper<K>
{
  public K key;
}

private static final Object NULL_KEY = "NULL";
K[] keys;
V[] values;

private int find(K key) {
  for (int i = 0; i < keys.length; i++) {
    if (keys[i] == key) {
      return i;
    }
  }
  return -1;
}

public V put(K key, V value) {
  V old = null;
  if (key != null) {
    int i = find(key);
    if (i >= 0) {
      old = values[i];
      values[i] = value;
    } else {
      // ...
    }
  } else {
    return put((K) NULL_KEY, value);
  }
  return old;
}

public V get(K key) {
  if (key != null) {
    int i = find(key);
    if (i >= 0) {
      return values[i];
    }
    return null;
  } else {
    return (get((K) NULL_KEY));
  }
}