public class LinearProbingHashTable implements Dictionary {
  
  /** Marker for deactivated buckets */
  private static Item AVAILABLE = new Item(null, null);
  /** number of items in the dictionary */
  private int n = 0;
  /** capacity of the bucket array */
  private int N;
  /** bucket array */
  private Item[] A;
  /** hash comparator */
  private HashComparator h;
  
  /** constructor providing the hash comparator */
  public LinearProbingHashTable(HashComparator hc) {
    h = hc;
    N = 1023; // default capacity
    A = new Item[N];
  }
  
  /** constructor providing the hash comparator and the capacity
    * of the bucket array */
  public LinearProbingHashTable(HashComparator hc, int bN) {
    h = hc;
    N = bN;
    A = new Item[N];
  }
  
  // auxiliary methods
  private boolean available(int i) { return (A[i] == AVAILABLE); }
  private boolean empty(int i) { return (A[i] == null); }
  private Object key(int i) { return A[i].key(); } 
  private Object element(int i) { return A[i].element(); }
  private void check(Object k) {
    if (!h.isComparable(k))
      throw new InvalidKeyException("Invalid key.");
  }