Practice Exercises: Hash tables

Exercise 1

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 \mod 9$.

Exercise 2

Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the professor’s modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions?

Exercise 3

Consider inserting keys into a hash table of length $m = 13$ using open addressing with the auxiliary hash function $h'(k) = k\mod m$. Does quadratic probing with $c_1 = c_2 = 1$ result in a probe sequence that is a permutation of $0, 1, \dots, 12$? Justify your answer.

Exercise 4

(a) Assume that we are using a hash table of size $m$. Show that if the universe $U$ has size $|U| > nm$, there is a subset of $U$ of size $n$ with the property that they all hash to the same position, so that the worst-case searching time for hashing with chaining is $\Theta(n)$.

(b) We are storing a set $S$ of $n$ numbers in a hash table $T[0..m-1]$ of size $m$ and we are choosing $m=n$. Should we resolve collisions with chaining or open addressing? Explain your answer.

In [ ]: