CRC32可以用作散列函数吗？

CRC32可以用作散列函数吗？这种方法的任何缺点？任何tradedeoffs？CRC32可以用作散列函数吗？

2012-06-08 Pradyot

似乎已经问。 http://stackoverflow.com/questions/2694740/can-one-construct-a-good-hash-function-using-crc32c-as-a-base?rq=1 – Pradyot

这取决于你想使用什么散列为。 – Gumbo

对于集合散列的一些子集，是的。然而，它不是一个代码块，它是一个流代码。对于非常小的块，使用表格会更快。 – starbolin

CRC32工作很好作为哈希算法。 CRC的整点是用尽可能少的冲突散列字节流。这就是说，都需要考虑几点：

CRC的是不安全的。为了安全散列，你需要一个计算量更大的算法。对于一个简单的桶式散列器来说，安全性通常不是问题。
不同口味的CRC具有不同特性的存在。确保你使用正确的算法，例如与哈希多项式0x11EDC6F41（CRC32C）这是最佳的通用选择。
作为哈希速度/质量权衡，在x86指令CRC32是很难被击败。但是，这个指令在旧CPU中不存在，所以要小心可移植性问题。

---- ----编辑

马克·阿德勒提供指向由布雷特·穆尔维的散列评估一个有用的文章。使用本文提供的源代码，我对CRC32C和Jenkins96进行了“桶测试”。这些表格显示了真正的均匀分布比单独偶然测量的结果更差的概率。所以，更高的数字是更好的。作者认为0.05或更低为弱，0.01或更低为弱。我完全相信作者，并且只是报告结果。

我把一个*通过其中CRC32C比Jenkins96表现较好的所有实例。通过这个简单的计数，CRC32C是一个比Jenkins96更为统一的散列96次96次。 尤其是如果您可以使用x86 CRC32指令，则速度性能折衷非常好。

 
CRC32C (0x1EDC6F41) 

     Uniform keys  Text keys   Sparse keys 

Bits 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.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 

     Uniform keys   Text keys   Sparse keys 

Bits 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.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

来源

2012-06-09 15:26:01 srking

不，CRC不会避免碰撞以及其他算法。见http://home.comcast.net/~bretm/hash/。 –

@Mark，作者没有使用CRC32C多项式。在他的测试程序中，CRC32C可以很好地用作字节串的散列。 – srking

好研究！ +1。但是我仍然不认为即使使用crc32指令，它也会打破为非（加密）散列而设计的散列算法。您可以在这里找到一些更高级的哈希算法开发和测试：http://code.google.com/p/smhasher/。 –

很明显，你可以，但你不应该。 crc32很难将输入位分配给哈希。此外它绝对不应该被用作单向散列，因为它不是一个。修改消息以产生给定的crc非常容易。

使用专为您心目中的目的，不管它是什么哈希算法。

来源

2012-06-08 22:30:25

很高兴看到阿德勒32的爸爸。 ;） – srking

我不知道为什么马克·阿德勒说，“CRC32不佳分配输入位散列” 。 crc32哈希中没有一个位与输入位完全相同。散列的任何位都是输入位的线性组合。其次，crc始终将相同数量的不同输入序列映射到给定的散列值。例如，如果您有1000位长的消息，在crc32之后，您总是可以找到生成给定散列值的2 ^（1000-32）序列，不多不少。

如果你不需要安全功能，crc可以完美地作为散列。

其实，我觉得其他非安全散列函数可能比CRC简单，如果你需要有一个较长的CRC，例如CRC-256。

来源

2015-02-27 01:58:15

我认为他说，因为CRC未能通过统计随机性测试 - 在代码范围内均匀分布，对某些位没有偏见。 – bryc

CRC32可以用作散列函数吗？

回答

相关问题