樞紐難題，以及解法
你在分治法那一階已經認識了樸素的快速排序：挑一個元素當樞紐，把陣列分割成「比它小的全在左邊、比它大的全在右邊」，再對兩側遞迴。當樞紐每次都落在接近中間的位置，陣列在每一層都對半切，你會得到大約 log n 層、每層 O(n) 的分割工作，總和是漂亮的 O(n log n)。但若樞紐永遠是最小或最大的元素，一側為空、另一側裝著 n-1 個元素；遞迴變成一條深度為 n 的瘦高鏈，成本崩塌成 Theta(n^2)。最痛的地方在於：這個災難情況一點也不罕見——若你總是挑第一個元素當樞紐，一個已排序的陣列就恰好觸發這個最壞情況。你最盼望它最容易的那個輸入，正是會害死你的那一個。
解法簡單到近乎羞辱人：別讓輸入挑樞紐——讓一枚硬幣來挑。隨機化快速排序每次都從當前子陣列中均勻隨機地挑出樞紐。其餘一切不變；分割步驟完全相同。但現在執行時間不再是輸入的固定性質，而成了一個隨機變數，因為演算法本身在做隨機選擇。再也沒有任何單一的壞輸入了。不論你給它什麼陣列——已排序、反向、由對手精心構造——樞紐的分布都一樣，所以期望執行時間也一樣。這正是本階第一篇所說的拉斯維加斯演算法：輸出永遠是一個正確排序好的陣列；只有它花的時間是隨機的。
用指示變數數比較次數
要界定期望執行時間，我們去數快速排序唯一花時間做的事：元素之間的比較。這裡有個優雅的把戲，能把整個分析壓進一頁。在腦中把這 n 個元素排好序，依遞增順序叫它們 z_1, z_2, ..., z_n（演算法從來看不到這個順序，這純粹是為了證明）。關鍵問題是：對於兩個特定的元素 z_i 與 z_j，演算法曾經比較它們的機率是多少？在快速排序中，兩個元素被比較，若且唯若其中一個被選為樞紐、而另一個此時仍在同一個子陣列裡——一旦它們被某個別的樞紐分到不同側，就再也碰不上面了。
現在把焦點放在這一段元素 z_i, z_{i+1}, ..., z_j 上——也就是數值介於 z_i 與 z_j 之間（含兩端）的那 j - i + 1 個元素。這當中最先被挑為樞紐的那一個，決定了這一對的命運。若那第一個樞紐正是 z_i 或 z_j 本身，那麼 z_i 與 z_j 就被比較了（樞紐會與所有人比較，包括它的夥伴）。若第一個樞紐是中間某個元素，它會把 z_i 與 z_j 分到對立兩側，它們便永不相比。在這一段的 j - i + 1 個元素中，每一個成為最先被選為樞紐者的機率相等——這正是「均勻隨機」買給我們的東西。所以 z_i 與 z_j 曾被比較的機率是 2 / (j - i + 1)：在 j - i + 1 個等機率的選擇中，有兩個有利的選擇（z_i 或 z_j）。
定義一個指示隨機變數 X_{ij}，當 z_i 與 z_j 曾被比較時為 1、否則為 0。總比較次數就是 X_{ij} 對所有 i < j 求和。根據期望值的線性性質——前幾篇的主力，它讓你即使在變數彼此糾纏、相依時也能把期望值相加——期望的總和就只是各個機率的總和。一個指示變數的期望值恰好等於它為 1 的機率，所以 E[X_{ij}] = 2 / (j - i + 1)，於是整個執行時間分析便化簡成把這些分數加起來。
加總成 O(n log n)
現在我們只要把 E[X_{ij}] = 2 / (j - i + 1) 對每一對 i < j 求和。固定 i、讓 j 向上跑：分母 j - i + 1 依序走過 2, 3, 4 等等，於是內層的和是 2 乘以 (1/2 + 1/3 + 1/4 + ...)，它被 2 乘以調和和 1 + 1/2 + 1/3 + ... + 1/n 所界定。那個調和數已知約為 ln n，大致是 n 的自然對數。把它對 i 的全部 n 種選擇加起來，得到期望比較次數至多為 2n 乘以調和數，也就是 O(n log n)。每個樞紐一次擲硬幣、每一對一個指示變數、一個調和和——脆弱的 Theta(n^2) 演算法就成了在每一個輸入上期望都是 O(n log n) 的穩健演算法。
E[comparisons] = sum over i<j of 2/(j-i+1)
<= sum over i of 2*(1 + 1/2 + ... + 1/n)
= 2n * H_n ~ 2n * ln n = O(n log n)兩個誠實的註腳。第一，這是期望比較次數，是對演算法自身擲硬幣取的平均，不是對某個輸入分布取的平均——這個區別很重要，因為樸素快速排序的平均情況分析假設輸入是隨機的，而這裡的保證對你能設計出的最壞輸入都成立。第二，同樣的指示變數構想也能分析隨機化快速選擇，它每次分割後只遞迴進一側來找第 k 小的元素；那裡的分數加總成幾何級數而非調和級數，期望成本降到乾淨的 O(n)。這裡真正的獎賞是這套技巧本身，而不只是那個界。
雜湊，以及破壞它的對手
現在換個問題。雜湊表把項目存在一個有 m 個槽的陣列裡，用一個雜湊函數 h 把每個鍵映射到一個槽號。要插入或查找一個鍵，你計算 h(鍵) 然後直接走到那個槽——若沒有兩個鍵碰撞，就是 O(1)。碰撞是指兩個相異的鍵映射到同一個槽；我們通常把所有碰撞的鍵存在那個槽的一個小串列（鏈）裡來處理它。整個效能故事就是那些鏈的長度：若每條鏈都短，操作就快；若某一條鏈裝了大部分的鍵，查找就退化成掃描一個長串列，你便失去了當初要的 O(1)。
這裡有個與快速排序樞紐難題完全對應的陷阱。對於任何單一固定的雜湊函數 h，都存在一組全部碰撞的鍵。可能的鍵集遠大於那 m 個槽，所以根據鴿籠原理，某個槽會是許多鍵的目標；一個知道你函數的對手，可以把恰好那些鍵交給你，逼它們全進同一條鏈，把每個操作拖成 O(n)。公開你的雜湊函數，就像永遠挑第一個元素當樞紐：它把最壞情況奉送給任何想要的人。沒有任何固定的決定性函數能逃脫這點，正如沒有任何固定的樞紐規則能逃脫它的壞輸入。
通用雜湊：隨機函數，可證明的界
解藥是通用雜湊。你不用一個固定函數，而是建立一整族雜湊函數 H，並在建表時從 H 中均勻隨機地挑一個函數 h。若對於每一對相異的鍵 x 與 y，它們碰撞的機率（對 h 的隨機選擇而言）至多為 1/m，這個族就稱為通用的——這恰好是若 h 把鍵完全隨機地撒進 m 個槽時你會得到的碰撞機率。這個定義性質只關乎成對的鍵，而這就是你所需的全部，因為鏈長取決於有多少其他鍵與你正在查找的那個鍵碰撞。
看著指示變數的把戲再次登場，因為它與快速排序是同一個證明形狀。假設你在一個裝了 n 個鍵的表裡查找鍵 x。對每個其他的鍵 y，令一個指示變數在 y 與 x 碰撞時為 1。x 那條鏈的期望長度，就是這些指示變數期望值的總和，根據期望值的線性性質，那等於對 n-1 個其他鍵的碰撞機率求和，每個至多 1/m。所以期望鏈長至多為 (n-1)/m，低於負載因子 n/m。讓 m 與 n 成正比，那個期望長度就是一個常數——每個操作期望 O(1)，對任何鍵集都成立，而現在最壞情況只來自運氣差的擲硬幣，絕不來自一個巧妙的對手。
一個你能裝進腦袋的具體族：挑一個比任何鍵都大的質數 p，選隨機的 a 屬於 {1, ..., p-1} 與隨機的 b 屬於 {0, ..., p-1}，令 h(k) = ((a*k + b) mod p) mod m。變動 a 與 b 便掃出一個通用族，且可以證明 1/m 的碰撞界對每一對相異的鍵都成立。若你再進一步、把 m 取得夠大——約 n^2 個槽——所有成對鍵之間的期望碰撞數便降到 1 以下，於是隨機函數重抽幾次，就給你一個完全沒有碰撞的表：這就是完美雜湊，它建出一個保證最壞情況 O(1) 查找的靜態字典，全靠同一個「隨機選取函數」的構想驅動。