bash - 在 bash 中查找重复文件的时间复杂度

Question

今天我不得不编写一个 Bash 脚本来删除重复的文件，使用它们的 md5 哈希值。我将这些哈希值作为文件存储在一个临时目录中:

for i in * ; do
    hash=$(md5sum /tmp/msg | cut -d " " -f1) ;
    if [ -f /tmp/hashes/$hash ] ;
    then
        echo "Deleted $i" ;
        mv $i /tmp/deleted ;
    else
        touch /tmp/hashes/$hash ;
    fi ;
done

它工作得很好，但让我想知道:这是一种节省时间的方法吗？我最初想将 MD5 哈希存储在一个文件中，但后来我想“不，因为检查给定的 MD5 是否在该文件中需要每次都重新读取它”。现在，我想知道:使用“在目录中创建文件”方法时是否相同？当同一目录中有很多文件时，Bash [-f] 是否检查线性或准常数复杂度？

如果它取决于文件系统，那么 tmpfs 的复杂性是多少？

Answer 1

我喜欢使用正确的工具来完成工作。在这种情况下，您只想查看重复的文件。我已经针对我手头的数千个文件对此进行了测试，重新阅读该文件似乎没有任何问题。另外我注意到我有数百个重复文件。当我将散列存储在单独的文件中然后处理如此大量的文件时，我的系统在一个目录中存储了大约 10,000 个散列文件后慢慢地爬行。将所有哈希值放在一个文件中大大加快了速度。

# This uses md5deep.  An alternate is presented later.
md5deep -r some_folder > hashes.txt

# If you do not have md5deep
find . -type f -exec md5sum \{\} \;

这会为您提供所有内容的哈希值。

cut -b -32 hashes.txt | sort | uniq -d > dupe_hashes.txt

这将使用cut 获取每个文件的散列，对散列进行排序，然后找到任何重复的散列。这些被写入 dupe_hashes.txt，但没有附加文件名。现在我们需要将 HashMap 回文件。

(for hash in $(cat dupe_hashes.txt); do
    grep "^$hash" hashes.txt | tail -n +2 | cut -b 35-
done) > dupe_files.txt

这对我来说似乎并不慢。 Linux 内核在将此类文件保存在内存中而不是频繁地从磁盘读取它们方面做得非常好。如果您希望强制将其保存在内存中，您可以只使用 /dev/shm/hashes.txt 而不是 hashes.txt。我发现在我的测试中没有必要。

这会为您提供重复的每个文件。到目前为止，一切都很好。您可能想要查看此列表。如果您还想列出原始的，请从命令中删除 tail -n +2 | 位。

当您觉得可以删除每个列出的文件时，您可以将内容通过管道传递给 xargs。这将以 50 个为一组删除文件。

xargs -L 50 rm < dupe_files.txt