// An implementation of Dictionaries, using hash tables.
// Keys need not be comparable, but they must have hashcode methods.
// (c) 1998, 2001 duane a. bailey
package structure;
import java.util.Iterator;
import java.lang.Math;
//+interface
/**
* Implements a dictionary as a table of hashed key-value pairs.
* Collisions are resolved through linear probing. Values used
* as keys in this structure must have a hashcode method that returns
* the same value when two keys are "equals". Initially, a table of suggested
* size is allocated. It will be expanded as the load factor (ratio of
* pairs to entries) grows.
*
* 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){
* Hashtable dict = new {@link #Hashtable()};
* 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: Hashtable.java,v 1.3 2005/11/30 19:39:44 terescoj Exp $
* @author, 2001 duane a. bailey
* @see ChainedHashtable
*/
public class Hashtable implements Map
{
//-interface
//+constructor
//+private
/**
* A single key-value pair to be used as a token
* indicating a reserved location in the hashtable.
* Reserved locations are available for insertion,
* but cause collisions on lookup.
*/
protected static Association reserved =
new Association("reserved",null);
/**
* The data associated with the hashtable.
*/
protected Association data[];
/**
* The number of key-value pairs in table.
*/
protected int count;
/**
* The size of the hashtable
*/
protected int capacity;
/**
* Load factor that causes rehashing of the table.
*/
protected final double loadFactor = 0.6;
//-private
//+interface
/**
* Construct a hash table that is capable of holding at least
* initialCapacity values. If that value is approached, it will
* be expanded appropriately. It is probably best if the capacity
* is prime. Table is initially empty.
*
* @pre initialCapacity > 0
* @post constructs a new Hashtable
* holding initialCapacity elements
*
* @param initialCapacity The initial capacity of the hash table.
*/
public Hashtable(int initialCapacity)
//-interface
{
data = (Association[]) new Association[initialCapacity];
capacity = initialCapacity;
count = 0;
}
//+interface
/**
* Construct a hash table that is initially empty.
*
* @post constructs a new Hashtable
*/
public Hashtable()
//-interface
{
this(997);
}
//-constructor
//+interface
//+clear
/**
* Remove all key-value pairs from hashtable.
*
* @post removes all elements from Hashtable
*/
public void clear()
//-interface
{
int i;
for (i = 0; i < capacity; i++) {
data[i] = null;
}
count = 0;
}
//-clear
//+interface
//+size
/**
* Return the number of key-value pairs within the table.
*
* @post returns number of elements in hash table
*
* @return The number of key-value pairs currently in table.
*/
public int size()
//-interface
{
return count;
}
//-size
//+interface
//+isEmpty
/**
* Determine if table is empty.
*
* @post returns true iff hash table has 0 elements
*
* @return True if table is empty.
*/
public boolean isEmpty()
//-interface
{
return size() == 0;
}
//-isEmpty
//+interface
//+contains
//+containsMethods
/**
* 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 i = iterator();
while (i.hasNext())
{
V nextValue = i.next();
// the value we seek?
if (nextValue != null &&
nextValue.equals(value)) return true; // yes!
}
// no value found
return false;
}
//-contains
//+interface
/**
* Returns true iff a specific key appears within the table.
*
* @pre key is a non-null Object
* @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
{
int hash = locate(key);
return data[hash] != null && data[hash] != reserved;
}
//-containsMethods
//+interface
//+elements
/**
* Returns a traversal that traverses over the values of the
* hashtable.
*
* @post returns traversal to traverse hash table
*
* @return A value traversal, over the values of the table.
*/
public Iterator iterator()
//-interface
{
return null; //new ValueIterator(new HashtableIterator(data));
}
//-elements
//+interface
//+get
/**
* 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
{
int hash = locate(key);
Association a = data[hash];
if (a == null || a == reserved) return null;
return data[hash].getValue();
}
//-get
//+keys
/**
* Get a traversal over the keys of the hashtable.
*
* @post returns traversal to traverse the keys of hash table;
*
* @return a traversal over the key values appearing within table.
*/
public Iterator keys()
{
return new KeyIterator(new HashtableIterator(data));
}
//-keys
//+locate
protected int locate(K key)
{
// compute an initial hash code
int hash = Math.abs(key.hashCode() % capacity);
// keep track of first unused slot, in case we need it
int firstReserved = -1;
while (data[hash] != null)
{
if (data[hash] == reserved) {
// remember reserved slot if we fail to locate value
if (firstReserved == -1) firstReserved = hash;
} else {
// value located? return the index in table
if (key.equals(data[hash].getKey())) return hash;
}
// linear probing; other methods would change this line:
hash = (1+hash)%capacity;
}
// return first empty slot we encountered
if (firstReserved == -1) return hash;
else return firstReserved;
}
//-locate
//+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
{
if (loadFactor*capacity <= (1+count)) {
extend();
}
int hash = locate(key);
Association a = data[hash];
if (a == null || a == reserved)
{ // logically empty slot; just add association
data[hash] = new Association(key,value);
count++;
return null;
} else {
// full slot; add new and return old value
V oldValue = a.getValue();
a.setValue(value);
return oldValue;
}
}
//-put
/**
* Put all of the values found in another map into this map,
* overriding previous key-value associations.
* @param other is the source mapping
* @pre other map is valid
* @post this hashtable is augmented by the values found in other
*/
public void putAll(Map other)
{
Iterator> i = other.entrySet().iterator();
while (i.hasNext())
{
Association e = (Association)i.next();
put(e.getKey(),e.getValue());
}
}
//+interface
//+remove
/**
* 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
{
int hash = locate(key);
Association a = data[hash];
if (a == null || a == reserved) {
return null;
}
count--;
V oldValue = a.getValue();
data[hash] = reserved; // in case anyone depends on us
return oldValue;
}
//-remove
//+interface
//+rehash
/**
* @post expands the hashtable to reduce loading
*/
protected void extend()
//-interface
{
// extends the hashtable for larger capacity.
int i;
AbstractIterator> it = new HashtableIterator(data);
// BE AWARE: at this point, we can change the hash table,
// but changes to the hashtable traversal implementation might
// be problematic.
capacity = capacity*2+1;
data = (Association[]) new Association[capacity];
count = 0;
while (it.hasNext())
{
Association a = (Association)it.next();
put(a.getKey(),a.getValue());
}
}
//-rehash
//+interface
/**
* @post returns a set of Associations associated with this Map
*/
public Set> entrySet()
//-interface
{
Set> result = new SetList>();
Iterator> i = new HashtableIterator(data);
while (i.hasNext())
{
result.add(i.next());
}
return result;
}
//+interface
/**
* @post returns a Set of keys used in this Map
*/
public Set keySet()
//-interface
{
Set result = new SetList();
Iterator i = new KeyIterator(new HashtableIterator(data));
while (i.hasNext())
{
result.add(i.next());
}
return result;
}
//+interface
//+values
/**
* @post returns a Structure that contains the (possibly repeating)
* values of the range of this map.
*/
public Structure values()
//-interface
{
List result = new SinglyLinkedList();
Iterator i = new ValueIterator(new HashtableIterator(data));
while (i.hasNext())
{
result.add(i.next());
}
return result;
}
//-values
//+interface
//+toString
/**
* Generate a string representation of the 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("");
return s.toString();
}
//-toString
//+interface
}
//-interface