Perfect Hashing S=fa,b,c,d,e,f}C [N]of size n uniform no collision random h [Ny→ml Pr[perfect]e-n22m 1/2 m n2 Table T: e b d ca Birthday SUHA:Simple Uniform Hash Assumption Query(x): retrieve hash function h; check whether TTh(x)]=x;Perfect Hashing S = {a, b, c, d, e, f} ⊆ [N] of size n e b d f c a h Table T: m uniform random Pr[perfect] Birthday = n2 [N] ! [m] SUHA: Simple Uniform Hash Assumption no collision Query(x): retrieve hash function h; check whether T[h(x)] = x; ≈ e−n2/2m > 1/2