Click here to Skip to main content
13,194,662 members (70,519 online)
Click here to Skip to main content
Add your own
alternative version


10 bookmarked
Posted 20 Jun 2002

Implementing Ordering in a Hashtable

, 20 Jun 2002
Rate this:
Please Sign up or sign in to vote.
A Hashtable provides a key-value lookup functionality. Hashtable in java.util.Hashtable is not guaranteed to Enumerate (or Iterate) keys in the same order as they were put in. This article explains how to implement ordering in a Hashtable.



Hashtables are a convenient choice when it comes to searching, particularly because in the collection, an element is stored depending upon the information in the element itself. This information is extracted in an (almost) exclusive way by use of hash-functions. While hashtables are a useful data structure, they do lack one thing - the order in which elements are stored in a hashtable is not preserved. That means, given a Hashtable, I can get an Iterator on the set of Hashtable keys, (by keySet() method) or I can get an Enumeration (by keys() method). But none of the two is guaranteed to retrieve elements in the same order as they were put in. This is plausible because Hashtables have generally been used more for their hashing capability rather than anything else.

Why Ordering

In our project, we had a situation where the results returned by an SQL query was stored in a Hashtable (so that it could be searched easily later). But at the same time, we needed to preserve the ordering returned by SQL, since ordering at database side is much faster than doing it programmatically. Moreover, database can handle multiple and complex sort orders quite well (using the order by clause). Here was a situation where we needed to implement ordering capabilities into a Hashtable.

The Algorithm

The obvious place to look was into the source code of the Java programming language, which gave us The solution came up right in the form of writing another class - which uses some techniques like inner classes.

The algo was simple: Take a Hashtable and a Vector. Whenever you put the objects into the Hashtable, put the corresponding keys in the Vector. Since Vector is ordered, Enumerations or Iterators on it are guaranteed to traverse the keys in the same order as they were put in. So if later you need to iterate through all the objects in the Hashtable (in the order they were put in), just take hold of the Iterator of the Vector and get the corresponding objects from the Hashtable. There you have an OrderedHashtable! Of course it still has the hashing capabilities of a Hashtable, and you can of course retrieve an object directly if you have its key (same way as in a Hashtable). Only new thing is that, Iterator (or Enumeration) is guaranteed to be ordered.

Some Issues to be Careful of!

Of course, there are some important things to take care of, like synchronization. Since items can be added as well as removed from OrderedHashtable, we need to make sure that the internal Vector and Hashtable of the class remains thread-safe. If two threads access it at the same time and one adds and other deletes the same object, it could leave the Hashtable in an arbitrary, indeterminate state, where either the Vector or the Hashtable or the internal COUNT of number of elements (or all of the three) may be incorrect. This calls for certain sections of code to be synchronized.

Similarly, there is another important issue of overflow. Both Hashtable and Vector are resizable, but the way their size increases is different. In Hashtable, we have a loadfactor which specifies how full the Hashtable is allowed to become before the size increases (by calling the rehash() method). Whenever the number of entries in a Hashtable exceeds the product of loadfactor and current capacity, the capacity is increased by twice the current capacity. Default values of initial capacity and loadfactor for Hashtable are 10 and 0.75 respectively. So in the default case, when the 9th object is put in, the Hashtable is doubled to 20.

The Vector however operates differently. In a Vector, you can specify a capacityIncrement value. Whenever the Vector becomes full, its capacity is incremented by capacityIncrement (or doubled in case the capacityIncrement is 0). Default values of initialcapacity and capacityIncrement for a Vector are 10 and 0. Here in the default case, the size grows only when the 11th object is put in and the size grows to 20. Again when 21st object comes in, size is doubled to 40 and so on. One would need to be careful in put() and get() methods to handle this correctly. Other issues like deletion etc, can also be handled easily with slight care.


Now comes the magic of inner classes. Iterators and Enumerations are implemented as inner classes. (Obviously, how else?). When either Enumeration (enumerateKeys() method) or an Iterator (iterateKeys() method) is called, it is this inner class which iterates on a private Vector and returns the corresponding object from the Hashtable and makes sure to keep it within error limits.


