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>

A hash table data structure that uses linear probing to handle collisions. The hash function uses the built-in hashCode method and the multiply-add-and-divide method. The load factor is alwyas kept less than or equal to 0.5. When the load factor reaches 0.5, the entries are rehashed into a new bucket array with twice the capacity.

Author:

Roberto Tamassia, Michael Goodrich, Eric Zamore

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	prime
protected long	scale
protected long	shift

Constructor Summary

HashTableMap()
Creates a hash table with prime factor 109345121 and capacity 1000.

HashTableMap(int cap)
Creates a hash table with prime factor 109345121 and given capacity.

HashTableMap(int p, int cap)
Creates a hash table with the given prime factor and capacity.

Method Summary

protected void	checkKey(K k) Determines whether a key is valid.
Iterable<Entry<K,V>>	entrySet() 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>	keySet() 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

prime

protected int prime

capacity

protected int capacity

bucket

protected Entry<K,V>[] bucket

scale

protected long scale

shift

protected long shift

Constructor Detail

HashTableMap

public HashTableMap()

Creates a hash table with prime factor 109345121 and capacity 1000.

HashTableMap

public HashTableMap(int cap)

Creates a hash table with prime factor 109345121 and given capacity.

HashTableMap

public HashTableMap(int p,
                    int cap)

Creates a hash table with the given prime factor and 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>

keySet

public Iterable<K> keySet()

Returns an iterable object containing all of the keys.

Specified by:

keySet 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

entrySet

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

Returns an iterable object containing all of the entries.

Specified by:

entrySet 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>