sdds
Class DHashTable<K,V>

java.lang.Object
  extended by sdds.HashTable<K,V>
      extended by sdds.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:

Author:
Stephen G. Ware

Field Summary
 
Fields inherited from class sdds.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, sdds.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 sdds.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,
                     sdds.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>