Sorting A Hashtable in Java

Keywords: Java Sort Hashtable

Copyright 2010, Gregory Bradford

Additional example by Luke T. Gilbert

 

Forward

Through a momentary lapse of diligence on my part I accidentally allowed Google to index some pages on my website that a few people in the aviation simulation community might have an interest. Unfortunately, a couple of the pages had some key words (or concepts if you will) in which it seems everybody is interested. One such concept is the sorting of a Hashtable in Java.

The sorting of a Hashtable isn't particularly difficult and the fact that you are looking at this material indicates your knowledge of Java and Hashtables may not be 100 percent complete. Well mine isn't either so we are probably even. But, I can show you how to sort a Hashtable assuming your data fits certain criteria. Under most circumstances (I haven't found an exception yet) the data within a Hashtable is sortable.

First a brief explanation of how a Hashtable works is worthwhile.

Wanna hack your iPhone 4, need a source for a Pentalobular Screwdriver? Find them here:
www.pentalobular-screwdriver.com

A Brief Hashtable Discussion

In general terms, when constructed, a Hashtable will have several locations where objects are stored. I personally call them "buckets". I haven't reviewed the code for Java's Hashtable class but I would guess they have used an array internally with each array element representing one of my so-called "buckets".

When the Hashtable user stores an object she provides a key value which represents the object and the object itself. Some sample code might look like this:

Hashtable hash           = new Hashtable ( 4 );
String    object_key     = "ABC";
Integer   integer_object = new Integer ( 563 );
hash.put ( object_key , integer_object );


View more gifts at Zazzle.

Once again, please allow me to repeat, this document is only attempting to explain the conceptual Hashtable issues, not actually how Hashtables are implemented within Java. If you want the actual implementation you have come to the wrong place. With that in mind, allow me to explain the above code:

The "Hashtable hash = new Hashtable ( 4 );" line creates a Hashtable object with four of my so-called buckets. Or perhaps internally an array with four elements. Each element in the array probably is an array itself (or maybe even a Vector object). These arrays are empty when the Hashtable is initially created.

The "String object_key = "ABC";" and "Integer integer_object = new Integer ( 563 );" lines are relatively self explanatory and will not be discussed here.

The "hash.put ( object_key , integer_object );" line stores the integer_object in the hash object with the key: object_key. Internally, when called, the put method computes a hash index from the object_key which indicates the bucket in which the object should be stored.

A simplistic way of computing the hash index would be to take the ASCII value of each character in the object_key, add those ASCII values together and then modula the sum by the number of buckets. That calculation would be: (65 + 66 + 67) % 4 = 2. Thus, bucket #2 (or array number 2) is chosen to store the integer_object.

As you can see through simple deduction, objects stored in Hashtables are not stored in any particular order. By changing the values of the characters in the object_key variable above another bucket would probably be chosen to store the integer_object.

Moving on, when you loop over a Hashtable using the standard looping facilities you are seeing the order the objects were stored in the Hashtable. And that order is relatively random from the perspective of someone who wants to see the data sorted.

Sorting a Hashtable

To sort the Hashtable you can do it in the following manner. There are probably much more efficient ways to do this task, but this one is offered as a solution. Don't complain to me if you don't like it.

First of all, you retrieve all of the objects out of the Hashtable and store them in an array that can be sorted. By the very nature of the beast (see the beginning of this document) a pure Hashtable itself cannot be sorted, but the data within it can.

An array provided by Java that can be sorted is the ArrayList class. Somebody at Sun dropped the ball when they designed the ArrayList class. Quite a few of the method names in ArrayList do not match those in the Vector class. Thus, I was always trying to remember, do I use add or addElement to add an item to an ArrayList. In frustration I created my own class that extends ArrayList and implements many of the method names found in the Vector class. I now exclusively use my "sarray" class when I'm in need of the capabilities of the ArrayList class. The source for the sarray class is as follows:

import java.util.*;
/**
sarray is a convenience class designed to make ArrayList methods consistent 
 with Vector.    Why did Sun not do this??
*/
/************************************************/
public class sarray extends ArrayList
{
private int last_index = 0;

/************************************************/
public int length ()
  {
  return ( size ( ) );
  }
/************************************************/
public Object elementAt ( int index )
  {
  last_index = index;
  return ( get ( index ) );
  }
/************************************************/
public void addElement ( Object o )
  {
  add ( o );
  }

/************************************************/
/**
Sets the last index requested to the supplied value.
*/

public void setLastIndex(int value)
  {
  last_index = value;
  }

/************************************************/
/**
Returns the last index requested by the elementAt method.
*/

public int getLastIndex()
  {
  return ( last_index );
  }
  
/************************************************/
/**
Make compatible with Vector.
*/
public void removeElementAt ( int index )
  {
  remove ( index );
  }

/************************************************/
/**
Make compatible with Vector.
*/
public void removeElement ( Object obj )
  {
  int index = indexOf ( obj );

  if ( index > -1 ) remove ( index );
  }
}

As mentioned, the sarray class can be sorted by Java supplied capabilities since it inherits the abilities of the ArrayList class which itself is sortable. The class that performs the sort is the Collections class in Java.

The most important thing to remember about sorting an sarray in Java using the Collections class is that ALL of the objects stored in your sarray must implement the Comparable interface. To this end, I have created another useful class which I call sortable. sortable implements the Comparable interface, thus objects of this type are sortable by the Collections class.

But, a warning is in order: Objects stored in a sortable object, or at least the key field, must also implement the Comparable interface. String objects, Integer objects, Double objects, and many other Java objects meet this criteria. Thus, usually if you can supply a String or an Integer for the key field you are ok.

The source code for the sortable object is as follows:

import java.io.*;
import java.util.*;

public class sortable
implements Comparable 
{
private  Comparable key = "";
private  Object       o = null;

/************************************************/
public sortable ( Comparable key , Object o )
  {
  this.key = key;
  this.o = o;
  }

/************************************************/
public void setKey ( Comparable key )
  {
  this.key = key;
  }

/************************************************/
public Comparable getKey()
  {
  return ( key );
  }

/************************************************/
public void setObject ( Object o )
  {
  this.o = o;
  }

/************************************************/
public Object getObject()
  {
  return ( o );
  }
/************************************************/
public int compareTo ( Object o )
  {
  return ( key.compareTo ( ((sortable) o).getKey() ) );
  }  
}

A Complete Example

If you've read all of the material above you may be a bit confused by this point. The following example brings together all the pieces noted above to show how to sort a Hashtable.

Expanding upon the example Hashtable code described earlier as a starting point:

Hashtable hash           = new Hashtable ( 4 );
String    object_key     = "ABC";
Integer   integer_object = new Integer ( 563 );
hash.put ( object_key , integer_object );
object_key     = "XYZ";
integer_object = new Integer ( 129 );
hash.put ( object_key , integer_object );
object_key     = "MNO";
integer_object = new Integer ( 6564 );
hash.put ( object_key , integer_object );

Three objects are stored in the hash which now need sorting. In our case it is desirable to sort by the object_key. Thus, pull all the objects out of the Hashtable and place them into an sarray; sort them; and then print the sorted list:

// Create an sarray object which will store sortable objects that the Collections class can sort.

sarray my_array = new sarray();
// loop over all of the keys
// Or loop over the elements instead with:
// for ( Enumeration e = hash.elements() ; e.hasMoreElements() ; )
for ( Enumeration e = hash.keys() ; e.hasMoreElements() ; )
{
// retrieve the object_key
String object_key = (String) e.nextElement();
// retrieve the object associated with the key
Integer integer_object = (Integer) hash.get ( object_key );
// build a sortable object with the two pieces of information
sortable s = new sortable ( object_key , integer_object );
// add the sortable object to the sarray
my_array.add ( s );
}
// sort the sarray
Collections.sort ( my_array );
// print the sorted sarray
for ( int i = 0 ; i < my_array.size() ; i++ )
{
sortable s = (sortable) my_array.elementAt ( i );
String object_key = (String) s.getKey();
Integer integer_object = (Integer) s.getObject();
System.out.println ("Key = " + object_key + " , Value = " + integer_object );
}


A Short Alternative Example

Just recently I received an email from Luke T. Gilbert who suggested that I might want to consider his methodology for sorting a HashTable. I took a look at it and found it quite useful. He graciously provided his permission to post the code.

There isn't any explanatory material but I believe that his code is very readable "as is". The code is:

import java.util.Hashtable;
import java.util.Vector;
import java.util.Collections;
import java.util.Enumeration;


public class SortHashtable {

  public static void main(String[] args) {
    // Create and populate hashtable
    Hashtable ht = new Hashtable();
    ht.put("ABC", "abc");
    ht.put("XYZ", "xyz");
    ht.put("MNO", "mno");
    
    // Sort hashtable.
    Vector v = new Vector(ht.keySet());
    Collections.sort(v);
    
    // Display (sorted) hashtable.
    for (Enumeration e = v.elements(); e.hasMoreElements();) {
      String key = (String)e.nextElement();
      String val = (String)ht.get(key);
      System.out.println("Key: " + key + "     Val: " + val);
    }
  }
}