algorithm - Rabin-Karp算法与去重的关系

Question

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

Answer 1

对于可变大小的分块重复数据删除，我们有两个步骤：

1. 分块
2. 索引

Rabin Karp 滚动哈希是一种分块算法，可将文件切割成不同大小的块。然后我们需要索引/查询数据块，因为我们进行了重复数据删除。一般的方法是计算chunk的hash值，以hash为key存储chunk。使用 Rabin Karp 算法，一切都是直截了当的，因为我们同时获得了哈希和数据块。

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

希望这会有所帮助。