Kristýna is sick, so we have a change of speaker & topic. We will learn simple but powerful methods
to hash, presented by Tung.
M.A. Bender, M. Farach-Colton, J. Kuszmaul, W. Kuszmaul: Modern Hashing Made Simple
https://epubs.siam.org/doi/pdf/10.1137/1.9781611977936.33 Using standard machinery we construct a simple hash table that offers guarantees much
stronger than what are classically taught:
• Operations are O(1)-time with high probability;
• The hash table stores n k-bit items in nk + O(n log log n) bits of space;
• The hash table is dynamically resized, so the space bound holds with
respect to the current size n at each time step.