test.java

/**
* By D. Lemire.
*/

import java.util.*;
class test {
    public static ArrayList<String> listofstrings(int lengthdividedby3) {
        String[] allcollide = { "Ace","BDe","AdF","BEF"};
        ArrayList<String> al = new ArrayList<String>();
        al.add("");
        if(lengthdividedby3 <= 0 ) return al;
        int mask = 0xFFFF;
        for(int k = 0; k<lengthdividedby3;++k) {
            ArrayList<String> oldarray = al;
            al = new ArrayList<String>();
            for(String s : oldarray)
              for(String t : allcollide)
                al.add(s+t);
        }
        System.out.println("generated "+al.size()+" ASCII strings of length "+al.get(0).length());
        int expectedhashcode = al.get(0).hashCode() & mask;
        for (String t: al)
          if((t.hashCode() & mask)!= expectedhashcode) throw new RuntimeException("Got it wrong!");
        System.out.println("... and they all collide (on first 16 bits)");
        return al;
    }
    static void testme(int lengthdividedby3) {
        long bef, aft;
        double average, worse;
        ArrayList<String> x = listofstrings(lengthdividedby3);
        {
          System.out.println("testing how long it usually takes to add "+x.size()+" elements to a hash table");

          bef = System.currentTimeMillis();
          Hashtable<String,Integer> testhash = new Hashtable<String,Integer>();
          for(int k = 0; k< x.size();++k)
            testhash.put(Integer.toString(k),1);
          aft = System.currentTimeMillis();
          average = (aft-bef)/1000.0;
          System.out.println("about "+average+" s");
        }
        {
          System.out.println("testing how long it usually takes to add "+x.size()+" elements to a hash table in our cooked up case");

            // now watch the hash table suffer!
          bef = System.currentTimeMillis();
            Hashtable<String,Integer> myhash = new Hashtable<String,Integer>();
            for(String s : x)
                myhash.put(s,1);
          aft = System.currentTimeMillis();
          worse =   (aft-bef)/1000.0;
          System.out.println("about "+worse+" s");
        }
        System.out.println("ratio = "+worse/average);
        {
          System.out.println("testing how long it usually takes to add "+x.size()+" elements to a tree in our cooked up case");

            // now watch the hash table suffer!
          bef = System.currentTimeMillis();
            TreeMap<String,Integer> myhash = new TreeMap<String,Integer>();
            for(String s : x)
                myhash.put(s,1);
          aft = System.currentTimeMillis();
          double treetime =     (aft-bef)/1000.0;
          System.out.println("about "+treetime+" s");
        }
        System.out.println();
    }
    static public void main(String[] args) {
        testme(6);
        testme(7);
        testme(8);

        testme(6);
        testme(7);
        testme(8);

    }
}