Suppose that we are storing a set of \(n\) keys into a hash table of size \(m\). Show that if the keys are drawn from a universe \(U\) with \(\lvert U \rvert > nm\), then \(U\) has a subset of size \(n\) consisting of keys that all hash to the same slot, so that the worst-case searching time for hashing with chaining is \(\Theta(n)\).

This can be solved using a tight-pigeonhole argument. If \(m-1\) slots contain at most \(n-1\) elements then the remaining slots must have at least \(n\) keys. These \(n\) keys all hash to the same slot, resulting in a worst-case \(\Theta(n)\) search time with chaining.

In other words, our remaining slot count is:

\[\begin{equation} \lvert U \rvert -(m-1)(n-1)>nm-(m-1)(n-1)=n+m-1\geq n \end{equation}\]