Search Operation Performance of Different Collection Classes

JDK Tutorials - Herong's Tutorial Examples

∟HashSet, Vector, HashMap and Collection Classes

∟Search Operation Performance of Different Collection Classes

This section provides a tutorial example on how to do performance comparison on search operations on different collection classes implemented in JDK 1.4.1. HashSet and LinkedHashSet have the best performance on search operations.

Once a collection is created, search is probably the most frequently used operation. So let's compare the performance of the search operation among the collection classes offered in JDK. Here is the main program, CollectionTest:

/* CollectionTest2.java
 * Copyright (c) HerongYang.com. All Rights Reserved.
 */
import java.util.*;
class CollectionTest2 {
   public static void main(String[] a) {
      Object[] arr = getObjects();

      Collection<Object> col;
      System.out.println("Collection Class, Number of Objects, Time");
      col = new HashSet<Object>();
      testCollection(arr,col);
      col = new LinkedHashSet<Object>();
      testCollection(arr,col);
//      col = new TreeSet<Object>(); // requires element.compareTo()
//      testCollection(arr,col);
      col = new Vector<Object>();
      testCollection(arr,col);
      col = new ArrayList<Object>();
      testCollection(arr,col);
      col = new LinkedList<Object>();
      testCollection(arr,col);

      Map<Object, Object> dic;
      System.out.println("Map Class, Number of Objects, Time");
      dic = new TreeMap<Object, Object>();
      testMap(arr,dic);
      dic = new HashMap<Object, Object>();
      testMap(arr,dic);
      dic = new IdentityHashMap<Object, Object>();
      testMap(arr,dic);
      dic = new WeakHashMap<Object, Object>();
      testMap(arr,dic);
      dic = new Hashtable<Object, Object>();
      testMap(arr,dic);
   }
   private static void testCollection(Object[] arr,
      Collection<Object> col) {
      for (int l=0; l<arr.length; l++) {
         col.add(arr[l]);
      }
      Date t1 = new Date();
      boolean ok = true;
      for (int l=0; l<arr.length; l++) {
         ok = ok && col.contains(arr[l]);
      }
      Date t2 = new Date();
      if (ok==false) System.out.println("Search failed.");
      System.out.println(col.getClass().getName()+", "+
         arr.length+", "+(t2.getTime()-t1.getTime()));
   }
   private static void testMap(Object[] arr, Map<Object, Object> col) {
      for (int l=0; l<arr.length; l++) {
         col.put(Integer.valueOf(l), arr[l]);
      }
      Date t1 = new Date();
      boolean ok = true;
      for (int l=0; l<arr.length; l++) {
         ok = ok && col.containsValue(arr[l]);
      }
      Date t2 = new Date();
      if (ok==false) System.out.println("Search failed.");
      System.out.println(col.getClass().getName()+", "+
         arr.length+", "+(t2.getTime()-t1.getTime()));
   }
   private static Object[] getObjects() {
      int max_l = 5000;
      Object[] arr = new Object[max_l];
      for (int l=0; l<max_l; l++) {
         arr[l] = new MySimpleDate();
      // arr[l] = new MyDate(); // with element.compareTo() implemented
      }
      return arr;
   }
}

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 created, 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:

/* MySimpleDate.java
 * Copyright (c) HerongYang.com. All Rights Reserved.
 */
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, an instance of time with minutes, seconds and milliseconds truncated, and date randomized.

Since MySimpleDate class is not implementing the Comparable interface, its objects cannot 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 running JDK 20 on my macOS computer:

herong$ javac MySimpleDate.java 
herong$ javac CollectionTest2.java 
herong$ java CollectionTest2 

Collection Class, Number of Objects, Time
java.util.HashSet, 40000, 4
java.util.LinkedHashSet, 40000, 1
java.util.Vector, 40000, 338
java.util.ArrayList, 40000, 295
java.util.LinkedList, 40000, 1922

Map Class, Number of Objects, Time
java.util.TreeMap, 40000, 5821
java.util.HashMap, 40000, 1585
java.util.IdentityHashMap, 40000, 585
java.util.WeakHashMap, 40000, 2241
java.util.Hashtable, 40000, 3504

Here is output of the program running JDK 17 on my Windows 10 computer:

Collection Class, Number of Objects, Time
java.util.HashSet, 40000, 0
java.util.LinkedHashSet, 40000, 0
java.util.Vector, 40000, 156
java.util.ArrayList, 40000, 157
java.util.LinkedList, 40000, 1281

Map Class, Number of Objects, Time
java.util.TreeMap, 40000, 4171
java.util.HashMap, 40000, 1250
java.util.IdentityHashMap, 40000, 357
java.util.WeakHashMap, 40000, 1922
java.util.Hashtable, 40000, 2671

A couple of notes about the output:

LinkedHashSet took no time (0 millisecond) to search 40000 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.
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.

Performances of different collection sizes on Windows 7 with JDK 1.8:

Collection           Number of Elements
Class           5000   10000   20000   40000
-------------   ----   -----   -----   -----
HashSet            0       0      10       0
LinkedHashSet      0       0       0       0
Vector           120     220    1480    4560
ArrayList         60     210    1480    3310
LinkedList        50     200    1600    3160
TreeMap          120     490    2810    7751
HashMap           80     290    1801    4630
IdentityHashMap   30     110     410    1671
WeakHashMap      110     450    2480  failed
Hashtable        160     640    3250   10120

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 JDK specification.

Performances of different collection sizes on Windows 2000 with JDK 1.4.1_01:

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