Collections

Part:   1  2   3  4 

(Continued from previous part...)

Data Structures of Collection Implementations

In the previous section, we only talked about the functionalities of collections, and divided collections into 3 types based on the differences in the their functionalities. In the section, we will look at what kind of data structures we are going to use to store the data elements. Choosing any data structure to implement a collection should not affect the accuracy of its functionalities, but it will affect the performance.

There 4 major types of data structures that can be used in the implementation of collections: array, linked list, binary tree, hash table.

Before going into any details on each data structures, we need to clarify one thing: when a user wants to store a data element into a collection, we only need to store the reference number of that data element in the collection. The reference member of a data element is usually the memory address where that data element is actually stored.

Array: Reference numbers of data elements are stored consecutively in the memory, one immediately after another.

Linked List: Reference numbers of data elements are stored randomly in the memory, but they are linked with a pointer associated with each reference number pointing to the next reference number.

Binary Tree: Reference numbers of data elements are stored randomly in the memory, but they are linked with two pointers associated with each reference number pointing to two other reference numbers.

Hash table: Reference numbers of data elements are stored in one single section of memory. The exact location of the each reference number is based the hash number obtained from the data element.

Of course, I am only giving a rough description for each data structure here. For more details, please read any data structure text book.

Collection Implementations in J2SDK

J2SDK 1.4.1_02 provides the following implementations of collections:

       Array       Linked List   Binary Tree   Hash Table

Set                              TreeSet       HashSet
Set                                            LinkedHashSet

List   ArrayList   LinkedList
List   Vector 
List   Stack

Map                              TreeMap       HashMap
Map                                            IdentityHashMap
Map                                            WeakHashMap
Map                                            Hashtable

Search Operation Performance

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 J2SDK. Here is the main program, CollectionTest:

import java.util.*;
class CollectionTest {
   public static void main(String[] a) {
      Object[] arr = getObjects();
      Collection col;
      System.out.println("Collection Class, Number of Objects, Time");
      col = new HashSet();
      testCollection(arr,col);
      col = new LinkedHashSet();
      testCollection(arr,col);
//      col = new TreeSet(); // requires element.compareTo()
//      testCollection(arr,col);
      col = new Vector();
      testCollection(arr,col);
      col = new ArrayList();
      testCollection(arr,col);
      col = new LinkedList();
      testCollection(arr,col);
      Map dic; 
      System.out.println("Map Class, Number of Objects, Time");
      dic = new TreeMap();
      testMap(arr,dic);
      dic = new HashMap();
      testMap(arr,dic);
      dic = new IdentityHashMap();
      testMap(arr,dic);
      dic = new WeakHashMap();
      testMap(arr,dic);
      dic = new Hashtable();
      testMap(arr,dic);
   }
   private static void testCollection(Object[] arr, Collection 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 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;
   }
}

(Continued on next part...)

Part:   1  2   3  4