Universality is good Theorem. let h be a hash function chosen uniformly ) at random from a universal set H of hash functions. Suppose h is used to hash n arbitrary keys into the m slots of a table T. Then, for a given key x, we have E#collisions with x <n/m o 2001 by Charles E Leiserson Introduction to Algorithms Day 12 L8. 4© 2001 by Charles E. Leiserson Introduction to Algorithms Day 12 L8.4 Universality is good Theorem. Let h be a hash function chosen (uniformly) at random from a universal set H of hash functions. Suppose h is used to hash n arbitrary keys into the m slots of a table T. Then, for a given key x, we have E[#collisions with x] < n/m