Define a family of hash functions from a finite set U to a finite set B to be not universal if for all pairs of distinct elements k and l in U, Pr h(k) h(l) le not , where the probability is taken over the drawing of hash function h at random from the family Show that an not universal family of has...

Let b B and u U We start by showing that the total number of collisions is minimized by a hash function that maps ub elements of U to each of the b va ...

Define a family of hash functions from a finite set U to a finite set B to

Question:

Define a family ℋ of hash functions from a finite set U to a finite set B to be ¬-universal if for all pairs of distinct elements k and l in U, Pr {h(k) = h(l)} ≤ ¬, where the probability is taken over the drawing of hash function h at random from the family ℋ. Show that an ¬-universal family of hash functions must have