Punchline

As long as we keep the table only a constant-fraction full, we are ok. For $\alpha = 9/10$, T = 10.

But, if the table is more full than that: $\alpha = (m-1)/m$,T=m!


next up previous
Next: Universal Hashing Up: ANALYSIS Previous: Open-Addressing Analysis