JavaScript中用于文件的快速低冲突非加密哈希

Question

JavaScript中用于文件的快速低冲突非加密哈希

20

我正在寻找一种快速且具有低碰撞率的哈希算法，需要用JavaScript实现。它不必是加密哈希。基本上，我使用它来查看用户是否已将给定文件上传（或部分上传）到其帐户中，以节省他们在大型（视频）文件上传方面的时间。

我正在使用新的HTML5文件API来读取文件的片段，然后将其交给SparkMD5来生成文件的哈希值。SparkMD5允许我进行增量哈希计算，这样我就不必在内存中读取整个文件。

总的来说，SparkMD5对我的需求来说还可以，但对于大型文件，生成哈希值可能需要一些时间（对于300MB文件，需要约30秒）。我理想情况下想减少这个过程的时间。我对哈希函数并不十分了解，因此不打算自行开发，而是希望能够找到一个已经实现好的库来使用。

- Eric Anderson

1

什么样的持续时间才算可以接受呢？你可以考虑使用CRC32，它应该比MD5更快，但可能不会有明显的变化，并且您可能会得到更高的冲突率。 - Graham

回答你的问题，我希望它只需要几秒钟就能处理1GB的文件。我不知道这是否现实。 - Eric Anderson

好的。每个用户可能有多少个视频？为什么不对上传的每个文件的前1MB进行校验和并将其存储在您的数据库中。当用户选择要上传的视频时，计算前1MB的校验和并将其与用户的数据库条目进行比较。如果存在匹配项，则需要对其余部分进行校验和，但在大多数情况下，您不会找到任何匹配项，用户可以继续上传。 - Graham

嗯，我在考虑一个简历功能。它不总是视频，我想确保如果他们拿一个文件并进行小修改，我不会以一种错过他们修改的方式恢复（如果他们进行任何更改，我基本上希望将其视为新文件）。 - Eric Anderson

如果文件不太可能具有相同的前1Mb，则可以仅对前1Mb进行哈希，例如。 - Patashu

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jo Liss · Accepted Answer

更新（2021年8月）： 我的基准测试早于WebAssembly，因此已经过时了。可能存在编译到 WebAssembly 中的哈希函数，它们比纯 JS 实现更快。如果有人想要更新此基准测试，欢迎在我的基准测试存储库中提交请求！

我对各种哈希算法进行了基准测试，并找到了最快的选项：

如果您仅需要 32 位摘要，请使用iMurmurHash。请注意，这将在大约 2 ** 14（16,000）次哈希后产生冲突。
如果您需要超过 32 位，请使用SparkMD5。我没有找到快速的 64 或 128 位 Murmur 实现，但是 SparkMD5 的速度非常快（75 MB / 秒）。
- 如果您需要增量更新，请考虑将字符串连接成较大的块，然后将它们馈送到 SparkMD5 中，因为 SparkMD5 的增量哈希似乎受到一些中等开销的影响。

这些建议适用于纯 JavaScript。我使用字符串对它们进行了基准测试，但 SparkMD5 也可以使用 ArrayBuffers。

如果您希望在 Node 上获得快速的哈希模块，最好的选择略有不同：

如果您正在对缓冲区进行哈希处理：请使用内置的crypto模块和 MD5 算法。
- 唯一的例外是: 如果您不需要增量哈希，并且需要超过500 MB /秒的吞吐量，且可以使用本地的npm依赖项，则可以使用murmurhash-native来获得额外的性能。我没有测试少于128位的摘要大小，因为即使使用128位哈希，速度也如此之快，不太可能成为瓶颈。
  
  (请注意，尽管murmurhash-native技术上支持增量哈希，但在此模式下它比Node内置的MD5算法慢。)
如果您正在对单个字符串进行哈希处理而非增量哈希，请将其转换为缓冲区并查看前面的项目。
如果您正在进行增量哈希处理：
- 如果只需要32位，请使用iMurmurHash。请注意，这将在约2 ** 14（16,000）个哈希后产生碰撞。
- 如果需要更多位：请使用内置的crypto模块和MD5算法。
  - 我还建议您尝试将字符串连接成较大的块，因为当您将它们传递给crypto模块时，字符串会被隐式转换为缓冲区，并且每个缓冲区创建都非常缓慢。性能通常会受到缓冲区创建和字符串连接的限制，因为本地哈希函数与之相比非常快。