finiteAutomata
Class Hashtable

java.lang.Object
  extended by finiteAutomata.Hashtable

public class Hashtable
extends java.lang.Object

Data structure which allows for insertions, deletions, and finds in constant average time.

This Hashtable class uses separate chaining to store Associations (key-value pairs). Any non-null object can be used as the key (which is used as input to the hashing function). To successfully store and retrieve values from a hashtable, the objects used as keys must implement the hashCode method and the equals method. To store an Association, apply the hash function to its key and store the Association in the resulting list (first check that an equivalent Association is not already present). To retrieve an Association, apply the hash function to its key and search for it in the resulting list. If the hashtable is appropriately long and if the hash function does a good job of distributing the keys evenly among the hashing locations, then all the lists should be short and it will be very quick to find, insert, and delete based on keys.

Data Fields: A Hashtable is based on an array "table" of Vectors. The integer field "tableSize" gives the length of the array, and should be a prime number (to help insure even distribution for the hashing function). The integer field "size" tells how many Associations are currently stored; load factor can thus be calculated by size / tableSize. (Load factor around 1.0 is ideal for efficient use of time and space in open chaining.)

Version:
Fall 2007
Author:
Barbara Wahl

Field Summary
protected  int size
          number of Associations currently stored
protected  java.util.Vector[] table
          Vector lists for storing Assocations
protected  int tableSize
          length of the "table" array
 
Constructor Summary
Hashtable()
          0-parameter constructor.
Hashtable(int n)
          1-parameter constructor.
 
Method Summary
 boolean contains(java.lang.Object key)
          Returns true if an item with this same key exists in the hashtable.
 java.lang.Object get(java.lang.Object key)
          Returns the value associated with key, or null (if not found).
private  int indexOf(java.lang.Object key, int hash)
          Returns the index, relative to the Vector table[hash], of the Association with the given key.
 void insert(java.lang.Object key, java.lang.Object value)
          Inserts an Association.
 boolean isEmpty()
          True if no Associations are stored.
 double loadFactor()
          Returns the current load factor, size divided by tableSize.
private  int locate(java.lang.Object key)
          Returns the hash location for the provided key.
static void main(java.lang.String[] args)
           
 void printTable()
          Pretty-prints the hash table information.
 java.lang.Object remove(java.lang.Object key)
          Removes an Association.
 int size()
          Returns number of Associations currently stored.
 int tableSize()
          Returns tableSize.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

table

protected java.util.Vector[] table
Vector lists for storing Assocations


tableSize

protected int tableSize
length of the "table" array


size

protected int size
number of Associations currently stored

Constructor Detail

Hashtable

public Hashtable(int n)
1-parameter constructor.

Parameters:
n - table size
Precondition:
n > 0
Postcondition:
creates an empty Hashtable with tableSize = n

Hashtable

public Hashtable()
0-parameter constructor.

Postcondition:
creates an empty Hashtable with tableSize = 101
Method Detail

tableSize

public int tableSize()
Returns tableSize.

Returns:
tableSize

size

public int size()
Returns number of Associations currently stored.

Returns:
size

loadFactor

public double loadFactor()
Returns the current load factor, size divided by tableSize.

Returns:
size / tableSize

locate

private int locate(java.lang.Object key)
Returns the hash location for the provided key.

Parameters:
key - the key to be hashed on
Returns:
key.hashCode() % tableSize, the hashing location
Precondition:
key is not null

indexOf

private int indexOf(java.lang.Object key,
                    int hash)
Returns the index, relative to the Vector table[hash], of the Association with the given key.

Parameters:
key - the key to be located
hash - indexes the Vector to be searched
Returns:
index of the Association in table[hash] with the given key, or -1 if not found there
Precondition:
key is not null, 0 <= hash < tableSize

get

public java.lang.Object get(java.lang.Object key)
Returns the value associated with key, or null (if not found).

Parameters:
key - the key to be searched on
Returns:
value of the stored Association with matching key
Precondition:
key is not null
Postcondition:
this Hashtable is not modified (the matching Association is not removed, just accessed)

contains

public boolean contains(java.lang.Object key)
Returns true if an item with this same key exists in the hashtable.

Parameters:
key - the key to be searched on
Returns:
true iff an Association with matching key is found
Precondition:
key is not null

insert

public void insert(java.lang.Object key,
                   java.lang.Object value)
Inserts an Association.

Parameters:
key - the key to be searched on
value - the associated value for key
Precondition:
key is not null
Postcondition:
if an equivalent Association is not found in the table, the given key-value pair is added to the appropriate vector and size is incremented

remove

public java.lang.Object remove(java.lang.Object key)
Removes an Association.

Parameters:
key - the key to be searched on
Returns:
the associated value for key, or null if not found
Precondition:
key is not null
Postcondition:
if found, the equivalent Association is removed from the table and size is decremented

isEmpty

public boolean isEmpty()
True if no Associations are stored.

Returns:
size == 0

printTable

public void printTable()
Pretty-prints the hash table information.

Postcondition:
Reports tableSize and load factor, and for each stored Association prints the hash value, the index relative to the vector in which the Association is stored, and the key-value pair.

main

public static void main(java.lang.String[] args)