Hashing and heavy hitters (Fundamental algorithms, Spring 2023, Lecture 23)
Kent Quanrud · 76:52
Universal hashing — even a weak family like \(ax+b \bmod p \bmod m\) — is enough to get dictionary operations in expected \(O(1+n/m)\) time with linear space, and the same pairwise-collision guarantee plus Markov plus...