更快的MD5替代方案？

Question

我正在开发一个程序，在整个驱动器中搜索给定的文件。目前，我对已知文件计算MD5哈希值，然后递归扫描所有文件，寻找匹配项。

唯一的问题是，MD5在大文件上速度非常慢。有没有更快的替代方案，同时保持非常小的误报率？

所有代码都使用C#编写。

谢谢。

更新

我读到即使是MD5也可以相当快，并且磁盘I/O应该是限制因素。这让我相信我的代码可能不是最优的。这种方法有什么问题吗？

        MD5 md5 = MD5.Create();
        StringBuilder sb = new StringBuilder();
        try
        {
            using (FileStream fs = File.Open(fileName, FileMode.Open, FileAccess.Read))
            {
                foreach (byte b in md5.ComputeHash(fs))
                    sb.Append(b.ToString("X2"));
            }
            return sb.ToString();
        }
        catch (Exception)
        {
            return "";
        }

- paulbeesley

---

不要使用.ToString("x2")，而是使用http://blogs.msdn.com/b/blambert/archive/2009/02/22/blambert-codesnip-fast-byte-array-to-hex-string-conversion.aspx，这样可以节省一些时间。 - tcables

调用 ToLower 和 ToUpper 的意义是什么？ - Chibueze Opata

Answer 1

我希望您只在文件大小已匹配的情况下才检查MD5匹配。

另一个优化是对前1K（或其他任意但合理小的数字）进行快速校验，确保它们与整个文件匹配后再处理整个文件。

当然，所有这些都假定您只是在寻找特定文件的匹配或不匹配决策。

- Mike B

---

支持这个切片。当第一个字节不同时，无需对37GB进行哈希处理。 - Dan Lugg

Answer 2

无论加密要求如何，哈希冲突的可能性存在，因此没有哈希函数可以用来“保证”两个文件是相同的。

我之前编写了类似的代码，通过先对所有文件建立索引并丢弃任何大小不同的文件，我得以使其运行得非常快速。然后在剩余的条目上执行快速的哈希比较（仅对每个文件的一部分进行比较），对于此步骤来说，比较字节被证明不太有用——许多文件类型具有相同的标头，这些标头在文件开头有相同的字节。在此阶段仍留下的任何文件将使用MD5进行检查，最后如果MD5匹配，则对整个文件进行字节比较，以确保内容相同。

- Rich.

---

听起来是一个不错的、合乎逻辑的方法 - 感谢你的参与。 - Paul Beesley

Answer 3

只是线性读取文件吗？似乎完全没有必要读取整个文件，计算md5哈希值，然后再比较哈希值。

按顺序读取文件，每次几个字节，可以在读取4个字节后丢弃绝大多数文件。这样，您将节省计算不需要的哈希函数的所有处理开销。

如果您已经拥有驱动器中所有文件的哈希值，则比较它们是有意义的，但是如果您必须即时计算它们，那么哈希似乎就没有任何优势。

我错过了什么吗？在这种情况下，哈希有什么用处？

- jalf

---

不幸的是，程序运行时我将无法访问原始文件，所以存储哈希值（实际上是多个哈希值）是我能够进行比较的唯一方式。 - Paul Beesley

至少，如果你能存储哈希值加上前几个字节（最好超过4个字节，因为通常这是文件格式魔数的大小），那么你可以在仅打开文件并读取几个字节后就丢弃绝大多数情况。 - Steve Jessop

Answer 4

首先考虑真正的瓶颈是什么：哈希函数本身还是磁盘访问速度？如果受限于磁盘，更改哈希算法不会有太大作用。根据您的描述，我推断您总是扫描整个磁盘来查找匹配项-请先构建索引，然后只将给定哈希与索引进行匹配，这样会快得多。

- Adam Byrtek

Answer 5

使用MD5比较文件存在一个小问题：已知存在一些不同的文件却具有相同的MD5值。

这意味着你可以使用MD5来判断文件是否不同（如果MD5不同，则文件必定不同），但你无法使用MD5来判断文件是否相同（如果文件相同，则MD5必须相同，但如果MD5相同，则文件可能相同也可能不同）。

你应该使用尚未被破解的哈希函数（如SHA-1），或者（正如@SoapBox所提到的）仅将MD5用作查找更深层次比较的快速方式。

参考资料：

• http://www.win.tue.nl/hashclash/SoftIntCodeSign/

- CesarB

---

正确，但这适用于哈希算法的所有情况。当哈希值是 n 位长时，只有 2^n 种可能的哈希值。但是不同文件的数量是可数无限的。因此，具有相同哈希值的不同文件对的数量也是可数无限的。 - Ingo

@Ingo: 是的，但对于MD5，我们知道如何创建一对具有相同散列值的文件（不仅如此，已经存在多个这样的文件对）。对于尚未被破解的加密散列，我们无法有意地创建这样的一对文件，而且偶然地创建出这样一对文件的可能性极小，小到我们可以将其视为根本不可能发生（至少在该散列算法被破解之前是这样的）。 - CesarB

他的使用情况似乎并不关心攻击，所以可能并不重要。 - Scott Stafford

Answer 6

使用MD5CryptoServiceProvider和BufferedStream。

        using (FileStream stream = File.OpenRead(filePath))
        {
            using (var bufferedStream = new BufferedStream(stream, 1024 * 32))
            {
                var sha = new MD5CryptoServiceProvider();
                byte[] checksum = sha.ComputeHash(bufferedStream);
                return BitConverter.ToString(checksum).Replace("-", String.Empty);
            }
        }

- Sergey Grischenko

---

这并不会使过程更快。要使其更快，只有那个五年前被接受且得到高赞的答案才能起作用。 - Oliver