All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class rpi.goldsd.container.Table 

java.lang.Object
   |
   +----rpi.goldsd.container.Table
public class Table
extends Object
implements AssociativeContainer
The Table class provides a generic associative hashtable by implementing the AssociativeContainer interface. Objects are identified by a unique key object that is also used in determining the corresponding hash values. The current implementation of the hashtable consists of an array of references to LinkedList objects.

One of the current shortcomings of this class is the implicit requirement that the Comparable key objects also implement the Hashable interface. Thus, instead of a compilation error indicating that a key must be Hashable, a run-time exception occurs.

Version:
1.3, 3/27/98
Author:
David Goldschmidt
See Also:
LinkedList, Comparable, Hashable, DuplicateElementException, EmptyEnumeration

Variable Index

o DEFAULT_SIZE
The default table size used by the default constructor.
o numElements
The number of associated elements in this hashtable.
o table
The array of references to LinkedList objects.

Constructor Index

o Table()
Constructs a hashtable with the default table size.
o Table(int)
Constructs a hashtable with the specified table size.

Method Index

o add(Comparable)
Adds a new associative entry to this hashtable.
o add(Comparable, Object)
Adds a new associative entry to this hashtable.
o clear()
Removes all elements from this hashtable.
o contains(Comparable)
Returns true if the given key maps to an element in the associative container.
o elements()
Provides an enumeration of the elements in this hashtable.
o elements(int)
Provides an enumeration of the elements in this hashtable for a specific hash value (i.e.
o getSize()
Returns the number of elements in this hashtable.
o getTableSize()
Returns the size of the hashtable.
o hash(Comparable)
Determines the hash value based on the Comparable key.
o isEmpty()
Returns true if this hashtable contains no elements.
o keys()
Provides an enumeration of the keys stored in this hashtable.
o map(Comparable)
Provides a mechanism for mapping a given key to its corresponding data.
o remove(Comparable)
Removes a data element from this hashtable identified by the given key.
o toString()
The toString() method is the default method used to display the keys and corresponding data elements of this hashtable.

Variables

o DEFAULT_SIZE 
 public static final int DEFAULT_SIZE
The default table size used by the default constructor.

o numElements 
 protected int numElements
The number of associated elements in this hashtable.

o table 
 protected LinkedList table[]
The array of references to LinkedList objects.

Constructors

o Table 
 public Table(int tableSize)
Constructs a hashtable with the specified table size.

Parameters:
tableSize - the number of hash "buckets" to construct.
o Table 
 public Table()
Constructs a hashtable with the default table size.

Methods

o add 
 public synchronized void add(Comparable keyAndData) throws DuplicateElementException, IllegalArgumentException
Adds a new associative entry to this hashtable. If the Comparable key parameter does not also implement the Hashable interface (which is a sub-interface of the Comparable interface), then an IllegalArgumentException is thrown.

This method performs in O(n) time in the worst-case, where n is the number of elements in the hashtable. Inherent in hashing, the average performance is significantly better since the linked-list used to store the data should be very small with an evenly distributed hash function.

Parameters:
keyAndData - the unique key used to identify the associated data which is simply the Comparable argument.
Throws: IllegalArgumentException
if the given key object does not implement the Hashable interface.
Throws: DuplicateElementException
if the key used already exists in this table.
o add 
 public synchronized void add(Comparable key,
                              Object data) throws DuplicateElementException, IllegalArgumentException
Adds a new associative entry to this hashtable. If the Comparable key parameter does not also implement the Hashable interface (which is a sub-interface of the Comparable interface), then an IllegalArgumentException is thrown.

This method performs in O(n) time in the worst-case, where n is the number of elements in the hashtable. Inherent in hashing, the average performance is significantly better since the linked-list used to store the data should be very small with an evenly distributed hash function.

Parameters:
key - the unique key used to identify the associated data.
data - the actual data to be stored.
Throws: IllegalArgumentException
if the given key object does not implement the Hashable interface.
Throws: DuplicateElementException
if the key used already exists in this table.
o clear 
 public synchronized void clear()
Removes all elements from this hashtable.

This method performs in constant time O(1).

o contains 
 public boolean contains(Comparable key)
Returns true if the given key maps to an element in the associative container. This method makes use of the map() method.

This method performs in O(n) in the worst-case; however, performance is substantially better in the average case, provided that the hash function provides an even distribution of hash values.

Parameters:
key - the unique key used to identify an element in the associative container.
Returns:
true if the given key maps to an element in the associative container; false otherwise.
o elements 
 public synchronized Enumeration elements()
Provides an enumeration of the elements in this hashtable.

This method performs in constant time O(1).

Returns:
an enumeration of the elements stored in this hashtable.
o elements 
 public synchronized Enumeration elements(int hashValue)
Provides an enumeration of the elements in this hashtable for a specific hash value (i.e. an enumeration of the elements in the linked list for the given hash value).

This method performs in constant time O(1).

Parameters:
hashValue - the hash value to look up.
Returns:
an enumeration of the elements stored in this hashtable for a specific hash value.
o getSize 
 public synchronized int getSize()
Returns the number of elements in this hashtable.

This method performs in constant time O(1).

Returns:
the number of elements in this hashtable.
o getTableSize 
 public synchronized int getTableSize()
Returns the size of the hashtable.

This method performs in constant time O(1).

Returns:
the size of the hashtable.
o hash 
 protected synchronized int hash(Comparable key)
Determines the hash value based on the Comparable key.

This method performs in constant time O(1).

Throws: IllegalArgumentException
if the given key object does not implement the Hashable interface.
o isEmpty 
 public synchronized boolean isEmpty()
Returns true if this hashtable contains no elements.

This method performs in constant time O(1).

Returns:
true if this hashtable contains no elements; false otherwise.
o keys 
 public synchronized Enumeration keys()
Provides an enumeration of the keys stored in this hashtable.

This method performs in constant time O(1).

Returns:
an enumeration of the keys stored in this hashtable.
o map 
 public synchronized Object map(Comparable key)
Provides a mechanism for mapping a given key to its corresponding data.

This method performs in O(n) time in the worst case, where n is the number of elements in the hashtable. Inherent in hashing, the average performance is substantially better since the linked-list used to store the data should be very small with an evenly distributed hash value.

Parameters:
key - the key used to identify and locate the associated data.
Returns:
the data stored in this hashtable identified by the given key; or null if the given key does not identify an element in this hashtable.
Throws: IllegalArgumentException
if the given key object does not implement the Hashable interface.
o remove 
 public synchronized Object remove(Comparable key)
Removes a data element from this hashtable identified by the given key.

This method performs in O(n) time in the worst-case, where n is the number of elements in the hashtable. Inherent in hashing, the average performance is substantially better since the linked-list used to store the data should be very small with an evenly distributed hash value.

Parameters:
key - the key used to identify and locate the associated data.
Returns:
the object that is removed from this hashtable.
Throws: IllegalArgumentException
if the given key object does not implement the Hashable interface.
o toString 
 public synchronized String toString()
The toString() method is the default method used to display the keys and corresponding data elements of this hashtable.

This method performs in O(n) time since each individual node of the hashtable must be visited once.

Returns:
a String representing the keys and corresponding data elements of this hashtable.
Overrides:
toString in class Object 
All Packages  Class Hierarchy  This Package  Previous  Next  Index