在C++中查找重复文件的最佳方法是什么？

Question

我想在C++中查找文件系统中的重复文件。是否有任何算法可以尽可能快地完成此操作？我需要创建多线程应用程序吗，还是只需使用一个线程即可完成？

- unresolved_external

---

通常只有1个线程执行IO操作，因为对于HDD来说，磁盘访问不能同时进行（SSD不确定）。要查找重复项，请比较哈希值，通常使用MD5或SHA1。 - nhahtdh

相关问题: https://dev59.com/tnRA5IYBdhLWcg3w6SRH - Andriy

你能详细说明一下吗？你想搜索整个磁盘，以查看驱动器上的任何目录中的任何文件是否与其他文件重复吗？你需要帮助文件系统访问、算法还是两者都需要？ - Mark B

你想搜索整个磁盘，查看驱动器上的任何目录中的任何文件是否与驱动器上的任何其他文件重复吗？没错。你需要帮助文件系统访问、算法还是两者都需要？我需要算法方面的帮助，但如果你能帮我解决文件系统访问问题，我会非常感激 :) - unresolved_external

Answer 1

我同意Kerrek SB的观点，认为有比C ++更好的工具来实现此操作，但是如果您确实需要使用C ++，在此提供一些建议和注意事项：

1. 使用boost :: filesystem以实现可移植的文件系统遍历

2. 针对每个文件进行散列处理是非常合理的建议，但是当具有重复大小的文件时，先制作一个多重映射可能会更有效。然后只在存在重复大小的文件时应用散列。

3. 决定如何处理空文件和符号链接/快捷方式

4. 决定如何处理特殊文件，例如在Unix上，您拥有目录FIFO，套接字等

5. 考虑到文件或目录结构可能会在算法运行时发生更改、消失或移动

6. 考虑到某些文件或目录可能无法访问或损坏（例如递归目录链接）

7. 使线程数量可配置，因为合理的并行度取决于底层磁盘硬件和配置。如果您正在简单的硬盘上，它将与昂贵的SAN不同。不要做出假设;测试一下。例如，Linux非常擅长缓存文件，因此许多读取将来自内存，因此不会阻塞I / O。

- frankc

---

+1 - 以文件大小为优先顺序肯定是更好的方法！ - Kerrek SB

什么是使用OpenSSL库查找文件哈希的最佳方法？查找文件哈希的功能是否适用于所有文件还是仅适用于txt文件？ - unresolved_external

是的，那可能没问题。您可以在此处查看如何计算md5sums：https://dev59.com/questions/c3M_5IYBdhLWcg3wzmkw 除非有人故意欺骗您的扫描仪会导致安全问题（例如，如果您正在自动删除重复项等），否则您不需要加密安全哈希用于此应用程序。 - frankc

Answer 2

1) 不要使用C++，所有需要的工具已经存在。

2) 对每个文件进行哈希（例如使用md5sum），并建立一个包含文件名、文件大小和哈希值的索引*。

3) 按照哈希值排序，并查找哈希值和大小相同的重复对（例如使用sort）。

4) 对候选的重复项执行普通的diff操作。

你可以通过一些工作来并行化步骤2)，但是你将受到存储的I/O速度的限制。你可以通过将大型索引文件分成多个部分，分别排序，然后合并它们（sort -m）来并行化步骤3)。

*) 正如@frankc所说，不要实际上哈希每个文件，而仅哈希那些大小不唯一的文件。从基于大小的索引开始。你将不得不哈希很多小文件，但只有极少数的大文件。

- Kerrek SB

---

我不想使用它，但它是任务的一部分。所以我需要一个单线程，对吗？ - unresolved_external

不确定第二步如何并行化。大部分时间都花在IO上了。 - nhahtdh

顺便问一下，我能对非文本文件（例如*.avi或*.mp3）进行哈希处理吗？ - unresolved_external

“Sort by” 嗯...只需通过哈希值（或哈希值+文件大小）进行索引（例如：列表字典），这样就不必排序。 - Karoly Horvath

正如@frankc所说，您应该先制作一个文件大小的索引，然后仅为这些候选项计算哈希值。 - Kerrek SB

Answer 3

我会这样做：

- 扫描您感兴趣的目录，查看每个文件的大小；将文件大小/路径对存储在“multimap”中，其中文件大小为索引； - 然后，扫描“multimap”，查找每个键仅有一个元素的桶，即大小唯一的文件；这些肯定不是重复项。 - 对剩余文件的内容进行哈希处理，并执行与之前相同的操作（使用哈希作为键值和路径作为值的“multimap”）。 - 然后仅对具有相同哈希的文件进行真正的（逐字节）比较。

这个过程应该比盲目地对所有文件进行哈希要快得多，因为大多数文件的大小不同，可以通过查看文件大小来区分它们。检查文件大小比哈希文件要便宜得多，因为它只是一个文件系统属性查找而不是读取整个文件的内容。

最后一步是必要的，因为存在哈希相同但内容不同的不同文件；但是好的哈希函数已经完成了大部分工作，因为无关文件的哈希冲突应该非常罕见。

请注意，您的哈希函数既不需要具有加密安全性，也不需要特别快（我认为此过程的时间将被IO主导）。

另外，由于您实际上不需要拥有排序的容器，因此可以使用“unordered_multimap”而不是“multimap”，因为它应该具有更快的查找时间，并且一旦您知道要处理多少文件，就可以调用“reserve”来获得确定的元素最大数量，避免重新分配。

- Matteo Italia