01:198:344 Lecture Notes - Lecture 10: Universal Hashing, Random Variable
30 Nov 2017
School
Department
Course
Professor
Document Summary
Last lecture: read pages 265 269 in clrs for universal hashing, perfect hashing. This lecture: a class h of hash functions h : u {1, , m } is universal if for all x 6= y u , we have. P rrandom h h (h(x) = h(y)) 1/m: universal hashing. Say keys are in 1u , that is, u = log u bits long. Pick g to be a random b u matrix of 0/1 and de ne h(x) = gx mod 2 (the additions are mod2). P rh[h(x) = h(y)] = 1/m = 1/2b. Say xi = 0 and yi = 1. Over the remaining choices of columns except the ith column, h(x) is xed. Each of the 2b di erent settings of the ith column gives a di erent value of h(y) (in particular, every time we ip a bit in that column, we ip the corresponding bit in h(y)).
