Class OpenHashTable<K,V>

java.lang.Object
  OpenHashTable<K,V>

All Implemented Interfaces:

SimpleHashMap<K,V>

public class OpenHashTable<K,V>
extends java.lang.Object
implements SimpleHashMap<K,V>

Nested Class Summary

private static class

OpenHashTable.Entry<K,V> An inner class that represents a key-value pair that can be stored in a hash table.

Field Summary

private OpenHashTable.Entry<K,V>	DELETED an indicator that can be stored in a hash table in place of an item that has been removed
private static int	INITIAL_CAPACITY constant which defines the initial size of the hash table
private double	LOAD_THRESHOLD maximum allowable capacity before expanding the hash table
private int	numDeletes how many keys (or entries) have been deleted from the table
private int	numKeys how many keys (or entries) are currently stored in the hash table, excluding the number of keys that were deleted
private java.util.List<OpenHashTable.Entry<K,V>>	table hash table - an arraylist of entries

Constructor Summary

OpenHashTable()
Hash table constructor which creates a hash table with an initial size given by INITIAL_CAPACITY.

Method Summary

private int	find(K key) Finds either the target key in the hash table or the first empty location in the hash table.
V	get(K key) Returns the value associated with the specified key.
int	getNumberOfKeys() Provides the number of keys in the map.
boolean	isEmpty() Returns true if this map contains no key-value mappings.
void	printTable() A debugging routine designed to display the contents of the hash table.
V	put(K key, V value) Associates the specified value with the specified key.
private void	rehash() Expands the table size whenever the number of entries exceeds some threshold (defined in LOAD_THRESHOLD).
V	remove(K key) Removes the mapping for this key if it is present.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

table

private java.util.List<OpenHashTable.Entry<K,V>> table

hash table - an arraylist of entries

INITIAL_CAPACITY

private static final int INITIAL_CAPACITY

constant which defines the initial size of the hash table

See Also:

Constant Field Values

LOAD_THRESHOLD

private double LOAD_THRESHOLD

maximum allowable capacity before expanding the hash table

numKeys

private int numKeys

how many keys (or entries) are currently stored in the hash table, excluding the number of keys that were deleted

numDeletes

private int numDeletes

how many keys (or entries) have been deleted from the table

DELETED

private final OpenHashTable.Entry<K,V> DELETED

an indicator that can be stored in a hash table in place of an item that has been removed

Constructor Detail

OpenHashTable

public OpenHashTable()

Hash table constructor which creates a hash table with an initial size given by INITIAL_CAPACITY.

Method Detail

find

private int find(K key)

Finds either the target key in the hash table or the first empty location in the hash table. The initial location to try in the hash table is found by applying the hashCode method to the key, dividing by the size of the table, and then using the remainder. Subsequent addresses are generated by using a simple linear probing scheme. If we reach the end of the array that represents the hash table, we wrap around to the beginning of the array. We assume that the hash table is never full.

Parameters:

key - specified key to search for

Returns:

returns the index position of the key in the array if found; otherwise, returns the index position of the first empty position in the array

get

public V get(K key)

Returns the value associated with the specified key.

Specified by:

get in interface SimpleHashMap<K,V>

Parameters:

key - the key being looked for

Returns:

the value associated with this key if found; otherwise, null

isEmpty

public boolean isEmpty()

Returns true if this map contains no key-value mappings.

Specified by:

isEmpty in interface SimpleHashMap<K,V>

Returns:

returns true if there are no key-value mappings; otherwise, returns false

getNumberOfKeys

public int getNumberOfKeys()

Provides the number of keys in the map.

Specified by:

getNumberOfKeys in interface SimpleHashMap<K,V>

Returns:

returns the number of keys in the map

put

public V put(K key,
             V value)

Associates the specified value with the specified key.

Specified by:

put in interface SimpleHashMap<K,V>

Parameters:

key - the key for the value to insert

value - the value associated with this key

Returns:

returns the previous value associated with the specified key, or null if there was no prior mapping for the key

rehash

private void rehash()

Expands the table size whenever the number of entries exceeds some threshold (defined in LOAD_THRESHOLD). We create a new hash table whose size is twice the size of the original hash table plus 1 (this ensures that the resulting size is always odd). Each non- deleted entry from the original hash table is inserted into the expanded hash table (in general, this means that entries will be placed into different locations in the expanded hash table compared to their locations in the original hash table). Entries that were marked as deleted are NOT inserted into the expanded hash table. The value of numKeys is reset to the number of entries actually inserted; the value of numDeletes is reset to 0.

remove

public V remove(K key)

Removes the mapping for this key if it is present.

Specified by:

remove in interface SimpleHashMap<K,V>

Parameters:

key - the key being looked for

Returns:

returns the previous value associated with the specified key, or null if there was no mapping for the key

printTable

public void printTable()

A debugging routine designed to display the contents of the hash table. Each line of output contains an array index followed by the contents of the array location, expressed as a key/value pair. If the array location is empty, only the array index is printed. A blank line is printed after the entire array is displayed. The exact format is illustrated below for a hash table consisting of seven locations.

 0: 0 0
 1:
 2: 30 30
 3: 10 10
 4:
 5: null null
 6: 20 20
               (<-- this blank line appears here)