As a first step, you should download the source code from moodle. Note that there are two variations of a HashMap implementation in this code. The first class is called HashMap and it implements a fixed (but developer specified) capacity HashMap. Once the capacity is reached the put() method throws an unchecked MapFullException. The second class is called RehashableHashMap. This class extends the basic HashMap class and implements support for rehashing when a fixed load factor is reached. This flexibility has been achieved by created a protected checkCapacity() method that can be overridden in subclasses. The default implementation does the capacity check while the overriding implementation in the RehashableHashMap class changes the behaviour to do a load factor check and where necessary, rehashing of the map.
(a) Before working on the code, lets start by identifying a new hash function and testing it manually (as a dry run) with some sample data. As discussed in the lecture, you can use an excel spreadsheet to do this).
Let's use an array of size 19 and the following MAD compression map: compression_map(x) = (3x + 7) % 19
Now, draw out the state of the hash map after inserting each of the following integer keys:
15, 7, 26, 39, 11, 9, 27, 5, 18, 2, 54, 22, 4
Ask a demonstrator to check you have the correct answer.
(b) Now, create a subclass of the HashMap class called MADHashMap and override the hashFunction() method to implement the compression map from (a). To replicate the map in (a) you will need to create a default constructor that invokes the constructor in the HashMap class, passing in the value 19 (this is the size of the map used in (a)).
(c) As a final step, create a test class with a main() method that performs the same operations as those listed in (a). Remember, (a) gave only the keys. You can use a String value type for your test class and use null or an empty string for the value (the same value can be used for all entries).
Print out the state after each operation (using the toString() method) and confirm that the output matches your answer to part (a).
This second problem is more complex as you need to modify the put(), get() and remove() operations. It is important that you read up on double hashing before you attempt the answer. Remember that the main difference between it and linear probing is the increment you apply when you probe for linear probing, it is 1; while for double hashing, it is d(k), where d(k) is the second hash function.
(a) As with part 1, before working on the code, let's start with my exploring a dry run to better understand how it will work. Let's reuse the example keys from 1(a), but instead of using linear probing, we will use double hashing using the 2'd hash function d(x) = 11 (x % 11). Again, write your answer in an excel spreadsheet, and if possible, ask a demonstrator to check you have the correct answer.
(b) Now, create a subclass of MADHashMap called DoubleMADHashMap. This means that we can reuse the hash function and the constructor from MADHashMap. Next, create a protected method called doubleHash() that implements the double hash function d(x) from 2(a). Finally, copy the get(), remove() and put() methods from the HashMap class and modify them to use the double hash function instead of linear probing.
(c) Copy your test program from 1(a) and modify it to use the MADHashMap. Run the program to confirm that the states match the states in 2(a).