我的目标是有效地执行目录树的详尽差异。给定一组文件F，我必须计算等价类EQV = [F₁, F₂, F₃, ... Fₙ]以便fⱼ, fₖ ∈ EQV[i] iff (fⱼ is identical to fₖ) for all i, j, k。
我的总体方法是从一个包含所有初始文件的大类开始，EQV₀ = [[f₁, f₂, ..., fₙ]]，并反复将其拆分为更精细的类EQV₁、EQV₂...... EQVₘ₋₁ ，基于一些m启发式方法，例如文件大小、校验和函数 1、校验和 2。在应用了所有启发式方法(EQVₘ₋₁(之后m必须对EQVₘ₋₁中每个类中的所有文件进行成对差异。因为这最后一步对于EQVₘ₋₁中的每个类都是二次的，即
O(sum(n² for n in map(len, EQVₘ₋₁)) )
如果每个 m 分裂都是线性时间完成的，并且可能会成为我的算法的瓶颈，我的目标是使EQVₘ₋₁尽可能平坦。
我想访问各种好的哈希函数，我可以应用这些函数来最大程度地减少EQVₘ₋₁上的冲突。我目前的想法是使用一些库提供的校验和函数，例如 adler，并通过简单地将其应用于文件中的不同起始字节来生成它的变体。另一种方法是首先应用快速哈希函数，例如 adler，然后仅在仍然太大的类上应用更昂贵的哈希函数(如 md5(。
考虑到我可以在一次读取给定文件时计算该文件的所有哈希值，我如何计算各种哈希值来帮助我区分不相同的文件？
或者，python中可用的非加密安全的哈希函数列表是什么？
编辑：另一个想法似乎使用基于一组固定的随机生成输入的"拉宾指纹"。这是否有意义？http://en.wikipedia.org/wiki/Rabin_fingerprint
我建议首先使用 adler32 ，然后使用 crc32 。 可能有许多非常短的文件具有相同的adler32，但crc32不同。 实际上，您可以考虑在第一次传递时对低于特定大小的文件使用crc32的单个步骤。 该大小可能约为 1K。 对于较长的文件，adler32 和 crc32 的冲突概率将接近相同。
根据您拥有的文件数量，您可以考虑使用更大哈希的后续步骤，例如 md5 或 sha1 。 有关 32 位校验值的预期冲突概率和计数，请参阅此答案。 粗略地说，如果您有数百万个文件，则这一步可能值得执行。
使用更长的哈希值不会给您带来任何好处。 来自 md5 的 128 位足以区分世界上每台计算机上的所有文件。