# 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 [ ]: