4

我试图找到比 SHA256 更快的东西。我有超过 10 亿条记录需要散列并验证它们是否唯一。我目前正在通过 MD5 运行它，它看起来非常快，然后通过 sha256 来避免碰撞。以这种顺序运行它们似乎给了我一点性能提升，但我仍然需要它更快。我正在寻找用 c# 或一些伪代码完成的一些哈希的名称或示例，以便我可以在 c# 中重新创建它。

4

6 回答 6

5

这里的答案中有很多可疑的信息。您标记了您的问题cryptography并仅提及加密哈希函数，但听起来您并不真正需要加密安全性，特别是因为您说：

我有超过 10 亿条记录需要散列并验证它们是否唯一。

加密哈希函数有四个属性：

  • 很容易计算任何给定消息的哈希值
  • 生成具有给定哈希的消息是不可行的
  • 在不更改哈希的情况下修改消息是不可行的
  • 找到具有相同哈希的两条不同消息是不可行的。

您实际上只对第一质量感兴趣，唯一性是较小规模的要求，仅与密码安全性的其他三个属性部分相关。

你为什么在乎？

加密安全存在开销。您不需要它，而且您对速度感兴趣，那么为什么不跳过它呢？毫无疑问，MD5 和 SHA 系列的散列宽度足以满足您的目的。

查看 wikipedia 上的散列函数列表，或查看有关普通散列函数的文章。更重要的是，内置的 .NET 散列函数有什么问题？您是否尝试过仅遵循该Object.GetHashCode()方法？该 MSDN 参考对使用哈希函数有很多话要说。你对你正在散列的数据没有说太多，所以很难说输出在你的对象之间是否是唯一的。您如何将对象输入 MD5 哈希器？我想你正在接受它的二进制表示。可以使用类似的方法来使用内置的非加密哈希函数。

您可能会担心内置散列函数的唯一性。它们只返回一个常规的 int，即 2^32，仅比您正在使用的数据集大 4 倍左右。但是，您始终需要为哈希函数制定备份计划。碰撞是不可行的，并非不可能。标准回退是执行更昂贵的比较，通常是参考比较和逐字段值比较。

如果您不准备对哈希输出进行精确比较，那么您基本上是在倒计时，直到得到误报。这对你来说可能没什么大不了的：只有你可以判断有什么缺点。

此外，执行另一个哈希函数计算可能并不比直接比较快多少。你最好在所有方面都选择确定的事情并进行冗长的直接比较。

另一种常见的防冲突技术是使用多个键。因此，如果您的数据点有几个大的子组件，您可以独立地进行散列和比较。如果它有一些大的和一些小的组件（比如一些简单的数字类型），你可以散列大的并直接比较小的。如果他们有一些很容易获取序数的数据（比如字符串的长度或某些容器的大小），您可以对这些位执行直接比较。

如果这对您不起作用，请查看 wiki 上列出的其他哈希函数的实现。这是MurmerHash3 的一个很好的参考，它可以计算 32 位或 128 位哈希值。列表中还有其他散列函数也具有长散列宽度，并且还有可用的 C# 库。但正如该参考资料所指出的，Murmurhash 比 MD5 和 SHA 函数快得多，尽管它没有与我上面提到的 Object.GetHashCode 方法进行直接比较。

于 2013-07-31T07:10:45.300 回答
3

做点不一样的怎么样？

对每条记录使用简单的散列函数，就像将记录插入散列表时使用的那样，可能将每条记录映射到 32 位 INT。然后，如果发生哈希冲突，则比较冲突记录的唯一性。

于 2013-06-28T12:34:15.940 回答
1

您可以使用 MD5，然后如果遇到冲突记录，您可以使用 SHA256 甚至 SHA128 检查它们。

于 2013-06-28T12:39:41.960 回答
1

您是否使用 sha256检查每条记录？您应该只需要检查您有 md5 冲突的记录，即使使用 md5 也应该很少见。那时，当您只是比较重复项时，将原始记录与原始记录进行比较可能会更快，因为比较将返回第一个差异。

于 2013-06-28T12:43:07.720 回答
0

您甚至可以执行类似 MD5 之类的操作，如果发生碰撞，请在两个值中添加一些额外数据（相同）并再次使用 MD5。如果它们不同，则 2 极不可能再次发生碰撞。因此，与其在碰撞后执行 SHA，不如在 MD5 中再次添加一些应该更快的东西。

于 2013-06-29T00:13:19.290 回答
0

从您提出问题的方式来看，您似乎不需要安全级哈希算法。如果您已经传达了您要完成的所有主要要求，您可能根本不需要哈希算法。

如果您正在构造一个名为 unique 的方法，当且仅当两行唯一时返回布尔值 true，您可以通过按此顺序使用以下三个行特征来提高速度并保持可靠性。

  • 长度（如果它们不是固定长度的记录）
  • 校验和
  • 实际价值

如果记录长度是可变的，第一个可能已经知道。秒可以在存储的时候快速计算出来。拥有 10 亿条记录，即使您使用安全级哈希算法（无论如何您说它太慢），您也必须考虑发生冲突的可能性。因此，当校验和匹配时，如果校验和中有足够数量的位，这将是罕见的，您将不得不涵盖逐字节比较实际值的情况。

于 2017-02-10T07:47:22.603 回答