Golang map 的設計與實現
【導讀】理解 Golang 中 map 的底層實現，對編碼（和麪試）非常有幫助，本文從 Go 語言底層實現開始詳細解讀了 Go map。
Go 中的 map 在底層是用哈希表實現的，你可以在 $GOROOT/src/pkg/runtime/hashmap.goc 找到它的實現。
數據結構
哈希表的數據結構中一些關鍵的域如下所示：
struct Hmap
{
uint8 B; // 可以容納2^B個項
uint16 bucketsize; // 每個桶的大小
byte *buckets; // 2^B個Buckets的數組
byte *oldbuckets; // 前一個buckets，只有當正在擴容時纔不爲空
};上面給出的結構體只是 Hmap 的部分的域。需要注意到的是，這裏直接使用的是 Bucket 的數組，而不是Bucket*指針的數組。這意味着，第一個 Bucket 和後面溢出鏈的 Bucket 分配有些不同。第一個Bucket是用的一段連續的內存空間，而後面溢出鏈的 Bucket 的空間是使用mallocgc分配的。
這個 hash 結構使用的是一個可擴展哈希的算法，由 hash 值 mod 當前 hash 表大小決定某一個值屬於哪個桶，而 hash 表大小是 2 的指數，即上面結構體中的2^B。每次擴容，會增大到上次大小的兩倍。結構體中有一個buckets和一個oldbuckets是用來實現增量擴容的。正常情況下直接使用buckets，而oldbuckets爲空。如果當前哈希表正在擴容中，則oldbuckets不爲空，並且buckets大小是oldbuckets大小的兩倍。
具體的 Bucket 結構如下所示：
struct Bucket
{
uint8 tophash[BUCKETSIZE]; // hash值的高8位....低位從bucket的array定位到bucket
Bucket *overflow; // 溢出桶鏈表，如果有
byte data[1]; // BUCKETSIZE keys followed by BUCKETSIZE values
};其中 BUCKETSIZE 是用宏定義的 8，每個 bucket 中存放最多 8 個 key/value 對, 如果多於 8 個，那麼會申請一個新的 bucket，並將它與之前的 bucket 鏈起來。
按 key 的類型採用相應的 hash 算法得到 key 的hash值。將hash值的低位當作 Hmap 結構體中buckets數組的index，找到 key 所在的bucket。將 hash 的高 8 位存儲在了bucket的tophash中。注意，這裏高 8 位不是用來當作 key/value 在bucket內部的offset的，而是作爲一個主鍵，在查找時對 tophash 數組的每一項進行順序匹配的。先比較 hash 值高位與bucket的tophash是否相等，如果相等則再比較bucket的第 i 個的 key 與所給的 key 是否相等。如果相等，則返回其對應的value，反之，在overflow buckets中按照上述方法繼續尋找。
整個hash的存儲如下圖所示 (臨時先採用了 XX 同學畫的圖，這個圖有點問題)：
圖：HMap 的存儲結構
注意一個細節是 Bucket 中 key/value 的放置順序，是將 keys 放在一起，values 放在一起，爲什麼不將 key 和對應的 value 放在一起呢？如果那麼做，存儲結構將變成 key1/value1/key2/value2… 設想如果是這樣的一個 map[int64]int8，考慮到字節對齊，會浪費很多存儲空間。不得不說通過上述的一個小細節，可以看出 Go 在設計上的深思熟慮。
增量擴容
大家都知道哈希表表就是以空間換時間，訪問速度是直接跟填充因子相關的，所以當哈希表太滿之後就需要進行擴容。
如果擴容前的哈希表大小爲2^B，擴容之後的大小爲2^(B+1)，每次擴容都變爲原來大小的兩倍，哈希表大小始終爲 2 的指數倍，則有(hash mod 2^B)等價於(hash & (2^B-1))。這樣可以簡化運算，避免了取餘操作。
假設擴容之前容量爲 X，擴容之後容量爲 Y，對於某個哈希值 hash，一般情況下(hash mod X)不等於(hash mod Y)，所以擴容之後要重新計算每一項在哈希表中的新位置。當 hash 表擴容之後，需要將那些舊的 pair 重新哈希到新的 table 上 (源代碼中稱之爲 evacuate)， 這個工作並沒有在擴容之後一次性完成，而是逐步的完成（在 insert 和 remove 時每次搬移 1-2 個 pair），Go 語言使用的是增量擴容。
爲什麼會增量擴容呢？主要是縮短 map 容器的響應時間。假如我們直接將 map 用作某個響應實時性要求非常高的 web 應用存儲，如果不採用增量擴容，當 map 裏面存儲的元素很多之後，擴容時系統就會卡住，導致較長一段時間內無法響應請求。不過增量擴容本質上還是將總的擴容時間分攤到了每一次哈希操作上面。
擴容會建立一個大小是原來 2 倍的新的表，將舊的 bucket 搬到新的表中之後，並不會將舊的 bucket 從 oldbucket 中刪除，而是加上一個已刪除的標記。
正是由於這個工作是逐漸完成的，這樣就會導致一部分數據在 old table 中，一部分在 new table 中， 所以對於 hash table 的 insert, remove, lookup 操作的處理邏輯產生影響。只有當所有的 bucket 都從舊錶移到新表之後，纔會將 oldbucket 釋放掉。
擴容的填充因子是多少呢？如果 grow 的太頻繁，會造成空間的利用率很低， 如果很久才 grow，會形成很多的overflow buckets，查找的效率也會下降。這個平衡點如何選取呢 (在 go 中，這個平衡點是有一個宏控制的 (#define LOAD 6.5), 它的意思是這樣的，如果 table 中元素的個數大於 table 中能容納的元素的個數， 那麼就觸發一次 grow 動作。那麼這個 6.5 是怎麼得到的呢？原來這個值來源於作者的一個測試程序，遺憾的是沒能找到相關的源碼，不過作者給出了測試的結果：
LOAD %overflow bytes/entry hitprobe missprobe
4.00 2.13 20.77 3.00 4.00
4.50 4.05 17.30 3.25 4.50
5.00 6.85 14.77 3.50 5.00
5.50 10.55 12.94 3.75 5.50
6.00 15.27 11.67 4.00 6.00
6.50 20.90 10.79 4.25 6.50
7.00 27.14 10.15 4.50 7.00
7.50 34.03 9.73 4.75 7.50
8.00 41.10 9.40 5.00 8.00
%overflow = percentage of buckets which have an overflow bucket
bytes/entry = overhead bytes used per key/value pair
hitprobe = # of entries to check when looking up a present key
missprobe = # of entries to check when looking up an absent key可以看出作者取了一個相對適中的值。
查找過程
-
根據 key 計算出 hash 值。
-
如果存在
old table, 首先在old table中查找，如果找到的bucket已經evacuated，轉到步驟 3。反之，返回其對應的 value。 -
在
new table中查找對應的 value。
這裏一個細節需要注意一下。不認真看可能會以爲低位用於定位 bucket 在數組的 index，那麼高位就是用於 key/valule 在 bucket 內部的offset。事實上高 8 位不是用作offset的，而是用於加快 key 的比較的。
do { //對每個桶b
//依次比較桶內的每一項存放的tophash與所求的hash值高位是否相等
for(i = 0, k = b->data, v = k + h->keysize * BUCKETSIZE; i < BUCKETSIZE; i++, k += h->keysize, v += h->valuesize) {
if(b->tophash[i] == top) {
k2 = IK(h, k);
t->key->alg->equal(&eq, t->key->size, key, k2);
if(eq) { //相等的情況下再去做key比較...
*keyp = k2;
return IV(h, v);
}
}
}
b = b->overflow; //b設置爲它的下一下溢出鏈
} while(b != nil);插入過程分析
-
根據 key 算出 hash 值，進而得出對應的 bucket。
-
如果 bucket 在 old table 中，將其重新散列到 new table 中。
-
在 bucket 中，查找空閒的位置，如果已經存在需要插入的 key，更新其對應的 value。
-
根據 table 中元素的個數，判斷是否 grow table。
-
如果對應的 bucket 已經 full，重新申請新的 bucket 作爲
overbucket。 -
將 key/value pair 插入到 bucket 中。
這裏也有幾個細節需要注意一下。
在擴容過程中，oldbucket是被凍結的，查找時會在 oldbucket 中查找，但不會在oldbucket中插入數據。如果在oldbucket是找到了相應的 key，做法是將它遷移到新 bucket 後加入evalucated標記。並且還會額外的遷移另一個pair。
然後就是隻要在某個 bucket 中找到第一個空位，就會將 key/value 插入到這個位置。也就是位置位於 bucket 前面的會覆蓋後面的 (類似於存儲系統設計中做刪除時的常用的技巧之一，直接用新數據追加方式寫，新版本數據覆蓋老版本數據)。找到了相同的 key 或者找到第一個空位就可以結束遍歷了。不過這也意味着做刪除時必須完全的遍歷 bucket 所有溢出鏈，將所有的相同 key 數據都刪除。所以目前 map 的設計是爲插入而優化的，刪除效率會比插入低一些。
map 設計中的性能優化
讀完 map 源代碼發現作者還是做了很多設計上的選擇的。本人水平有限，談不上優劣的點評，這裏只是拿出來與讀者分享。
HMap 中是 Bucket 的數組，而不是 Bucket 指針的數組。好的方面是可以一次分配較大內存，減少了分配次數，避免多次調用mallocgc。但相應的缺點，其一是可擴展哈希的算法並沒有發生作用，擴容時會造成對整個數組的值拷貝 (如果實現上用 Bucket 指針的數組就是指針拷貝了，代價小很多)。其二是首個 bucket 與後面產生了不一致性。這個會使刪除邏輯變得複雜一點。比如刪除後面的溢出鏈可以直接刪除，而對於首個bucket，要等到evalucated完畢後，整個oldbucket刪除時進行。
沒有重用設freelist重用刪除的結點。作者把這個加了一個 TODO 的註釋，不過想了一下覺得這個做的意義不大。因爲一方面，bucket大小並不一致，重用比較麻煩。另一方面，下層存儲已經做過內存池的實現了，所以這裏不做重用也會在內存分配那一層被重用的，
bucket直接 key/value 和間接 key/value 優化。這個優化做得蠻好的。注意看代碼會發現，如果 key 或 value 小於 128 字節，則它們的值是直接使用的bucket作爲存儲的。否則bucket中存儲的是指向實際 key/value 數據的指針，
bucket存 8 個 key/value 對。查找時進行順序比較。第一次發現高位居然不是用作offset，而是用於加快比較的。定位到bucket之後，居然是一個順序比較的查找過程。後面仔細想了想，覺得還行。由於bucket只有 8 個，順序比較下來也不算過分。仍然是 O(1) 只不過前面係數大一點點罷了。相當於 hash 到一個小範圍之後，在這個小範圍內順序查找。
插入刪除的優化。前面已經提過了，插入只要找到相同的 key 或者第一個空位，bucket中如果存在一個以上的相同 key，前面覆蓋後面的 (只是如果，實際上不會發生)。而刪除就需要遍歷完所有bucket溢出鏈了。這樣 map 的設計就是爲插入優化的。考慮到一般的應用場景，這個應該算是很合理的。
作者還列了另個 2 個 TODO：將多個幾乎要 empty 的bucket合併；如果 table 中元素很少，考慮shrink table。(畢竟現在的實現只是單純的 grow)。
轉自：
tiancaiamao.gitbooks.io/go-internals/content/zh/02.3.html
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Gk5IKN70QsshGOzUmJCdRw