Task: Implementation of the ProbeHashTable class with linear probing. The template of ProbeHashTable class and relevant classes are given below:

public class ProbeHashTable extends AbstractHashMap { private MapEntry[] table; private MapEntry DEFUNCT = new MapEntry(null,null); //constructors protected void createTable() { // your implementation here } private boolean isAvailable(int i) { // your implementation here } private int findSlot(int h, String k) { // your implementation here } protected Object bucketPut(int h, Object key, Object value) { // your implementation here } protected Object bucketGet(int h, Object key) { // your implementation here } protected Object bucketRemove(int h, Object key) { // your implementation here } public String toString() { // convert the ProbeHashTable object to a string in the format of // "index key value" tuples, for example // 0 CSU OHIO // 1 CLE PIT // 2 PLAY HOUSE } } 

public class MapEntry { private String key; private String value; // constructor public String getKey() {return key;} public String getValue() {return value;} public int hashCode() { int h = 0; for (int i=0; i>>27); h += (int)key.charAt(i); } return h; } } 

public abstract class AbstractHashMap extends AbstractMap { protected int n = 0; // the number of entries protected int capacity; // size of the map private int prime; // the prime number private long scale, offset; // a = scale, b = offset public AbstractHashMap() { capacity = 199; prime = 999331; Random rand = new Random(); scale = rand.nextInt(prime-1) + 1; offset = rand.nextInt(prime); createTable(); } public AbstractHashMap(int c, int p, long scale, long off) { this.capacity = c; this.prime = p; this.scale = scale; this.offset = off; createTable(); } public int size() {return n;} public boolean isEmpty() {return n == 0;} public 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); } 

public abstract class AbstractMap { public Object get(Object key); public Object remove(Object key); public Object put(Object key, Object value); public int size(); public boolean isEmpty(); } 

Implement the ProbeHashMap class using skeleton codes above and below. Implementation has to follow the specification given. Any other implementation will not be accepted.

Test: write a test program to create a hash table with the default size. Insert 100 data items (random strings) and then remove 10 of them. Finally, please print out the remaining items in the hash table. Submit your filles with source codes for classes ProbeHashTable.java, AbstractHashMap.java, AbstractMap.java, MapEntry.java and Test.java.

Skeleton codes with more info listed below. Please follow skeleton ONLY.

public class ProbeHashMap extends Abstract HashMap { private MapEntry[] table; private MapEntry DEFUNCT = new MapEntry(null, null);

//constructor //construction process should allocate the tablle

private boolean isAvailable(int i) { return(table[i] == null) || (table[i] == DEFUNCT); }

private int findSlot(int h, String k) { int avail = -1; int i = h; do { if(isAvailable(i)) if (avail == -1) avail = i; if (table[i] == null) break; } else if (table[i].getkey().equals(k)) ---- treat is as the pseudocode and write a method to perform comparism return i;

i = (i+1)%capacity; } while (i!=h) return -(avail+1); }

protect Object bucketGet(int h, Object key) { int i = findSlot(h, (String)key); if(i<0) return null;

return table[i].getValue(); }

protected Object bucketPut (int h, Object key, Object value) { int i = findSlot(h, (String)key); if(i>=0) return table[i].setValue(value); table[-(i+1)] = new MapEntry(key, value); .........where key and value are strings n++; return table[i].getvalue(); }

protected Object bucketRemove(int h, Object key) { int i = findSlot(h, (String)key); if (i<0) return null; String answer = (String) table[i].getvalue(); table[i] = DEFUNCT; n--; return answer; }