滾動雜湊（rolling hash）
假設你想把一段長文字裡每一個長度為 5 的視窗都拿去和某目標比較，但每個視窗都從頭重算一個指紋太慢。滾動雜湊是一個技巧，讓你把視窗滑動一步並在常數時間內更新指紋——丟掉從左邊離開的字元、加入從右邊進來的字元——而不必重讀整個視窗。它把一連串重疊視窗變成一串廉價的更新。
標準的構造把一個字元視窗看成某個底數 b 之下的一個數的各位數字，再對一個大質數 q 取模以保持其值不大。字元 c0 c1 ... c(m-1) 的雜湊是 (c0*b^(m-1) + c1*b^(m-2) + ... + c(m-1)) mod q，是一個以 b 為變數的多項式。神奇之處在於視窗向右滑一格時的更新規則：減去離開的最左字元的貢獻（其值乘以 b^(m-1)），把整個值乘以 b 使其餘各位數字往上挪一位，再加上進來的字元——全部對 q 取模。這是常數次算術運算，所以在 O(m) 的初始設定後，每次滑動只花 O(1)。選 q 為質數（且常把底數 b 隨機選取）能讓雜湊值分布良好，使意外碰撞稀少。
滾動雜湊是 Rabin-Karp 演算法的核心，並出現在任何需要快速比較大量子字串的地方：偵測重複段落、備份系統中以內容定義的分塊、抄襲檢查器。關鍵的誠實：雜湊相符是強烈的提示，不是證明。兩個不同的視窗可能雜湊到同一個值（碰撞），所以雜湊相符後你應該直接驗證字元。用一個好的隨機質數，每次比較的碰撞機率約為 1/q，很小但不是零——把雜湊當作快速的過濾器，而非最終答案。
底數 b=256（位元組值），質數 q=101。視窗 "ab" 雜湊為 (97*256 + 98) mod 101。滑到 "bc"：新雜湊 = ((舊值 - 97*256 mod 101)*256 + 99) mod 101。我們重用了舊值，只做一次減、一次乘、一次加——沒有重讀 'b'——這正是那個 O(1) 更新，使得掃描所有視窗整體上是線性的。
滑動視窗藉由移除舊位數、加入新位數，在 O(1) 內更新雜湊，全部對 q 取模。
雜湊相等不保證字串相等——命中時務必驗證，否則知道你模數的對手能蓄意製造碰撞。只用單一固定小質數有風險；用大質數或隨機質數（或兩個雜湊）能大幅壓低碰撞率。