DoubleHashing:

Part A) Implement a DblHashMap class. Your implementation should be very similar to ProbeHashMap class below except for the findSlot method.

Hint for DblHashMap An easy way is to directly use the hashValue (obtained in AbstractHashMap) as the key value to generate h'(). So, it is actually h'(h(key)).

Part B) Improve your ProbeHashMap class below by adding a module that keeps track of the number of collisions.

Hint for counting the collisions: Given the provided compareStr(String s, String t) method inProbeHashMap.java, it is straightforward to revise it a little to correctly count the number of collisions. Notice that the current method is implemented as:

private boolean compareStr(String s, String t) { count++; return s.equals(t); }

To correctly count the number of collision, we only need increment count when string s is not equivalent to string t. So you only need to add a if-else branch to correctly count the number of collisions. In addition, you may want to add a countClear(0 method to allow the user to clear the counter for different tests.

//ProbeHashMap.java

import java.util.Iterator;

public class ProbeHashTable extends AbstractHashMap{

private MapEntry[] table;

private MapEntry DEFUNCT = new MapEntry(null, null);

private int count = 0;

public ProbeHashTable() {

super();

}

public ProbeHashTable(int cap,int p) {

super(cap, p);

}

private boolean compareStr(String s, String t) {

count++;

return s.equals(t);

}

protected void createTable() {

table = new MapEntry[capacity];

}

private boolean isAvailable(int i) {

return (table[i] == null || table[i] == DEFUNCT);

}

private int findSlot(int h, String k) {

int available = -1;

int j = h;

do {

if(isAvailable(j)) {

if(available == -1)

available = j;

if(table[j] == null)

break;

} else if(compareStr(table[j].getKey(),k))

return j;

j = (j + 1) % capacity;

}

while(j != h);

return -(available + 1);

}

protected Object bucketPut(int h, Object key, Object value) {

int slot = findSlot(h, (String) key);

if(slot >= 0)

return table[slot].setValue((String) value);

table[-(slot + 1)] = new MapEntry((String) key, (String) value);

n++;

return null;

}

protected Object bucketGet(int h, Object key) {

int j = findSlot(h, (String) key);

if(j < 0)

return null;

return table[j].getValue();

}

protected Object bucketRemove(int h, Object key) {

int i = findSlot(h, (String) key);

if(i < 0)

return null;

Object answer = table[i].getValue();

table[i] = DEFUNCT;

n--;

return answer;

}

private class KeyIterable implements Iterable{

public Iterator iterator() {

ArrayList buffer = new ArrayList(n);

for(int i = 0; i < capacity; i++)

try {

if(!isAvailable(i))

buffer.add(buffer.size(), table[i].getKey());

}

catch(OutOfRangeException e) {

System.out.println("keySet: Out Of Range");

}

return new SArrayIterator(buffer);

}

}

public Iterable keySet() {

return new KeyIterable();

}

public int getCollisions(){

return count;

}

public String toString() {

String str = "";

for (int i = 0; i < capacity; i++) {

if(!isAvailable(i)) {

String key = table[i].getKey();

int tableValue = table[i].getValue().indexOf("\t");

String value = table[i].getValue().substring(tableValue);

str += hashValue(key) + " " + key + " " + value + " ";

}

}

return str;

}

}

//AbstractHashMap.java

import java.util.Random;

public abstract class AbstractHashMap extends AbstractMap {

protected int n = 0;

protected int capacity;

private int prime;

private long scale, offset; //scale=a, offset=b

public AbstractHashMap() { //default constructor

this(61, 999331);

}

public AbstractHashMap(int cap, int p) { //overloaded constructor

this.capacity = cap;

this.prime = p;

Random rand = new Random();

this.scale = rand.nextInt(prime - 1) + 1;

this.offset = rand.nextInt(prime);

createTable();

}

public int size() {

return n;

}

public boolean isEmpty() {

return n == 0;

}

protected int hashValue(Object key) {

return (int) ((Math.abs(key.hashCode() * scale + offset) % prime) % capacity);

}

public Object get(Object key) {

int h = hashValue(key);

return bucketGet(h, key);

}

public Object remove(Object key) {

int h = hashValue(key);

return bucketRemove(h, key);

}

public Object put(Object key, Object value) {

int h = hashValue(key);

return bucketPut(h, key, value);

}

protected abstract void createTable();

protected abstract Object bucketGet(int h, Object k);

protected abstract Object bucketRemove(int h, Object k);

protected abstract Object bucketPut(int h, Object k, Object v);

}

//AbstractMap.java

public abstract class AbstractMap {

public abstract Object get(Object key);

public abstract Object put(Object key, Object value);

public abstract Object remove(Object key);

public abstract boolean isEmpty();

public abstract int size();

public abstract Iterable keySet();

}