javascript - 文件的 JavaScript 中的快速低冲突非加密哈希

Question

我正在寻找一种用 JavaScript 实现的具有低冲突的快速散列。它不需要是加密哈希。我基本上是用它来查看给定文件是否已经上传(或部分上传)到用户的帐户，以节省他们在大型(视频)文件上的一些上传时间。

我正在使用新的 HTML5 文件 API 读取文件的切片。然后我把它交给SparkMD5给我文件的哈希值。我喜欢 SparkMD5 允许我执行增量哈希的事实，这样我就不必读取内存中的整个内容。

总的来说，SparkMD5 可以满足我的需求，但对于大文件，它可能需要一段时间才能获得我的哈希值(对于 300MB 的文件大约需要 30 秒)。理想情况下，我想减少这个。我不太了解哈希函数，所以我不打算移植某些东西，理想情况下我正在寻找一个已经实现的库。

Answer 1

更新(2021 年 8 月):我的基准测试早于 WebAssembly因此已经过时了。可能存在哈希函数编译成击败纯 JS 实现的 WebAssembly。如果有人想要更新这个基准，对我的拉取请求 benchmark repo非常欢迎!

---

我benchmarked各种哈希算法，这是我找到的最快的选项:

• 如果您只需要 32 位摘要，请使用 iMurmurHash .请注意，这将在大约 2**14 (16,000) 个哈希后给您带来冲突。

• 使用 SparkMD5如果您需要超过 32 位。我没有找到快速的 64 位或 128 位 Murmur 实现，但 SparkMD5 出奇地快(75 MB/秒)。

  • 如果您需要增量更新，请考虑在将字符串提供给 SparkMD5 之前将它们连接成更大的 block ，因为 SparkMD5 的增量哈希似乎会受到一些适度开销的影响。

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

---

如果你想在 Node 上使用快速哈希模块，你最好的选择略有不同:

• 如果您正在散列缓冲区:使用内置的 crypto模块与MD5算法。

  • 异常(exception)情况是:如果您不需要增量哈希，并且您需要超过 500 MB/秒的吞吐量，并且您是可以使用 native npm 依赖项，使用 murmurhash-native一些额外的性能。我没有测试小于 128 位的摘要大小，因为即使是 128 位，散列也非常快，不太可能成为瓶颈。

    (注意 murmurhash-native 在技术上支持增量哈希，但在这种模式下它比 Node 内置的 MD5 算法慢。)

• 如果您非递增地散列单个字符串，请转换它到缓冲区并查看前面的要点。

• 如果您对字符串进行增量哈希处理:

  • 如果您只需要 32 位，请使用 iMurmurHash。请注意，这将在大约 2**14 (16,000) 个哈希后给您带来冲突。

  • 如果您需要超过 32 位:使用带有 MD5 算法的内置加密模块。

    • 我还建议您尝试将字符串连接成更大的 block ，因为当您将字符串传递给加密模块时，字符串会隐式转换为缓冲区，并且每个缓冲区的创建都非常缓慢。性能通常会受到缓冲区创建和字符串连接的瓶颈，因为相比之下， native 哈希函数非常快。