什么是最快的哈希算法来检查两个文件是否相等？

Question

如何快速创建哈希函数以检查两个文件是否相同？

安全性不是非常重要。

编辑：我会通过网络连接发送文件，并确保双方的文件相同。

- eflles

---

一个哈希函数无法告诉你两个文件是否相等，它只能告诉你两个文件是否不相等。如果您只需要比较两个文件一次，那么最快的方法是直接读取文件并进行比较，比任何哈希算法都要快。 - jemfinch

哈希函数是一种更快的方法，用于证明不在同一文件系统上的文件不相同。 - dotancohen

只要哈希函数无法证明两个文件不相等的概率小于其他可能出错情况（如计算机故障）的概率之和，就说明一切正常。对于256位的哈希函数而言，你的电脑变成猫（更大的动物很不可能发生），或者一碗紫罗兰花卉可能更有可能。 - ctrl-alt-delor

你没有详细说明这个问题的使用情况，但其中之一可能是：你想要避免获取一个大且未更改的文件的副本。 假设有一个大文件的本地哈希值和一个本地的大文件。 假设服务器上有一个大文件以及该文件的当前哈希值。你可以下载服务器的哈希值并查看它是否与本地哈希值匹配 - 如果匹配，则无需获取文件的新副本。你还可以使用哈希和本地算法来对本地的大文件进行检查。 - Steven the Easily Amused

哇，我从来没有见过这么多人刻意回避一个问题！ 哈哈...我也想知道这个（在我的情况下，我下载了一个包含8个相同文件大小和日期的.exe文件的软件包，所以想检查它们的内容/看看它们是否相同）--你的问题 应该 给我所需的答案，但是没有人提供可用的命令/指令，所以在阅读了几千字后，我还是一无所知，哦天呐，哈哈！ -- 无论如何，@eflles，你有我的同情。 - Martin

Answer 1

除非您使用的是非常复杂和/或缓慢的哈希算法，否则从磁盘加载数据所需的时间会比计算哈希值更长（除非您使用RAM磁盘或顶级SSD）。

因此，要比较两个文件，请使用以下算法：

• 比较大小
• 比较日期（在这里要小心：这可能会给您错误的答案；您必须测试是否对您适用）
• 比较哈希值

这允许进行快速失败（如果大小不同，则知道文件不同）。

为了使事情更快，您可以计算一次哈希值并将其保存到文件中。还要将文件日期和大小保存到此额外文件中，以便在主文件更改时快速了解何时重新计算哈希值或删除哈希文件。

- Aaron Digulla

---

我已经实现了一个可行的解决方案，使用NTFS下的备用数据流来存储哈希值。不过，我必须对哈希值进行时间戳，这样我才能知道文件是否自上次哈希以来被修改过。 - Steven Sudit

现今快速的硬盘可以以每秒2.5GB的速度读取数据。以我的经验来看，哈希算法远没有达到那么快的速度。 - Abhi Beckert

@AbhiBeckert 我明白了。SHA和MD是为加密而设计的（安全性比速度更重要）。这些问题可能会有所帮助：https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed - Aaron Digulla

@AaronDigulla 我知道这一点。我的观点是，你应该澄清你的答案，因为它目前是错误的。几乎所有哈希都是为加密而设计的，它们都可以比仅从磁盘读取内容并直接比较每个字节要慢得多。你的答案应该说“如果你使用X、Y或Z快速哈希……”，而不是“除非你使用一个真正复杂/慢的哈希……”。此外，许多这些更快的哈希函数对于任何足够大以关心速度的文件来说，冲突风险都是无法接受的。也许可以添加一个“比较内容”的步骤，其中哈希匹配。 - Abhi Beckert

xxh128sum在文件比较方面比使用像sha1这样的加密哈希函数快得多...但我认为Aaron在他的回答中暗示了这一点，只是没有明确说明。然而，对于不那么有经验的用户来说，大多数预安装的哈希命令行工具都会针对加密安全进行优化，而不是速度。xxHash在许多存储库中都可用，包括Ubuntu（sudo apt install xxhash）和OpenBSD（doas pkg_add -U xxhash）。 - moo

