3. Hashtable with Quadratic Probing. Implement a simple hashtable using quadratic probing for collision resolution. 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