/** Let's test the efficiency of hashing, using the Java API HashSet
 *  data structure.  We'll compare its speed to a LinkedList and ArrayLIst.
 */
import java.util.*;

public class Hashing
{
  public static void main(String [] args)
  {
    int size = 1000000;
    Random gen = new Random();

    // Let's generate a lot of random numbers and store them.
    // Then let's try to retrieve a value that's not there.
    
    long t1 = System.currentTimeMillis();

    HashSet set = new HashSet();
    for (int i = 0; i < size; ++i)
      set.add(new Integer(gen.nextInt(size)));
    long t2 = System.currentTimeMillis();

    boolean contains = set.contains(new Integer(-1));
    long t3 = System.currentTimeMillis();
    set = null;
    
    // Now do the same for LinkedList.

    LinkedList list = new LinkedList();
    for (int i = 0; i < size; ++i)
      list.add(new Integer(gen.nextInt(size)));
    long t4 = System.currentTimeMillis();

    contains = list.contains(new Integer(-1));
    long t5 = System.currentTimeMillis();
    list = null;

    // And finally for the ArrayList.
    ArrayList a = new ArrayList();
    for (int i = 0; i < size; ++i)
      a.add(new Integer(gen.nextInt(size)));
    long t6 = System.currentTimeMillis();

    contains = a.contains(new Integer(-1));
    long t7 = System.currentTimeMillis();

    System.out.println("Time in milliseconds when size = " + size);
    System.out.println("            insert   search");
    System.out.println("hash set    " + (t2 - t1) + "       " + (t3 - t2));
    System.out.println("linked list " + (t4 - t3) + "       " + (t5 - t4));
    System.out.println("array list  " + (t6 - t5) + "       " + (t7 - t6));
  }
}