Lab 20: Resizing Hash tables
Intro
You’ll work in this lab with ad-hoc partners.
The two of you will work as a team to solve problems. At any time, one of you will be the Head and the other will be the Hands. The Head does the thinking and the Hands does the typing. Hands type only what the Head tells them to, but you’re free to discuss any issues that pop up. You should switch off during the lab to make sure each of you get practice problem solving, dealing with syntax, and getting finger exercises on the keyboard.
You should start this lab with this project skeleton.
Recall
We saw in lecture how to build a hash table implementation that correctly deals with hash collisions. Toward the end, we talked about resizing hash tables to maintain a bound on the number of hash collisions in a table.
Starting from the code from lecture, do the following.
Do we have a bound?
Consider the code we wrote in class. Is it true that the code as written maintains an invariant that the size of every ListTable is less than the bound?
If true, why is it true? (Make an argument to convince your partner.)
If false, construct a counter-example: a program that will end up with more than bound entries in a ListTable.
How long does a put take?
How long does the put method take when there is no need for a resize? How long does it take when there is a resize?
Is put guaranteed to terminate, i.e. can you write a program such that doing a put runs forever? If yes, make an argument for why. If no, make a program that runs forever when doing a put.
Evaluating performance
long startTime = System.nanoTime(); |
methodToTime(); |
long endTime = System.nanoTime(); |
|
long duration = (endTime - startTime); //divide by 1000000 to get milliseconds. |
Design a method that takes a table and inserts a given number of randomly generated key value pairs. (You can use Random.nextInt() to get a random integer.)
Use this method and the above approach to timing to compare the performance of inserting and looking up elements in both ListTables and HashTables with 100, 1000, 10000, and 1000000 elements.
Submission
Submit a zip file of your work at the end of lab.