CRC32可作为哈希函数使用吗？这种方法有什么缺点吗？是否存在任何权衡之处？
3个回答
53
CRC32作为哈希算法非常有效。CRC的整个目的是使用尽可能少的冲突来哈希字节流。但是，需要考虑以下几点：
- CRC不安全。要进行安全哈希，您需要一种计算量更大的算法。 - 存在不同属性的CRC变体。确保使用正确的算法，例如具有哈希多项式0x11EDC6F41（CRC32C）的算法，这是最佳通用选择。 - 作为哈希速度/质量折衷，x86 CRC32指令很难被击败。但是，这个指令不存在于旧的CPU中，因此要注意可移植性问题。
----编辑----
位数 下限 上限 下限 上限 下限 上限 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.025 10 *0.719 0.161 *0.970 *0.740 *0.789 0.344 11 *0.610 0.225 *0.849 *0.814 *0.854 *0.003 12 *0.979 *0.239 *0.709 0.786 0.171 *0.865 13 *0.515 0.395 0.192 0.600 0.869 *0.238 14 0.089 *0.609 0.055 *0.414 *0.286 *0.398 15 *0.372 *0.719 *0.944 0.100 *0.852 *0.300 16 0.015 *0.946 *0.467 0.459 0.372 *0.793
统一键 文本键 稀疏键
位数 下限 上限 下限 上限 下限 上限 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.543 10 0.382 0.933 0.038 0.559 0.746 0.511 11 0.043 0.918 0.101 0.290 0.584 0.822 12 0.895 0.036 0.207 0.966 0.486 0.533 13 0.290 0.872 0.902 0.934 0.877 0.155 14 0.859 0.568 0.428 0.027 0.136 0.265 15 0.290 0.420 0.915 0.465 0.532 0.059 16 0.155 0.922 0.036 0.577 0.545 0.336
- CRC不安全。要进行安全哈希，您需要一种计算量更大的算法。 - 存在不同属性的CRC变体。确保使用正确的算法，例如具有哈希多项式0x11EDC6F41（CRC32C）的算法，这是最佳通用选择。 - 作为哈希速度/质量折衷，x86 CRC32指令很难被击败。但是，这个指令不存在于旧的CPU中，因此要注意可移植性问题。
----编辑----
Mark Adler提供了一篇由Bret Mulvey撰写的有关哈希计算的有用文章链接。 使用文章中提供的源代码，我对CRC32C和Jenkins96分别进行了“桶测试”。 这些表格显示了真正均匀分布会比机会差 的概率。 因此，数值越高越好。 作者认为0.05或更低是较弱的，0.01或更低则非常弱。 我完全相信作者的所有内容，只是报告结果。
我在所有CRC32C表现优于Jenkins96的实例旁添加了*。 通过这个简单的统计，CRC32C在96次中有54次比Jenkins96更均匀。 特别是如果您可以使用x86 CRC32指令，则速度质量权衡非常好。
CRC32C（0x1EDC6F41）
位数 下限 上限 下限 上限 下限 上限 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.025 10 *0.719 0.161 *0.970 *0.740 *0.789 0.344 11 *0.610 0.225 *0.849 *0.814 *0.854 *0.003 12 *0.979 *0.239 *0.709 0.786 0.171 *0.865 13 *0.515 0.395 0.192 0.600 0.869 *0.238 14 0.089 *0.609 0.055 *0.414 *0.286 *0.398 15 *0.372 *0.719 *0.944 0.100 *0.852 *0.300 16 0.015 *0.946 *0.467 0.459 0.372 *0.793
对于文章作者认为是优秀哈希函数的Jenkins96：
Jenkins96统一键 文本键 稀疏键
位数 下限 上限 下限 上限 下限 上限 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.543 10 0.382 0.933 0.038 0.559 0.746 0.511 11 0.043 0.918 0.101 0.290 0.584 0.822 12 0.895 0.036 0.207 0.966 0.486 0.533 13 0.290 0.872 0.902 0.934 0.877 0.155 14 0.859 0.568 0.428 0.027 0.136 0.265 15 0.290 0.420 0.915 0.465 0.532 0.059 16 0.155 0.922 0.036 0.577 0.545 0.336
----编辑----
修复过时链接和进行轻微清理。- srking
14
2好的研究！+1。然而，即使有crc32指令，我仍然认为它不会超过专门设计用于（非加密）哈希的哈希算法。您可以在此处找到更高级的哈希算法开发和测试：http://code.google.com/p/smhasher/。 - Mark Adler
6作为一个旁注，布雷特·马尔维几个月前将该网站迁移到以下地址：http://bretmulvey.com/hash/。 - Nico Erfurth
2仍然不行。CRC-32和CRC-32C在雪崩测试中表现非常糟糕。 - Mark Adler
2该页面已经再次移动，现在位于https://papa.bretmulvey.com/post/124027987928/hash-functions。 - Lorenz
1我可以证实，在碰撞方面，包括C语言在内的crc32算法相当糟糕：我刚刚对一个包含150k个单词的英语词典和300k容量的哈希表进行了一些测试，结果crc32平均每个哈希值产生1140次碰撞，而fnv-1a算法只有1.5次。 - abel1502
显示剩余9条评论
8
我不知道Mark Adler为什么说“crc32在将输入位分配到哈希中表现不佳”。在crc32哈希中，没有一个单独的位与输入位完全相等。哈希的任何一位都是输入位的线性组合。其次，crc总是将相同数量的不同输入序列均匀地映射到给定的哈希值。例如，如果您有1000位长的消息，在进行crc32之后，您始终可以找到2^(1000-32)个产生给定哈希值的序列，不多也不少。
如果您不需要安全功能，crc可以完美地作为哈希使用。
实际上，我认为其他非安全哈希函数可能比crc更简单，如果您需要更长的crc，例如crc-256。
如果您不需要安全功能，crc可以完美地作为哈希使用。
实际上，我认为其他非安全哈希函数可能比crc更简单，如果您需要更长的crc，例如crc-256。
- Heng Tang
1
1我相信他这么说是因为CRC在统计随机性测试中失败了 - 在代码范围内均匀分布，没有偏向某些位。 - bryc
2
CRC32将字节映射为32位整数，并在累加它们与xor之前。这意味着每个字节只影响哈希中的32位中的8位。当然，CRC32也进行了移位，但这只是把问题藏在地毯下。也就是说，它将不均匀地分布密钥，在某些区域会有严重的聚类现象。它可能看起来能够正常工作，直到你遇到那个区域，突然你的O(1)哈希表变成了O(n)。
CRC32是为检测损坏文件而设计的，而不是哈希。正如Mark所提到的，它也不能保护您的文件免受修改，因为黑客可以通过在更改后插入一个经过精心制作的32位值来随意修改它们。
- Nash Gold
1
我在哈希表的上下文中对crc32指令进行了大量测试。我特别关注了桶的大小。我将其与常见的哈希函数如fnv1和djp2进行了比较，并发现它的性能相当或更好。我使用记录的真实世界数据进行了测试。 - undefined
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接