#hashing

Stanford CS161 Lecture 8：雜湊、碰撞與期望 O(1) 到底保證什麼

Universal hash family 只需讓任意兩個不同 key 的碰撞機率不超過 1/n，就能把某個 key 所在 bucket 的期望長度壓到 2 以下；這給的是 expected O(1)，不是每次操作的最壞 O(1)。