Lab 8: Hash Tables
Due: Thursday, Mar. 31, 11:59pm
During this lab we'll be implementing a Hash Table. For this lab, you are welcome to use pair programming (two people, one computer, make sure to switch off who is at the computer every 30 minutes).
The skeleton of the hash table class is given in Table.java, and the file TestTable.java will help you test your code. The implementation has gaps in some of the method definitions. Your job is to fill them in, using the comments that have been added as a guide. Note that this class uses two private functions, hash() and locate(). These are private so as to hide the details of where a key gets stored from the public interface. The first simply calculates the hash of a given key. The second is called by both insert() and lookup() to determine where a particular key should end up in the table, after handling collisions. When you implement lookup(), you should use linear probing.
First, look at the small class at the end of Table.java, which is where we store the (key, value) pairs. This is what we talked about in class: a data structure that can store whatever data we would like to keep in our hash table. Create two fields, the key and the value, then initialize them in the constructor.
Next, implement the hash function. This should be the first function discussed in class:
h(k) = k mod n
Now we will implement locate, which should return the index where our data will be stored (but shouldn't store it just yet, it's a helpful function). First locate should call the hash function. If this position is full, it should add 1 to the position until an empty position is found (hint: what type of loop would this be?) Assume for now our hash table is not full, so there will always be an empty slot.
Next, implement insert, using locate. This should create a new TableRow and also increment the number of elements stored in the hash table.
Finally, implement lookup, which should return the value associated with the given key. Return null if there is nothing associated with that key.