Exercise 11.2.2

Demonstrate what happens when we insert the keys 5, 28, 19, 15, 20, 33, 12, 17, 10 into a hash table with collisions resolved by chaining. Let the table have 9 slots, and let the hash function be $h(k) = k \bmod 9$.

First, let's calculate the hashes:

h(5)  = 5
h(28) = 1
h(19) = 1
h(15) = 6
h(20) = 2
h(33) = 6
h(12) = 3
h(17) = 8
h(10) = 1

Next, let's ASCII-ART this bad boy:

  +-----+
0 |     |
  +-----+
1 |  o--|---> [ 10 ] ---> [ 19 ] ---> [ 28 ]
  +-----+
2 |  o--|---> [ 20 ]
  +-----+
3 |  o--|---> [ 12 ]
  +-----+
4 |     |
  +-----+
5 |  o--|---> [  5 ]
  +-----+
6 |  o--|---> [ 33 ] ---> [ 15 ]
  +-----+
7 |     |
  +-----+
8 |  o--|---> [ 17 ]
  +-----+

Where each cell of the array is a null pointer (empty bucket) or the pointer to a head of a linked list.