Universal hashing Definition. let u a universe of keys, and let be a finite collection of hash functions each mapping ( to (0,1,., m-1. We say 升 is universal if for allx,y∈ where x≠ we have{h∈升:h(x)=h(y)}=1H|m That is the chance of a collision th: h(x)=ho)) between x and y is 1/m, if we choose h randomly from H 升 o 2001 by Charles E Leiserson Introduction to Algorithms Day 12 L8.3© 2001 by Charles E. Leiserson Introduction to Algorithms Day 12 L8.3 Universal hashing Definition. Let U be a universe of keys, and let H be a finite collection of hash functions, each mapping U to {0, 1, …, m–1}. We say H is universal if for all x, y ∈ U, where x ≠ y, we have |{h ∈ H : h(x) = h(y)}| = |H|/m. That is, the chance of a collision between x and y is 1/m if we choose h randomly from H. {h : h(x) = h(y)} H |H| m