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

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	HashTableMap.HashEntry<K,V> Nested class for an entry in a hash table.

Constructor Summary

Constructors

Constructor and Description
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

Modifier and Type	Method and Description
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

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>

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

hashValue

public int hashValue(K key)

Hash function applying MAD method to default hash code.

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>

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

size

public int size()

Returns the number of entries in the hash table.

Specified by:

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