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 separate chaining 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: (You can have the buckets reversed if you like; but in practice, since it's easier to insert at the head of a linked list, it will look like this.)

   +----+
   | :  |
   | :  |
   +----+
 3 |    |  +----+---+  +----+---+
   |  *-+->| 83 | *-+->|  3 | *-+->NULL
   +----+  +----+---+  +----+---+
 4 |    |
   |  *-+->NULL
   +----+
 5 |    |  +----+---+  +----+---+
   |  *-+->| 65 | *-+->|  5 | *-+->NULL
   +----+  +----+---+  +----+---+
   | :  |
   | :  |
   +----+
 8 |    |  +----+---+  +----+---+
   |  *-+->| 28 | *-+->|  8 | *-+->NULL
   +----+  +----+---+  +----+---+
   | :  |
   | :  |
   +----+
18 |    |  +----+---+  +----+---+
   |  *-+->| 18 + *-+->| 38 | *-+->NULL
   +----+  +----+---+  +----+---+
   | :  |
   | :  |
   +----+

On a search for 48, the algorithm will search the 8's bucket. Since the bucket has two elements, the search will look at two keys.