public class DoubleHashTable<T extends KeyedItem> 
implements HashTableInterface<T>
{  
  private KeyedItem[] table;
  // special values: null = EMPTY, T with key=0 = AVAILABLE
  private static KeyedItem AVAILABLE = new KeyedItem(0);
  private int q; // should be a prime number
  
  public DoubleHashTable(int size,int q)
  // size: should be a prime number;
  //       recommended roughly twice bigger
  //       than the expected number of elements
  // q: recommended to be a prime number, should be smaller than size
  {
    table = new KeyedItem[size];
    this.q=q;
  }
  
  private int h(long key) // hash function
  // return index
  {
    return (int)(key % table.length); // typecast to int
  }
  
  private int hh(long key) // second hash function
  // return step multiplicative constant
  {
    return (int)(q - key%q);
  }
  
  private int step(int k,long key) // step function
  {
    return k*hh(key); 
  }
  
  public void insert(T item) throws HashTableFullException
  {
    int index = h(item.getKey());
    int probe = index;
    int k = 1;
    do {
      if (table[probe]==null || table[probe]==AVAILABLE) {
        // this slot is available
        table[probe] = item;
        return;
      }
      probe = (index + step(k,item.getKey())) % table.length; // check next slot
      k++;
    } while (probe!=index);
    throw new HashTableFullException("Hash table is full.");
  }
  
  private int findIndex(long key)
  // return -1 if the item with key 'key' was not found
  {
    int index = h(key);
    int probe = index;
    int k = 1;
    do {
      if (table[probe]==null) {
        // probe sequence has ended
        break;
      }
      if (table[probe].getKey()==key)
        return probe;
      probe = (index + step(k,key)) % table.length; // check next slot
      k++;
    } while (probe!=index);
    
    return -1; // not found
  }
  
  public T find(long key)
  {
    int index = findIndex(key);
    if (index>=0)
      return (T) table[index];
    else
      return null; // not found
  }
  
  public T delete(long key)
  {
    int index = findIndex(key);
    if (index>=0) {
      T item = (T) table[index];
      table[index] = AVAILABLE; // mark available
      return item;
    } else
      return null; // not found    
  }
}