通用雜湊（universal hashing）

雜湊表把項目存進由雜湊函數選定的槽位，而當許多項目碰撞到同一個槽時麻煩就開始了。對任何一個固定的雜湊函數，知道它的對手可以挑出全都碰撞的鍵，毀掉效能。通用雜湊靠在一開始從一個精心設計的函數族中隨機選取雜湊函數來擺脫這點，於是沒有任何固定的鍵集能被弄成太常碰撞——對手無法瞄準一個你尚未挑出的函數。

精確地說：一個把鍵映到 m 個槽的雜湊函數族 H 稱為通用的，若對每一對相異鍵 x 與 y，當 h 從 H 中均勻隨機選取時，碰撞機率 Pr[h(x) = h(y)] 至多為 1/m。這個單一保證正是你所需要的。由指示變數論證，在 n 個已存鍵中，與某給定鍵碰撞的鍵數期望至多為 (n - 1)/m，因此以大小 m = O(n) 的表，每次查詢平均碰觸期望 O(1) 個項目——常數期望時間，無論插入哪些鍵。一個標準的通用函數族：挑一個大於任何鍵的質數 p，隨機選 a 屬於 {1,...,p-1} 與 b 屬於 {0,...,p-1}，並令 h(x) = ((a x + b) mod p) mod m；可以證明對隨機的 a, b，任兩個相異鍵碰撞的機率至多為 1/m。

通用雜湊之所以重要，是因為它讓雜湊表效能成為你隨機選擇的性質，而非對輸入的指望，在期望上擊敗最壞情況乃至對抗性輸入。它支撐了完美雜湊、指紋法與許多隨機資料結構。誠實的提醒：那個 O(1) 是對雜湊函數的選擇取的期望，不是每次操作的保證——某個特定函數仍可能產生很長的鏈——而這個保證只有在函數真正隨機選取、且對提供鍵的人保密時才成立。重用一個固定函數會重新打開對抗的大門。