Answer 2

一种方法可能是使用简单的CRC-32算法，只有当CRC值相等时，才使用SHA1或其他更强大的哈希重新运行哈希。快速的CRC-32比安全的密码哈希更加有效。

- Greg Hewgill

---

我认为对文件进行哈希处理很可能会受到I/O限制，因此最好使用具有良好分布和大范围的哈希（任何加密哈希算法都可以） 。 - Steven Sudit

我这里要自相矛盾一下：如果只有两个等长的文件，使用哈希和直接比较速度是一样的。但如果你有很多文件想找到相同的，使用哈希就有意义了。 - Steven Sudit

如果您正在通过网络比较文件（正如OP所做的那样），那么每读取一个文件就相当于第二次重传该文件。因此，使用某种哈希算法可能是明智的选择。但我建议第一次就使用一个好的哈希算法，而不是进行初步的CRC32校验，然后再使用其他算法。 - Jonathan Hall

@StevenSudit 这并不是在快速固态硬盘上受到IO限制。我有个测试文件，计算MD5需要一分钟，但我的固态硬盘只需要25秒就可以读取该文件。而且我的固态硬盘已经使用了几年，现在有更快的型号可用。 - Abhi Beckert

即使只是本地比较，如果唯一需要的结果是“相等”/“不相等”，哈希可能仍然有意义，因为这样可以让驱动器/操作系统尽可能快地读取文件，而不是在两个文件之间交替块。 - hmijail

Answer 3

xxhash声称在碰撞方面非常快且强大：

http://cyan4973.github.io/xxHash/

64位变体在64位处理器上运行的速度比32位更快，但总体而言在32位处理器上更慢（奇怪）。

http://code.google.com/p/crcutil 也被认为非常快（并利用硬件CRC指令，如果存在这些指令，则可能非常快，但如果您没有支持它们的硬件，则不够快）。不知道CRC32c是否像xxHash那样好（就碰撞而言）......

https://code.google.com/p/cityhash/ 似乎与crcutil类似且相关[可以编译成使用硬件CRC32c指令的代码]。

如果您“只想要最快的原始速度”，并且不太关心散列输出的随机分布质量（例如对于小集合或速度至关重要的情况），则此处提到了一些快速算法：http://www.sanmayce.com/Fastest_Hash/ （这些“不太随机”分布类型的算法，在某些情况下，“足够好”且非常快）。显然，FNV1A_Jesteress是用于“长”字符串的最快算法，其他一些算法则可能适用于小字符串。 http://locklessinc.com/articles/fast_hash/ 似乎也相关。我没有研究它们的碰撞属性。

最新的热门技术似乎是https://github.com/erthink/t1ha, https://github.com/wangyi-fudan/wyhash, 以及xxhash也有稍微更新的版本。

- rogerdpack

---

有一个64位变体，它在64位处理器上比32位处理器运行得更快，但总体上在32位处理器上较慢（想一想就知道）。好吧，我猜测64位代码针对64位处理器进行了优化，并使用64位长整数来分块哈希机制。 - Ben Personick

@BenPersonick - 如果其他条件相同，64位版本在32位处理器上运行速度较慢是有道理的... 32位处理器必须将64位块大小分成两个部分才能运行，而不是一次性运行 :) - warren

@warren 如果在32位CPU上可能会出现这种情况，但是你无法在32位CPU上运行64位代码。我认为他的意思是，在64位CPU上运行64位代码比在64位CPU上运行32位程序版本更快。由于这是一个数据处理程序，因此使用更大的本机64位变量将允许通过操作64位数据块来更快地执行操作，而不是双倍数量的32位数据块。 :) - Ben Personick

@BenPersonick - 你可以在64位处理器上运行256位算法（例如SHA256）。在32位处理器上运行64位算法肯定是可能的（MD5已经存在比消费级64位CPU更长时间，它是一个128位算法）。运行“本地大小”的算法比那些“非本地大小”的算法要快是有道理的 :) - warren

已经过了很长时间，经过浏览后我认为我们之间存在误解，编写64位代码和使用任意位数的算法是有区别的。我的原始观点是，如果你编写使用64位变量的代码，它将允许64位处理器更有效地利用其内存和缓存，64位代码无法在32位上本地运行，而编写为32位变量的代码在64位架构上运行时也不会受益。 - Ben Personick

