xxHash極快的哈希算法
xxHash 是一種極快的哈希算法，在 RAM 速度限制下運(yùn)行。它成功完成了 SMHasher 測(cè)試套件，該套件評(píng)估了哈希函數(shù)的碰撞、分散和隨機(jī)性質(zhì)量。代碼具有高度的可移植性，所有平臺(tái)上的哈希值都相同（little / big endian）。
它有四種版本（XXH32、XXH64、XXH3_64bits和XXH3_128bits）。最新的變體，XXH3，提供了全面的性能改進(jìn)，特別是在小數(shù)據(jù)上。
參考系統(tǒng)使用英特爾 i7-9700K cpu，并運(yùn)行 Ubuntu x64 20.04。開源基準(zhǔn)測(cè)試程序是用 clang v10.0編 譯的，使用- O3flag。
| Hash Name | Width | Bandwidth (GB/s) | Small Data Velocity | Quality | Comment |
|---|---|---|---|---|---|
| XXH3 (SSE2) | 64 | 31.5 GB/s | 133.1 | 10 | |
| XXH128 (SSE2) | 128 | 29.6 GB/s | 118.1 | 10 | |
| RAM sequential read | N/A | 28.0 GB/s | N/A | N/A | for reference |
| City64 | 64 | 22.0 GB/s | 76.6 | 10 | |
| T1ha2 | 64 | 22.0 GB/s | 99.0 | 9 | Slightly worse collisions |
| City128 | 128 | 21.7 GB/s | 57.7 | 10 | |
| XXH64 | 64 | 19.4 GB/s | 71.0 | 10 | |
| SpookyHash | 64 | 19.3 GB/s | 53.2 | 10 | |
| Mum | 64 | 18.0 GB/s | 67.0 | 9 | Slightly worse collisions |
| XXH32 | 32 | 9.7 GB/s | 71.9 | 10 | |
| City32 | 32 | 9.1 GB/s | 66.0 | 10 | |
| Murmur3 | 32 | 3.9 GB/s | 56.1 | 10 | |
| SipHash | 64 | 3.0 GB/s | 43.2 | 10 | |
| FNV64 | 64 | 1.2 GB/s | 62.7 | 5 | Poor avalanche properties |
| Blake2 | 256 | 1.1 GB/s | 5.1 | 10 | Cryptographic |
| SHA1 | 160 | 0.8 GB/s | 5.6 | 10 | Cryptographic but broken |
| MD5 | 128 | 0.6 GB/s | 7.8 | 10 | Cryptographic but broken |
XXH3 專為在長(zhǎng)輸入和小輸入上都具有出色的性能而設(shè)計(jì)，如下圖所示：
xxHash已經(jīng)用Austin Appleby的優(yōu)秀的SMHasher測(cè)試套件進(jìn)行了測(cè)試，并通過(guò)了所有測(cè)試，確保了合理的質(zhì)量水平。它還通過(guò)了SMHasher較新分叉的擴(kuò)展測(cè)試，具有額外的場(chǎng)景和條件。
最后，xxHash提供了自己的大規(guī)模碰撞測(cè)試器，能夠生成并比較數(shù)十億的哈希值，以測(cè)試64位哈希算法的極限。在這方面，xxHash也具有良好的結(jié)果，與生日悖論一致。更詳細(xì)的分析記錄在 wiki 中。
評(píng)論
圖片
表情