srk*_*ing 34
CRC32 作为哈希算法非常有效.在整点的CRC的是哈希字节流用尽可能少的冲突成为可能.也就是说,有几点需要考虑:
CRC不安全.对于安全散列,您需要一个计算量更大的算法.对于简单的存储桶,安全性通常不是问题.
存在具有不同属性的不同CRC风味.确保使用正确的算法,例如使用哈希多项式0x11EDC6F41(CRC32C),这是最佳的通用选择.
作为散列速度/质量权衡,x86 CRC32指令很难被击败.但是,此指令在旧CPU中不存在,因此请注意可移植性问题.
----编辑----
马克·阿德勒(Mark Adler)提供了一篇关于布雷特·马尔维(Bret Mulvey 使用文章中提供的源代码,我为CRC32C和Jenkins96运行了"桶测试".这些表格显示了真正均匀分布比单独偶然测量结果差的概率.所以,更高的数字更好.作者认为0.05或更低是弱,0.01或更低是非常弱.我完全相信作者所有这些,我只是报告结果.
在所有CRC32C表现优于Jenkins96的情况下,我放置了一个*.通过这个简单的计数,CRC32C比89次的Jenkins96 54更加统一. 特别是如果你可以使用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
Mar*_*ler 18
显然你可以,但你不应该.crc32很难将输入位分配给散列.此外,它当然不应该被用作单向哈希,因为它不是一个.修改消息以生成给定的crc非常容易.
使用为您的目的而设计的哈希算法,无论是什么.
小智 7
我不知道为什么Mark Adler说"crc32很难将输入位分配给hash".crc32散列中没有单个位完全等于输入位.散列的任何位都是输入位的线性组合.其次,crc总是将相同数量的不同输入序列均匀地映射到给定的散列值.例如,如果你有1000位长的消息,在crc32之后,你总能找到产生给定散列值的2 ^(1000-32)个序列,不多也不少.
如果您不需要安全功能,crc可以完美地充当哈希.
实际上,我认为其他非安全散列函数可能比crc更简单,如果你需要更长的crc,例如crc-256.