Universality of dot-product hash functions Theorem. The set H-h, is universal Proof. Suppose that x=ro, x1,...,x and y Vo, y1,.,y, be distinct keys. Thus, they differ in at least one digit position, wlog position For how many ∈H do x and y collide? We must have h(x)=h(), which implies that ∑ax=2ay;(modm i=0 o 2001 by Charles E Leiserson Introduction to Algorithms Day 12 l8.11© 2001 by Charles E. Leiserson Introduction to Algorithms Day 12 L8.11 Universality of dot-product hash functions Theorem. The set H = {ha} is universal. Proof. Suppose that x = 〈x0, x1, …, xr〉 and y = 〈y0, y1, …, yr〉 be distinct keys. Thus, they differ in at least one digit position, wlog position 0. For how many ha ∈ Hdo x and y collide? (mod ) 0 0 a x a y m r i i i r i ∑ i i ∑ = = ≡ . We must have ha(x) = ha(y), which implies that