Modern Hashing Made Simple

Modern work on hashing has led to hash tables with extraordinary guarantees. However, these data structures are too complex to be taught in (even an advanced) data structures course. In this paper, we show that this need not be the case: using standard machinery that we already teach, one can 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.