确定文件身份的算法

Question

对于一个开源项目，我在文件系统之上编写了一个抽象层。

这一层允许我将元数据和关系附加到每个文件。

如果文件被重命名/移动或复制，我希望该层能够优雅地处理文件重命名并维护元数据。

为此，我需要一种计算文件身份的机制。显而易见的解决方案是为每个文件计算一个 SHA1 散列，然后根据该散列分配元数据。但是……那真的很贵，尤其是电影。

因此，我一直在考虑一种算法，虽然不是 100% 正确，但在绝大多数情况下都是正确的，而且成本低廉。

其中一种算法可能是使用文件大小和该文件的字节样本来计算哈希值。

我应该为示例选择哪些字节？我如何保持计算成本低廉且相当准确？我知道这里需要权衡，但性能至关重要。并且用户将能够处理系统出错的情况。

我需要这个算法来处理非常大的文件(1GB+ 和小文件 5K)

编辑

我需要这个算法在 NTFS 和所有 SMB 共享(基于 linux 或 windows)上工作，我希望它支持文件从一个地方复制到另一个地方的情况(存在 2 个物理副本被视为一个身份) .我什至可能考虑希望它在重新标记 MP3 的情况下工作(物理文件已更改，因此我可能有每个文件类型的身份提供者)。

编辑 2

相关问题:Algorithm for determining a file’s identity (Optimisation)

Answer 1

分桶、多层比较应该是最快的并且可扩展到您正在讨论的文件范围内。

第一级索引只是文件的长度。

第二层是散列。在一定大小以下，它是一个整个文件的哈希值。除此之外，是的，我同意您对采样算法的想法。我认为可能影响采样速度的问题:

1. 为避免命中可能高度相似或相同的规则间隔的 header ，您需要输入不符合要求的数字，例如:质数的倍数或连续质数。
2. 避免可能最终遇到常规记录 header 的步骤，因此如果尽管位置不同但您从样本字节中获得相同的值，请尝试通过另一个素数调整步骤。
3. 处理具有大量相同值的异常文件，因为它们是未编码的图像或只是填充了空值。