data_structures
Class DHashTable<K,V>

java.lang.Object
  data_structures.HashTable<K,V>
      data_structures.DHashTable<K,V>

Type Parameters:

K - the type of object that will act as keys for the hash table

V - the type of object that is being stored in the hash table

All Implemented Interfaces:

java.lang.Cloneable

public class DHashTable<K,V>
extends HashTable<K,V>

A simple dynamic HashTable.

In general, the time for each operation is as follows:

• add an element: O(1) amortized time
• search for an element: O(1) amortized time
• remove an element: O(1) amortized time

Author:

Stephen G. Ware

Field Summary

Fields inherited from class data_structures.HashTable

DEFAULT_EXPANSION_FACTOR, DEFAULT_INITIAL_SIZE, DEFAULT_LOAD_FACTOR_THRESHOLD, size, table

Constructor Summary

	DHashTable() Construct an empty dynamic hash table.
protected	DHashTable(int size, data_structures.HashTable.Node<K,V>[] table) Construct a dynamic hash table with a given number of mappings and given set of buckets.
	DHashTable(K[] keys, V[] values) Construct a dynamic hash table which initially contains mappings for a given set of keys and values.

Method Summary

DHashTable<K,V>	add(K[] keys, V[] values) Add multiple key/value mappings to the dynamic hash table.
DHashTable<K,V>	add(K key, V value) Add a key/value mapping to the dynamic hash table.
DHashTable<K,V>	addEquals(K[] keys, V[] values) Add multiple key/value mappings to the dynamic hash table.
DHashTable<K,V>	addEquals(K key, V value) Add a key/value mapping to the dynamic hash table.
DHashTable<K,V>	clone() Return a deep copy of the dynamic hash table.
boolean	equals(java.lang.Object other) Check if this hash table is the same as another.
V	get(K key) Return the value mapped to a given key.
V	getEquals(K key) Return the value mapped to a given key.
protected float	getLoadFactor() Return the load factor of the dynamic hash table.
java.util.Iterator<K>	keys() Return an Iterator that will yield all the keys in the dynamic hash table.
DHashTable<K,V>	remove(K key) Remove a key/value mapping from the dynamic hash table.
DHashTable<K,V>	remove(K[] keys) Remove multiple key/value mappings from the dynamic hash table.
DHashTable<K,V>	removeEquals(K key) Remove a key/value mapping from the dynamic hash table.
DHashTable<K,V>	removeEquals(K[] keys) Remove multiple key/value mappings from the dynamic hash table.
int	size() Return the number of mappings in the dynamic hash table.
java.lang.String	toString() Return a string representation of this hash table and all its elements.
java.util.Iterator<V>	values() Return an Iterator that will yield all the values in the dynamic hash table.

Methods inherited from class data_structures.HashTable

cloneTable, getBucket, rehash, rehash

Methods inherited from class java.lang.Object

finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

DHashTable

protected DHashTable(int size,
                     data_structures.HashTable.Node<K,V>[] table)

Construct a dynamic hash table with a given number of mappings and given set of buckets.

Parameters:

size - the number of mappings in the hash table

table - the buckets

DHashTable

public DHashTable()

Construct an empty dynamic hash table.

DHashTable

public DHashTable(K[] keys,
                  V[] values)

Construct a dynamic hash table which initially contains mappings for a given set of keys and values.

Mappings are added as if using add(K, V).

Parameters:

keys - the objects which can be used to retrieve the values

values - the objects to be retrieved using the keys

Throws:

java.lang.ArrayIndexOutOfBoundsException - if the array of keys is not the same length as the array of values

Method Detail

getLoadFactor

protected final float getLoadFactor()

Return the load factor of the dynamic hash table.

The load factor is defined as the number of mapping divided by the number of buckets.

Overrides:

getLoadFactor in class HashTable<K,V>

Returns:

the load factor

size

public int size()

Return the number of mappings in the dynamic hash table.

Overrides:

size in class HashTable<K,V>

Returns:

the number of mappings

add

public DHashTable<K,V> add(K key,
                           V value)

Add a key/value mapping to the dynamic hash table. If a mapping exists whose key is == to this key, it is replaced.

Specified by:

add in class HashTable<K,V>

Parameters:

key - the object which can be used to retrieve the value

value - the object to be retrieved using the key

