cpsc331.collections

Class ChainHashTable<K,V>

java.lang.Object

cpsc331.collections.ChainHashTable<K,V>

public class ChainHashTable<K,V>
extends java.lang.Object

Implements a hash table with chaining that can be used to implement either a Set or a Mapping: Table entries store ordered pairs of keys and values.

ChainHashTable Invarianb:

1. TABLESIZE is a positive integer.
2. H is a well-defined total function from K to the set of integers between 0 and T−1
3. T is a hash table with chaining with size TABLESIZE, that is being used to represent a partial function f from K to V: For each integer i from 0 to TABLESIZE−1, T[i] is a linked list storing ordered pairs (k, v) such that f(k) is defined and equal to v and such that hashValue(k)=i.

Constructor Summary

Constructors

Constructor and Description
ChainHashTable(int t) Creates an empty hash table.

Method Summary

Modifier and Type	Method and Description
boolean	defined(K k) Reports whether a value for a given key k is defined.
V	remove(K k) Sets the value for a given key to be undefined.
V	search(K k) Searches for the value associated with a given key, throwing an exception if no such value is defined.
void	set(K k, V v) Sets the value associated with an input key k to be an input value v.

Methods inherited from class java.lang.Object

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

Constructor Detail

ChainHashTable

public ChainHashTable(int t)
               throws java.lang.IllegalArgumentException

Creates an empty hash table.

Parameters:

t - the table size to be used

Throws:

java.lang.IllegalArgumentException - if the input table size is not positive

Precondition: An integer t is given as input.
Postcondition: If t is positive then an empty hash table with chaining, with size t, is created. An IllegalArgumentException is thrown otherwise.

Method Detail

search

public V search(K k)
         throws java.util.NoSuchElementException

Searches for the value associated with a given key, throwing an exception if no such value is defined.

Parameters:

k - the key whose value is being checked for

Returns:

the value associated with this key

Throws:

java.util.NoSuchElementException - if no value for this key is defined

Precondition: A non-null key k with type K is received as input.
Postcondition: If a value is associated with k then this is returned. An IllegalArgumentException is thrown otherwise.

defined

public boolean defined(K k)

Reports whether a value for a given key k is defined.

Parameters:

k - a key of type k

Returns:

true if a value is associated with k; false otherwise

Precondition: A key k of type k is given as input.
Postcondition: If a value is defined for this key then “true” is returned; “false” is returned otherwise.

set

public void set(K k,
                V v)

Sets the value associated with an input key k to be an input value v.

Parameters:

k - the value for which a new value is to be defined

v - the value to be associated with this key

Precondition: A key k with type K and value v with type V are given as input.
Postcondition: The partial function f being represented is changed so that f(k) = v.

remove

public V remove(K k)
         throws java.util.NoSuchElementException

Sets the value for a given key to be undefined.

Parameters:

k - the key for which no value should be defined

Returns:

the value previously associated with this key

Throws:

java.util.NoSuchElementException - if no value was defined for this key

Precondition: A key k of type K is given as input.
Postcondition: If a value v was associated with this key then this value is returned and no value is associated with the key after that. A NoSuchElementException is thrown otherwise.