指紋法（fingerprinting）

逐位元組比較兩個巨大的檔案很慢，但比較兩個短短的校驗碼卻是瞬間。若校驗碼不同，檔案必然不同；若相符，檔案幾乎確定相同。指紋法就是把這個把戲變嚴謹：用一個小小的隨機摘要——它的指紋——取代每個大物件，並比較指紋而非物件，接受兩個不同物件碰撞到同一指紋的微小機會。

精確地說：指紋是一個大物件的短雜湊，用隨機選取的雜湊函數計算，使相異物件只以小機率碰撞。標準方案把物件當成一個數、對隨機選取的質數取模，或把它當成多項式在隨機點求值。兩個不相等的物件 x 與 y 恰在它們的差能被隨機模數整除時碰撞；因為一個固定的非零差只有少數質因數，隨機選的質數能整除它的機率很低，所以 Pr[fingerprint(x) = fingerprint(y) 但 x != y] 很小。教科書上的收穫是拉賓-卡普字串比對：要在長度 n 的文字中找長度 m 的模式，先對模式取一次指紋，再把一個視窗滑過文字、比較視窗的指紋與模式的指紋。滾動雜湊在視窗移動一個字元時以 O(1) 更新其指紋（去掉離開字元的貢獻、加入進入字元的），給出 O(n + m) 的期望時間而非 O(nm)；在指紋相符時你逐字元驗證，以排除罕見的偽陽性。

指紋法之所以重要，是因為它把大資料上昂貴的相等測試，變成小摘要上便宜的測試，而且它是拉賓-卡普、弗萊瓦爾德斯檢查、內容定址儲存與去重背後的引擎。它是「隨機摘要鮮少巧合一致」這個想法的實用面貌。誠實的提醒：指紋可能碰撞，所以相符只是「很可能相等」——你要嘛在相符時驗證（使它成為拉斯維加斯、永遠正確），要嘛接受一個受控的偽陽性率（讓它停留在蒙地卡羅）。而碰撞保證取決於模數或求值點是隨機選取的；固定的選擇可能被一個專門構造碰撞的對手擊敗。