茶年 · 中文维基百科

旋转哈希

Wikipedia · 2021-12-23 维基百科 👁 1 阅读

旋转哈希（也称为滚动哈希、递归哈希、滚动校验和或滑动哈希）是一种哈希函数，输入的内容在一个窗口中进行移动哈希。

少数哈希函数允许快速计算滚动哈希值 — 只给出旧的哈希值，新的哈希值被快速计算出来，旧的值从窗口中移除，新的值添加到窗口中 — 类似于移動平均函数的计算方式，比其他低通滤波器更快。

主要应用之一是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指纹是另一种哈希，它也将输入解释为多项式，但是在伽罗瓦域（即除以2的同余）上。它不把输入视为字节的多项式，而是将其视为位的多项式，并且所有算术均在GF(2)中完成（类似于CRC32）。哈希是该多项式除以GF(2)的不可约多项式的结果。可以只使用进入和离开的字节来更新Rabin指纹，使其成为有效的滚动哈希。

因为它与Rabin-Karp字符串搜索算法有着相同的作者，而Rabin-Karp字符串搜索算法经常被用另一种更简单的滚动哈希来解释，而且这种更简单的滚动哈希也是一种多项式，所以这两种滚动哈希通常彼此混淆。 备份软件[https://restic.net/ 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连续的位。

使用滚动哈希进行基于内容的分片
滚动哈希函数的一个有趣的用例是，它可以创建动态的、基于内容的流或文件的分块。当需要在网络上只发送一个大文件的变化块时，这一点特别有用，因为在文件的最前面增加一个简单的字节会导致所有固定大小的窗口成为更新状态，而实际上只有第一个“块”被修改。

计算动态分块的最简单方法是计算滚动哈希，如果它符合一个模式（例如低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 Gear 指纹是提前计算的一个哈希散列数组。它采用了 Gear 哈希算法，其保证了哈希结果分布均匀性的同时可以快速地计算哈希值。与传统的 Rabin 算法相比，它的计算速度更快。经过实验比较 ，在进行数据分段的时候，同 Rabin 算法相比，他们产生的数据块大小分布几乎一致而 Gear 算法需要的时间更短 。

算法从数组下标为 MinSize 开始循环，省去了处理长度不足最小分块所浪费的时间。计算当前字节下对应的指纹信息，当发现指纹信息等于提前预设好的 Mask 时，则进行分段处理。如果计算到最大的 MaxSize 时仍然没有匹配到 Mask 时，此时强行进行分块。

计算的复杂度
所有滚动哈希函数在字符数上都是线性的，但其复杂度与窗口长度的关系（k）不等。Rabin–Karp滚动哈希需要两个k位数字的乘法，整数乘法是在O(k \log k 2^{O(\log^*k)})。通过循环多项式对ngram进行哈希处理，可以在线性时间内完成。

软件

参见

  • 最小哈希

*

外部链接

引用

#散列函数

评论 (0)

  • 还没有评论，来抢沙发吧。