net.datastructures
Class HashTable

java.lang.Object
  net.datastructures.HashTable

All Implemented Interfaces:

Map

Direct Known Subclasses:

AdjacencyListGraph.MyPosition

public class HashTable

extends Object

implements Map

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

protected static class	HashTable.DefaultEqualityTester An inner class for a simple equality tester.
protected static class	HashTable.HashEntry Nested class for an entry in a hash table.

Field Summary

protected Entry[]	A
protected static Entry	AVAILABLE
protected int	n
protected int	N
protected int	scale
protected int	shift
protected EqualityTester	T

Constructor Summary

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

HashTable(int bN, EqualityTester tester)
Creates a hash table with the given capacity and equality tester.

Method Summary

protected void	checkKey(Object k) Determines whether a key is valid.
protected int	findEntry(Object key) Helper search method - returns index of found key or -index-1, where index is the index of an empty or available slot.
Object	get(Object key) Returns the value associated with a key.
int	hashValue(Object key) Hash function applying MAD method to default hash code.
boolean	isEmpty() Returns whether or not the table is empty.
Iterator	keys() Returns an iterator of keys.
Object	put(Object key, Object 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.
Object	remove(Object key) Removes the key-value pair with a specified key.
int	size() Returns the number of entries in the hash table.
Iterator	values() Returns an iterator of values.

Methods inherited from class java.lang.Object

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

Field Detail

AVAILABLE

protected static Entry AVAILABLE

n

protected int n

N

protected int N

A

protected Entry[] A

T

protected EqualityTester T

scale

protected int scale

shift

protected int shift

Constructor Detail

HashTable

public HashTable()

Creates a hash table with initial capacity 1023.

HashTable

public HashTable(int bN,
                 EqualityTester tester)

Creates a hash table with the given capacity and equality tester.

Method Detail

checkKey

protected void checkKey(Object k)

Determines whether a key is valid.

hashValue

public int hashValue(Object 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

isEmpty

public boolean isEmpty()

Returns whether or not the table is empty.

Specified by:

isEmpty in interface Map

findEntry

protected int findEntry(Object key)
                 throws InvalidKeyException

Helper search method - returns index of found key or -index-1, where index is the index of an empty or available slot.

Throws:

InvalidKeyException

get

public Object get(Object key)
           throws InvalidKeyException

Returns the value associated with a key.

Specified by:

get in interface Map

Throws:

InvalidKeyException

put

public Object put(Object key,
                  Object value)
           throws InvalidKeyException

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

Specified by:

put in interface Map

Throws:

InvalidKeyException

rehash

protected void rehash()

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

remove

public Object remove(Object key)
              throws InvalidKeyException

Removes the key-value pair with a specified key.

Specified by:

remove in interface Map

Throws:

InvalidKeyException

keys

public Iterator keys()

Returns an iterator of keys.

Specified by:

keys in interface Map

values

public Iterator values()

Returns an iterator of values.

Specified by:

values in interface Map