Answer 4

您可以尝试使用MurmurHash，它被专门设计为快速且编码相当简单。如果MurmurHash返回匹配结果，您可能需要添加第二个更安全的哈希以确保安全。

- int3

---

原帖作者表示安全性在这里并不是一个考虑因素，所以我不确定为什么第二个哈希会有帮助。相反，我建议使用Murmur的64位变体之一。 - Steven Sudit

我将自相矛盾地建议使用更新的128位变体更好，然后又自相矛盾地补充说，对于这种用例，我会坚持使用适当的加密哈希函数，例如SHA-256。 - Steven Sudit

http://cbloomrants.blogspot.com/2010/08/08-21-10-adler32.html 和 http://www.strchr.com/hash_functions 似乎暗示 murmurhash 比 adler/crc32 更快，只是稍微快一点。这可能完全取决于实现，例如这个 SSE 版本说它是一个“快速”的 crc-like 哈希：http://cessu.blogspot.com/2008/11/hashing-with-sse2-revisited-or-my-hash.html - rogerdpack

Answer 5

我们优化的是完成任务所需的时间。 不幸的是，我们对手头的任务了解得不够，无法确定最佳解决方案。

如果只是比较两个任意文件，则应该先比较它们的大小，然后逐字节（或以MB为单位）比较它们的内容（如果IO更好的话）。

如果要比较两个大型文件集或多个文件集，并且这不是一次性任务，而是会经常发生的事情，则应该为每个文件存储哈希值。 哈希值并不是唯一的，但一串9位数字的哈希值（32位）足以表示40亿种组合，而64位数字足以区分约16 * 10^18 Quintillion个不同的文件。

一个不错的折衷方案是为每个文件生成2个32位哈希值，一个用于前8k，另一个用于1MB + 8k，将它们作为单个64位数字拼接在一起。将所有现有文件编入目录应该相当快速，针对此目录查找候选文件也应非常快速。一旦出现匹配，仅有的确定它们是否相同的方法就是比较整个文件。

我相信给人们他们需要的东西，这通常不是他们认为自己需要的或想要的。

- bjorn

Answer 6

如果只是一次性的话，考虑到您需要读取两个文件来生成它们的哈希值，为什么不每次只读取少量内容并进行比较呢？

如果无法实现，CRC 是一个非常简单的算法。

- Jeff Foster

---

+1 for CRC，因为OP要求“最快”。当然，他又要求“确保文件相同”，这有点自相矛盾哈哈。 - rogerdpack

@rogerdpack，即使使用汇编语言，CRC也不是最快的哈希算法。 - OneOfOne

@OneOfOne 真的，我相信当时我没有意识到这一点。现在我建议使用xxhash或cityhash，请参见我的其他答案https://dev59.com/H3I-5IYBdhLWcg3wn525#11422479 [显然，使用crc32c可以编译成非常快的CPU指令...虽然这不是我最初所指的，但我认为你的评论是正确的] - rogerdpack

Answer 7

对于这种类型的应用程序，Adler32 可能是最快的算法，并具有合理的安全级别。对于更大的文件，您可以计算多个哈希值，例如每个 5 Mb 的文件块一个哈希值，从而降低错误的机会（即哈希相同但文件内容不同的情况）。此外，这种多哈希值设置可能允许哈希的计算以多线程方式实现。

编辑: （根据Steven Sudit的评论）
如果文件很小，需要注意！
Adler32的“加密”属性，或者说它的弱点，尤其是对于短消息而言已经广为人知。因此，建议在文件大小小于几千字节时避免使用所提出的解决方案。
然而，在问题中，OP明确寻求快速算法并放弃了安全方面的顾虑。此外，追求速度可能意味着处理的是“大型”文件而不是小文件。在这种情况下，Adler32，可能应用于每个5MB的文件块，并行计算，仍然是一个非常有效的答案。 Alder32以其简单和快速而闻名。此外，其可靠性虽然低于相同长度的CRC，但对于超过4000字节的消息是完全可以接受的。

