1)
Implement the put(key, value) method. The template for the
put(key; value) method
is listed as below. There are three lines missing. Please fill in the three lines so that the program can run and get the correct counting. Note that your counting result should be the same as using the Heap method.
2)
A careful reading of the program reveals that the
myhash()
method is too slow. The approach and the formula it uses has no problem, but the code is too slow. This code is slow because of the invocation of the power function Math.pow(). Please rewrite the code using Horners method, so that in each loop you only need to a multiplication once.
I have highlighted the part that need fixing. Everything else is fine. Must be done in java.
HashMap Code:
/** HashMap for 254. A simplified version of HashMap. * Use separate chaining to resolve collisions. */ import java.util.LinkedList; import java.util.Random;
public class HashMap254 { private static final int INIT_CAPACITY = 4; private int n; // number of elements private int m; // hash table size private LinkedListForHash254[] st; // array of linked-list. public HashMap254() { this(INIT_CAPACITY); }
// used in resize. public HashMap254(int m) { this.m = m; st = (LinkedListForHash254[]) new LinkedListForHash254[m]; for (int I = 0; I <> st[i] = new LinkedListForHash254(); }
// resize the hash table to have the given number of chains, // rehashing all of the keys private void resize(int n) { HashMap254 temp = new HashMap254(n); for (int I = 0; I <> for (Key key : st[i].keys()) { temp.put(key, st[i].get(key)); } } this.m = temp.m; this.n = temp.n; this.st = temp.st; }
// hash value between 0 and m-1
private int myhash(Key key) {
int hash = 7;
String k = (String) key; //here we assume keys are strings.
int base=31;
for (int I = 0; I <>
//calculate hashcode (h1) using polynomial method:
// hash=base^{n-1} key[0]+base^{n-2} key[1] +....+key[n-1]
hash=(int)Math.round((Math.pow(31,k.length()-i-1)))*k.charAt(i)+hash;
//Implement h2 using division method
hash=Math.abs(hash) % m;
return hash;
}
public Value get(Key key) { int I = myhash(key); return st[i].get(key); }
public void put(Key key, Value val) {
// double table size if load factor m/n >0.1
if (n >= 10 * m)
resize(2 * m);
// Put your code here.
// 1) get the hash value of the key i.
// 2) then put (key, value) in the i-th linkedList implemented in LinkedListForHash254
// 3) you need to handle the case whether the key is already there.
int I = myhash (key);
if (st[i]. get (key )== null )
n++;
st[i]. put (key , val );
}
public void delete(Key key) { if (key == null) throw new IllegalArgumentException(“argument to delete() is null”); int I = myhash(key); if (st[i].get(key)!=null) n--; st[i].delete(key);
// halve table size if average length of list if (m > INIT_CAPACITY && n <=> resize(m / 2); }
public LinkedList keys() { LinkedList queue = new LinkedList(); for (int I = 0; I <> for (Key key : st[i].keys()) queue.add(key); } return queue; } }
Linked List Code:
import java.util.LinkedList; public class LinkedListForHash254 { private int n; // number of key-value pairs private Node first; // the linked list of key-value pairs
// a helper linked list data type private class Node { private Key key; private Value val; private Node next;
public Node(Key key, Value val, Node next) { this.key = key; this.val = val; this.next = next; } }
public LinkedListForHash254() { }
public LinkedList keys() { LinkedList queue = new LinkedList(); for (Node x = first; x != null; x = x.next) queue.add(x.key); return queue; } public Value get(Key key) { for (Node x = first; x != null; x = x.next) { if (key.equals(x.key)) return x.val; } return null; } public void put(Key key, Value val) { if (val == null) { delete(key); return; }
for (Node x = first; x != null; x = x.next) { if (key.equals(x.key)) { x.val = val; return; } } first = new Node(key, val, first); n++; }
public void delete(Key key) { first = delete(first, key); }
private Node delete(Node x, Key key) { if (x == null) return null; if (key.equals(x.key)) { n--; return x.next; } x.next = delete(x.next, key); return x; }
}