cpsc331.collections

Class OpenHashTableDouble<K,V>

java.lang.Object

cpsc331.collections.OpenHashTableDouble<K,V>

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

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

OpenHashTable Invariant:

1. TABLESIZE is a positive integer, and a power of two.
2. H is a well-defined total function from ordered pairs of elements of K and nonnegative integers to the set of integers between 0 and T−1.
3. T is a table that effectively stores either “nil” “deleted” or ordered pairs of keys (with type K) and values (with type V). There is at most one entry of the table storing any key k∈K, so that a partial function f from K to V is being represented.
4. For each k∈K and integer i≥0, if T[H(k, j)] does not store k for every integer j such that 0≤j≤i−1, and T[H(k, i)] is nil, then f(k) is not defined.
5. For every key k∈K, if T[h(k, j)] does not store k for every integer j between 0 and T−1, then f(k) is not defined.

Constructor Summary

Constructors

Constructor and Description
OpenHashTableDouble(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

OpenHashTableDouble

public OpenHashTableDouble(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 open addressing, with size TABLESIZE, is created, where TABLESIZE is the smallest power of two greater than or equal to max(t, 2). 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)
         throws TableFullException

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

Throws:

TableFullException - if is not possible to incude this new data.

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 if there is room for this data in the hash table. A TableFullException is thrown and neither the partial function nor hash table are changed, otherwise.

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.