Collections

Part:   1  2  3   4 

(Continued from previous part...)

The idea of the test is simple. First, an array of objects of my own class, MySimpleDate, is created. Then, an object of the to-be-tested collection class is create, and filled with all the objects from the array. The performance test is concentrated on the CPU time used to search all the objects in the collection one by one.

MySimpledate class is really simple. Here is the source code:

import java.util.*;
public class MySimpleDate {
   private static Random r;
   private Date my_date; 
   public MySimpleDate () {
      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);
   }
}

It contains only one piece of information, a instance of time with minutes, seconds and milliseconds truncated, and date randomized.

Since MySimpleDate class is not implementing the Comparable interface, its objects can not be managed by TreeSet collection. So I have commented out some lines in the CollectionTest program to avoid testing on TreeSet collection.

Here is output of the program compiled and executed by J2SDK 1.4.1_01:

Collection Class, Number of Objects, Time
java.util.HashSet, 5000, 10
java.util.LinkedHashSet, 5000, 0
java.util.Vector, 5000, 661
java.util.ArrayList, 5000, 651
java.util.LinkedList, 5000, 762
Map Class, Number of Objects, Time
java.util.TreeMap, 5000, 1021
java.util.HashMap, 5000, 1712
java.util.IdentityHashMap, 5000, 391
java.util.WeakHashMap, 5000, 1572
java.util.Hashtable, 5000, 3145

A couple of notes about the output:

• LinkedHashSet took no time (0 millisecond) to search 5000 elements. I can not believe this. Something must be wrong here.
• HashSet performed better than most other collection classes, as expected, because locations of elements in a HashSet are based the hash value of each elements, which will provide almost instant access time.
• Vector, and ArrayList, took about the same time, as expected, because they both are based on array data structure.
• LinkedList took longer time than ArrayList, as expected, because iterating through a linked list is slower that an array.
• TreeMap, HashMap, WeakHashMap and Hashtable took must longer time, because maps are not really designed to search elements directly. We should search the keys instead of elements.
• IdentityHashMap out performed all others map collections. I don't know why.

I repeated the execution 3 times with different number of elements and recorded the following results:

Collection      Number of Elements
Class           5000   10000   20000

HashSet           10      20      20
LinkedHashSet      0      10      20
Vector           661    2714   10936
ArrayList        651    2694   10676
LinkedList       762    3305   28122
TreeMap         1021   10256   52719
HashMap         1712   12629   60050
IdentityHashMap  391    1532    7000
WeakHashMap     1572  failed  failed
Hashtable       3145   21261   89103

The results show that:

• HashSet and LinkedHashSet maintained an almost constant performance level, while the number of elements doubled twice. They are perfectly designed for the search operation.
• Vector, ArrayList and LinkedList decreased their performance exponentially as the number of elements doubles.
• TreeMap, HashMap, IdentityHashMap and Hashtable decreased their performance exponentially as the number of elements doubles.
• WeakHashMap is not reliable as mentioned in the J2SDK specification.

(Continued on next part...)

Part:   1  2  3   4