A final thought that comes to mind immediately after this is - "What is the performance overhead of implementing this ordering?" Since we are using a Vector, which is known to be one of the slow performing classes among all Java classes, we do expect our OrderedHashtable to be slower than Hashtable. I have included two small test files apart from the source code of OrderedHashtable, in the download package. The code is well commented, and I hope it is easily understood. While one of them ( establishes the fact that ordering is properly implemented (after all that is what this article is about!) the other file ( does some basic performance testing. It populates a Hashtable and an OrderedHashtable with one million objects and compares the time spent in accessing them. While prints the items retrieved to the standard output stream to show that they are indeed in the same order as they were inserted, doesn't print the objects themselves. There are two reasons for this - one, I don't want to be flooding the screen with two million lines, and second (more importantly) the System.out.println() will itself take some time, whereas we just want to compare the time spent in accessing the elements of the Hashtables.

On my system, a number of trial runs indicate that for very large values (like 1 million), the time required by both are almost same (31 milliseconds). This is surprising because I had expected the Vector to slow down the OrderedHashtable quite a bit. Yes, once in a while, the OrderedHashtable takes twice the time as that of Hashtable, but such instances are rare. You are welcome to test-run it on your system. Your mileage may vary because of the system, the system settings and the current load on it. If there are any issues, comments, suggestions, or new findings, you are most welcome to enlighten me and other fellow programmers at CP.

Final Notes

The source code presented here implements most of the methods of java.util.Hashtable. But there are a few methods which have been left out, some because they are not in line with the concept of ordering (e.g. those which return a Set), and some because of their being declared as protected or private in the underlying Hashtable class (e.g. rehash()). However, enough methods have been implemented to provide the full functionality of a Hashable (for almost all situations) while maintaining ordering at the same time. But if you feel that it should be having some other methods also, which could improve the functionality/usefulness of the OrderedHashtable, then you are most welcome to provide any feedback and discuss it with the CP community. :-)

Thanks for reading the article. Have a great day!


This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


About the Author

Animesh Srivastava
Web Developer
India India
C/C++ Win32 developer, working on Java! Wink | ;)

You may also be interested in...

Comments and Discussions

GeneralNice idea but I was doing some search... Pin
Olivier Voutat1-Oct-07 4:19
memberOlivier Voutat1-Oct-07 4:19 
GeneralNice... but here's something a bit cleaner Pin
wlburgess7-Jan-06 11:16
memberwlburgess7-Jan-06 11:16 
First of all, thank you to Animesh for his solution, and getting our creative juices flowing by presenting an interesting solution to a pre 1.4 problem.

I agree with the comments that this class is heavy on space usage, but time-wise the performance is not bad (the trade-off here is space).
For small usages, its not bad, and it still has merit as thread-safe even with the existance of LinkedHashMap (needs help being thread safe) since 1.4.2.

One thing I noticed was that the class was not taking full use of inheritance and had not only extended the Hashtable class but contained a Hashtable object...

So I shortened things a bit and made calls to non-overided methods work at the same time.

There's lots of ways to do something similar but this is still of interest.

Here's the updated code:
import java.util.*;

/* This class is used to combine the key-value lookup capabilities of a
Hashtable along with order preserving capabilities of a Vector.
Iterator on a Set of Hashtable keys, obtained by keySet() or an
Enumeration obtained by keys() method, both are not guaranteed to
iterate in the same order as the values were put in.

This class behaves like a queue, (FIFO). Objects are returned in the
same order they were put in.

@author Animesh Srivastava
@author Wayne Burgess

// friendly only
public class OrderedHashtable extends Hashtable {

//member variables
private Vector mSerialOrder;

/** Public Constructor */
public OrderedHashtable()
this.mSerialOrder = new Vector();

