Simple Linear Probing Hash Table Class
/*
* Title: class LinearHashTable
* Description: A simple hash table class implementation using linear probing.
* 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 LinearHashTable
{
/**
* Helper class used to store a hash table entry (a key/value pair).
* 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 Entry
{
/**
* Key object.
*/
public Object key;
/**
* Data object.
*/
public Object val;
/**
* Constructor for an Entry object
*
*@param key key object reference
*@param val data object reference
*/
public Entry(Object key, Object val)
{
this.key = key;
this.val = val;
}
}
/**
* Array of Entry references used as the hash table data structure.
* By default all elements are initialised to null.
*/
private Entry[] data;
/**
* Special entry used to mark a deleted entry in the array.
* Entries have to be marked deleted in order to manage the
* probing correctly, if not then a probe for an entry would
* not be able to determine whether a null marks the end of the
* probe or whether it is a previously valid entry that has been
* removed and the entry being searched for appears later on.
*/
private static final Entry DELETED = new Entry("", "");
/**
* Size of array and, hence, number of entries allowed in table.
*/
private int tableSize;
/**
* Default table size.
*/
private static final int TABLESIZE = 100;
/**
* Construct table with default array size.
*/
public LinearHashTable()
{
this(TABLESIZE);
}
/**
* Construct table with given array size. The size fixes the maximum
* number of values that can be stored in the table.
*
* @param size size of table array
*/
public LinearHashTable(int size)
{
tableSize = size;
data = new Entry[tableSize];
}
/**
* Put a key/value pair into the table by hashing the key to get the array
* index at which the search for an empty slot (probing) should start.
* Probing is actually carried out by calling a private helper method.
* If an existing element with the same key is present then overwrite its value,
* otherwise add element in an empty slot (either holding null or the DELETED
* entry).
*
*@param key key object reference
*@param val data object reference
*/
public void put(Object key, Object val)
{
int index = findEntry(key, true);
Entry entry = data[index];
if ((entry == null) || (entry == DELETED))
{
data[index] = new Entry(key, val);
}
else
{
entry.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)
{
int index = findEntry(key, false);
if ((index != -1) && (data[index] != null))
{
return data[index].val;
}
else
{
return null;
}
}
/**
* Remove a key/value pair from table if present, otherwise make no change.
* Removing is actually done by marking the relevant array element as
* DELETED, by storing a reference to the DELETED entry into it. The array
* element cannot be simply set to null to ensure that following elements can still
* be found by probing (when probing, finding a null value terminates the
* probe).
*
*@param key key object reference
*/
public void remove(Object key)
{
int index = findEntry(key, false);
if ((index != -1) && (data[index] != null))
{
data[index] = DELETED;
}
}
/**
* Given a key, use a hash function to obtain the array index
* 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 element corresponding to key
*/
private int getIndex(Object key)
{
return Math.abs(key.hashCode() % tableSize);
}
/**
* Helper method to find (probe for) an entry in the table array and
* return its index.
* Probing stops when either null or an entry with a matching key
* is found. If stopAtDeleted is true then the search additionally
* stops when a DELETED entry is found. This allows the method to be
* used by all of the get/put/remove methods, avoiding duplication of
* code and keeping all probing code in a single method.
* While probing, the array is treated as a circular array. Probing moves
* forward one array element at a time. Alternative strategies such as
* quadratic probing could be implemented.
*
* @param key key object reference
* @param stopAtDeleted flag to determine whether search should stop
* when a DELETED entry is found.
*
* @return index of array element where search stops, or -1 if search
* wraps around to start and no unused or not DELETED entry found.
*/
private int findEntry(Object key, boolean stopAtDeleted)
{
int index = getIndex(key);
int probe = index;
for (int i = 0; i < tableSize; i++)
{
if (data[index] == null)
{
return index;
}
if (stopAtDeleted && (data[index] == DELETED))
{
return index;
}
if (data[index] != DELETED)
{
if (data[index].key.equals(key))
{
return index;
}
}
index = (index + 1) % tableSize;
}
return -1;
}
}
JUnit test class for class LinearHashTable
/*
* Title: class LinearHashTableTest
* Description: JUnit test class for LinearHashTable 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 LinearHashTableTest extends TestCase
{
private LinearHashTable empty ;
private LinearHashTable one ;
private LinearHashTable several ;
private LinearHashTable many ;
private static final int MANYSIZE = 100 ;
public LinearHashTableTest(String s)
{
super(s) ;
}
public void setUp()
{
empty = new LinearHashTable() ;
one = new LinearHashTable() ;
one.put("One",new Integer(1)) ;
several = new LinearHashTable() ;
several.put("One",new Integer(1)) ;
several.put("Two",new Integer(2)) ;
several.put("Three",new Integer(3)) ;
many = new LinearHashTable(MANYSIZE) ;
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 = MANYSIZE ; i > -1 ; i--)
{
many.remove(""+i) ;
assertNull("Check many remove",many.get(""+i)) ;
}
many.put("1000",new Integer(1000)) ;
assertEquals("Check put after delete",new Integer(1000),many.get("1000")) ;
}
public static Test suite()
{
return new TestSuite(LinearHashTableTest.class) ;
}
public static void main (String[] args)
{
junit.textui.TestRunner.run(suite()) ;
}
}