Self doubt

Question

Let |U| =  $m^{2}$and consider hashing with chaining. For any hash function h : U → {1, 2, . . . , m − 1}, there exists a sequence of m insertions that leads to a chain of length m. Explain

Answer 1

I think the hash function is h: U → {0,1,2,.....,m-1}

Let us assume that there does not exist any slot that contains a chain of length m.

Here we are given m slots. According to our assumption none of these slots would contain a chain of length m.

So, the lengths of chains in the m slots are <= (m-1).

So, the number of keys in the universe will be <= m×(m-1) = m² -m.

But in the question it is given that |U| = m².   

Hence contradiction.

So, there exists a slot which contains the chain of length m.

And the keys of that slot are the required sequence of m insertions that leads to a chain of length m.