Implement a HashTable using linear probing. Doesn't do array resizing, you could just double array, but better to have a prime M.

LinearProbingHash.java

public class LinearProbingHash<Key, Value> {
   private int N, M = 11;
   private Key[] keys;
   private Value[] vals;

   public LinearProbingHash() {
      keys = (Key[]) new Object[M];
      vals = (Value[]) new Object[M];
   }

   private int hash(Key key) {
      // mask away sign bit from java's hash, mod by array size
      return (key.hashCode() & 0x7fffffff) % M;
   }

   public boolean isEmpty() { return size() == 0; }

   public void add(Key key, Value val) {
      int index = indexOf(key);
      // don't increment N if we only replace the value
      N = nullKeyAt(index) ? N + 1 : N;
      keys[index] = key;
      vals[index] = val;
   }

   public int size() { return N; }

   public boolean contains(Key key) {
      int index = indexOf(key);
      return validKeyAt(index);
   }

   public Value get(Key key) {
      int index = indexOf(key);
      if (validKeyAt(index))
         return vals[index];
      return null;
   }

   public Value remove(Key key) {
      int index = indexOf(key);
      if (nullKeyAt(index)) return null;
      Value returnValue = vals[index];
      keys[index] = null;
      vals[index] = null;
      index = ++index % M;
      while (validKeyAt(index)) {
         Key keyToAddBack = keys[index];
         Value valToAddBack = vals[index];
         keys[index] = null;
         vals[index] = null;
         // add will do increment N
         N--;
         add(keyToAddBack, valToAddBack);
         index = ++index % M;
      }
      N--;
      return returnValue;
   }

   @Override
   public String toString() {
      String hashTable = "[ ";
      for (int i = 0; i < M; i++)
         if(validKeyAt(i))
            hashTable = hashTable.concat(i + " : ( " + keys[i].toString() +
                  ", " + vals[i].toString() + " ) ");
      return hashTable.concat(" ]");
   }

   private boolean nullKeyAt(int index) { return keys[index] == null; }

   private boolean validKeyAt(int index) { return !nullKeyAt(index); }

   private int indexOf(Key key) {
      int index;
      for (index = hash(key); validKeyAt(index); index = ++index % M)
         if (key.equals(keys[index]))
            return index;
      return index;
   }

}