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 linear probing 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 | 83 |
   +----+
 5 |  5 |
   +----+
 6 | 65 |
   +----+
 7 |    |
   +----+
 8 |  8 |
   +----+
 9 | 28 |
   +----+
   | :  |
   | :  |
   +----+
18 | 38 |
   +----+
19 | 18 |
   +----+
   | :  |
   | :  |
   +----+

On a search for 48, the algorithm will look at 8's bucket and move up until it either reaches 4 or it reaches an empty slot. In this case it looks at the keys in slots 8 and 9 before getting to the empty slot 10, so it looks at two of the inserted keys.