Collections

Part:   1  2  3  4  

(Continued from previous part...)

Data Elements with Natural Order

In order to use TreeSet collection, data elements must be comparable. So I enhanced MySimpleDate class and rename it as MyDate clase:

import java.util.*;
public class MyDate implements Comparable {
   private static Random r;
   private Date my_date; 
   public MyDate () {
      my_date = new Date();
      long l = my_date.getTime();
      int i = (int) (l/1000/60/60/24);
      if (r==null) r = new Random();
      i = r.nextInt(i);
      l = ((long) i)*24*60*60*1000;      
      my_date.setTime(l);
   }
   public long getTime() {
      return my_date.getTime();
   }
   public int compareTo(Object o) {
      if (getTime()<((MyDate) o).getTime()) return -1;
      else if (getTime()==((MyDate) o).getTime()) return 0;
      else return 1;
   }
   public boolean equals(Object o) {
      return compareTo(o)==0;
   }
   public int hashCode() {
      return (int)(getTime()^(getTime()>>>32));
   }
}

Note that:

• Comparable interface is implemented in this class. It requires to implement the compareTo() method.
• If the compareTo() method is implemented, the equals() method must be overriden, in order to maintain the following logic: if x.compareTo(y)==0, then x.equals(y)==true. The default equals() method compares two objects based on the their reference numbers (addresses in memory), not looking at any data inside the objects. So two separate objects, even with identical data, will always fail the default equals() method.
• If the equals() method is overriden, the hashCode() method must also be overriden, in order to maintain the following logic: if x.equals(y)==true, then x.hashCode()==y.hashCode(). The default hashCode() method generates hash value also based on the object's reference number (address in memory), not looking at any data inside the object. So two separate objects with identical data may not have the same hash value, if the default hashCode() method is used.
• I copied the hash code generation expression from the Long class.

Using the MyDate class with my own compareTo(), equals(), and hashCode() methods, I repeated the search operation performance tests. Here is the results:

                With MySimpleDate       With MyDate
Collection      Number of Elements      Number of Elements
Class           5000   10000   20000    5000   10000   20000

HashSet           10      20      20      70      10      30
LinkedHashSet      0      10      20       0      10      10
TreeSet          n/a     n/a     n/a      10      40      70
Vector           661    2714   10936    1502    9424   37626
ArrayList        651    2694   10676    1573    9314   37646
LinkedList       762    3305   28122    2193   14102   54902
TreeMap         1021   10256   52719    4276   18417   56205
HashMap         1712   12629   60050    4727   29024   92068
IdentityHashMap  391    1532    7000     381    1532    6980
WeakHashMap     1572  failed  failed  failed  failed  failed
Hashtable       3145   21261   89103    5518   23395   89094

The results show that:

• HashSet, LinkedHashSet, and TreeSet did very well. The well designed hash value helped to reduce the number of objects to be fetched for comparison.
• Vector, ArrayList, and LinkedList took 3 times longer than the MySimpleDate version. My guess is that the overriden equals() method is 3 times slower than the default equals() method, which just checks the memory addresses of the objects.
• TreeMap and HashMap took a little bit longer than the MySimpleDate version.
• IdentityHashMap and Hashtable took about the same time as the MySimpleDate version.

Part:   1  2  3  4