Another option for resolving collisions is to use linear probing. Instead of resolving collisions by putting keys into a linked list, linear probing resolves collisions by putting keys into empty slots in the hash table. If the slot given by h(k) is occupied, check h(k)+1, h(k)+2, etc., until an empty slot is found. If we reach the end of the table, we wrap around to check slots 0, 1, ..., h(k)-1.

A

Given input keys {4371, 1323, 6173, 4199, 4344, 9679, 1989} and a hash function h(x) = x mod 10, draw the resulting hash table, if collisions are resolved with linear probing. Assuming there are 10 slots in the table. Make sure you label the indices of your table.

B

Suppose we add the keys {4356, 5876, 1288, 9768} to the hash table above, after the keys from 6A have been added. Where would the key 9,768 be hashed?