旋轉哈希

旋轉哈希（也稱為滾動哈希、遞歸哈希、滾動校驗和或滑動哈希）是一種哈希函數，輸入的內容在一個窗口中進行移動哈希。

少數哈希函數允許快速計算滾動哈希值 — 只給出舊的哈希值，新的哈希值被快速計算出來，舊的值從窗口中移除，新的值添加到窗口中 — 類似於移動平均函數的計算方式，比其他低通濾波器更快。

主要應用之一是Rabin–Karp字符串搜索算法，該算法使用下面描述的滾動哈希。另一個流行的應用是rsync程序，它使用基於Mark Adler的adler-32的校驗和作為滾動哈希。低帶寬網絡文件系統（LBFS）使用Rabin指紋作為其滾動哈希。

滾動哈希值最多只能是成對獨立的或強通用的。例如，它們不能是三向獨立的。

多項式滾動哈希

通常使用僅包含乘法和加法的滾動哈希函數來解釋Rabin–Karp字符串搜索算法：

$H=c_{1}a^{k-1}+c_{2}a^{k-2}+c_{3}a^{k-3}+...+c_{k}a^{0},$

其中$a$是一個常數，並且$c_{1},...,c_{k}$是輸入字符（但此函數不是Rabin指紋，見下文）。

為了避免操縱巨大的$H$值，所有數學運算都要取模$n$。$a$和$n$的選擇對獲得良好哈希至關重要；更多的討論請參見線性同餘生成器。

移除和增加字符只需將第一項或最後一項加減即可。將所有字符向左移動一個位置，需要將整個和$H$乘以$a$。將所有字符向右移一個位置，需要將整個和$H$除以$a$。注意，在取模運算中，$a$可以選擇更換為模倒數$a^{-1}$，據此，可以在不實際執行除法的情況下，通過將$H$與之相乘的方法得到除法的結果。

Rabin指紋

Rabin指紋是另一種哈希，它也將輸入解釋為多項式，但是在伽羅瓦域GF(2)（即除以2的同餘）上。它不把輸入視為字節的多項式，而是將其視為位的多項式，並且所有算術均在GF(2)中完成（類似於CRC32）。哈希是該多項式除以GF(2)的不可約多項式的結果。可以只使用進入和離開的字節來更新Rabin指紋，使其成為有效的滾動哈希。

因為它與Rabin-Karp字符串搜索算法有着相同的作者，而Rabin-Karp字符串搜索算法經常被用另一種更簡單的滾動哈希來解釋，而且這種更簡單的滾動哈希也是一種多項式，所以這兩種滾動哈希通常彼此混淆。 備份軟件restic （頁面存檔備份，存於網際網路檔案館）使用Rabin指紋來分割文件，其Blob大小在512字節和8MiB之間變化。

循環多項式

通過循環多項式 — 有時也被稱為Buzhash — 進行哈希，也很簡單，但它的好處是避免了乘法，而是使用桶式移位器。這是列表哈希的一種形式：它假定存在一些從字符到整數區間$[0,2^{L})$的哈希函數$h$。該哈希函數可以是一個簡單的數組，也可以是一個將字符映射到隨機整數的哈希表。讓函數$s$是一個循環二進制旋轉（或循環移位 ）：它將位向左旋轉1，將最新位推到第一個位置。 例如，$s(10011)=00111$。$\oplus$是按位異或。哈希值定義為

$H=s^{k-1}(h(c_{1}))\oplus s^{k-2}(h(c_{2}))\oplus \ldots \oplus s(h(c_{k-1}))\oplus h(c_{k}),$

其中2的冪的乘法可以通過二進制移位來實現。結果是一個在區間$[0,2^{L})$中的數。

以滾動方式計算哈希值的方法如下。 讓$H$是先前的哈希值。 旋轉$H$一次：$H\leftarrow s(H)$。如果$c_{1}$是要刪除的字符，旋轉它$k$次：$s^{k}(h(c_{1}))$。然後簡單地設置

$H\leftarrow s(H)\oplus s^{k}(h(c_{1}))\oplus h(c_{k+1}),$

這裡$c_{k+1}$是增加的新字符。

由循環多項式進行哈希處理具有很強的普遍性或對偶性：只需保持第一個$L-k+1$位。也就是說，取結果$H$並且不需要考慮任何$k-1$連續的位。在實際操作中，這可以通過整數除法$H\rightarrow H\div 2^{k-1}$來實現。

備份軟件Attic使用可自定義分塊大小範圍的Buzhash算法來切分文件流。

使用滾動哈希進行基於內容的分片

