java - 如何为重叠 block 生成滚动校验和？

Question

我最近接触到 Rsync 算法并想到使用 java 来实现它。该算法的一个重要部分是发送端的滚动校验和。

在http://en.wikipedia.org/wiki/Rsync ,它解释说

"if one had already calculated the rolling checksum of bytes 1–25, one could calculate >the rolling checksum of bytes 2–26 solely from the previous checksum (R), byte 1 (n), and >byte 26 (n+S)."

我可以使用 MD5 或 SHA 为文件或字符串生成校验和。但我想了解这一行，因为我们如何实现它。

Answer 1

假设您的滚动窗口覆盖 3 个字节，而我们的输入字符串为 5 个字节。考虑字符串 23456。我们将使用一个简单的哈希函数:如果窗口覆盖字节 a、b 和 c，则哈希为 a x 100 + b x 10 + c。

因此，对于我们的输入字符串 2345，前 3 个字节的校验和为 2 x 100 + 3 x 10 + 4 = 234。

接下来，窗口向左移动一步，现在覆盖3、4和5。除了计算 3 x 100 + 4 x 10 + 5，我们还可以使用之前的校验和和我们对刚刚进入和离开窗口的数字的了解，分别是 5 和 2。

因此，我们知道 2 刚刚离开窗口，我们从 234 中减去 2 x 100，得到 34。将 34 乘以 10 并加 5。这给了我们新的哈希值 345，而无需遍历所有元素出现在新窗口中。对于下一个字节序列，我们可以使用相同的方法，通过遍历窗口中的所有字节来避免计算哈希值。