You are given the following classes: class LLNode { String key; String value; in
ID: 3836209 • Letter: Y
Question
You are given the following classes:
class LLNode {
String key; String value; int hashCode; LLNode next;
LLNode(String k, String v, int h, LLNode nxt) {
key=k; value=v; hashCode=h; next=nxt;
}
}
class Hashtable {
LLNode[] table;
int numValues;
float loadFactorThreshold;
Hashtable(float loadFactorThreshold) {...}
}
a) Implement a method in the Hashtable class to insert a key-value pair into the hash table, using the function k mod N to map a hash code k to a table location. N is table size (capacity):
// inserts (key,value) into hash table,
// calls rehash method (part b) if load factor threshold is exceeded public void insert(String key, String value) {
b) Also implement a rehash method, which doubles the table size when expanding it. NO new nodes should be created.
private void rehash() {
Explanation / Answer
PROGRAM CODE:
class LLNode {
String key; String value; int hashCode; LLNode next;
LLNode(String k, String v, int h, LLNode nxt) {
key=k; value=v; hashCode=h; next=nxt;
}
}
class Hashtable {
LLNode[] table;
int numValues;
float loadFactorThreshold;
int threshold;
Hashtable(float loadFactorThreshold, int capacity) {
numValues = 0;
threshold =(int)( capacity*loadFactorThreshold);
this.loadFactorThreshold = loadFactorThreshold;
table = new LLNode[capacity];
}
public void insert(String key, String value) {
int hashcode = key.hashCode();
int index = hashcode%table.length;
if(table[index]!= null)
{
LLNode temp = table[index];
while(table[index].next != null)
temp = temp.next;
temp.next = new LLNode(key, value, hashcode, null);
}
else
table[index] = new LLNode(key, value, hashcode, null);
numValues++;
if(numValues==threshold)
rehash();
}
private void rehash() {
int oldCapacity = table.length;
int newcapacity = 2*oldCapacity + 1;
LLNode oldTable[] = table;
LLNode newTable[] = new LLNode[newcapacity];
threshold =(int)( newcapacity*loadFactorThreshold);
table = newTable;
for (int i = oldCapacity ; i-- > 0 ;) {
for (LLNode old = oldTable[i] ; old != null ; ) {
int hashcode = old.key.hashCode();
int index = hashcode%newcapacity;
LLNode newNode = old;
newNode.next = newTable[index];
newTable[index] = newNode;
old =old.next;
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.