Overview
This lab gives a quick peek at the implementation of hash tables. Since the lab period is not that long, you will be filling in parts of an existing class definition to create a working class. Next, you will use that class to explore the relationship between table fullness and collision frequency.
The skeleton of the hash table class is given in Table.java and TestTable.java. 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, because the implementation of remove() assumes this. You are not asked to implement remove() because of the short time frame of this lab.
To Do
First, fill in the implementation in Table.java according to the comments. You can use TestTable.java to see if everything is working.
Now you will do a little experimentation. Before you begin, write down a guess for the following values:
- Mean number of collisions per insertion with {50, 80, 95} items in a table of size {101, 151, 199}. (This will be 9 guesses; make a little grid.)
- Maximum displacement with {50, 80, 95} items in a table of size {101, 151, 199}. (This will be 9 guesses too.)
Now look at TableStats.java, which reads in a file containing key/data pairs, stores each pair in a table, and keeps track of statistics about how often collisions occur. Using three input files (states, animals, and foods), you can test the interaction between number of elements and table size. Test each file with tables of size 101, 151, and 199 (all primes) and make a little chart showing the results. Compare them to your guesses. Are you close? Write a short summary file about what you've learned.
To Submit
- Table.java (as modified by you)
- readme.txt
- typescript (showing your TestTable program running)