旋轉雜湊

旋轉雜湊（也稱為捲動雜湊、遞迴雜湊、捲動校驗和或滑動雜湊）是一種雜湊函式，輸入的內容在一個窗口中進行移動雜湊。

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

主要應用之一是Rabin–Karp字串搜尋演算法，該演算法使用下面描述的捲動雜湊。另一個流行的應用是rsync程式，它使用基於Mark Adler的adler-32的校驗和作為捲動雜湊。低頻寬網路檔案系統（LBFS）使用Rabin指紋作為其捲動雜湊。

捲動雜湊值最多只能是成對獨立（英語：pairwise independent）的^[1]或強通用（英語：universal hashing）的。例如，它們不能是三向獨立（英語：k-independent hashing）的。

多項式捲動雜湊

通常使用僅包含乘法和加法的捲動雜湊函式來解釋Rabin–Karp字串搜尋演算法：

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

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

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

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

Rabin指紋

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

因為它與Rabin-Karp字串搜尋演算法有著相同的作者，而Rabin-Karp字串搜尋演算法經常被用另一種更簡單的捲動雜湊來解釋，而且這種更簡單的捲動雜湊也是一種多項式，所以這兩種捲動雜湊通常彼此混淆。 備份軟體restic （頁面存檔備份，存於網際網路檔案館）使用Rabin指紋來分割檔案，其Blob大小在512位元組和8MiB之間變化。 ^[2]

迴圈多項式

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

${\displaystyle 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的冪的乘法可以通過二進制移位來實現。結果是一個在區間${\displaystyle [0,2^{L})}$中的數。

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

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

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

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

備份軟體Attic（英語：Attic_(backup_software)）使用可自訂分塊大小範圍的Buzhash演算法來切分檔案流。^[4]

使用捲動雜湊進行基於內容的分片

捲動雜湊函式的一個有趣的用例是，它可以建立動態的、基於內容的流或檔案的分塊。當需要在網路上只傳送一個大檔案的變化塊時，這一點特別有用，因為在檔案的最前面增加一個簡單的位元組會導致所有固定大小的窗口成為更新狀態，而實際上只有第一個「塊」被修改。

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

當知道邊界後，需要通過對其雜湊值進行比較，來檢測哪個分塊被修改，需要在網路上傳輸。 ^[5]

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

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

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

${\displaystyle H(n)=S(n)\mod 4096,}$

其中

• ${\displaystyle S(n)}$是8196個連續位元組之和，以位元組${\displaystyle n}$結尾（需要21位儲存空間）；
• ${\displaystyle c_{i}}$是檔案的第${\displaystyle i}$個位元組；
• ${\displaystyle H(n)}$是一個「雜湊值」，由${\displaystyle S(n)}$底部12位元組成。

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

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

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

基於內容的切片演算法需要逐位元組地對於字串進行雜湊計算，並在匹配到特定的模式時進行分片處理。逐位元組的比較會帶來巨大的額外計算開銷，而 FastCDC ^[7] 演算法則提出了一種快速計算基於內容的分塊演算法。這種演算法採用了基於捲動雜湊的 ${\displaystyle Gear}$ 指紋^[8] 演算法，跳過最小分段長度，同時可以進行長度歸一化，同時滑動兩個位元組等操作。這樣可以大大加快分塊演算法的處理速度，處理速度可以達到原先的 3-12 倍^[9]。 基礎版本的演算法虛擬碼如下：

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

其中

• ${\displaystyle Gear}$ 指紋是提前計算的一個雜湊雜湊陣列。它採用了 ${\displaystyle Gear}$ 雜湊演算法，其保證了雜湊結果分布均勻性的同時可以快速地計算雜湊值。與傳統的 ${\displaystyle Rabin}$ 演算法相比，它的計算速度更快。經過實驗比較 ^[9]，在進行資料分段的時候，同 ${\displaystyle Rabin}$ 演算法相比，他們產生的資料塊大小分布幾乎一致而 ${\displaystyle Gear}$ 演算法需要的時間更短 ^[8]。

演算法從陣列下標為 ${\displaystyle MinSize}$ 開始迴圈，省去了處理長度不足最小分塊所浪費的時間。計算當前位元組下對應的指紋資訊，當發現指紋資訊等於提前預設好的 ${\displaystyle Mask}$ 時，則進行分段處理。如果計算到最大的 ${\displaystyle MaxSize}$ 時仍然沒有匹配到 ${\displaystyle Mask}$ 時，此時強行進行分塊。

計算的複雜度

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

軟體

• rollinghashcpp （頁面存檔備份，存於網際網路檔案館）是幾個捲動雜湊函式的免費軟體C++實現
• rollinghashjava （頁面存檔備份，存於網際網路檔案館）是捲動雜湊函式的Apache許可Java實現
• rdedup （頁面存檔備份，存於網際網路檔案館） 是 FastCDC 函式的 Rust 實現

參見

• 最小雜湊

• w-重迭（英語：w-shingling）

外部連結

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

參照

1. Daniel Lemire, Owen Kaser: Recursive n-gram hashing is pairwise independent, at best, Computer Speech & Language 24 (4), pages 698–710, 2010. arXiv:0705.4676.
2. References — restic 0.9.0 documentation. restic.readthedocs.io. [2018-05-24]. （原始內容存檔於2020-12-25） （英語）.
3. Jonathan D. Cohen, Recursive Hashing Functions for n-Grams, ACM Trans. Inf. Syst. 15 (3), 1997.
4. Data structures and file formats — Borg - Deduplicating Archiver 1.1.5 documentation. borgbackup.readthedocs.io. [2018-05-24]. （原始內容存檔於2021-03-11） （英語）.
5. Horvath, Adam. Rabin Karp rolling hash - dynamic sized chunks based on hashed content. October 24, 2012 [2020-06-11]. （原始內容存檔於2013-02-24） （英語）.
6. Rsyncrypto Algorithm. rsyncrypto.lingnu.com. [2020-06-11]. （原始內容存檔於2016-08-15） （英語）.
7. Xia, Wen; Zhou, Yukun; Jiang, Hong; Feng, Dan; Hua, Yu; Hu, Yuchong; Liu, Qing; Zhang, Yucheng. FastCDC: A Fast and Efficient Content-Defined Chunking Approach for Data Deduplication. USENIX. [2020-07-24]. （原始內容存檔於2020-08-22）.
8. Xia, Wen; Jiang, Hong; Feng, Dan; Tian, Lei; Fu, Min; Zhou, Yukun. Ddelta: A deduplication-inspired fast delta compression approach. Performance Evaluation. 2014, 79: 258–272. ISSN 0166-5316. doi:10.1016/j.peva.2014.07.016.
9. The Design of Fast Content-Defined Chunking for Data Deduplication Based Storage Systems. IEEE Journals & Magazine. 2020-06-16 [2020-07-22]. （原始內容存檔於2020-07-24）. 參照錯誤：帶有name屬性「IEEE Journals & Magazine 2020」的<ref>標籤用不同內容定義了多次
10. M. Fürer, Faster integer multiplication, in: STOC 』07, 2007, pp. 57–66.