-
hashtable chaining
I'm having trouble with finishing the remove and rehash methods.
Here is what the remove method should do:
set index to key.hashCode()%table.length
if index is negative, add table.length
if table[index] is null
key is not in the table; return null
search the list at table[index] to find the key
if the search is successful
remove the entry with this key and decrement numkeys
if the list at table[index] is empty
set table[index] to null
return the value associated with the key
the key is not in the table; return null
The part I can't figure out is the search and if the search was successful.
On the rehash method I can't figure out how to reinsert each table entry into the new hash table.
here is my code
Code:
import java.util.*;
public class HashtableChain<K , V>
{
private LinkedList<Entry<K, V>>[] table; //the hash table
private int numKeys; //the number of elements within hash table
private static final int INITIAL_CAPACITY = 101; // the size of the table
private static final double LOAD_THRESHOLD = 3.0; //the max load factor
private static class Entry<K, V>
{
private K key;
private V value;
public Entry(K key, V value)
{
this.key = key;
this.value = value;
}
public void setValue(V value)
{
this.value = value;
}
}
public HashtableChain() //constructor
{
table = new LinkedList[INITIAL_CAPACITY];
}
/**
* Method get for class HashtabelChain
* @param key The key being sought
* @return the value associated with this key if found; otherwise, null
*/
public V get(K key)
{
int index = key.hashCode() % table.length;
if(index < 0)
{
index += table.length;
}
if(table[index] == null)
{
return null; //key is not in table
}
//Search the list at table[index] to find the key
for(Entry<K, V> nextItem : table[index])
{
if(nextItem.key.equals(key))
return nextItem.value;
}
//Key is not in the table
return null;
}
/**
* Method put for class HashtableChain.
* post: This key-value pair is inserted in the table and numKeys is incremented.
* If the key is already in the table, its value is changed to the argument
* value and numKeys is not changed.
* @pram key The key of the item being inserted
* @pram value The value for this key
* @return The old value associated with this key if found; otherwise, null
*/
public V put(K key, V value)
{
int index = key.hashCode() % table.length;
if(index < 0)
{
index += table.length;
}
if(table[index] == null)
{
table[index] = new LinkedList<Entry<K, V>>(); //Create a new linked list at table[index]
}
//Search the list at table[index] to find the key.
for(Entry<K, V> nextItem : table[index])
{
//If search is successfu, replace the old value.
if(nextItem.key.equals(key))
{
//Replace value for this key
V oldVal = nextItem.value;
nextItem.setValue(value);
return oldVal;
}
}
//Key is not in table, add new item
table[index].addFirst(new Entry<K, V>(key , value));
numKeys++;
if(numKeys > (LOAD_THRESHOLD * table.length))
{
rehash();
}
return null;
}
public V remove(K key)
{
int index = key.hashCode() % table.length;
//If index is negative, add table.lenght
if(index < 0)
{
index += table.length;
}
if(table[index] == null)
{
return null; //Key is not in the list
}
}
/**
* Method rehash for class HashtableChin
* Here are the three main steps for the rehash method.
* 1. Allocate a new hash table that is double the size and has an odd length.
* 2. Rest the number of keys to 0.
* 3. Reinsert each table entry in the new hash table.
*/
private void rehash()
{
LinkedList<Entry<K, V>>[] oldTable = table;
//double capacity of this table and add 1
table = new LinkedList[2*oldTable.length+1];
//reset numkeys to 0
numKeys = 0;
//Reinsert all items in oldTable into expanded tabel
for(int i = 0; i < oldTable.length; i++ )
{
if(oldTable[index] != null)
{
}
}
}
}
Any help would be much appreciated.
Thanks