寻找比MD5或SHA256更快的C#哈希算法

Question

寻找比MD5或SHA256更快的C#哈希算法

4

我正在寻找比SHA256更快的算法。我有超过10亿条记录需要进行哈希和验证是否唯一。目前我使用MD5来加速，避免碰撞，然后再使用SHA256进行处理。这样做可以稍微提高一下性能，但我仍然需要更快的算法。我正在寻找在C#中实现的哈希函数名称或示例伪代码，以便我可以在C#中重现它。

- EntryLevel

2

我目前正在运行它通过MD5，这似乎相当快，然后通过sha256避免碰撞。只是为了确保，您正在哈希到MD5，然后如果两个记录具有相同的哈希，则检查sha256以避免碰撞？如果是这样，您可以尝试用CRC替换MD5，这应该更快（但显然会生成更多的碰撞）。 - Kevin Gosse

1

如果MD5值发生碰撞，那么SHA-256输出也会发生碰撞，这是肯定的吧？或者我对你使用SHA-256的方式有所误解？ - Duncan Jones

首先，你永远不会意外地创建一个MD5碰撞。其次，正如其他人指出的那样，如果你的第一个哈希碰撞了，你的第二个也会碰撞。选择一个并只使用它。 - Nick Johnson

1

“SHA-2(MD5(x))” 这个想法不好。在你的情况下，与 “MD5(x)” 相比并没有优势。 - CodesInChaos

您的记录有多大？重复出现频率如何？它们存储在RAM还是磁盘上？恶意实体是否能够创建记录？ - CodesInChaos

显示剩余3条评论

6个回答

3

做些不同的事情怎么样？

对每条记录使用一种简单的哈希函数，比如将每条记录映射到32位INT的哈希表中，就像插入记录时使用的那种。如果发生哈希冲突，则比较冲突的记录以确定唯一性。

- ase

+1 这基本上意味着你指望一个非常简单（且糟糕）的哈希值不同，那么一个非常好的哈希值肯定也会不同。没有错误的负面影响。 - Andrei

1

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

- VahiD

1

你是否正在检查每个具有sha256的记录？你只需要检查那些具有md5碰撞的记录，即使使用md5，这样的记录应该很少。在这种情况下，当你只是比较重复项时，直接比较原始记录可能会更快，因为一旦出现差异，比较就会返回。

- Joel Coehoorn

拥有超过10亿条记录，我的碰撞几率是多少？或者我在哪里可以找到这个信息？ - EntryLevel

大约每2^64个记录就会发生一次碰撞。虽然发生碰撞就像中彩票一样，但如果你购买了足够多的彩票，它可能会发生。也许吧。好吧，可能不会，但你仍然需要做好准备。https://dev59.com/mmox5IYBdhLWcg3w95E9 - Joel Coehoorn

1

这是一个生日悖论问题。MD5密钥（即天数）有128位，因此共有2^128个密钥。对于10亿条记录（即生日），发生碰撞的近似概率为1 - exp(-1e18 / 2^129) ~= 1.5e-21。碰撞的概率很低，但比人们最初可能期望的要高得多（本评论的初始版本包含错误，我深表歉意）。有关详细信息，请参见此答案。 - jason

0

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

如果您正在构建一个名为“unique”的方法，该方法返回布尔值true，仅当两行是唯一的时才返回true，您可以按照以下三个顺序使用以下三个行特征来获得速度并保持可靠性。

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

如果记录长度是可变的，则第一个特征可能已经知道。第二个特征可以在存储时快速计算。即使您使用安全级别的哈希算法（您已经表示这些算法太慢了），在十亿条记录中，您仍然必须覆盖碰撞的可能性。因此，当校验和匹配时（如果校验和具有足够数量的位，则这种情况很少发生），您将不得不逐字节比较实际值。

- Douglas Daseeco

0

你甚至可以采用 MD5，如果发生冲突，则向两个值都添加一些额外数据（相同），然后再次进行 MD5。如果它们不同，那么它们高度不可能再次发生冲突。因此，在发生冲突之后，不要使用 SHA，而是使用添加了一些内容的 MD5 再次进行操作，这应该会更快。

- Ruchir Patwa

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

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

- Patrick M · Accepted Answer

这里的答案中有很多可疑的信息。您使用了cryptography标签来提问，但只提到了加密哈希函数，听起来您并不真正需要加密安全性，尤其是因为您说：

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

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

对于任何给定的消息，计算哈希值很容易

生成具有给定哈希的消息是困难的

修改消息而不更改哈希是困难的

找到两个具有相同哈希的不同消息是困难的。

你真正感兴趣的只是第一个质量和唯一性，这只是与加密安全的其他三个属性部分相关的较小规模的要求。

你为什么关心？

加密安全性存在开销。您不需要它，并且您对速度感兴趣，那么为什么不跳过它呢？ MD5和SHA系列的哈希宽度确实足够大，适合您的用途。

请查看维基百科上的哈希函数列表，或者查看普通哈希函数的文章。更重要的是，内置的.NET哈希函数有什么问题吗？您是否尝试过只使用Object.GetHashCode()方法？ MSDN参考文献对使用哈希函数有很多介绍。您没有提及正在哈希的数据，因此很难说输出是否在对象之间是唯一的。您如何将对象输入到MD5哈希器中？我假设您正在获取其二进制表示。类似的方法可以用于使用内置的非加密哈希函数。

您可能会担心内置哈希函数的唯一性。它们只返回一个常规整数，即2^32，仅比您正在处理的数据集大约4倍。但是，您总是需要备用哈希函数。冲突是不可行的，但并非不可能发生。标准的备选方案是执行更昂贵的比较，通常是引用比较和按字段值比较。

如果您没有准备好对哈希输出进行精确比较，那么您基本上在倒计时，直到出现错误结果。这对您来说可能并不是什么大问题：只有您可以判断其中的下降趋势。

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

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

如果这不适合您，可以查看维基上列出的其他哈希函数的实现。这里有一个相当不错的 MurmurHash3 参考资料，它可以计算32位或128位哈希值。列表中还有其他具有长哈希宽度并且也有C#库可用的哈希函数。但正如该参考所指出的那样，Murmurhash比MD5和SHA函数要快得多，尽管它没有直接与我上面提到的Object.GetHashCode方法进行比较。