如何查找具有相同内容的所有文件？

Question

这是一个采访问题:"给定一个包含大量文件的目录,找到具有相同内容的文件".我建议使用哈希函数来生成文件内容的哈希值,并仅比较具有相同哈希值的文件.是否有意义 ？

接下来的问题是如何选择哈希函数.你会为此目的使用SHA-1吗？

Answer 1

我宁愿使用哈希作为第二步.首先按文件大小对dir进行排序,并且仅在存在重复大小时进行散列和比较,这可能会在一般情况下提高搜索范围.

Answer 2

与大多数面试问题一样，它更多的是为了引发对话，而不是提供单一答案。

如果文件很少，那么简单地进行逐字节比较可能会更快，直到到达不匹配的字节（假设您这样做）。如果有很多文件，计算哈希值可能会更快，因为您不必在磁盘上从多个文件中分块读取数据。随着您逐步浏览文件以消除潜力，可以通过抓取每个文件中越来越大的块来加快此过程。如果文件足够多，也可能需要将问题分布到多个服务器上。

我将从比 SHA-1 更快、更简单的哈希函数开始。SHA-1 具有加密安全性，但在本例中不一定需要。例如，在我的非正式测试中，Adler 32 的速度快 2-3 倍。您还可以使用更弱的推定测试，而不是重新测试任何匹配的文件。这个决定还取决于 IO 带宽和 CPU 功率之间的关系，如果您有更强大的 CPU，请使用更具体的哈希来节省在后续测试中重新读取文件的麻烦，如果您有更快的 IO，则重新读取可能比执行更便宜不必要的昂贵的哈希值。

另一个有趣的想法是在处理文件时使用启发式方法，根据文件大小、计算机速度和文件熵来确定最佳方法。