(Sort of) Randomly Organizing Data
Kent Quanrud · 32:18
Universal hashing lets you get near-constant expected dictionary operations on adversarial keys without a fully random hash function: a simple \(h(x)=(ax+b \bmod P)\bmod m\) is enough for expected load \(O(n/m)\), tho...