structure5
Class ChainedHashtable<K,V>

java.lang.Object
  extended by structure5.AbstractMap<K,V>
      extended by structure5.ChainedHashtable<K,V>
All Implemented Interfaces:
java.lang.Iterable<V>, Map<K,V>

public class ChainedHashtable<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, java.lang.Iterable<V>

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

See Also:
Hashtable

Field Summary
protected  int count
          The number of key-value pairs stored within the table.
protected  Vector<List<Association<K,V>>> data
          The array of chains used to store values.
 
Constructor Summary
ChainedHashtable()
          Constructs a reasonably large hashtable.
ChainedHashtable(int size)
          Constructs a hashtable with capacity for at size elements before chaining is absolutely required.
 
Method Summary
 void clear()
          Removes the values from the hashtable.
 boolean containsKey(K key)
          Returns true iff a specific key appears within the table.
 boolean containsValue(V value)
          Returns true if a specific value appears within the table.
 Set<Association<K,V>> entrySet()
           
 V get(K key)
          Get the value associated with a key.
 boolean isEmpty()
          Returns true if no elements are stored within the table.
 java.util.Iterator<V> iterator()
          Returns an iterator that traverses over the values of the hashtable.
 java.util.Iterator<K> keys()
          Get an iterator over the keys of the hashtable.
 Set<K> keySet()
           
protected  List<Association<K,V>> locate(K key)
           
 V put(K key, V value)
          Place a key-value pair within the table.
 V remove(K key)
          Remove a key-value pair from the table.
 int size()
          Computes the number of elements stored within the hashtable.
 java.lang.String toString()
          Generate a string representation of the chained hash table.
 Structure<V> values()
           
 
Methods inherited from class structure5.AbstractMap
hashCode, putAll
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface structure5.Map
equals, hashCode, putAll
 

Field Detail

data

protected Vector<List<Association<K,V>>> data
The array of chains used to store values.


count

protected int count
The number of key-value pairs stored within the table.

Constructor Detail

ChainedHashtable

public ChainedHashtable(int size)
Constructs a hashtable with capacity for at size elements before chaining is absolutely required.

Parameters:
size - The number of entries initially allocated.
Precondition:
size > 0
Postcondition:
constructs a new ChainedHashtable

ChainedHashtable

public ChainedHashtable()
Constructs a reasonably large hashtable.

Postcondition:
constructs a new ChainedHashtable
Method Detail

clear

public void clear()
Removes the values from the hashtable.

Specified by:
clear in interface Map<K,V>
Postcondition:
removes all the elements from the ChainedHashtable

size

public int size()
Computes the number of elements stored within the hashtable.

Specified by:
size in interface Map<K,V>
Returns:
The number of elements within the hash table.
Postcondition:
returns number of elements in hash table

isEmpty

public boolean isEmpty()
Returns true if no elements are stored within the table.

Specified by:
isEmpty in interface Map<K,V>
Returns:
True iff size() == 0.
Postcondition:
returns true iff hash table has 0 elements

locate

protected List<Association<K,V>> locate(K key)

containsValue

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

Specified by:
containsValue in interface Map<K,V>
Parameters:
value - The value sought.
Returns:
True iff the value appears within the table.
Precondition:
value is non-null Object
Postcondition:
returns true iff hash table contains value

containsKey

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

Specified by:
containsKey in interface Map<K,V>
Parameters:
key - The key sought.
Returns:
True iff the key sought appears within table.
Precondition:
value is non-null key
Postcondition:
returns true if key appears in hash table

iterator

public java.util.Iterator<V> iterator()
Returns an iterator that traverses over the values of the hashtable.

Specified by:
iterator in interface java.lang.Iterable<V>
Returns:
A value iterator, over the values of the table.
Postcondition:
returns iterator to traverse hash table

keySet

public Set<K> keySet()
Specified by:
keySet in interface Map<K,V>

entrySet

public Set<Association<K,V>> entrySet()
Specified by:
entrySet in interface Map<K,V>

values

public Structure<V> values()
Specified by:
values in interface Map<K,V>

get

public V get(K key)
Get the value associated with a key.

Specified by:
get in interface Map<K,V>
Parameters:
key - The key used to find the desired value.
Returns:
The value associated with the desired key.
Precondition:
key is non-null Object
Postcondition:
returns value associated with key, or null

keys

public java.util.Iterator<K> keys()
Get an iterator over the keys of the hashtable.

Returns:
An iterator over the key values appearing within table.
Postcondition:
returns iterator to traverse the keys of hash table

put

public V put(K key,
             V value)
Place a key-value pair within the table.

Specified by:
put in interface Map<K,V>
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.
Precondition:
key is non-null object
Postcondition:
key-value pair is added to hash table

remove

public V remove(K key)
Remove a key-value pair from the table.

Specified by:
remove in interface Map<K,V>
Parameters:
key - The key of the key-value pair to be removed.
Returns:
The value associated with the removed key.
Precondition:
key is non-null object
Postcondition:
removes key-value pair associated with key

toString

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

Overrides:
toString in class java.lang.Object
Returns:
The string representing the table.
Postcondition:
returns a string representation of hash table