Hash函數預覽

轉載（全文）位址：http://blog.csdn.net/zajin/article/details/12648587 最先進的非加密散列函數在過去幾年中得到了快速推廣。當我這周搜尋的時候，我很高興的看到新的尖端散列函數已經釋出即使上次我進行這個方面的搜尋是6個月到1年前的事情了。 非加密散列函數将字元串作為輸入，通過計算輸出一個整數。理想的散列函數的一個特性是輸出非常均勻分布在可能的輸出域，特别是當輸入非常相似的時候。不同于加密散列函數，這些函數不是為防止攻擊者找出碰撞而設計的。加密散列函數有這個特性但是要慢的多：  SHA-1大約為0.09 bytes/cycle，而最新的非加密散列函數的速度大約為3 bytes/cycle。是以在不考慮抵禦攻擊的成本下，非加密散列大約要快33倍。非加密散列函數用的最多的地方是hash table。

一個有趣的題外話，現在Lua社群上有個關于針對Lua的散列函數理論上可以被攻擊使得hash table最壞情況下的查找複雜度降低到O(n) 的事實我們應該做些什麼（如果可以的話）的争論，如果攻擊者引導你輸入你放入lua hash table的東西，那麼他可以通過DoS攻擊你。Lua的作者懷疑這種攻擊實施的可行性（以及它的代價是否比其他DoS攻擊更小），但是他還是打算在将要使用的散列函數的開始時候生成随機種子。這是一個有趣的加密替代函數，能夠給你與加密散列函數相同的耐碰撞能力（假設你有能夠給你真正随機位的資訊源），但這将以非重複性輸出為代價。 由于非加密散列函數有很多種選擇，并且可供選擇的數目不斷擴大，我想我應該總結以下我對這個領域的了解。

Bob Jenkins' Functions Bob Jenkins已經在散列函數領域工作了将近15年。在1997年他在《 Dr. Dobbs Journal》雜志上發表了一片關于散列函數的文章《A hash function for hash Table lookup》，這篇文章自從發表以後現在網上有更多的擴充内容。這篇文章中，Bob廣泛收錄了很多已有的散列函數，這其中也包括了他自己所謂的“lookup2”。随後在2006年，Bob釋出了lookup3，由于它即快速（Bob自稱，0.5 bytes/cycle）又無嚴重缺陷，在這篇文章中我把它認為是第一個“現代”散列函數。 更多有關Bob's散列函數的内容請參閱維基百科：Jenkins hash function.

第二代: MurmurHash Austin Appleby在2008年釋出了一個新的散列函數——MurmurHash。其最新版本大約是lookup3速度的2倍（大約為1 byte/cycle），它有32位和64位兩個版本。32位版本隻使用32位數學函數并給出一個32位的哈希值，而64位版本使用了64位的數學函數，并給出64位哈希值。根據Austin的分析，MurmurHash具有優異的性能，雖然Bob Jenkins 在《Dr. Dobbs article》雜志上聲稱“我預測[MurmurHash ]比起lookup3要弱，但是我不知道具體值，因為我還沒測試過它”。MurmurHash能夠迅速走紅得益于其出色的速度和統計特性。

第三代: CityHash 和 SpookyHash 2011年，釋出了兩個散列函數，相對于MurmurHash ，它們都進行了改善，這主要應歸功于更高的指令級并行機制。Google釋出了CityHash（由Geoff Pike 和Jyrki Alakuijala編寫），Bob Jenkins釋出了他自己的一個新散列函數SpookyHash（這樣命名是因為它是在萬聖節釋出的）。它們都擁有2倍于MurmurHash的速度，但他們都隻使用了64位數學函數而沒有32位版本，并且CityHash的速度取決于CRC32 指令，目前為SSE 4.2（Intel Nehalem及以後版本）。SpookyHash給出128位輸出，而CityHash有64位，128位以及256位的幾個變種。

哪一個散列函數最好/最快？ 從我所了解的情況來看，這篇文章中所提到的所有散列函數從統計學角度來看已經足夠好。需要考慮的一個因素是CityHash/SpookyHash的輸出超過了64位，但是對于一個32位的hash table來說這輸出太多了。其他應用可能會用到128或256位輸出。 如果你用的是32位機器，MurmurHash看起來是最明顯的赢家，因為它是唯一一個快于lookup3的32位原生版本。32位機器很可能可以編譯并運作City和Spooky，但我預計它們的運作速度和在64位機器上運作的速度比起來要慢的多，畢竟32位機器需要模拟64位的數學運算。 在64位機器上，由于沒有更深層次的基準，也很難說哪種算法是最好的。對比City我更傾向于Spooky，因為City的運作速度需要依賴于CRC32指令，畢竟這種環境并不是任何機器上都有的。

另一個需要考慮的是對齊和非對齊的通路。Murmur散列（不像City或者Spooky）是一個僅能進行對齊讀取的變種，因為在很多架構上非對齊的讀取會崩潰或者傳回錯誤的資料（非對齊的讀取操作在C中是未定義的行為）。City和Spooky都強調使用memcpy()把輸入資料複制到對齊的存儲結構中；Spooky使用一次memcpy()操作一個塊（如果ALLOW_UNALIGNED_READS未定義），City使用一次memcpy()操作一個整型！在可以處理非對稱讀取的機器上（像x86和x86-64），memcpy将被優化，但我在我的小ARM上做了一個測試，發現如下： 1 #include <stdint.h> 2 #include <string.h> 3 int32_t read32_unaligned( const void *buf) { 4 int32_t ret; 5 memcpy (&ret, buf, 4); 6 return ret; 7 } 編譯這段低效的代碼（在x86上是一個單獨的操作）： 1 0: b500       push {lr} 2 2: 2204       movs r2, #4 3 4: b083       sub sp, #12 4 6: 4601       mov r1, r0 5 8: eb0d 0002  add.w r0, sp, r2 6 c: f7ff fffe  bl 0 7 10: 9801       ldr r0, [sp, #4] 8 12: b003       add sp, #12 9 14: bd00       pop {pc} 結論是，如果你需要32位或者僅僅是對齊讀取的話，Murmur散列看起來依舊是最好的選擇。City散列和Spooky散列在x86-64上看起來更快，但我更傾向于認為它們是特定用于那個架構的，因為我不知道是否有其他既是64位又允許非對其讀取的架構。 文中若有謬誤，敬請告知。