Dot-product method Randomized strategy Let m be prime. decompose key k into r+1 digits, each with value in the set (0, l,.., m-1) That is,letk=(ko,k1,…,km1), Where0≤k≤m Pick a=(ao, a1,.,am-1) where each a; is chosen randomly from 0, 1,., m-1 Define h(k)=∑ak1modm i=0 Excellent in practice but expensive to compute o 2001 by Charles E Leiserson Introduction to Algorithms Day 11 l7. 13© 2001 by Charles E. Leiserson Introduction to Algorithms Day 11 L7.13 Dot-product method Randomized strategy: 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, …, km–1〉, where 0 ≤ ki < m. Pick a = 〈a0, a1, …, am–1〉 where each ai is chosen randomly from {0, 1, …, m–1}. h k a k m r i a ( ) i i mod 0 ∑ = Define = . • Excellent in practice, but expensive to compute