net.datastructures
Class HashTableMap<K,V>

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

All Implemented Interfaces:

Map<K,V>

public class HashTableMap<K,V>
extends java.lang.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 always 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.

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

java.lang.Iterable<Entry<K,V>>	entries() Returns an iterable object containing all of the entries.
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.
java.lang.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.
V	remove(K key) Removes the key-value pair with a specified key.
int	size() Returns the number of entries in the hash table.
java.lang.Iterable<V>	values() Returns an iterable object containing all of the values.

Methods inherited from class java.lang.Object

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

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

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 java.lang.Iterable<K> keys()

Returns an iterable object containing all of the keys.

Specified by:

keys in interface Map<K,V>

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

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 java.lang.Iterable<Entry<K,V>> entries()

Returns an iterable object containing all of the entries.

Specified by:

entries in interface Map<K,V>

values

public java.lang.Iterable<V> values()

Returns an iterable object containing all of the values.

Specified by:

values in interface Map<K,V>