我最近遇到了 Rsync 算法，并考虑使用 java 来实现它。该算法的重要部分之一是发送方的滚动校验和。
在http://en.wikipedia.org/wiki/Rsync中，它解释说
“如果已经计算了字节 1-25 的滚动校验和，则可以仅根据前一个校验和 (R)、字节 1 (n) 和 >字节 26 (n+S) 计算 > 字节 2-26 的滚动校验和)。”
我可以使用 MD5 或 SHA 为文件或字符串生成校验和。但我想了解这一行，因为我们如何实现它。
问问题
695 次
1 回答
4
假设您的滚动窗口覆盖 3 个字节，并且我们的输入字符串为 5 个字节。考虑字符串 23456。我们将使用一个简单的散列函数：如果窗口覆盖字节 a、b 和 c，那么散列是 ax 100 + bx 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，而无需遍历其中存在的所有元素新窗口。对于下一个字节序列，我们可以使用相同的方法，并通过遍历窗口中的所有字节来避免计算哈希值。
于 2012-09-17T13:45:51.343 回答