X1:load of the first bin Binomial m u=E[X1]= n Chernoff bound: Pr[X≥t]≤2-for t≥2eu Form≥nlnn,u≥lnn. x2W=mX2gu≤2ws22a<点 The max load is ()w.h.p..X1: load of the first bin µ = E[X1] = m n X1 = Binomial￾ m, 1 n ⇥ Chernoff bound: Pr[X ⇤ t] ⇥ 2￾t for t ⇤ 2eµ For m ￾ n lnn, µ ￾ lnn. Pr￾ X1 ⇤ 2em n ⇥ = Pr[X1 ⇤ 2eµ] ⇥ 2￾2eµ ⇥ 2￾2e lnn < 1 n2 The max load is O ￾ m n ⇥ w.h.p