// An implementation of hashtables, using external chaining
// Keys need not be comparable.
// (c) 1998, 2001 duane a. bailey
package structure;
import java.util.Iterator;
import java.lang.Math;
//+interface
/**
* This class implements a hash table whose collisions are resolved
* through external chaining. Values used as keys in this structure
* must have a hashcode method that returns the same value when two
* keys are "equals". Initially, a hash table of suggested size is
* allocated.
*
* Example Usage:
*
* To create a hashtable by reading a collection of words and
* definitions from System.in we could use the following:
*
*
* public static void main (String[] argv){
* ChainedHashtable dict = new {@link #ChainedHashtable()};
* ReadStream r = new ReadStream();
* String word, def;
* System.out.println("Enter a word: ");
* while(!r.eof()){
* word = r.readLine();
* System.out.println("Enter a definition: ");
* def = r.readLine();
* dict.{@link #put(Object,Object) put(word,def)};
* System.out.println("Enter a word: ");
* }
* System.out.println(dict);
* }
*
* @version $Id: ChainedHashtable.java,v 1.1 2005/09/22 22:01:14 terescoj Exp $
* @author, 2001 duane a. bailey
* @see Hashtable
*/
public class ChainedHashtable extends AbstractMap implements Map
{
//-interface
//+constructor
//+private
/**
* The array of chains used to store values.
*/
protected List> data[];
/**
* The number of key-value pairs stored within the table.
*/
protected int count;
/**
* The length of the table.
*/
protected int capacity;
//-private
//+interface
/**
* Constructs a hashtable with capacity for at size elements
* before chaining is absolutely required.
*
* @pre size > 0
* @post constructs a new ChainedHashtable
*
* @param size The number of entries initially allocated.
*/
public ChainedHashtable(int size)
//-interface
{
data = (List>[])new Object[size];
capacity = size;
count = 0;
}
//-constructor
//+interface
/**
* Constructs a reasonably large hashtable.
*
* @post constructs a new ChainedHashtable
*/
public ChainedHashtable()
//-interface
{
this(997);
}
//+interface
/**
* Removes the values from the hashtable.
*
* @post removes all the elements from the ChainedHashtable
*/
public void clear()
//-interface
{
int i;
for (i = 0; i < capacity; i++) {
data[i].clear();
}
count = 0;
}
//+interface
/**
* Computes the number of elements stored within the hashtable.
*
* @post returns number of elements in hash table
*
* @return The number of elements within the hash table.
*/
public int size()
//-interface
{
return count;
}
//+interface
/**
* Returns true if no elements are stored within the table.
*
* @post returns true iff hash table has 0 elements
*
* @return True iff size() == 0.
*/
public boolean isEmpty()
//-interface
{
return size() == 0;
}
protected List> locate(K key)
{
int hash = Math.abs(key.hashCode() % capacity);
if (data[hash] == null) data[hash] = new SinglyLinkedList>();
return data[hash];
}
//+interface
//+contains
/**
* Returns true if a specific value appears within the table.
*
* @pre value is non-null Object
* @post returns true iff hash table contains value
*
* @param value The value sought.
* @return True iff the value appears within the table.
*/
public boolean containsValue(V value)
//-interface
{
Iterator elements = iterator();
while (elements.hasNext())
{
if (value.equals(elements.next())) return true;
}
return false;
}
//-contains
//+interface
/**
* Returns true iff a specific key appears within the table.
*
* @pre value is non-null key
* @post returns true if key appears in hash table
*
* @param key The key sought.
* @return True iff the key sought appears within table.
*/
public boolean containsKey(K key)
//-interface
{
List> l = locate(key);
return l.contains(new Association(key,null));
}
//+interface
/**
* Returns an iterator that traverses over the values of the
* hashtable.
*
* @post returns iterator to traverse hash table
*
* @return A value iterator, over the values of the table.
*/
public Iterator iterator()
//-interface
{
return new ValueIterator(new ChainedHashtableIterator(data));
}
public Set keySet()
{
Set result = new SetList();
Iterator i = new KeyIterator(new ChainedHashtableIterator(data));
while (i.hasNext())
{
result.add(i.next());
}
return result;
}
public Set> entrySet()
{
Set> result = new SetList>();
Iterator> i = new ChainedHashtableIterator(data);
while (i.hasNext())
{
result.add(i.next());
}
return result;
}
public Structure values()
{
List result = new SinglyLinkedList();
Iterator i = new ValueIterator(new ChainedHashtableIterator(data));
while (i.hasNext())
{
result.add(i.next());
}
return result;
}
//+interface
/**
* Get the value associated with a key.
*
* @pre key is non-null Object
* @post returns value associated with key, or null
*
* @param key The key used to find the desired value.
* @return The value associated with the desired key.
*/
public V get(K key)
//-interface
{
List> l = locate(key);
Association a = l.remove(new Association(key,null));
if (a == null) return null;
l.addFirst(a);
return a.getValue();
}
//+interface
/**
* Get an iterator over the keys of the hashtable.
*
* @post returns iterator to traverse the keys of hash table
*
* @return An iterator over the key values appearing within table.
*/
public Iterator keys()
//-interface
{
return new KeyIterator(new ChainedHashtableIterator(data));
}
//+interface
//+put
/**
* Place a key-value pair within the table.
*
* @pre key is non-null object
* @post key-value pair is added to hash table
*
* @param key The key to be added to table.
* @param value The value associated with key.
* @return The old value associated with key if previously present.
*/
public V put(K key, V value)
//-interface
{
List> l = locate(key);
Association newa = new Association(key,value);
Association olda = l.remove(newa);
l.addFirst(newa);
if (olda != null)
{
return olda.getValue();
}
else
{
count++;
return null;
}
}
//-put
//+interface
/**
* Remove a key-value pair from the table.
*
* @pre key is non-null object
* @post removes key-value pair associated with key
*
* @param key The key of the key-value pair to be removed.
* @return The value associated with the removed key.
*/
public V remove(K key)
//-interface
{
List> l = locate(key);
Association pair = l.remove(new Association(key,null));
if (pair == null) return null;
count--;
return pair.getValue();
}
//+interface
/**
* Generate a string representation of the chained hash table.
*
* @post returns a string representation of hash table
*
* @return The string representing the table.
*/
public String toString()
//-interface
{
StringBuffer s = new StringBuffer();
int i;
s.append("> hi = new ChainedHashtableIterator(data);
while (hi.hasNext()) {
Association a = hi.next();
s.append(" "+a.getKey()+"="+a.getValue());
}
s.append(">");
return s.toString();
}
//+interface
}
//-interface