This assignment is due on 08/02/18 at 11:59:59am.This assignment should be according to the given notes ONLY.

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 void setValue(String v) {this.value = v;} 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(); } 

Requirements:

Implement the ProbeHashMap class as we discussed in the lectures.

Your implementation has to follow the specification given. Any other implementation (there are tons of HashTable code on the Internet) will not receive any credit.

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. Note that your implementation will be evaluated by a specific test program while being graded.

Bonus: 10 point bonus will be given for those implementation that prints out the number collisions while the 100 data items are inserted into the hash table. Hint: to do that, you may want to change the return type of the put() method to int type, which is the number of collisions. Your README file must state the bonus option you are taking to earn the bonus.

Submission:

Each student submits one copy of the source code: ProbeHashTable.java, AbstractHashMap.java, AbstractMap.java, MapEntry.java and Test.java.

Create a folder and name it as your Linux user account, e.g., hwang_hw8, by the following command:

$ mkdir hwang_hw8 

Copy all your source code to the above folder (clean your source code folder and remove all class files). Linux copy command is "cp filename destination_folder".

Compile a README file (in text format only, do not use Microsoft, use gedit instead) and provide the following:

Your name and

Compiling instruction

A sample test run (again in text)

Existing bug (things not finished)

Log in grail, go to the parent director of the folder you created, and run (suppose the your folder is "hwang_hw8")

turnin -c cis265w -p hw8 hwang_hw8 

If there is no error message, your submission is successful.

Protected int n20; 11?of-entries. Protecter int aacit of size of tha potces int Prime Potetke int Shift l, Shift 2 ?. Protected-long-Scale, offset, ll constructo Pubic int size) Freum n3 leon isEmp-y Pubic object get Ckey is)e Pubic Ober remove Cke k) etum un bucket femoveChik)