哈希表（HashMap、字典）是日常編程當中所經常用到的一種數據結構，程序員經常接解到的大數據Hadoop技術棧、Redis緩存數據庫等等最近熱度很高的技術，其實都是對鍵值（key-value)數據的高效存儲與提取，而key-value恰恰就是哈希表中存儲的元素結構，可以說Redis、HDFS這些都是哈希表的經典應用，不過筆者之前也只知道哈希表比較快，但對於具體什麼場景下快，怎麼用才快等等知識卻一知半解，因此這裡把目前的一些研究成果分享給大家。
重新認識哈希表
所謂的哈希表就是通過哈希算法快速搜索查詢元素的方法，比如說你要在茫茫人海當中找到一位筆名叫做beyondma的博主，但卻並不知道他具體的博客地址，在這種情況下就只能在所有的博主範圍內展開逐個的排查與摸索，運氣差的話我可能以找遍所有n個博主的主頁，才到beyondma，這也就是這種遍歷查找的時間複雜度是o(n)，查找的時間會隨著博主的數量而線增長。
而哈希算法就是直接將beyondma這個名字進行算法處理，直接得到beyondma的博客地址信息，在哈希算法的加持下定位某一元素的時間度變成了o(1)，由於哈希算法能夠將key（鍵值本例中指beyond）和value（本例中指beyond.csdn.net）以o(1)的時間複雜度，直接對應起來，因此哈希表被人稱為key-value表，存儲的元素也被稱為key-value對（鍵值對）。哈希表的查找過程特別像查字典，給出一個字並找到這個字在字典中的位置，只是哈希表在一般情況下都很快。當然哈希表也有代價：
以空間換時間：哈希算法也稱為散列算法，這種叫法相對比較直觀，由於哈希算法是通過計算確認存儲地址的，因此首先進入到哈希表的元素並不一定存到第一個位置，存儲n個鍵值對的哈希表往往會消耗比切片多很多的內存空間。
哈希碰撞：哈希碰撞是指不同的鍵值，在經過哈希計算後得到的內存地址槽位是相同的，也就是說相同的地址上要存儲兩個以上的鍵值對，一旦發生這種情況，也就是哈希碰撞了。在發生碰撞的場景下哈希表會進行退化，其中Java會在碰撞強度到達一定級別後，會使用紅黑樹的方式來進行哈希鍵值對的存儲，而Go和Rust一般都是退化成為鏈表。
下面我們首先來詳細講講兩個哈希表的常見誤用。
哈希表的誤用
不要遍歷哈希表！：局部快，不意味著整體快，由於哈希表提取單個元素的速度很快，因此整個遍歷整個集合所需要的時間也會更短，這種看法明顯是個美麗的誤會。
我們後文也會具體講到，哈希表在遍歷方面的表現結果，是由計算機組成原理決定的，與Go、Rust和Java的區別不大，因此以下例子先以Go語言的代碼為例來說明。
package main
import (
"fmt"
"time"
)
func main() {
testmap := make(map[int]int)
len := 1000000
//tests1ice := make([]int, len, len)
for i := 0; i < len; i++ {
testmap[i] = i + 1
}
sum := 0
now := time.Now().UnixNano()
for k, v := range testmap {
sum = sum + k + v
}
diff := time.Now().UnixNano() - now
fmt.Println("sum=", sum)
fmt.Println("diff=", diff)
// fmt PrintIn("slice=", slice)
}
可以看到使用哈希表進行遍歷的話，以上代碼運行的結果為：
sum= 1000000000000
diff= 29297200
成功: 進程退出代碼 0.
而對比使用切片遍歷的代碼如下：
package main
import (
"fmt"
"time"
)
func main() {
//testmap := make(map[int]int)
len := 1000000
tests1ice := make([]int, len, len)
for i := 0; i < len; i++ {
tests1ice[i] = i + 1
}
sum := 0
now := time.Now().UnixNano()
for k, v := range tests1ice {
sum = sum + k + v
}
diff := time.Now().UnixNano() - now
fmt.Println("sum=", sum)
fmt.Println("diff=", diff)
// fmt PrintIn("slice=", slice)
}
以上代碼運行結果為：
sum= 1000000000000
diff= 1953900
成功: 進程退出代碼 0.
可以看到同樣長度的集合遍歷性能表現，切片的耗時只有哈希表的5%左右，兩者幾乎相差兩個數量級。
數據訪問局部性原理的制約：局部性原理可能是計算機基本原理中威力最強的基本定理之一，也是程序員在編程過程中必須要考慮的規律，因此我們看到在計算機世界中局部性原理，經常在速度不匹配的存儲介質中得到運用，比如英特爾的CPU往往分為三級高速緩存，彼此之間的速度差距大概在8到10倍之間，其中高速緩存中的第三級緩存又比內存快10倍，這樣彼此之間各差10倍左右的緩存體系加速效果最好，這就像軍事行動中，先鋒部隊既要率先行動，又不能與大部隊過於脫節，才能圓滿的完成任務。在實際CPU的工作當中，如果數據單元A1被訪問了，那麼A1的鄰居A0和A2被訪問到的可能性也會極大的增加，因此CPU一般都會在數據單元A1被訪問的同時，將他的鄰居們調入高速緩存。
也就是說切片這種在內存當中連續分佈的數據結構，其元素都是以高速緩存行的大小為單位讀入到高速緩存的，而高速緩存的平均速度又是內存的幾十倍，因此相當於一次讀取操作，就能快速處理好幾個元素；但由於哈希表實際也是稀疏表，一個鍵值對的周圍可能沒有其它有效鍵值對，因此哈希表在遍歷時實際上只能一個一個元素的處理。這樣比較下來哈希表在單個元素的訪問上快，但在整體遍歷上慢也就不足為奇了。
在元素不多不要用哈希表！我經常看到有不少程序員在元素不多的情況下，還堅持使用哈希表來建立key-value的對應關係，其實這樣的做法並不會帶來效率的提升，正如我們剛剛所說，哈希算法也被稱為散列算法，鍵值對的內存地址分佈很可能並不連續，這就特別不方便局部性原理發揮作用。剛剛我們上文也提到了內存緩存行的大小通常是64byte，在實際測試過程中可以看到如果元素能在一個內存緩存行存儲下來，就不要用哈希表了，這時候用數據切片，每次遍歷查找的性能反而比哈希表更快。具體代碼如下：
哈希表實現示例
package main
import (
"fmt"
"time"
)
func main() {
testmap := make(map[int]int)
len := 10
times := 100000
//tests1ice := make([]int, len, len)
for i := 0; i < len; i++ {
testmap[i] = i + 1
}
sum := 0
now := time.Now().UnixNano()
for i := 0; i < times; i++ {
//for k, v := range testmap {
//if i%len == v {
sum = sum + i%len + testmap[i%len]
//break
//}
//}
//sum = sum + k + v
//tests1ice[i%len] = i + 1
}
diff := time.Now().UnixNano() - now
fmt.Println("sum=", sum)
fmt.Println("diff=", diff)
// fmt PrintIn("slice=", slice)
}
以上代碼結果如下：
sum= 1000000
diff= 2929500
而切片遍歷查找的實現如下：
package main
import (
"fmt"
"time"
)
func main() {
//testmap := make(map[int]int)
len := 10
times := 100000
tests1ice := make([]int, len, len)
for i := 0; i < len; i++ {
tests1ice[i] = i + 1
}
sum := 0
now := time.Now().UnixNano()
for i := 0; i < times; i++ {
for k, v := range tests1ice {
if i%len == k {
sum = sum + k + v
break
}
}
//sum = sum + k + v
//tests1ice[i%len] = i + 1
}
diff := time.Now().UnixNano() - now
fmt.Println("sum=", sum)
fmt.Println("diff=", diff)
// fmt PrintIn("slice=", slice)
}
sum= 810000
diff= 1953000
成功: 進程退出代碼 0.
少元素方面集合的元素定位性能上，哈希表比切片慢了40%，當然這也是局部性原理造成的，由於元素比較少，因此切片這樣內存連續數據結構，完全可以在高速緩存中完成數據的查找定位，這樣綜合下來其性能反而還要比哈希表要快。
正如前文所述，哈希算法的工作機制本身就決定了哈希表對存儲空間就有一定的浪費，因此在沒有性能優勢的情況下，尤其是上述遍歷及短表的場景下，就不要再用哈希表了，完全沒有必要。
哈希表的實現機制要點
在筆者看了部分哈希表的代碼之後，Java、Go和Rust這三種語言有一些相同的機制，也有一些不同，其中有兩點值得關注，當然由於水平有限，如有錯誤之處敬請指正。
避免使用連續內存塊：我們知道在內存、硬盤等存儲設備的管理中，連續的空間往往是比較寶貴的，而哈希表是相對比較稀疏的數據結構，因此Java、Go和Rust基本都引用了一些比如桶的機制，儘量避免佔用連續的內存塊。以Go語言的實現為例：
type hmap struct {
count int // map的長度
flags uint8
B uint8 // map中的bucket的數量，
noverflow uint16 //
hash0 uint32 // hash 種子
buckets unsafe.Pointer // 指向桶的指針
oldbuckets unsafe.Pointer // 指向舊桶的指針，這裡用於溢出
nevacuate uintptr
extra *mapextra // optional fields
}
// 在桶溢出的時候會用到extra
type mapextra struct {
overflow *[]*bmap
oldoverflow *[]*bmap
nextOverflow *bmap
}
type bmap struct {
tophash [bucketCnt]uint8// Map中的哈希值的高8位為桶的地址
}
在訪問Map中的鍵值對時，需要先計算key的哈希值，其中哈希的值的低8位定位到具體的桶（bucket），通過高8位在桶內定位到具體的位置，而不同桶之間所佔用的內存區域也不需要是連續的空間，這樣也就從一定程度上彌補哈希表佔用空間較大的缺點。
哈希碰撞處理：我們剛剛也介紹了哈希表碰撞的內容，也就是出現了不同的鍵值對要存儲在同一個內存槽位的場景，極端情況下是所有鍵值對全部發生碰撞，這樣哈希表實際也就退化成了鏈表，Java對碰撞的處理相對比較成熟，如果退化的鏈表長度大於8，那麼Java會選擇用紅黑樹這種近似於二叉排序樹的數據結構進行替代，從而保證定位性能不低於O(logn)
而如果鏈表的長度小於等於8，那麼如我們上文介紹，在數據長度比較短的情況下其實鏈表的性能可能還會更好，沒必要使用引入紅黑樹，由此可見Java這門語言的確已經非常成熟。