滾動哈希函數的一個有趣的用例是，它可以創建動態的、基於內容的流或文件的分塊。當需要在網絡上只發送一個大文件的變化塊時，這一點特別有用，因為在文件的最前面增加一個簡單的字節會導致所有固定大小的窗口成為更新狀態，而實際上只有第一個「塊」被修改。

計算動態分塊的最簡單方法是計算滾動哈希，如果它符合一個模式（例如低N位全為零），那麼它就是一個分塊邊界。這種方法可以確保文件的任何變化都只會影響其當前和可能的下一個分塊，而不會影響其他的。

當知道邊界後，需要通過對其哈希值進行比較，來檢測哪個分塊被修改，需要在網絡上傳輸。

使用移動和的基於內容的切片

一些程序，包括gzip（帶有--rsyncable選項）和rsyncrypto，會根據這個特定的（未加權的）移動和進行基於內容的分片：

$S(n)=\sum _{i=n-8195}^{n}c_{i},$

$H(n)=S(n)\mod 4096,$

其中

• $S(n)$是8196個連續字節之和，以字節$n$結尾（需要21位存儲空間）；
• $c_{i}$是文件的第$i$個字節；
• $H(n)$是一個「哈希值」，由$S(n)$底部12位組成。

將窗口移動一個字節，只需將新字符添加到總和中，並從總和中減去最舊的字符（不再在窗口中）。

對於每個使$H(n)==0$的$n$，這些程序會在$n$和$n+1$之間切開文件。這種方法將確保文件中的任何變化將只影響其當前和可能的下一個分塊，而不會影響其他分塊。

Gear指紋以及快速基於內容分塊算法FastCDC

基於內容的切片算法需要逐字節地對於字符串進行哈希計算，並在匹配到特定的模式時進行分片處理。逐字節的比較會帶來巨大的額外計算開銷，而 FastCDC 算法則提出了一種快速計算基於內容的分塊算法。這種算法採用了基於滾動哈希的 $Gear$ 指紋 算法，跳過最小分段長度，同時可以進行長度歸一化，同時滑動兩個字節等操作。這樣可以大大加快分塊算法的處理速度，處理速度可以達到原先的 3-12 倍。 基礎版本的算法偽代碼如下：

algorithm FastCDC
    input: data buffer src , 
           data length n, 
    output: cut point i
    
    MinSize ← 2KB     //split minimum chunk size is 2KB
    MaxSize ← 64KB    //split maximum chunk size is 64KB
    fp ← 0
    i ← MinSize
    Mask ← 0x0000d93003530000LL
    
    // buffer size is less than minimum chunk size
    if n ≤ MinSize then
        return n;
    if n ≥ MaxSize then
        n ← MaxSize
     
    while i < n do
        fp ← (fp << 1 ) + Gear[src[i]]
        if !(fp & Mask) then
            return i
   
    return i

其中

• $Gear$ 指紋是提前計算的一個哈希散列數組。它採用了 $Gear$ 哈希算法，其保證了哈希結果分布均勻性的同時可以快速地計算哈希值。與傳統的 $Rabin$ 算法相比，它的計算速度更快。經過實驗比較 ，在進行數據分段的時候，同 $Rabin$ 算法相比，他們產生的數據塊大小分布幾乎一致而 $Gear$ 算法需要的時間更短 。

算法從數組下標為 $MinSize$ 開始循環，省去了處理長度不足最小分塊所浪費的時間。計算當前字節下對應的指紋信息，當發現指紋信息等於提前預設好的 $Mask$ 時，則進行分段處理。如果計算到最大的 $MaxSize$ 時仍然沒有匹配到 $Mask$ 時，此時強行進行分塊。

計算的複雜度

所有滾動哈希函數在字符數上都是線性的，但其複雜度與窗口長度的關係（$k$）不等。Rabin–Karp滾動哈希需要兩個$k$位數字的乘法，整數乘法是在$O(k\log k2^{O(\log ^{*}k)})$。通過循環多項式對ngram進行哈希處理，可以在線性時間內完成。

軟件

• rollinghashcpp （頁面存檔備份，存於網際網路檔案館）是幾個滾動哈希函數的免費軟件C++實現
• rollinghashjava （頁面存檔備份，存於網際網路檔案館）是滾動哈希函數的Apache許可Java實現
• rdedup （頁面存檔備份，存於網際網路檔案館） 是 FastCDC 函數的 Rust 實現

參見

• 最小哈希

• w-重迭

外部連結

• MIT 6.006: Introduction to Algorithms 2011- Lecture Notes - Rolling Hash （頁面存檔備份，存於網際網路檔案館）