Simple Chained Hash Table Class
/*
* Title: class HashTable
* Description: A simple chained hash table class implementation.
* For a detailed description about the design and implementation
* of hash tables see the text book chapter 18.
* Copyright: Copyright (c) 2002
* Company: Dept. of Computer Science, University College London
* @author Graham Roberts
* @version 1.0 01-Mar-02
*/
public class HashTable
{
/**
* Helper class used to implement chains. As this is a private helper
* class it is acceptable to have public instance variables. Instances of this
* class are never made available to client code of the hash table.
*/
private static class Node
{
/**
* Next node in chain.
*/
public Node next;
/**
* Key object.
*/
public Object key;
/**
* Data object.
*/
public Object val;
/**
* Constructor for the Node object
*
*@param next next node in chain reference or null
*@param key key object reference
*@param val data object reference
*/
public Node(Node next, Object key, Object val)
{
this.next = next;
this.key = key;
this.val = val;
}
}
/**
* Array of mode references used to store the chains.
* By default all elements are initialised to null.
*/
private Node[] data;
/**
* Size of array and, hence, number of chains allowed.
*/
private static final int SIZE = 100;
/**
* Constructor for the HashTable class.
*/
public HashTable()
{
data = new Node[SIZE];
}
/**
* Put a key/value pair into the table by hashing the key to get the array
* index of the chain that should hold the node containing the pair.
* If an existing node with the same key is present then overwrite its value,
* otherwise add a new node.
*
*@param key key object reference
*@param val data object reference
*/
public void put(Object key, Object val)
{
int index = getIndex(key);
Node node = find(key, data[index]);
// Use helper method to determine if node with same key is already in
// chain. If not, add a new node to head of chain.
if (node == null)
{
data[index] = new Node(data[index], key, val);
}
else
{
// Otherwise update data value of existing node.
node.val = val;
}
}
/**
* Given a key object, return a data object from the table or
* null if it is not found.
*
*@param key key object reference
*@return data object reference or null if no object found
*/
public Object get(Object key)
{
Node temp = find(key, data[getIndex(key)]);
if (temp != null)
{
return temp.val;
}
else
{
return null;
}
}
/**
* Remove a key/value pair from table if present, otherwise make no change.
*
*@param key key object reference
*/
public void remove(Object key)
{
int index = getIndex(key);
Node ref = data[index];
Node previous = null;
while (ref != null)
{
if ((ref.key).equals(key))
{
if (previous == null)
{
data[index] = ref.next;
}
else
{
previous.next = ref.next;
}
return;
}
previous = ref;
ref = ref.next;
}
}
/**
* Given a key, use a hash function to obtain the array index of the chain
* corresponding to the key.
* The hashCode method inherited (and possibly overridden)
* from class Object is called to do the hashing, with the returned
* value constrained to the hash table array bounds.
* The distribution of objects in the hash table will depend
* on the quality of the hash function implemented by hashCode.
*
*@param key reference to object to be hashed
*@return array index of chain corresponding to key
*/
private int getIndex(Object key)
{
return Math.abs(key.hashCode() % data.length);
}
/**
* Find node given a key and a chain to search.
*
*@param key key object reference
*@param ref node object reference where search will start
*@return node object holding key or null if not found
*/
private Node find(Object key, Node ref)
{
while (ref != null)
{
if ((ref.key).equals(key))
{
return ref;
}
ref = ref.next;
}
return null;
}
}
JUnit test class for class HashTable
/*
* Title: class HashTableTest
* Description: JUnit test class for HashTable class
* Copyright: Copyright (c) 2002
* Company: Dept. of Computer Science, University College London
* @author Graham Roberts
* @version 1.0 01-Mar-02
*/
import junit.framework.* ;
public class HashTableTest extends TestCase
{
private HashTable empty ;
private HashTable one ;
private HashTable several ;
private HashTable many ;
private static final int MANYSIZE = 500 ;
public HashTableTest(String s)
{
super(s) ;
}
public void setUp()
{
empty = new HashTable() ;
one = new HashTable() ;
one.put("One",new Integer(1)) ;
several = new HashTable() ;
several.put("One",new Integer(1)) ;
several.put("Two",new Integer(2)) ;
several.put("Three",new Integer(3)) ;
many = new HashTable() ;
for (int i = 0 ; i < MANYSIZE ; i++)
{
many.put(""+i,new Integer(i)) ;
}
}
public void testGet()
{
assertEquals("Check <One,1>",new Integer(1),one.get("One")) ;
assertEquals("Check <One,1>",new Integer(1),several.get("One")) ;
assertEquals("Check <Two,2>",new Integer(2),several.get("Two")) ;
assertEquals("Check <Three,3>",new Integer(3),several.get("Three")) ;
}
public void testGetMany()
{
for (int i = 0 ; i < MANYSIZE ; i++)
{
assertEquals("Check many contents",new Integer(i),many.get(""+i)) ;
}
}
public void testGetNotInTable()
{
assertNull("Check null returned",empty.get("One")) ;
assertNull("Check null returned",one.get("Two")) ;
assertNull("Check null returned, different case letter",several.get("three")) ;
assertNull("Check null returned, wrong type of object",one.get(new Double(2.3))) ;
}
public void testPutChangeValue()
{
one.put("One",new Integer(10)) ;
assertEquals("Check one <One,10>",new Integer(10),one.get("One")) ;
several.put("One",new Integer(10)) ;
assertEquals("Check several <One,10>",new Integer(10),several.get("One")) ;
several.put("Two",new Integer(20)) ;
assertEquals("Check several <Two,20>",new Integer(20),several.get("Two")) ;
several.put("Three",new Integer(30)) ;
assertEquals("Check several <Three,30>",new Integer(30),several.get("Three")) ;
}
public void testPutChangeValueMany()
{
for (int i = 0 ; i < MANYSIZE ; i++)
{
many.put(""+i,new Integer(i+1)) ;
assertEquals("Check many change value",new Integer(i+1),many.get(""+i)) ;
}
}
public void testRemove()
{
empty.remove("One") ;
assertNull("Check null returned",empty.get("One")) ;
one.remove("One") ;
assertNull("<One> removed, check null returned",one.get("One")) ;
several.remove("One") ;
assertNull("<One> removed, check null returned",several.get("One")) ;
several.remove("Four") ;
assertEquals("Check <Two> still in table",new Integer(2),several.get("Two")) ;
assertEquals("Check <Three> still in table",new Integer(3),several.get("Three")) ;
several.remove("Two") ;
assertNull("<Two> removed, check null returned",several.get("Two")) ;
several.remove("Three") ;
assertNull("<Three> removed, check null returned",several.get("Three")) ;
}
public void testRemoveMany()
{
for (int i = 0 ; i < MANYSIZE ; i++)
{
many.remove(""+i) ;
assertNull("Check many remove",many.get(""+i)) ;
}
}
public static Test suite()
{
return new TestSuite(HashTableTest.class) ;
}
public static void main (String[] args)
{
junit.textui.TestRunner.run(suite()) ;
}
}