c - 从大文件中查找唯一值

Question

我有一个带有 MD5 哈希流（包含重复项）的大文件（比如 10 TB），我有 10MB 的内存（非常有限）和无限的硬盘空间。使用给定条件查找所有唯一哈希（消除重复）。请帮忙，这显然不是作业问题

Answer 1

您可以使用外部排序算法（例如，使用多相合并排序）对哈希进行排序，之后您只需要遍历文件并跳过任何等于最近哈希的哈希

hash mostRecentHash;
while(fileHasHashes) {
    temp = fileWithDuplicates.readHash();
    if(!hashesAreEqual(mostRecentHash, temp)) {
        mostRecentHash = temp;
        fileWithoutDuplicates.writeHash(mostRecentHash);
    }
}

Answer 2

如果性能无关紧要，并且您的文件系统没有限制，那么您可以简单地为每个哈希创建一个文件。如果在创建过程中遇到EEXIST，则有重复，可以跳过。

for (each hash) {
    r = open(hash_to_filename(hash), O_CREAT|O_EXCL);
    if (r < 0) {
        if (errno == EEXIST) continue;
        perror(hash);
        exit(EXIT_FAILURE);
    }
    close(r);
    output(hash);
}

这样做的好处是它保留了哈希值在流中首次出现的顺序。

此方案的实际性能取决于文件系统的性能。如果将文件组织在 B-Tree 中，那么性能将大致为 O(N log(N))。如果文件系统使用哈希表来组织文件，那么性能预计为 O(N)，但这取决于冲突发生的频率（并且常数因子很高，因为磁盘访问）。

Answer 3

我喜欢 Zim-Zam 的解决方案……提出一个小的变化。

如果我们可以假设指纹在 128 位空间上是均匀分布的，那么我们是否可以使用像 Bucket sort 之类的东西将指纹分桶成（较小的）桶文件，对桶文件进行单独排序，然后将桶文件合并为一个使用堆排序文件？这可能会降低 nlogn 成本。