Comparable Interface and compareTo() Method

JDK Tutorials - Herong's Tutorial Examples

∟HashSet, Vector, HashMap and Collection Classes

∟Comparable Interface and compareTo() Method

This section provides a tutorial example on how to construct object with the Comparable interface, so that they can be stored in collections using the TreeSet class. Search operations on TreeSet class perform nicely - almost the same as HastSet and LinkedHashSet.

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

/* MyDate.java
 * Copyright (c) HerongYang.com. All Rights Reserved.
 */
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 overridden, 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 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 overridden, the hashCode() method must also be overridden, 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 on Windows 2000 with JDK 1.4.1_01:

                  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 result shows 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 overridden 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.