Working with HashMaps to Explore Load Factor Performance

This homework will have you working with HashMaps. There are a lot of source files needed to make these classes work. Please pay careful attention to this document as I will give you directions on what you need to do for completion of this assignment.

I have modified the AbstractHashMap class so that it includes a “loadMax” instance variable. I have provided an accessor and mutator method for this variable as well. The loadMax variable will allow us to configure how often the table will be rehashed. In this homework assignment you will explore the effects of load factor on the performance of the hash table.

Task 1

In the file AbstractHashMap.java complete the getLoadFactor() method. (Hint: look at put() method for how to do this. Also see the text book on page 420).

Task 2

Modify the put() method in the file AbstractHashMap.java. Instead of resizing the Map when the load factor is >= .5, change it so that the Map is resized when the load factor is >= the loadMax.

Task 3

Read the engmix.txt file into an ArrayList. Each word should be an element in your ArrayList. (hint: use hasNextLine() and nextLine() methods). Print the first and last element from this list in your tester. You output should look like this:

Task 4

In the HashTester class you need to create tests to make sure your new methods work. I have provided sample output below. (Hint: default capacity is 17.). Create a new ChainHashMap that maps Strings to Integers. For the String just go through your list of words in your Array List created in Task 3. You can map each String to the order it was inserted (just an int counter in your loop). (hint: to print your hash map use System.out.println(chm.entrySet());. Here the variable chm is my ChainHashMap.) If you add the first 100 words to a ChainHashMap you should end up with this as the final state of the ChainHashMap:

Task 5

Now repeat Task 4 for a ProbeHashMap. However, in this case use load max = .5 for the first run, and use load max = .9 for the second run. You should fill out this table.

Task 6

1) Plot the data from your four experiments above. I have included a sample graph of some of my data for the first experiment. (Include the tables in your report as well). You should have 4 graphs.

2) In my data, the ChainHashMap is slower than the ProbeHashMap given the same number of Put / Get operations. (see data below). (note your data may be a lot different – your computer configuration can affect things greatly – this is why we focus on theoretical analysis in this class more so than experimental). Give a possible explanation for this variation in the same data. (note that the ChainHashMap used a load max of .75, while the ProbeHashMap used a load max of .

5. Therefore, the ProbeHashMap was rehashing more often … yet was still faster). (hint: think about what we have discussed in relation to caches effecting speed).

3) Which data structure can handle a load factor of > 1 and which one cannot? Why for each data structure?

4) What are the recommended load factor maxes for each data structure?

5) What load factor max does java use by default for a separate chaining hash map? 6) How do the hash maps ensure that the Map is never full? Explain what needs to happen when the current load factor gets to the load max value. 7) Turn in a PDF report that answers these questions, and includes graphs and tables with all of your data. Also turn in the source code for your entire project. Include ALL files in a single .zip file for submission.

Sample Graph