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) 2014, 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(new Integer(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) 2014, 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 1.8 on my Windows 7 computer:

Collection Class, Number of Objects, Time
java.util.HashSet, 5000, 0
java.util.LinkedHashSet, 5000, 0
java.util.Vector, 5000, 120
java.util.ArrayList, 5000, 60
java.util.LinkedList, 5000, 50

Map Class, Number of Objects, Time
java.util.TreeMap, 5000, 120
java.util.HashMap, 5000, 80
java.util.IdentityHashMap, 5000, 30
java.util.WeakHashMap, 5000, 110
java.util.Hashtable, 5000, 160

A couple of notes about the output:

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:

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

Last update: 2014.

Table of Contents

 About This JDK Tutorial Book

 Downloading and Installing JDK 1.8.0 on Windows

 Downloading and Installing JDK 1.7.0 on Windows

 Downloading and Installing JDK 1.6.2 on Windows

 Java Date-Time API

 Date, Time and Calendar Classes

 Date and Time Object and String Conversion

 Number Object and Numeric String Conversion

 Locales, Localization Methods and Resource Bundles

 Calling and Importing Classes Defined in Unnamed Packages

HashSet, Vector, HashMap and Collection Classes

 Types of Collections-of-Elements

 Data Structures of Collection Implementations

 Collection Implementations in JDK

Search Operation Performance of Different Collection Classes

 Comparable Interface and compareTo() Method

 Character Set Encoding Classes and Methods

 Character Set Encoding Maps

 Encoding Conversion Programs for Encoded Text Files

 Socket Network Communication

 Datagram Network Communication

 DOM (Document Object Model) - API for XML Files

 SAX (Simple API for XML)

 DTD (Document Type Definition) - XML Validation

 XSD (XML Schema Definition) - XML Validation

 XSL (Extensible Stylesheet Language)

 Message Digest Algorithm Implementations in JDK

 Private key and Public Key Pair Generation

 PKCS#8/X.509 Private/Public Encoding Standards

 Digital Signature Algorithm and Sample Program

 "keytool" Commands and "keystore" Files

 KeyStore and Certificate Classes

 Secret Key Generation and Management

 Cipher - Secret Key Encryption and Decryption

 The SSL (Secure Socket Layer) Protocol

 SSL Socket Communication Testing Programs

 SSL Client Authentication

 HTTPS (Hypertext Transfer Protocol Secure)

 Outdated Tutorials

 References

 PDF Printing Version