Stanford CS161 Lecture 8: Hashing, Collisions, and What Expected O(1) Actually Guarantees
A universal hash family only needs to keep the collision probability of every distinct key pair at most 1/n; that makes the expected bucket size below 2, yielding expected O(1), not per-operation worst-case O(1).