[TIL][文章推薦] 設計高效能的 Hash Table

原文

Felix Chern: 設計高效能的Hash Table（一）

心得

還記得當初在寫 Consistent Hashing 的時候，一直不願意拿人家寫好的 Hash Function 來改，硬要自己寫一個．

結果發現寫出來的 Hashing 一直出問題．才知道原來 Hash Function 是實作 Consistent Hashing 的一個重點．

這一篇文章有了一些基本對於 Hash Function 的介紹，也把幾個好用的 Hash Function 一一的列出來．

其中包括了最近被移到了 Google 的 “highwayhash”

或是之前有介紹過在 Uber/ringpop 下作為 Consistent Hashing 的 farmhash

這篇文章相當推薦，原因如下:

1. 作者 (Felix Chern) 目前似乎在 Google 工作，部落格文章都相當有深度．
2. 有 Hash Function 列出的清單並且有簡單的介紹．

參考:

• ringpop 是 Uber 的去中心化 App :
• 這篇文章有下集，在這裡

關於實作與相關測試:

其實 Damian Gryski 實作了不少 Hash Function 的 Go 套件

HighWay Hash

其 Benchmark 如下:

 ~/s/g/s/g/d/go-highway   master  go test -bench=.             六  4/29 01:31:56 2017
BenchmarkHighway8-8    	50000000	        26.3 ns/op	 304.36 MB/s
BenchmarkHighway16-8   	50000000	        26.7 ns/op	 599.24 MB/s
BenchmarkHighway40-8   	50000000	        29.7 ns/op	1345.35 MB/s
BenchmarkHighway64-8   	50000000	        33.3 ns/op	1924.53 MB/s
BenchmarkHighway1K-8   	10000000	       137 ns/op	7452.07 MB/s
BenchmarkHighway8K-8   	 2000000	       873 ns/op	9378.40 MB/s

Farm Hash

其 Benchmark 如下:

 !  ~/s/g/s/g/d/go-farm   master  go test -bench=.    257ms  六  4/29 01:30:43 2017
BenchmarkHash32-8    	20000000	       100 ns/op
BenchmarkHash64-8    	20000000	        58.2 ns/op
BenchmarkHash128-8   	20000000	       123 ns/op

xxHash

這不是 Damian Gryski 實作的，是由 LiftOff Caleb Spare 但是做得很好而且也有被 InfluxDB 使用喔．

xxHash 是選定 64bit 輸出的通用 Hash Function ，使用範圍廣泛而且速度快．

結語:

本來想只是寫個簡單的推薦文，後來決定來跑跑看每個 Hash Function 的效能評比．跑完之後，又想去偷看是不是裡面都沒有使用除法．

發現其實 Hash Function 主要還是針對不同 CPU 的優化，讓他們的速度能夠更快．處理的資料類型能夠更多．

P.S.:

• 其實 Damian Gryski 把幾乎所有 Google 出品的 Hash Function 都重寫成 Golang 版本．

• Google 出了好幾個的 Hash Function 讓我覺得大公司對於 Hash Function 的注意．