Sorting A HashMap in Java

Keywords: Java Sort HashMap

Copyright 2011, Gregory Bradford

  

HashMap Description

HashMaps are, for the most part, simply hashes which in this case are not synchronized by Java. If you need synchronization the it is suggested that you use the Hashtable class instead. The discussion of whether to use a synchronized class, or to not use one, is beyond the scope of this discussion.

HashMaps have several locations where Java objects are stored. Sometimes referred to as "buckets". Some of the earliest implementers of hashes used an array with each element of the array representing a "buckets".

To store an object in a HashMap the user provides a key value which represents the object and the object itself. Some sample code might look like this:

HashMap hash           = new HashMap ( 4 );
String    object_key     = "JKL";
Integer   integer_object = new Integer ( 890 );
hash.put ( object_key , integer_object );

Music by Steven G. Terry

Please note, this document only attempts to describe HashMap concepts, not how Java implements HashMaps.

Now on to an explanation of the above code:

The "HashMap hash = new HashMap ( 4 );" line creates a HashMap object with four buckets. Internally there is probably an array with four elements. Each element in the internal array is probably an array. when the HashMap is initially created the arrays have no data.

The "String object_key = "JKL";" and "Integer integer_object = new Integer ( 890 );" lines explain themselves.

The "hash.put ( object_key , integer_object );" line stores the integer_object in the HashMap "hash" object. The key used is: "object_key". The put method computes a hash index from the object_key which determines the bucket to store the object.

A method of computing the hash index would be to examine the object_key and then take the ASCII value of each of it's characters. Then sum the ASCII values. Modulo the sum by how many buckets there are. In this case that computation would be: (74 + 75 + 76) % 4 = 1. Thus, bucket #1 (or the array at index number 1) will store the integer_object.

Objects stored in HashMaps are not stored in an order of any kind. object_key changes would probably cause another bucket to be chosen to store the integer_object.

Looping over a HashMap reveals the order the objects were stored in the HashMap. That order appears random and nothing close to sorted in any manner.

Sorting a HashMap

To sort the HashMap the following methodology is offered. It is not the most efficient method. The technique is meant to be illustrative for the novice user.

The initial step is to retrieve all objects from the HashMap and store them in your own array. Your array will then be sorted. It is worth noting that a HashMap itself cannot be sorted, but the data within it can be sorted.

Java provides a sortable ArrayList class. This class is an array that can be sorted. Unfortunately many of the method names in ArrayList do not match those in the Vector class. I was always trying to remember, do I use add or addElement to add an item to an ArrayList. To combat this problem I created a class extending ArrayList and implements many of the method names found in the Vector class. The class I created is called "sarray" and 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 );
  }
}

The sarray class is sortable since it inherits the capabilities of the ArrayList class. You utilize the Collections class in Java to perform the actual sort.

You must remember that when sorting a sarray in Java using the Collections class ALL objects stored in the sarray must implement the Comparable interface.

To accomplish this I created another useful class called sortable. sortable implements the Comparable interface, thus allowing objects of this type to be sortable by the Collections class.

Note: Objects stored in a sortable object's key field must implement the Comparable interface. String objects, Integer objects, Double objects, and many other Java objects aer suitable.

The sortable object source code 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

The following example shows how to use the above described material to sort a Java HashMap.

HashMap hash           = new HashMap ( 4 );
String    object_key     = "ZXC";
Integer   integer_object = new Integer ( 890 );
hash.put ( object_key , integer_object );
object_key     = "QWE";
integer_object = new Integer ( 111 );
hash.put ( object_key , integer_object );
object_key     = "JKL";
integer_object = new Integer ( 555 );
hash.put ( object_key , integer_object );

Three objects are stored in the hash to be sorted. We want to sort by the object_key. Thus, we retrieve all objects from the HashMap and put them into a sarray; perform the sort; and print:

// Create an sarray object.
sarray my_array = new sarray();
// loop over the keys
// Or loop over the elements with:
for ( Iterator e = ( (Collection) hash.values() ).iterator()  ; e.hasNext() ; )
{
// retrieve object_key
String object_key = (String) e.next();
// retrieve object
Integer integer_object = (Integer) hash.get ( object_key );
// build a sortable object
sortable s = new sortable ( object_key , integer_object );
// add the sortable object to the sarray
my_array.add ( s );
}
// sort
Collections.sort ( my_array );
// print
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 );
}