重定向;重新导向;字符;字元;文件; 档案;快捷方式; 捷径;项目;专案;计划;计划;计划;计算机; 电脑; 电脑; 旋转哈希（也称为滚动哈希、递归哈希、滚动校验和或滑动哈希）是一种哈希函数，输入的内容在一个窗口中进行移动哈希。 少数哈希函数允许快速计算滚动哈希值 — 只给出旧的哈希值，新的哈希值被快速计算出来，旧的值从窗口中移除，新的值添加到窗口中 — 类似于移动平均函数的计算方式，比其他低通滤波器更快。 主要应用之一是Rabin–Karp字符串搜索算法，该算法使用下面描述的滚动哈希。另一个流行的应用是rsync程序，它使用基于Mark Adler的adler-32的校验和作为滚动哈希。低带宽网络文件系统（LBFS）使用Rabin指纹作为其滚动哈希。 滚动哈希值最多只能是的或的。例如，它们不能是的。 多项式滚动哈希. 通常使用仅包含乘法和加法的滚动哈希函数来解释Rabin–Karp字符串搜索算法： formula_1 其中formula_2是一个常数，并且formula_3是输入字符（但此函数不是Rabin指纹，见下文）。 为了避免操纵巨大的formula_4值，所有数学运算都要取模formula_5。formula_2和formula_5的选择对获得良好哈希至关重要；更多的讨论请参见线性同余生成器。 移除和增加字符只需将第一项或最后一项加减即可。将所有字符向左移动一个位置，需要将整个和formula_4乘以formula_2。将所有字符向右移一个位置，需要将整个和formula_4除以formula_2。注意，在取模运算中，formula_2可以选择更换为模倒数formula_13，据此，可以在不实际执行除法的情况下，通过将formula_4与之相乘的方法得到除法的结果。 Rabin指纹. Rabin指纹是另一种哈希，它也将输入解释为多项式，但是在伽罗瓦域（即除以2的同余）上。它不把输入视为字节的多项式，而是将其视为位的多项式，并且所有算术均在GF(2)中完成（类似于CRC32）。哈希是该多项式除以GF(2)的不可约多项式的结果。可以只使用进入和离开的字节来更新Rabin指纹，使其成为有效的滚动哈希。 因为它与Rabin-Karp字符串搜索算法有着相同的作者，而Rabin-Karp字符串搜索算法经常被用另一种更简单的滚动哈希来解释，而且这种更简单的滚动哈希也是一种多项式，所以这两种滚动哈希通常彼此混淆。 备份软件restic （页面存档备份，存于互联网档案馆;网际网路档案馆;互联网档案馆;互联网档案馆;）使用Rabin指纹来分割文件，其Blob大小在512字节和8MiB之间变化。 循环多项式. 通过循环多项式 — 有时也被称为Buzhash — 进行哈希，也很简单，但它的好处是避免了乘法，而是使用桶式移位器。这是的一种形式：它假定存在一些从字符到整数区间formula_15的哈希函数formula_16。该哈希函数可以是一个简单的数组，也可以是一个将字符映射到随机整数的哈希表。让函数formula_17是一个循环二进制旋转（或循环移位 ）：它将位向左旋转1，将最新位推到第一个位置。 例如，formula_18。formula_19是按位异或。哈希值定义为 formula_20 其中2的幂的乘法可以通过二进制移位来实现。结果是一个在区间formula_15中的数。 以滚动方式计算哈希值的方法如下。 让formula_4是先前的哈希值。 旋转formula_4一次：formula_24。如果formula_25是要删除的字符，旋转它formula_26次：formula_27。然后简单地设置 formula_28 这里formula_29是增加的新字符。 由循环多项式进行哈希处理具有很强的普遍性或对偶性：只需保持第一个formula_30位。也就是说，取结果formula_4并且不需要考虑任何formula_32连续的位。在实际操作中，这可以通过整数除法formula_33来实现。 备份软件使用可自定义分块大小范围的Buzhash算法来切分文件流。 使用滚动哈希进行基于内容的分片. 滚动哈希函数的一个有趣的用例是，它可以创建动态的、基于内容的流或文件的分块。当需要在网络上只发送一个大文件的变化块时，这一点特别有用，因为在文件的最前面增加一个简单的字节会导致所有固定大小的窗口成为更新状态，而实际上只有第一个“块”被修改。 计算动态分块的最简单方法是计算滚动哈希，如果它符合一个模式（例如低N位全为零），那么它就是一个分块边界。这种方法可以确保文件的任何变化都只会影响其当前和可能的下一个分块，而不会影响其他的。 当知道边界后，需要通过对其哈希值进行比较，来检测哪个分块被修改，需要在网络上传输。 使用移动和的基于内容的切片. 一些程序，包括gzip（带有codice_1选项）和rsyncrypto，会根据这个特定的（未加权的）移动和进行基于内容的分片： formula_34 formula_35 其中 将窗口移动一个字节，只需将新字符添加到总和中，并从总和中减去最旧的字符（不再在窗口中）。 对于每个使formula_42的formula_5，这些程序会在formula_5和formula_45之间切开文件。这种方法将确保文件中的任何变化将只影响其当前和可能的下一个分块，而不会影响其他分块。 Gear指纹以及快速基于内容分块算法FastCDC. 基于内容的切片算法需要逐字节地对于字符串进行哈希计算，并在匹配到特定的模式时进行分片处理。逐字节的比较会带来巨大的额外计算开销，而 FastCDC 算法则提出了一种快速计算基于内容的分块算法。这种算法采用了基于滚动哈希的 formula_46 指纹 算法，跳过最小分段长度，同时可以进行长度归一化，同时滑动两个字节等操作。这样可以大大加快分块算法的处理速度，处理速度可以达到原先的 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" &amp; "Mask") then return "i" return "i" 其中 算法从数组下标为 formula_52 开始循环，省去了处理长度不足最小分块所浪费的时间。计算当前字节下对应的指纹信息，当发现指纹信息等于提前预设好的 formula_53 时，则进行分段处理。如果计算到最大的 formula_54 时仍然没有匹配到 formula_55 时，此时强行进行分块。 计算的复杂度. 所有滚动哈希函数在字符数上都是线性的，但其复杂度与窗口长度的关系（formula_26）不等。Rabin–Karp滚动哈希需要两个formula_26位数字的乘法，整数乘法是在formula_58。通过循环多项式对ngram进行哈希处理，可以在线性时间内完成。