Rabin-Karp算法与去重的关系

Question

许多重复数据删除库或应用程序应用 Rabin Karp 滚动散列算法进行快速散列以从文件二进制文件中切出一个块。
我的问题是，为什么Rabin Karp算法经常用于切割块？
我知道这是快速滚动哈希算法，但我的问题更基础。
有很多方法可以切一块。
例如，将一个字节（没有 mod 操作）与值进行比较以切割块将导致平均 256 字节块。
比较 9 位将导致平均 512 字节块等。
难道不只是比较最后几位而没有类似于滚动哈希算法（例如 Rabin Karp）但速度更快的哈希结果吗？

Answer 1

对于可变大小的分块去重，我们有两个步骤：

1. 分块
2. 索引

Rabin Karp rolling hash 是一种分块算法，它将文件分成不同大小的块。然后我们需要 index/query 数据块，因为我们要进行重复数据删除。一般的方法是计算chunk的hash值，以hash为key存储chunk。使用 Rabin Karp 算法，一切都很简单，因为我们同时获得了哈希和数据块。

您提到比较最后几位的方法可以帮助将文件切块，但是如果要对这些块进行索引，我们如何获取密钥？所以你必须计算哈希。

希望这会有所帮助。