Answer: Hashing

Question: In the following, say our hash function for n is n % 20 and our second hash function, where applicable, is (n % 7) + 1.

Say we use double hashing for collision resolution. Beginning with an empty hash table, we insert the following.

How will the hash table look after the final insertion? If we then search for 48, how many of the inserted keys will we look at?

Answer:

   +----+
   | :  |
   | :  |
   +----+
 3 |  3 |
   +----+
 4 |    |
   +----+
 5 |  5 |
   +----+
 6 |    |
   +----+
 7 |    |
   +----+
 8 |  8 |
   +----+
 9 | 28 |
   +----+
10 | 83 |
   +----+
11 | 65 |
   +----+
12 |    |
   +----+
13 | 18 |
   +----+
   | :  |
   | :  |
   +----+
18 | 38 |
   +----+
19 |    |
   +----+

On a search for 48, the algorithm will look at 8's bucket and move up until it either reaches 48 or it reaches an empty slot. In this case it looks at the key in slot 8 before reaching slot 15 and halting on this empty slot; so it sees one key only.