import java.util.*;

public class HashTable {

    private int capacity;                   // hash table capacity, should be prime
    private Object[] S;                     // bucket array
    private int scalingFactor;
    private int shift;
    private int size;
	
    public HashTable(int capacity){
	this.capacity = capacity;
	Random rand = new Random();
	scalingFactor = rand.nextInt(capacity-1) + 1;
	shift = rand.nextInt(capacity);
	S = new Object[capacity];
	for (int i=0;i<capacity;i++) S[i] = new ArrayList<String>();
	size = 0;
    }
	
    public int size(){return size;}
	 
    public boolean isEmpty(){return size > 0;}

    private long hashCode(String s){
	//return s.hashCode();
	long h = 0;
	int  a = 33;
	for (int i=0;i<s.length();i++) h = a*h + s.charAt(i);
	return h;
    }
    //
    // polynomial hash code ... to quote from Go&Ta
    // "33, 37, 39 and 41 are good choices for a ... when using English words ..."
    // cut and paste replacement of the above from Arash Partow's 
    // "General Purpose Hash Function Algorithms Library"
    // Also try the java s.hashCode() 
    //

    private int hash(String s){
	return (int)(Math.abs(scalingFactor*hashCode(s) + shift) % capacity);
    }

    public void put(String s){
	int i = hash(s);
	ArrayList<String> bucket = (ArrayList<String>)S[i];
	if (!bucket.contains(s)){bucket.add(s); size++;}
    }

    public boolean get(String s){
	int i = hash(s);
	ArrayList<String> bucket = (ArrayList<String>)S[i];
	return bucket.contains(s);
    }

    public String stats(){
	String s = "capacity: " + capacity +" ";
	s = s + "size: " + size +" ";
	int collisions = 0;
	for (int i=0;i<capacity;i++) if (((ArrayList<String>)S[i]).size() > 1) collisions = collisions + ((ArrayList)S[i]).size();
	s = s + "collisions: " + collisions +" ";
	int max = 0;
	for (int i=0;i<capacity;i++) max = Math.max(((ArrayList<String>)S[i]).size(),max);
	s = s + "maxBucketSize: " + max +" ";
	int tot = 0;
	int n = 1;
	for (int i=0;i<capacity;i++) 
	    if (((ArrayList<String>)S[i]).size() > 0){n++; tot = tot + ((ArrayList<String>)S[i]).size();}
	s = s + "averageOccupiedBucketSize: " + tot/n;
	return s;
    }

}