3. Hashtable with Quadratic Probing. Implement a simple hashtable using quadratic probing for collision resolution in Java. I have started it, but need help! Please follow the model I am sharing and comment the code! Thank you!!

Both the keys and values are integers, assuming greater than 0. The initial table size m should be 11 (it is too small for a real hashtable, we just use it for the purpose of this homework). Let n be the number of items in the table. When n ? m/2, use the technique of dynamic arrays to enlarge the table. You want to approximately double the table size but keep to the primes. The next table size m will be 23. You should use key%m as the hash function. Let b be the hash value modulo m. If bucket b is occupied, you probe (b + 12 ) % m,(b + 2 2 ) % m,(b + 32 ) % m, ,(b + (m/2)2 ) % m, and stop as soon as you find an empty bucket. As long as n is kept less than m/2, you will find an empty bucket by the end of the probing. You should at least implement the following functions: (a) void put(int key, int value): insert key-value pair to the hashtable. Insert key to the key array, value to the value array based on the hash function. (b) int get(int key): get the value of the key (c) boolean contains(int key): return true if the hashtable contains the key (d) void remove(int key): remove the key-value pair (e) void rehashing(): this method is called automatically when n ? m/2. You should enlarge the table and use findPrime(2 ? m) to get the new table size. You need to compute new hash index for every key stored in the existing hash table. (f) int findPrime(int x): find the next (the smallest) prime bigger than x. For example, findPrime(8) = 11, findPrime(22) = 23

public class MyHashTable { int[] keys; int[] values; int m; //table size int n; //item size public MyHashTable(int m){ this.m = m; keys = new int[m]; // creat two array for keys and values size m values = new int[m]; } int hash(int key){ return key % this.m;// m is prime numbers } // we need to implement put and get void printArray(){ System.out.println("key array: "); for (int i = 0; i < this.m; i++) if(keys[i] != 0) System.out.print("(" + i + ": " + keys[i] + ") "); System.out.println(" value array: "); for (int i = 0; i < this.m; i++) if(values[i] != 0) System.out.print("(" + i + ": " + values[i] + ") "); } //Implement other functions public void put (int key, int val)// hash the key hash of key { if (n+1) >= m/2){ System.out.println("Rehashing needed"); return; } int b = hash(key); if(this.key[b] > 0) // if there is colision here, if not we just insert the value and key { // rehashing function here // collision management System.out.println(" collision!"); } else { this.keys[b] = keys; this.value[b] = val; n +=1; } public int get (int key)// how do i read the value? { int b = hash(key); if(this.keys[b]==key) { retun values[b]; // if we do remove we need to check everything for empty space // } else{// either empty or had a collision and stored somewhere else System.out.println(" empty or collision!"); return -1; } return -1; } public static void main(String[] args) {// delete string args MyHashTable hashtable = new MyHashTable(11);// when do we need a rehashing? if we had 5, whats my new m? 2x11+1 = 23 System.out.println(hashtable.hash(5)); for(int i = 5; i <= 10; i++) //hashtable.put(11*i, 11*i*10); hashtable.put(i,i);// not coll hashtable.put(1,1);//for collision hashtable.put(2,2);//for collision hashtable.put(3,3);//for collision hashtable.printArray(); for(int i = 5; i <= 10; i++) // when collision doesnt happen //System.out.println(hashtable.get(11*i)); System.out.println("results from get " +hashtable.get(i)); //(example) when i = 5, rehashing function should be called automatically from put function //because hashtable has 5 items, m/2 = 11/2 = 5 //the size of new hashtable should be 23 for(int i = 5; i <= 10; i++) hashtable.put(11*i, 11*i*10); hashtable.printArray(); //put into the hashtable with more items //you can generate your own version of key-value pairs, do not have to (11*i, 11*i*10) //note that all keys and values must be nonzero, it is important. //because in this homework, we are assuming 0 as the empty bucket. //test other functions: remove, contain } }