import java.util.*;
/**
 * Class to illustrate hashing.
 * 
 * @author (Harish Karnick) 
 * @version (5-4-05)
 */
public class Hash {
    private Student[] arr;
    private LinkedList[] hashArr;
    private Random r=new Random(System.currentTimeMillis());
    private int prime=613;//307,613,997,1009
    private Hashtable htab;
    //Assumes chain length of 3 on average.
    public Hash(int n) {
        arr=new Student[n];
        hashArr=new LinkedList[prime];
        htab=new Hashtable(prime);
        for(int i=0;i<n;i++){
            arr[i]=new Student(i);
            add(arr[i].getRollNo(), arr[i]);//adds to hashArr
            htab.put(arr[i].getRollNo(), arr[i]);
        }
    }
    private void add(int key, Student val) {
        int i=key % prime;
        if(hashArr[i]==null)
            hashArr[i]=new LinkedList();           
        hashArr[i].addFirst(val);
    }
    public void test(int n) {
        //runs n iterations of 1000 probes
        int rn;
        long time1=System.currentTimeMillis(), time2=0;
        Student s=null;
        for (int i=0;i<n;i++)
        for (int j=0;j<1000;j++) {
            rn=r.nextInt(1000);
            LinkedList l=hashArr[rn % prime];
            if(l!=null){
                ListIterator lt=l.listIterator();
                while (lt.hasNext()) {
                    s=(Student)lt.next();
                    if(s.getRollNo()==rn) break;
                 }
            }
        }
        time2=System.currentTimeMillis();
        System.out.println("Hash: "+(time2-time1));
        time1=System.currentTimeMillis();
        time2=0;
        for (int i=0;i<n;i++)
        for (int j=0;j<1000;j++) {
            rn=r.nextInt(1000);
            htab.get(rn);
        }
        time2=System.currentTimeMillis();
        System.out.println("Hashtable: "+(time2-time1));
        time1=System.currentTimeMillis();
        for (int i=0;i<n;i++)
        for (int j=0;j<1000;j++) {
            rn=r.nextInt(1000);
            for(int k=0;k<arr.length;k++) {
                if(rn==arr[k].getRollNo()) break;
            }
        }

        time2=System.currentTimeMillis();
        System.out.println("Linear search: "+(time2-time1));
    }
    public int maxChainLength(){
        int n=0,len;
        for(int i=0;i<hashArr.length;i++) {
            if(hashArr[i]!=null) {
                len=hashArr[i].size();
                if(len>n) n=len;
            }
        }
        return n;
    }        
}