http://www.oschina.net/translate/state-of-hash-functions

最先進的非加密散列函數在過去幾年中得到了快速推廣。當我這周搜索的時候，我很高興的看到新的尖端散列函數已經發布即使上次我進行這個方面的搜索是6個月到1年前的事情了。

一個有趣的題外話，現在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位的數學運算。

另一個需要考慮的是對齊和非對齊的訪問。Murmur散列（不像City或者Spooky）是一個僅能進行對齊讀取的變種，因為在很多架構上非對齊的讀取會崩潰或者返回錯誤的數據（非對齊的讀取操作在C中是未定義的行為）。City和Spooky都強調使用memcpy()把輸入數據復制到對齊的存儲結構中；Spooky使用一次memcpy()操作一個塊（如果ALLOW_UNALIGNED_READS未定義），City使用一次memcpy()操作一個整型！在可以處理非對稱讀取的機器上（像x86和x86-64），memcpy將被優化，但我在我的小ARM上做了一個測試，發現如下：

#include <stdint.h>#include <string.h>int32_t read32_unaligned(const void *buf) {  int32_t ret;  memcpy(&ret, buf, 4);  return ret;}編譯這段低效的代碼（在x86上是一個單獨的操作）：
   0: b500       push {lr}   2: 2204       movs r2, #4   4: b083       sub sp, #12   6: 4601       mov r1, r0   8: eb0d 0002  add.w r0, sp, r2   c: f7ff fffe  bl 0   10: 9801       ldr r0, [sp, #4]  12: b003       add sp, #12  14: bd00       pop {pc}
結論是，如果你需要32位或者僅僅是對齊讀取的話，Murmur散列看起來依舊是最好的選擇。City散列和Spooky散列在x86-64上看起來更快，但我更傾向于認為它們是特定用于那個架構的，因為我不知道是否有其他既是64位又允許非對其讀取的架構。