旋轉雜湊
输入的内容在一个窗口中进行移动的哈希函数 / 維基百科,自由的 encyclopedia
旋轉雜湊(也稱為捲動雜湊、遞歸雜湊、捲動校驗和或滑動雜湊)是一種雜湊函數,輸入的內容在一個窗口中進行移動雜湊。
少數雜湊函數允許快速計算捲動雜湊值 — 只給出舊的雜湊值,新的雜湊值被快速計算出來,舊的值從窗口中移除,新的值添加到窗口中 — 類似於移動平均函數的計算方式,比其他低通濾波器更快。
主要應用之一是Rabin–Karp字串搜尋演算法,該演算法使用下面描述的捲動雜湊。另一個流行的應用是rsync程式,它使用基於Mark Adler的adler-32的校驗和作為捲動雜湊。低頻寬網絡檔案系統(LBFS)使用Rabin指紋作為其捲動雜湊。
捲動雜湊值最多只能是成對獨立(英語:pairwise independent)的[1]或強通用(英語:universal hashing)的。例如,它們不能是三向獨立(英語:k-independent hashing)的。