proj4

Class Hashtable<K,V>

java.lang.Object

proj4.Hashtable<K,V>

Type Parameters:

K - the type of the key.

V - values stored.

public class Hashtable<K,V>
extends java.lang.Object

A generic hashtable class, mapping keys to values. Uses the built in hashCode method on the keys. A generic hashtable class, mapping keys to values. Uses the built in hashCode method on the keys. Insert and get should be on average O(1), no matter what the user does. The hashtable should have a reasonable amount of memory usage; it should never have more than five times the number of slots as it has enteries. The hashtable should handle collisions gracefully in whatever way you choose. The number of collisions should be low relative to the size of the hashtable.

Constructor Summary

Constructors

Constructor and Description
Hashtable()

Method Summary

Methods

Modifier and Type	Method and Description
boolean	containsKey(K key) Returns true if the key is contained in the table, false otherwise.
V	get(K key) Retrieves the object associated with this key.
int	getPositionInHashtable(K key) This method should tell you where in the hashtable this key will be stored, ASSUMING NO COLLISIONS.
int	numCollisions() Returns the number of times a collision has occurred.
int	numEntries() Returns the number of things actually stored in this hashtable.
int	numSlots() Returns the size of the array used to back your hashtable.
void	put(K key, V value) Puts a key value pair in the hashtable.

Methods inherited from class java.lang.Object

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

Constructor Detail

Hashtable

public Hashtable()

Method Detail

get

public V get(K key)

Retrieves the object associated with this key. If the key maps to nothing, it should return null.

Parameters:

key - Key we're using for retrieval

Returns:

Associated object.

containsKey

public boolean containsKey(K key)

Returns true if the key is contained in the table, false otherwise.

Parameters:

key - Key we're looking for

Returns:

true if key maps to a value.

put

public void put(K key,
       V value)

Puts a key value pair in the hashtable. If this key already corresponds to a value, that value is overwritten.

Parameters:

key - The key used for retreival later

value - Corresponding value.

numSlots

public int numSlots()

Returns the size of the array used to back your hashtable. The array slots need not be full to count.

Returns:

Size of the hashtable array.

numEntries

public int numEntries()

Returns the number of things actually stored in this hashtable.

Returns:

Number of elements stored.

numCollisions

public int numCollisions()

Returns the number of times a collision has occurred. If you are handling collisions using by storing multiple entries on one cell, you may return the number of doubled up entries. If you are handling collisions by rehashing (using a secondary hash function when collisions are detected) have an instance variable that keeps track of how often this has happened.

Returns:

Number of collisions.

getPositionInHashtable

public int getPositionInHashtable(K key)

This method should tell you where in the hashtable this key will be stored, ASSUMING NO COLLISIONS. Depending on how you design your project, this may be as simple as key.hashCode() % array.length.

Parameters:

key - The key we're trying to figure out where to store

Returns:

The index in the array we would store this key.