structure
Class Hashtable

java.lang.Object
  |
  +--structure.Hashtable
All Implemented Interfaces:
Map

public class Hashtable
extends java.lang.Object
implements Map

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 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.put(word,def);
	    System.out.println("Enter a word: ");
	}
	System.out.println(dict);
 }
 

See Also:
ChainedHashtable

Field Summary
protected  int capacity
          The size of the hashtable
protected  int count
          The number of key-value pairs in table.
protected  Association[] data
          The data associated with the hashtable.
protected  double loadFactor
          Load factor that causes rehashing of the table.
protected static Association reserved
          A single key-value pair to be used as a token indicating a reserved location in the hashtable.
 
Constructor Summary
Hashtable()
          Construct a hash table that is initially empty.
Hashtable(int initialCapacity)
          Construct a hash table that is capable of holding at least initialCapacity values.
 
Method Summary
 void clear()
          Remove all key-value pairs from hashtable.
 boolean containsKey(java.lang.Object key)
          Returns true iff a specific key appears within the table.
 boolean containsValue(java.lang.Object value)
          Returns true if a specific value appears within the table.
 Set entrySet()
           
protected  void extend()
           
 java.lang.Object get(java.lang.Object key)
          Get the value associated with a key.
 boolean isEmpty()
          Determine if table is empty.
 java.util.Iterator iterator()
          Returns a traversal that traverses over the values of the hashtable.
 java.util.Iterator keys()
          Get a traversal over the keys of the hashtable.
 Set keySet()
           
protected  int locate(java.lang.Object key)
           
 java.lang.Object put(java.lang.Object key, java.lang.Object value)
          Place a key-value pair within the table.
 void putAll(Map other)
          Put all of the values found in another map into this map, overriding previous key-value associations.
 java.lang.Object remove(java.lang.Object key)
          Remove a key-value pair from the table.
 int size()
          Return the number of key-value pairs within the table.
 java.lang.String toString()
          Generate a string representation of the hash table.
 Structure values()
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface structure.Map
equals, hashCode
 

Field Detail

reserved

protected static Association reserved
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.


data

protected Association[] data
The data associated with the hashtable.


count

protected int count
The number of key-value pairs in table.


capacity

protected int capacity
The size of the hashtable


loadFactor

protected final double loadFactor
Load factor that causes rehashing of the table.

See Also:
Constant Field Values
Constructor Detail

Hashtable

public Hashtable(int initialCapacity)
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.

Parameters:
initialCapacity - The initial capacity of the hash table.

Hashtable

public Hashtable()
Construct a hash table that is initially empty.

Method Detail

clear

public void clear()
Remove all key-value pairs from hashtable.

Specified by:
clear in interface Map

size

public int size()
Return the number of key-value pairs within the table.

Specified by:
size in interface Map
Returns:
The number of key-value pairs currently in table.

isEmpty

public boolean isEmpty()
Determine if table is empty.

Specified by:
isEmpty in interface Map
Returns:
True if table is empty.

containsValue

public boolean containsValue(java.lang.Object value)
Returns true if a specific value appears within the table.

Specified by:
containsValue in interface Map
Parameters:
value - The value sought.
Returns:
True iff the value appears within the table.

containsKey

public boolean containsKey(java.lang.Object key)
Returns true iff a specific key appears within the table.

Specified by:
containsKey in interface Map
Parameters:
key - The key sought.
Returns:
True iff the key sought appears within table.

iterator

public java.util.Iterator iterator()
Returns a traversal that traverses over the values of the hashtable.

Returns:
A value traversal, over the values of the table.

get

public java.lang.Object get(java.lang.Object key)
Get the value associated with a key.

Specified by:
get in interface Map
Parameters:
key - The key used to find the desired value.
Returns:
The value associated with the desired key.

keys

public java.util.Iterator keys()
Get a traversal over the keys of the hashtable.

Returns:
a traversal over the key values appearing within table.

locate

protected int locate(java.lang.Object key)

put

public java.lang.Object put(java.lang.Object key,
                            java.lang.Object value)
Place a key-value pair within the table.

Specified by:
put in interface Map
Parameters:
key - The key to be added to table.
value - The value associated with key.
Returns:
The old value associated with key if previously present.

putAll

public void putAll(Map other)
Put all of the values found in another map into this map, overriding previous key-value associations.

Specified by:
putAll in interface Map
Parameters:
other - is the source mapping

remove

public java.lang.Object remove(java.lang.Object key)
Remove a key-value pair from the table.

Specified by:
remove in interface Map
Parameters:
key - The key of the key-value pair to be removed.
Returns:
The value associated with the removed key.

extend

protected void extend()

entrySet

public Set entrySet()
Specified by:
entrySet in interface Map

keySet

public Set keySet()
Specified by:
keySet in interface Map

values

public Structure values()
Specified by:
values in interface Map

toString

public java.lang.String toString()
Generate a string representation of the hash table.

Overrides:
toString in class java.lang.Object
Returns:
The string representing the table.