detect-duplicates

检测并报告文件系统中的重复文件。

该程序以线性时间运行，相对于检查的文件数量，并且（期望中）每次只加载两个文件到内存中，因此可以用于高效地检查大量非常大的文件中的重复项。

作为一个基准，它可以在大约5秒内检查整个Linux内核仓库（约5GB，超过70,000个文件）。

安装

为了安装此程序，您需要安装 Rust。安装Rust后，安装过程非常简单

cargo install detect-duplicates

使用方法

该程序接受一个目录的路径，并输出该目录或其子目录中任何其他文件的副本。每个相等文件的组将作为一个换行符分隔的列表输出。文件组由两个换行符分隔。

例如，给定以下目录结构

files
├── a.txt
├── b.txt
└── more_files
    ├── c.txt
    ├── d.txt
    └── even_more_files
        ├── e.txt
        └── f.txt

如果 a.txt 和 e.txt 内容相同，并且 b.txt、c.txt 和 d.txt 内容相同，那么此命令

detect-duplicates files

将生成以下输出

files/a.txt
files/more_files/even_more_files/e.txt

files/b.txt
files/more_files/c.txt
files/more_files/d.txt

此命令

detect-duplicates files/more_files

将输出

files/more_files/c.txt
files/more_files/d.txt

技术细节

比较大文件很昂贵，所以我们想尽量减少比较的数量。读取文件也很昂贵，但并不像购买更多RAM那样昂贵。我们可以通过以下方式在读取每个文件最多两次的同时实现线性数量的比较

1. 我们计算每个文件内容的哈希，并将哈希与具有相同哈希的文件列表的映射存储起来。
2. 对于至少有两个具有相同哈希的文件列表，我们存储内容与具有相同内容的文件列表的映射。
3. 我们报告所有在第二个映射中具有相同键的文件为重复文件。

因为我们使用了高质量的64位哈希，所以多个文件具有相同内容哈希但内容不同的情况的概率大约为[^1] #files with same content hash/2^64，这应该非常小。因此，我们预计第二张映射中一次只有一个键，并且一次只加载一个文件，我们需要将其与映射中的值进行比较，这意味着，我们最多期望同时加载两个文件到RAM中。每个文件总共最多加载两次；一次用于计算第一张映射的键，一次（如果适用）用于计算第二张映射的键。

[^1]：确切值是 1 - ((k - 1) / k) ** F，其中F是具有相同内容哈希的文件数量，k是2^64，对于实际值来说，这大致等同于 F/k（F < 1,000,000,000）。