Lab 12: Hash tables

Task 1: Review hash table basics

Your work for this task should be done on paper. Please show your work to a staff member before you leave the lab.

Consider the hash table shown below. Assume that:

• It was filled using the hash function from lecture:

  h(key) = key.charAt(0) - 'a'
  

  (In other words, the hash code of a key is the ASCII code of its first character minus the ASCII code of 'a'.)

• Collisions were resolved using linear probing.

• Gray cells are ones from which an item has been removed.

• White cells are ones in which an item has never been inserted.

• Occupied cells contain the key of their key-value pair.

1. Which item in the table has been inserted incorrectly? How can we be certain?

2. If we insert an item with a key of "ferret" into the table using linear probing, what is the probe sequence that would be used? (In other words, what sequence of positions would be considered by the insert() method to determine where the item should go?)

3. If we insert an item with a key of "ferret" into the table using linear probing, where would it end up?

Now consider the following hash table, which was filled using the same hash function but with quadratic probing.

4. If we insert an item with a key of "dolphin" into the table using quadratic probing, what is the probe sequence? Where would the item end up?

5. After inserting "dolphin", we now insert an item with a key of "ant" using quadratic probing. What is the probe sequence? Where would the item end up?

6. If this table were implemented using the same hash function but with separate chaining, what it would look like? Include both the original keys and the new ones ("dolphin" and "ant").

Task 2: Practice using a hash table

In lecture, we have been considering the OpenHashTable class. Let’s practice writing client code for this class.

Begin by downloading the following zip file: lab12.zip

Unzip this archive, and you should find a folder named lab12, and within it the files you will need for this lab.

In DrJava, open OpenHashTable.java, compile it, and then take the following steps from the Interactions Pane.

1. Create an instance of the class:

   > OpenHashTable table = new OpenHashTable(7);
   

   This will create an OpenHashTable object with a size of 7. It will use double hashing, because that is the default method of probing in the OpenHashTable class.

2. Insert several key-value pairs:

   > table.insert("ant", 23);
   > table.insert("bee", 10);
   > table.insert("ant", 30);
   

3. If we remove the semi-colon from the calls to insert(), the Interactions Pane will show us that this method returns either true (if the key-value pair was successfully inserted) or false (if there was overflow and the key-value pair could not be inserted).

   > table.insert("bee", 50)
   true
   

4. We can then search for a given key as follows:

   > table.search("ant")
   {23, 30}
   > table.search("antelope")
   null
   

   Note that search() returns either an LLQueue object containing the values associated with the key (which is displayed as a set of values), or null if the key isn’t found.

5. Now perform the following insertion:

   > table.insert("cow", 10);
   

   The key "cow" now has a single value associated with it. Complete the following line of code so that it retrieves the queue containing this value and assigns it to the variable values:

   > Queue<Object> values = _______________________;
   

6. Check that the queue contains the expected value:

   > values
   {10}
   

7. Now let’s say that you want to change the value associated with the key "cow" – multiplying its current value (which you should pretend that you don’t know) by 2.

   To do so, you will need to do the following:

   • remove the current value from the queue, using casting to obtain a value that is an integer:

     int val = (Integer)values.remove();
     

   • insert the doubled value in the queue:

     values._____________________________
     

     (If necessary, consult the Queue interface to remind yourself of the signature of the method you should use.)

8. Use the search() method to check that the value associated with "cow" has been changed:

   > _____________________________
   {20}
   

Task 3: Use a hash table to optimize an algorithm

In Problem Set 4, we considered the pair-sums problem:

Suppose you are given an array of n integers, and you need to find all pairs of values in the array (if any) that sum to a given integer k. For example, if k is 12 and the array is {10, 4, 7, 7, 8, 5, 15}, your code should output something like the following:

4 + 8 = 12
7 + 5 = 12
7 + 5 = 12

We considered two possible approaches:

• Brute force: Try all possible pairs of values in the array. This requires O(n²) steps.

• Sort the array using an efficient sorting algorithm like merge sort, and then use an approach similar to the one taken in partitioning to find the relevant pairs. This requires O(nlogn) steps.

Using a hash table, we can solve this problem using O(n) steps! Use an instance of our OpenHashTable class to do so.

• Implement the findPairSumsHash() method in the Lab12Task3.java file that we’ve provided.

• To ensure that you obtain adequate performance, use a hash table that is twice the size of the original array. This will ensure that the load factor is <= 0.5, which is the recommended maximum load when using open addressing.

• In the example above, we obtained two 7 + 5 sums because 7 appears twice in the array. While the method that you write may print a given pair of values more than once in such cases, it is not necessary to do so.

• In addition, the order in which the sums (and the terms within each sum) are printed does not matter.

• If no pairs are found, the method does not need to print anything.

When you think you have a working solution, test it!

> int[] arr = {10, 4, 7, 7, 8, 5, 15};
> Lab12Task3.findPairSumsHash(12, arr);
8 + 4 = 12
5 + 7 = 12
> Lab12Task3.findPairSumsHash(11, arr);
7 + 4 = 11
7 + 4 = 11

Task 4: Submit your work

You should show the paper with your work to the teaching assistant.

You should use Apollo to submit your modified Lab12Task3.java file.

Don’t worry if you didn’t finish all of the tasks. You should just submit whatever work you were able to complete during lab.

Here are the steps:

1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
2. Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
3. Find the appropriate lab section on the main page and click Upload files.
4. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
5. Click the Upload button at the bottom of the page.
6. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
7. Once all of your files have been successfully uploaded, return to the upload page by clicking the link at the top of the results page. The upload page will show you when you uploaded each file, and it will give you a way to view or download the uploaded file. Click on the link for each file so that you can ensure that you submitted the correct file.