- mjv

---

我不建议在任何情况下使用Adler32。它的特性非常糟糕，尤其是对于短文件来说。 - Steven Sudit

有更快的算法，但仍然更好。MurmurHash3是一个不错的选择，但对于这种情况，我建议I/O速度是限制因素，所以SHA-256会更好。 - Steven Sudit

（另外，请使用评论选项而不是编辑选项，否则我只有在幸运的情况下才会知道您的回复。） - Steven Sudit

显然adler32在数字方面表现不佳，但CRC32至少在分布方面还可以。http://www.strchr.com/hash_functions - rogerdpack

Answer 8

背景：

在文件比较中，使用加密级别的哈希函数，例如 MD5、SHA-1、SHA-2、SHA-3 等，会非常缓慢，因为这些工具是针对良好的统计和安全性能进行优化而不是速度。

不幸的是，许多用户熟悉的工具使用加密哈希函数，因为这可能是哈希从用户角度最广泛使用的方式。因此，虽然您可以使用 openssl dgst 或 sha1、sha256 等来比较文件，但速度将非常缓慢。这尤其适用于大量大文件的目录，这也是非常典型的用例！

对于内部应用程序，您可能不关心加密属性。具体而言，如果您担心对手可能有意创建冲突，则应坚持使用上述算法之一（并避免已被攻破的 MD5 或 SHA-1）。

基准测试哈希函数：

SMhasher网站有一些基准测试，可直接进行性能比较，并注明/弱点，如果您有特定需求。

好的折衷方案：

xxdhash非常快（以安全为代价），非常适合在内部进行文件比较任务，当安全不受关注时。二进制文件广泛可用，其中包括命令行实用程序。

优化： 您只需要对相同大小的文件运行哈希功能：https://unix.stackexchange.com/questions/339491/find-a-file-by-hash

示例用例：

我想检查一个大型照片目录，看看是否有一些重复的文件已经被添加进来了。在我的使用情况下，我没有与外部世界进行集成，也没有恶意操作者会尝试添加具有相同哈希的非重复照片（称为碰撞）。

安装：

“xxdhash” 可在许多发行版的软件仓库中获得。要在基于 Debian 的发行版上安装（包括 Ubuntu）：

sudo apt update && sudo apt install xxhash

在 OpenBSD 上：

doas pkg_add -U xxdhash

或从 github 下载。

获取整个目录中文件的唯一哈希值：

现在，命令行工具 “xxh128sum” 应该已经可用了。您可以将其与 find 命令结合使用以查找重复的文件：

find . -type f -exec xxh128sum {} \; > hashes.txt

查找重复项：

现在，您有一个包含哈希值和文件名的文件，可用于查找重复项。只列出第二个找到的重复文件的文件名：

awk 'visited[$1]++ { print $2 }' hashes.txt

- moo

Answer 9

为什么要使用哈希？

如果您想确保两个文件相等，那么根据定义，您将不得不读取整个文件（除非它们实际上是相同的文件，在这种情况下，您可以通过查看文件系统上的元数据来确定）。无论如何，没有理由进行哈希，只需阅读它们并查看它们是否相同即可。哈希会使其效率降低。即使哈希匹配，您仍然不确定文件是否真的相等。

编辑：在问题未指定任何关于网络的内容之前发布了此回答。它只是询问有关比较两个文件的问题。现在我知道文件之间存在网络跳跃，我会建议只使用MD5哈希，并完成它。

- tster

---

我正在通过网络连接发送文件，并会确保两端的文件相等。 - eflles

那好吧，那么就使用一个真正的哈希算法吧。我保证你的网络比哈希算法更慢。 - Greg Hewgill

在这种情况下，使用已经存在的哈希函数。Greg发布了一些很好的例子。 - tster

Answer 10

无论如何，您都应该完全阅读每个文件（除非大小不匹配的情况），因此只需读取两个文件并逐块进行比较。

使用哈希只会增加 CPU 使用率，没有其他好处。由于您不写任何内容，操作系统的缓存将有效地删除您读取的数据，因此在 Linux 上，只需使用 cmp 工具。

- socketpair