net.datastructures
Class HashTableMap<K,V>

java.lang.Object
  net.datastructures.HashTableMap<K,V>

All Implemented Interfaces:

Map<K,V>

Direct Known Subclasses:

AdjacencyListGraph.MyPosition

public class HashTableMap<K,V>
extends Object
implements Map<K,V>

Nested Class Summary

static class

HashTableMap.HashEntry<K,V> Nested class for an entry in a hash table.

Field Summary

protected Entry<K,V>	AVAILABLE
protected Entry<K,V>[]	bucket
protected int	capacity
protected int	n
protected int	scale
protected int	shift

Constructor Summary

HashTableMap()
Creates a hash table with initial capacity 1023.

HashTableMap(int cap)
Creates a hash table with the given capacity.

Method Summary

protected void	checkKey(K k) Determines whether a key is valid.
Iterable<Entry<K,V>>	entries() Returns an iterable object containing all of the entries.
protected int	findEntry(K key) Helper search method - returns index of found key or -(a + 1), where a is the index of the first empty or available slot found.
V	get(K key) Returns the value associated with a key.
int	hashValue(K key) Hash function applying MAD method to default hash code.
boolean	isEmpty() Returns whether or not the table is empty.
Iterable<K>	keys() Returns an iterable object containing all of the keys.
V	put(K key, V value) Put a key-value pair in the map, replacing previous one if it exists.
protected void	rehash() Doubles the size of the hash table and rehashes all the entries.
V	remove(K key) Removes the key-value pair with a specified key.
int	size() Returns the number of entries in the hash table.
Iterable<V>	values() Returns an iterable object containing all of the values.

Methods inherited from class java.lang.Object

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

Field Detail

AVAILABLE

protected Entry<K,V> AVAILABLE

n

protected int n

capacity

protected int capacity

bucket

protected Entry<K,V>[] bucket

scale

protected int scale

shift

protected int shift

Constructor Detail

HashTableMap

public HashTableMap()

Creates a hash table with initial capacity 1023.

HashTableMap

public HashTableMap(int cap)

Creates a hash table with the given capacity.

Method Detail

checkKey

protected void checkKey(K k)

Determines whether a key is valid.

hashValue

public int hashValue(K key)

Hash function applying MAD method to default hash code.

size

public int size()

Returns the number of entries in the hash table.

Specified by:

size in interface Map<K,V>

isEmpty

public boolean isEmpty()

Returns whether or not the table is empty.

Specified by:

isEmpty in interface Map<K,V>

keys

public Iterable<K> keys()

Returns an iterable object containing all of the keys.

Specified by:

keys in interface Map<K,V>

findEntry

protected int findEntry(K key)
                 throws InvalidKeyException

Helper search method - returns index of found key or -(a + 1), where a is the index of the first empty or available slot found.

Throws:

InvalidKeyException

get

public V get(K key)
      throws InvalidKeyException

Returns the value associated with a key.

Specified by:

get in interface Map<K,V>

Throws:

InvalidKeyException

put

public V put(K key,
             V value)
      throws InvalidKeyException

Put a key-value pair in the map, replacing previous one if it exists.

Specified by:

put in interface Map<K,V>

Throws:

InvalidKeyException

rehash

protected void rehash()

Doubles the size of the hash table and rehashes all the entries.

remove

public V remove(K key)
         throws InvalidKeyException

Removes the key-value pair with a specified key.

Specified by:

remove in interface Map<K,V>

Throws:

InvalidKeyException

entries

public Iterable<Entry<K,V>> entries()

Returns an iterable object containing all of the entries.

Specified by:

entries in interface Map<K,V>

values

public Iterable<V> values()

Returns an iterable object containing all of the values.

Specified by:

values in interface Map<K,V>