旋转哈希

通常使用仅包含乘法和加法的滚动哈希函数来解释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指纹是另一种哈希，它也将输入解释为多项式，但是在伽罗瓦域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}$ 之间切开文件。这种方法将确保文件中的任何变化将只影响其当前和可能的下一个分块，而不会影响其他分块。

基于内容的切片算法需要逐字节地对于字符串进行哈希计算，并在匹配到特定的模式时进行分片处理。逐字节的比较会带来巨大的额外计算开销，而 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. ^ ^{1.0 1.1 1.2} 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. ^ ^{8.0 8.1} 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. ^ ^{9.0 9.1} 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.