public class SeparateChainingHashTable<Key,Value> implements SymbolTable<Key,Value>{
    
   private int m;  // number of slots in table
   private KeyValueList<Key,Value>[] table;
   private int size;
    
   public SeparateChainingHashTable() {
      this(997);
   }
    
   public SeparateChainingHashTable(int m) {
      this.m = m;
      table = (KeyValueList<Key,Value>[]) (new KeyValueList[m]); // generic array creation 
                                                                 // not allowed, so use raw
                                                                 // type and cast
      for (int i = 0; i < m; i++) 
         table[i] = new KeyValueList<Key,Value>(); 
   }
   
   private int hash(Key key) {
       return (key.hashCode() & 0x7fffffff) % m;
   }
   
   public Value get(Key key) {
       return table[hash(key)].get(key);
   }
   
   public void put(Key key, Value val) {
       int h = hash(key);
       int listSizeBefore = table[h].size();
       table[h].put(key, val);
       size += table[h].size() - listSizeBefore; 
   }

    public boolean contains(Key key) {
        return (get(key) != null);
    }
    
    public void delete(Key key) {
        int h = hash(key);
        int listSizeBefore = table[h].size();
        table[h].delete(key);
        size -= listSizeBefore - table[h].size(); 
    }
    
    public boolean isEmpty() {
        return (size == 0);
    }
    
    public int size() {
        return size;
    }
    
    public Iterable<Key> keys() {
        java.util.Stack<Key> stack = new java.util.Stack<Key>();
        for (int i = 0; i < table.length; i++)  {
           Iterable<Key> keys = table[i].keys();
           for (Key key : keys) 
              stack.add(key);
        }
        return stack;
    }
    
    public String toString() {
        StringBuilder sb = new StringBuilder("");
        for (int i = 0; i < table.length; i++) {
            sb.append(i + " : " + table[i] + System.lineSeparator());
        }
        return sb.toString();
    }
    
}