In: Advanced Math
A hash table works as follows. We allocate a table of m slots. All the items we intend to store in the table belong to a large set U of items. We adopt a function f: U ->{0,1...m-1) which maps an item to a slot.
Suppose we seek to store n items from U in a table of m slots.
(a) Suppose f maps every item in U with equal probability to one of the m slots. What is the probability, given two distinct items i1,i2∈ U, that f(i1),f(i2)?
(b) Prove that if |U| > nm, then no matter what f is, there exist n items in U all of which are mapped by f to the same slot.