从文件中找到重复的1kb块
TL; DR：如何从一个很大的文件中识别重复的非重叠1kb块，也可以是二进制文件？
我最近在其中一个挑战中遇到了这个问题。
我们有一个文件名。 该文件的大小将是1kb的倍数。 我们必须对此文件执行重复数据删除操作，并将修改后的内容写入另一个文件。 重复数据删除操作从文件中查找并删除重复的，不重叠的1kb块。 该文件可以是非常大的文件，也可以是二进制文件。
问题的第二部分涉及反转重复数据删除操作并从重复数据删除的文件重新生成原始文件。
我的方法：我尝试使用Adam Horwath的博客中建议的哈希。 我计算了每个1kb字节数据的散列，并将其存储在散列表中，散列作为键，并将块的索引作为值考虑。 这是我的代码来计算1kb数据的哈希值（类似于博客中的inithash）：
//implement hashing used in Rabin-Karp algorithm // sum of p^n * a[x] //hconst = 69069; //good multiplier for mod 2^32; public static long calculateHash(int [] data, int chunkSize){ long hash = 1; for(int i =0; i < chunkSize; i++) { int c = data[i]; hash *= hconst; //multiply with const hash += c; //add the byte to hash } return hash; } （显然）我的理解或实施有些不对，但是没有给出正确的结果。 我的问题是：
- 散列方法是否正确以识别重复的块？（比较每个字节是昂贵的过程）
- 有没有更好的方法来识别重复的块？
有没有比核心哈希表更好的方法？ 是。 特别是如果输入文件大于RAM。
您解释说，您有大量的1 KiB文档，大量文件段。 通过读取每个段并将每个段写入一行到包含两列的临时segments.txt文件来预处理它们。 第一列包含段内容的副本，或内容的SHA224哈希。 第二列具有段索引号，它是从零开始的序列号。 您可以随意使用散列的前几个字节，具体取决于您对散列冲突的敏感度。
现在使用/usr/bin/sort （核外合并输出）来创建segments_sorted.txt 。 在这一点上，你的问题是微不足道的。 只需读取每一行，同时记住以前的哈希值。 如果cur_hash == prev_hash您已识别出重复的块。 相关索引可让您快速seek()以查找原始内容，以防止在您的应用程序中排除潜在的冲突。