public class SCHashTable<T extends KeyedItem> 
implements HashTableInterface<T>
{  
  private List<T>[] table;
  
  private int h(long key) // hash function
  // return index
  {
    return (int)(key % table.length); // typecast to int
  }
  
  public SCHashTable(int size)
  // recommended size: prime number roughly twice bigger
  //                   than the expected number of elements
  {
    table = new List[size];
    // initialize the lists
    for (int i=0; i<size; i++)
      table[i] = new List<T>(); 
  }
  
  public void insert(T item)
  {
    int index = h(item.getKey());
    List<T> L = table[index];
    // insert item to L
    L.add(1,item); // if linked list is used, 
                   // insertion will be efficient
  }
  
  private int findIndex(List<T> L, long key)
  // search for item with key 'key' in L
  // return -1 if the item with key 'key' was not found in L
  {
    // search of item with key = 'key'
    for (int i=1; i<=L.size(); i++)
      if (L.get(i).getKey() ==  key)
        return i;
    
    return -1; // not found
  }
  
  public T find(long key)
  {
    int index = h(key);
    List<T> L = table[index];
    int list_index = findIndex(L,key);
    if (index>=0)
      return L.get(list_index);
    else
      return null; // not found
  }
  
  public T delete(long key)
  {
    int index = h(key);
    List<T> L = table[index];
    int list_index = findIndex(L,key);
    if (index>=0) {
      T item = L.get(list_index);
      L.remove(list_index);
      return item;
    } else
      return null; // not found    
  }
}