algorithm - 列出给定根目录的文件系统中的所有重复文件。

Question

您将如何设计一种算法来列出文件系统中的所有重复文件？我首先想到的是使用散列，但我想知道是否有更好的方法来做到这一点。需要牢记任何可能的设计权衡？

Answer 1

散列所有文件将花费很长时间，因为您必须读取所有文件内容。

我会推荐一个三步算法:

1. 扫描目录并记下文件的路径和大小
2. 仅对与其他文件具有相同大小的文件进行哈希处理，前提是存在超过 2 个相同大小的文件:如果一个文件仅与一个其他文件具有相同大小，则不需要进行哈希处理，只需一对一比较它们的内容(节省散列时间，之后您将不需要散列值)
3. 即使散列值相同，您仍然必须逐字节比较文件，因为不同文件的散列值可能相同(尽管如果文件大小相同并且是您的文件，则这种情况不太可能发生 文件系统)。

您也可以完全不进行散列，尽可能同时打开所有文件，然后比较内容。这将节省对大文件的多次读取。您可以根据数据类型进行很多调整以节省时间(例如:如果 2 个压缩/tar 文件具有相同的大小 > x Ggigabytes 大小(以及相同的名称)，请不要读取内容，鉴于您的过程，文件很可能是重复的)

这样，您就可以避免对系统中大小唯一的文件进行哈希处理。节省大量时间。

注意:我在这里不考虑名称，因为我认为名称可能不同。

编辑:我做了一些研究(为时已晚)，发现如果您使用的是类似 Un*x 的系统，fdupes 似乎就是这样做的:

https://linux.die.net/man/1/fdupes

在那个问题中看到:List duplicate files in a directory in Unix