COMP1927 14s2 Final Exam

Question 5 (9 marks)

Consider a scenario where we have

a hash table with 7 slots,
key values are positive integers,
a hash function h(x) = x%7,
a secondary hash function h2(x) = x%5

Based on the above answer the following questions:

In the ideal case (no collisions), what is the complexity of searching for a key in a hash table with N slots?
Consider the scenario where the above hash table uses chaining for collision resolution, and has the following distribution of chain lengths: 2 slots are empty, 2 slots have a chain of length 1, 1 slot has a chain of length 2, 1 slot has a chain of length 3, and 1 slot has a chain of length 4.
1. What is the minimum number of key comparisons required to search for a key in this table?
2. What is the maximum number of key comparisons required to search for a key in this table?
Now consider the scenario where the hash table uses linear probing for collision resolution. If we start from an initially empty hash table and insert the following keys (in the order supplied) into the table:
```
11  21  31  32  12  22  24
```
show the state of the hash table after the insertion of each key. (The q5.txt file contains a template for how to show the table, and even shows the state of the table after the insertion of the first key).
Now consider the scenario where the hash table uses double hashing for collision resolution, with h2 as the secondary hash function. If we start from an initially empty hash table and insert the following keys (in the order supplied) into the table:
```
11  21  31  32  12  22  24
```
show the state of the hash table after the insertion of each key. (The q5.txt file contains a template for how to show the table, and even shows the state of the table after the insertion of the first key).

Type the answer to this question into the file called q5.txt and submit it using the command:

$ submit q5

The above command will make a copy of q5.txt as your answer for this question.