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可以用作散列函數嗎？

回答

相關問題