Constructing a set of universal hash functions Let m be prime. Decompose key k into r+ 1 digits, each with value in the set (0, 1,..., m-1) That is,letk=(ko,k12…,k, Where0≤k<m Randomized strategy: Pick a=(ao, a,.,a, where each a; is chosen randomly from 0, 1,.,m-1) Define ha(k)=2a, k; mod m. DO ot product. modulo m i=0 How big is={hn}?升|=m+ REMEMBER THIS! o 2001 by Charles E Leiserson Introduction to Algorithms Day 12 L8.10© 2001 by Charles E. Leiserson Introduction to Algorithms Day 12 L8.10 REMEMBER THIS! Constructing a set of universal hash functions Let m be prime. Decompose key k into r + 1 digits, each with value in the set {0, 1, …, m–1}. That is, let k = 〈k0, k1, …, kr〉, where 0 ≤ ki < m. Randomized strategy: Pick a = 〈a0, a1, …, ar〉 where each ai is chosen randomly from {0, 1, …, m–1}. h k a k m r i a ( ) i i mod 0 ∑ = Define = . How big is H = {ha}? |H| = mr + 1. Dot product, modulo m