/** Clears this OrderedHashtable so that it has no keys.
* @exception UnsupportedOperationException - clear is not supported by
* the underlying Interface java.util.Map.
synchronized public void clear() throws UnsupportedOperationException

/** Removes the key (and its corresponding value) from this OrderedHashtable.
* Does nothing if key is not in the OrderedHashtable.
* @param key - the key that needs to be removed.
* @returns the value to which the key had been mapped in this OrderedHashtable,
* or null if the key did not have a mapping.
synchronized public Object remove(Object key)
return super.remove(key);

/** Maps the specified key to the specified value in this OrderedHashtable.
* Neither the key nor the value can be null. If the key already exists
* then the ordering is not changed. If it does not exists then it is added
* at the end of the OrderedHastable.
* @param key - the key.
* @param value - the value.
* @exception - NullPointerException, if the key or value is null.
* @returns the previous value of the specified key in this hashtable, or
* null if it did not have one.
synchronized public Object put(Object key,Object value) throws NullPointerException
Object toReturn = super.put(key,value);
if(toReturn == null)
return toReturn;

/** Returns an Iterator to iterate through the keys of the OrderedHashtable.
* Iteration will occur in the same order as the keys were put in into the
* OrderedHashtable.
* The remove() method of Iterator interface is optional in jdk1.3 and hence
* not implemented.
public Iterator iterateKeys() {
return new Enumerator();

/** Returns an Enumeration to enumerate through the keys of the OrderedHashtable.
* Enumeration will occur in the same order as the keys were put in into the
* OrderedHashtable.
public Enumeration enumerateKeys() {
return new Enumerator();

/** Returns a string representation of the OrderedHashtable. */
public String toString()
StringBuffer s = new StringBuffer();
s.append("{ ");
Object key=null;
int i=0;
while(i<this.mSerialOrder.size()) {
key = this.mSerialOrder.elementAt(i++);
s.append("; ");
s.append(" }");
return s.toString();

//inner class,
private class Enumerator implements Enumeration, Iterator
int COUNT = mSerialOrder.size(); //number of elements in the Vector
int SERIAL = 0; //keep track of the current element

public boolean hasMoreElements() {
return SERIAL < COUNT;

public Object nextElement() {
synchronized (OrderedHashtable.this) {
throw new NoSuchElementException("OrderedHashtable Enumerator");
return mSerialOrder.elementAt(SERIAL++);

public boolean hasNext() {
return hasMoreElements();

public Object next() {
return nextElement();

//optional in jdk1.3
public void remove() {

* Copies all of the mappings from the specified Map to this Hashtable
* These mappings will replace any mappings that this Hashtable had for any
* of the keys currently in the specified Map.
* If the map is an instance of OrderedHashtable, then the copy will have
* the same ordering.
* @param m Mappings to be stored in this map.
* @throws NullPointerException if the specified map is null.
synchronized public void putAll(Map m) throws NullPointerException
// if its one of "us" its ordered, make sure copy is ordered too!
if(m instanceof OrderedHashtable) {
OrderedHashtable c = (OrderedHashtable)m;
Iterator itr = c.iterateKeys();
while (itr.hasNext())
Object o =;
put(o, c.get(o));
else // the map is not ordered, so add at will
Iterator itr = m.entrySet().iterator();

while (itr.hasNext())
Map.Entry e = (Map.Entry);
// Optimize in case the Entry is one of our own.
put(e.getKey(), e.getValue());

Wayne L. Burgess
TEN-K Computer Services Inc.
Generali need codes for a project Pin
aaku21-Dec-05 6:46
memberaaku21-Dec-05 6:46 
GeneralNice one Pin
Manish Hatwalne10-Sep-02 22:02
memberManish Hatwalne10-Sep-02 22:02 
GeneralA bit crazy Pin
Mike Asher22-Jun-02 7:58
memberMike Asher22-Jun-02 7:58 
GeneralRe: A bit crazy Pin
Anonymous22-Dec-03 4:42
sussAnonymous22-Dec-03 4:42 
GeneralRe: A bit crazy Pin
newkidtown8-Sep-04 12:16
membernewkidtown8-Sep-04 12:16 
GeneralIncorrect Pin
Mike Asher10-Sep-04 8:33
memberMike Asher10-Sep-04 8:33 
Generalcool Pin
Rishabh21-Jun-02 5:04
memberRishabh21-Jun-02 5:04 
GeneralRe: cool Pin
JamesCook20-Aug-03 3:27
memberJamesCook20-Aug-03 3:27 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.171018.2 | Last Updated 21 Jun 2002
Article Copyright 2002 by Animesh Srivastava
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid