寻找重复项的算法

Question

寻找重复项的算法

algorithmfileduplicates

4

有没有著名的算法可以有效地查找重复项？

例如，假设我有数千张照片，并且这些照片都有唯一的名称。可能存在不同子文件夹中的重复项。使用std::map或任何其他哈希映射是否是一个好主意？

- sarat

问题可以重新表述为：给定一棵树，找到具有相同数据内容的重复节点？ - Shamim Hafiz - MSFT

1

你可以使用 HashMap 非常高效地查找某个值是否已经存储。 - Mark Huk

1

你是在寻找文件名相同但内容不同的两个文件，还是文件名不同但内容完全相同的两个文件？ - MK.

2个回答

1

也许你想对每个对象进行哈希，并将哈希值存储在某种表中？要测试重复项，只需在表中快速查找即可。

神秘数据结构???

至于完成此任务的“著名算法”，请参阅MD5。

- tskuzzy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- woliveirajr · Accepted Answer

如果你正在处理文件，一个想法是先验证文件的长度，然后仅对具有相同大小的文件生成哈希。

然后只需比较文件的哈希值。如果它们相同，则表示有重复文件。

安全性和准确性之间存在权衡：可能会发生不同的文件具有相同的哈希值。因此，您可以改进解决方案：生成一个简单，快速的哈希以查找重复项。当它们不同时，您有不同的文件。当它们再次相等时，请生成第二个哈希。如果第二个哈希不同，则只是误报。如果它们再次相等，可能您有一个真正的重复文件。

换句话说：

generate file sizes
for each file, verify if there's some with the same size.
if you have any, then generate a fast hash for them.
compare the hashes.
If different, ignore.
If equal: generate a second hash.
Compare.
If different, ignore.
If equal, you have two identical files.

如果大多数文件都不同，为每个文件进行哈希处理将花费太多时间，并且是无用的。