structure
Class ChainedHashtable

java.lang.Object
  |
  +--structure.AbstractMap
        |
        +--structure.ChainedHashtable

All Implemented Interfaces:

Map

public class ChainedHashtable

extends AbstractMap

implements Map

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	capacity The length of the table.
protected int	count The number of key-value pairs stored within the table.
protected List[]	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(Object key) Returns true iff a specific key appears within the table.
boolean	containsValue(Object value) Returns true if a specific value appears within the table.
Set	entrySet()
Object	get(Object key) Get the value associated with a key.
boolean	isEmpty() Returns true if no elements are stored within the table.
Iterator	iterator() Returns an iterator that traverses over the values of the hashtable.
Iterator	keys() Get an iterator over the keys of the hashtable.
Set	keySet()
protected List	locate(Object key)
Object	put(Object key, Object value) Place a key-value pair within the table.
Object	remove(Object key) Remove a key-value pair from the table.
int	size() Computes the number of elements stored within the hashtable.
String	toString() Generate a string representation of the chained hash table.
Structure	values()

Methods inherited from class structure.AbstractMap

hashCode, putAll

Methods inherited from class java.lang.Object

, clone, equals, finalize, getClass, notify, notifyAll, registerNatives, wait, wait, wait

Methods inherited from interface structure.Map

equals, hashCode, putAll

Field Detail

data

protected List[] data

The array of chains used to store values.

count

protected int count

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

capacity

protected int capacity

The length of 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.

ChainedHashtable

public ChainedHashtable()

Constructs a reasonably large hashtable.

Method Detail

clear

public void clear()

Removes the values from the hashtable.

Specified by:

clear in interface Map

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

Postcondition:

returns number of elements in hash table

Returns:

The number of elements within the hash table.

isEmpty

public boolean isEmpty()

Returns true if no elements are stored within the table.

Specified by:

isEmpty in interface Map

Postcondition:

returns true iff hash table has 0 elements

Returns:

True iff size() == 0.

locate

protected List locate(Object key)

containsValue

public boolean containsValue(Object value)

Returns true if a specific value appears within the table.

Specified by:

containsValue in interface Map

Parameters:

value - The value sought.

Precondition:

value is non-null Object

Postcondition:

returns true iff hash table contains value

Returns:

True iff the value appears within the table.

containsKey

public boolean containsKey(Object key)

Returns true iff a specific key appears within the table.

Specified by:

containsKey in interface Map

Parameters:

key - The key sought.

Precondition:

value is non-null key

Postcondition:

returns true if key appears in hash table

Returns:

True iff the key sought appears within table.

iterator

public Iterator iterator()

Returns an iterator that traverses over the values of the hashtable.

Postcondition:

returns iterator to traverse hash table

Returns:

A value iterator, over the values of the table.

keySet

public Set keySet()

Specified by:

keySet in interface Map

entrySet

public Set entrySet()

Specified by:

entrySet in interface Map

values

public Structure values()

Specified by:

values in interface Map

get

public Object get(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.

Precondition:

key is non-null Object

Postcondition:

returns value associated with key, or null

Returns:

The value associated with the desired key.

keys

public Iterator keys()

Get an iterator over the keys of the hashtable.

Postcondition:

returns iterator to traverse the keys of hash table

Returns:

An iterator over the key values appearing within table.

put

public Object put(Object key,
                  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.

Precondition:

key is non-null object

Postcondition:

key-value pair is added to hash table

Returns:

The old value associated with key if previously present.

remove

public Object remove(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.

Precondition:

key is non-null object

Postcondition:

removes key-value pair associated with key

Returns:

The value associated with the removed key.

toString

public String toString()

Generate a string representation of the chained hash table.

Overrides:

toString in class Object

Postcondition:

returns a string representation of hash table

Returns:

The string representing the table.