hash - CRC32可以用作哈希函数吗？

Question

CRC32可以用作哈希函数吗？这种方法有什么缺点吗？有什么权衡吗？

Answer 1

CRC32 作为一种哈希算法工作得很好。 CRC 的重点是对字节流进行哈希处理，并尽可能减少冲突。也就是说，有几点需要考虑:

• CRC 不安全。为了安全散列，您需要计算成本更高的算法。

• 不同的 CRC 风格具有不同的属性。确保使用正确的算法，例如哈希多项式 0x11EDC6F41 (CRC32C) 是最佳通用选择。

• 作为哈希速度/质量的权衡，x86 CRC32 指令很难被击败。然而，该指令在较旧的 CPU 中不存在，因此请注意可移植性问题。

---- 编辑 ----

Mark Adler provided一个link to a useful article Bret Mulvey 进行哈希评估。使用文章中提供的源代码，我对 CRC32C 和 Jenkins96 运行了“桶测试”。这些表格显示了真正均匀的分布比偶然测量的结果更差的概率。因此，数字越高越好。作者认为0.05或更低为弱，0.01或更低为非常弱。我完全相信作者对这一切的看法，我只是报告结果。

我在 CRC32C 性能优于 Jenkins96 的所有实例旁边打了 *。通过这个简单的统计，CRC32C 是比 Jenkins96 更均匀的哈希值 54 次(共 96 次)。 尤其如果您可以使用 x86 CRC32 指令，则速度质量权衡非常出色。

CRC32C (0x1EDC6F41)       Uniform keys        Text keys         Sparse keysBits  Lower    Upper     Lower    Upper     Lower    Upper 1    0.671   *0.671    *1.000    0.120    *0.572   *0.572 2   *0.706   *0.165    *0.729   *0.919     0.277    0.440 3   *0.878   *0.879    *0.556    0.362    *0.535   *0.542 4    0.573    0.332     0.433    0.462    *0.855    0.393 5    0.023   *0.681     0.470    0.907     0.266    0.059 6   *0.145   *0.523     0.354   *0.172    *0.336    0.588 7    0.424    0.722     0.172   *0.736     0.184   *0.842 8   *0.767    0.507    *0.533    0.437     0.337    0.321 9    0.480    0.725    *0.753   *0.807    *0.618    0.02510   *0.719    0.161    *0.970   *0.740    *0.789    0.34411   *0.610    0.225    *0.849   *0.814    *0.854   *0.00312   *0.979   *0.239    *0.709    0.786     0.171   *0.86513   *0.515    0.395     0.192    0.600     0.869   *0.23814    0.089   *0.609     0.055   *0.414    *0.286   *0.39815   *0.372   *0.719    *0.944    0.100    *0.852   *0.30016    0.015   *0.946    *0.467    0.459     0.372   *0.793

对于 Jenkins96，文章作者认为这是一个出色的哈希:

Jenkins96      Uniform keys         Text keys         Sparse keysBits  Lower    Upper     Lower    Upper     Lower    Upper 1    0.888    0.572     0.090    0.322     0.090    0.203 2    0.198    0.027     0.505    0.447     0.729    0.825 3    0.444    0.510     0.360    0.444     0.467    0.540 4    0.974    0.783     0.724    0.971     0.439    0.902 5    0.308    0.383     0.686    0.940     0.424    0.119 6    0.138    0.505     0.907    0.103     0.300    0.891 7    0.710    0.956     0.202    0.407     0.792    0.506 8    0.031    0.552     0.229    0.573     0.407    0.688 9    0.682    0.990     0.276    0.075     0.269    0.54310    0.382    0.933     0.038    0.559     0.746    0.51111    0.043    0.918     0.101    0.290     0.584    0.82212    0.895    0.036     0.207    0.966     0.486    0.53313    0.290    0.872     0.902    0.934     0.877    0.15514    0.859    0.568     0.428    0.027     0.136    0.26515    0.290    0.420     0.915    0.465     0.532    0.05916    0.155    0.922     0.036    0.577     0.545    0.336

---- 编辑 ----修复了过时的链接和较小的清理。