Please help:

Step 1: Hash Code Generation.

Create a map elements class for pairs. This will be a non-generic implementation. Specifically, have Keys of Integer type, while Values can be anything you want. Ensure your implementation has the following two methods (in addition to standard methods you will need):

a. Write a constructor that generates a new pair with a random Integer key.

b. Write a method: public int hashCode(). This should implement one of the hashing methods discussed in class (e.g., polynomial accumulation, Unicode, etc.). The output of hashCode() is int; your hash does not have to use the full capacity of int but should be at least 16 bits.

Step 2: Compression and Hash Tables.

Create an abstract hash table with a fixed capacity (passed in as an int at construction time). Create a set of children classes that are concrete hash tables that implement the following collision resolution mechanisms: (1) separate chaining (the bucket object can be any suitable data structure), (2) linear probing, and (3) quadratic probing. Any function that is the same across these three implementations should be placed in the abstract parent class. To compress the output of hashCode() to an index in the table, mod the output by the capacity of the table. The following methods should be supported:

Size(): Returns the number of entires in M.

isEmpty(): Returns a boolean indicating whether M is empty.

get(k): Returns the value v associated with key k, if such an entry exists; otherwise returns null.

put(k, v): If M does not have an entry with key equal to k, then adds entry (k, v) to M and returns null; else, replaces with v the existing value of the entry with key equal to k and returns the old value.

Remove(k): Removes from M the entry with key equal to k, and returns its value; if M has no such entry, then returns null.

Step 3: Instrumentation.

Instrument your hash table with the following data gathering methods. Each invocation of put(k,v) should print out:

the size of the table,

the number of elements in the table after the method

the number of keys that resulted in a collision (you do not have to decrement this amount after a remove),

the number of probing attempts before adding the element (for linear/quadratic probing only) and the number of items in the bucket (for separate chaining).

Additionally, each invocation of get(k), put(k,v), and remove(k) should print the time used to run the method. If any put(k,v) takes an excessive amount of time, handle this with a suitable exception.

Step 4: Validate.

Construct a hash table with each of the three collision resolution mechanisms (separate chaining, linear probing and quadratic probing), each with capacity of 100 (note: you should never use a nonprime in practice but do this for the purposes of this experiment). For each table, generate 50 random pairs and run put(k,v) on each pair. Next run get(k) on each of the 50 keys. Then run remove(k) on the first 25 keys, followed by get(k) on each of the 50 keys. Ensure your table functions correctly for all values.

Step 5: Experiment and Interpret.

Construct a new hash table of each of the three types, each with capacity 100. Now generate 150 pairs. Write a short document to: 1) Describe (by inspection or graphing) how the time to run put(k,v) increases as you approach (for example) 50 values, 75 values, 95 values, 100 values, and 150 values; and provide reasons for your observations. 2) If your put(k,v) method takes an excessive amount of time, describe why this is happening and why it happens at the value it happens at. 3) Re-run the experiment for quadratic probing with a table that has capacity of 101 (which is a prime number). Does this make a difference for any of the experiments? If so, why?

Step 6: Dynamic Resizing.

For one of the hash collision resolution mechanisms (either one is fine), implement dynamic resizing. For dynamic resizing, the capacity of the table should start at 128 and double every time size() reaches one half of the tables capacity. That is, once 64 out of 128 elements have been added, the capacity will increase to 256. Benchmark the cost of adding 10,000 elements to the table, the cost of an additional put(k,v) on a table of this size, and the cost of a get(k).