Returns:

this hash table

add

public DHashTable<K,V> add(K[] keys,
                           V[] values)

Add multiple key/value mappings to the dynamic hash table. If mappings exist whose keys are == to the given keys, they are replaced.

Specified by:

add in class HashTable<K,V>

Parameters:

keys - the objects which can be used to retrieve the values

values - the objects to be retrieved using the keys

Returns:

this hash table

Throws:

java.lang.ArrayIndexOutOfBoundsException - if the array of keys is not the same length as the array of values

addEquals

public DHashTable<K,V> addEquals(K key,
                                 V value)

Add a key/value mapping to the dynamic hash table. If a mapping exists whose key Object.equals(java.lang.Object) this key, it is replaced.

Specified by:

addEquals in class HashTable<K,V>

Parameters:

key - the object which can be used to retrieve the value

value - the object to be retrieved using the key

Returns:

this hash table

addEquals

public DHashTable<K,V> addEquals(K[] keys,
                                 V[] values)

Add multiple key/value mappings to the dynamic hash table. If mappings exist whose keys are Object.equals(java.lang.Object) to the given keys, they are replaced.

Specified by:

addEquals in class HashTable<K,V>

Parameters:

keys - the objects which can be used to retrieve the values

values - the objects to be retrieved using the keys

Returns:

this hash table

Throws:

java.lang.ArrayIndexOutOfBoundsException - if the array of keys is not the same length as the array of values

get

public V get(K key)

Return the value mapped to a given key. Keys are searched using ==.

Overrides:

get in class HashTable<K,V>

Parameters:

key - the object that was mapped to the desired value

Returns:

the value

getEquals

public V getEquals(K key)

Return the value mapped to a given key. Keys are searched using Object.equals(java.lang.Object).

Overrides:

getEquals in class HashTable<K,V>

Parameters:

key - the object that was mapped to the desired value

Returns:

the value

remove

public DHashTable<K,V> remove(K key)

Remove a key/value mapping from the dynamic hash table. Keys are searched using ==.

Specified by:

remove in class HashTable<K,V>

Parameters:

key - the key of the key/value mapping to be removed

Returns:

this hash table

remove

public DHashTable<K,V> remove(K[] keys)

Remove multiple key/value mappings from the dynamic hash table. Keys are searched using ==.

Specified by:

remove in class HashTable<K,V>

Parameters:

keys - the keys of the key/value mappings to be removed

Returns:

this hash table

removeEquals

public DHashTable<K,V> removeEquals(K key)

Remove a key/value mapping from the dynamic hash table. Keys are searched using Object.equals(java.lang.Object).

Specified by:

removeEquals in class HashTable<K,V>

Parameters:

key - the key of the key/value mapping to be removed

Returns:

this hash table

removeEquals

public DHashTable<K,V> removeEquals(K[] keys)

Remove multiple key/value mappings from the dynamic hash table. Keys are searched using Object.equals(java.lang.Object).

Specified by:

removeEquals in class HashTable<K,V>

Parameters:

keys - the keys of the key/value mappings to be removed

Returns:

this hash table

keys

public java.util.Iterator<K> keys()

Return an Iterator that will yield all the keys in the dynamic hash table.

Overrides:

keys in class HashTable<K,V>

Returns:

an iterator of keys

values

public java.util.Iterator<V> values()

Return an Iterator that will yield all the values in the dynamic hash table.

Overrides:

values in class HashTable<K,V>

Returns:

an iterator of values

equals

public boolean equals(java.lang.Object other)

Check if this hash table is the same as another.

Two hash tables are considered the same if they contain the same key/value mappings. Keys and values are compared using Object.equals(java.lang.Object).

The class of the hash table is not taken into account. In other words, a DHashTable can be equal to an SHashTable if they contain the same key/value mappings.

Overrides:

equals in class HashTable<K,V>

Parameters:

other - another hash table

Returns:

true is the hash tables are the same, false if the hash tables are different or if other is not a hash table

clone

public DHashTable<K,V> clone()

Return a deep copy of the dynamic hash table.

The clone hash table can be modified without affecting the original.

Specified by:

clone in class HashTable<K,V>

toString

public java.lang.String toString()

Return a string representation of this hash table and all its elements.

Overrides:

toString in class HashTable<K,V>