查找重复的算法

Question

是否有任何着名的算法可以有效地找到重复？

例如,如果我有数千张照片,并且照片以唯一名称命名.可能存在重复可能存在于不同子文件夹中的可能性.使用std :: map或任何其他哈希映射是个好主意吗？

Answer 1

如果您处理文件,一个想法是首先验证文件的长度,然后为具有相同大小的文件生成哈希.

然后只比较文件的哈希值.如果它们是相同的,那么你有一个重复的文件.

在安全性和准确性之间存在权衡:谁知道,可能会发生具有相同散列的不同文件.因此,您可以改进您的解决方案:生成一个简单,快速的哈希来查找重复项.当它们不同时,您会有不同的文件.当它们相等时,生成第二个哈希值.如果第二个哈希是不同的,那么你只是误报了.如果它们再次相等,那么你可能真的重复了.

换一种说法:

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.

为每个文件执行哈希将花费太多时间,如果大多数文件不同,则无效.