Lab 19: Fixing 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 that a hash table built out of an array list of optional key value pairs has a bug when two entries have keys with the same hashCode() modulo table size. This is what’s called a hash collision.

There’s a failing test case in the skeleton that demonstrates the bug.

Fixing collisions

The idea for how to fix the problem is to change the representation to use a list of key value pairs for each entry in the array list. Each of these elements has in common that their hashCode() modulo table size are the same.

When looking something up, just like before, you must compute the appropriate index, but now you must scan through the list looking for a key that is equal.

When you put something in, just like before, you must compute the appropriate index, but now you must scan through the list looking for a key that is equal. If you find one, you should update the value. If you don’t, you should grow the list with the new key value pair.

Revise the design of HashTable to solve the collision problem.

Submission

Submit a zip file of your work at the end of lab.