在開發(fā)過程中璧眠，map是必不可少的數(shù)據(jù)結(jié)構(gòu)，在Golang中迈螟，使用map或多或少會遇到與其他語言不一樣的體驗海渊，比如訪問不存在的元素會返回其類型的空值、map的大小究竟是多少勤婚，為什么會報"cannot take the address of"錯誤摹量，遍歷map的隨機性等等。
本文希望通過研究map的底層實現(xiàn)，以解答這些疑惑缨称。
基于Golang 1.8.3
1. 數(shù)據(jù)結(jié)構(gòu)及內(nèi)存管理
hashmap的定義位于 src/runtime/hashmap.go 中凝果，首先我們看下hashmap和bucket的定義：
type hmap struct {
count int // 元素的個數(shù)
flags uint8 // 狀態(tài)標志
B uint8 // 可以最多容納 6.5 * 2 ^ B 個元素，6.5為裝載因子
noverflow uint16 // 溢出的個數(shù)
hash0 uint32 // 哈希種子
buckets unsafe.Pointer // 桶的地址
oldbuckets unsafe.Pointer // 舊桶的地址睦尽，用于擴容
nevacuate uintptr // 搬遷進度器净，小于nevacuate的已經(jīng)搬遷
overflow *[2]*[]*bmap
}
其中，overflow是一個指針当凡，指向一個元素個數(shù)為2的數(shù)組山害，數(shù)組的類型是一個指針，指向一個slice沿量，slice的元素是桶(bmap)的地址浪慌，這些桶都是溢出桶；為什么有兩個朴则？因為Go map在hash沖突過多時权纤，會發(fā)生擴容操作，為了不全量搬遷數(shù)據(jù)乌妒，使用了增量搬遷汹想，[0]表示當前使用的溢出桶集合，[1]是在發(fā)生擴容時撤蚊，保存了舊的溢出桶集合古掏；overflow存在的意義在于防止溢出桶被gc。
// A bucket for a Go map.
type bmap struct {
// 每個元素hash值的高8位拴魄，如果tophash[0] < minTopHash冗茸，表示這個桶的搬遷狀態(tài)
tophash [bucketCnt]uint8
// 接下來是8個key席镀、8個value匹中，但是我們不能直接看到；為了優(yōu)化對齊豪诲，go采用了key放在一起顶捷，value放在一起的存儲方式，
// 再接下來是hash沖突發(fā)生時屎篱，下一個溢出桶的地址
}
tophash的存在是為了快速試錯服赎，畢竟只有8位，比較起來會快一點交播。
從定義可以看出重虑，不同于STL中map以紅黑樹實現(xiàn)的方式，Golang采用了HashTable的實現(xiàn)秦士，解決沖突采用的是鏈地址法缺厉。也就是說，使用數(shù)組+鏈表來實現(xiàn)map。特別的提针，對于一個key命爬，幾個比較重要的計算公式為:
| key | hash | hashtop | bucket index |
|---|---|---|---|
| key | hash := alg.hash(key, uintptr(h.hash0)) | top := uint8(hash >> (sys.PtrSize*8 - 8)) | bucket := hash & (uintptr(1)<<h.B - 1)，即 hash % 2^B |
例如辐脖，對于B = 3饲宛，當hash(key) = 4時， hashtop = 0嗜价， bucket = 4艇抠，當hash(key) = 20時，hashtop = 0久锥， bucket = 4练链；這個例子我們在搬遷過程還會用到。
內(nèi)存布局類似于這樣：
2. 創(chuàng)建 - makemap
map的創(chuàng)建比較簡單奴拦，在參數(shù)校驗之后媒鼓，需要找到合適的B來申請桶的內(nèi)存空間，接著便是穿件hmap這個結(jié)構(gòu)错妖，以及對它的初始化绿鸣。
3. 訪問 - mapaccess
對于給定的一個key，可以通過下面的操作找到它是否存在
方法定義為
// returns key, if not find, returns nil
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
// returns key and exist. if not find, returns nil, false
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)
// returns both key and value. if not find, returns nil, nil
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer)
可見在找不到對應(yīng)key的情況下暂氯，會返回nil
4. 分配 - mapassign
為一個key分配空間的邏輯潮模，大致與查找類似；但增加了寫保護和擴容的操作痴施；注意擎厢，分配過程和刪除過程都沒有在oldbuckets中查找，這是因為首先要進行擴容判斷和操作辣吃；如下：
擴容是整個hashmap的核心算法动遭，我們放在第6部分重點研究。
新建一個溢出桶神得，并將其拼接在當前桶的尾部厘惦，實現(xiàn)了類似鏈表的操作：
// 獲取當前桶的溢出桶
func (b *bmap) overflow(t *maptype) *bmap {
return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize))
}
// 設(shè)置當前桶的溢出桶
func (h *hmap) setoverflow(t *maptype, b, ovf *bmap) {
h.incrnoverflow()
if t.bucket.kind&kindNoPointers != 0 {
h.createOverflow()
//重點，這里講溢出桶append到overflow[0]的后面
*h.overflow[0] = append(*h.overflow[0], ovf)
}
*(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf
}
5. 刪除 - mapdelete
刪除某個key的操作與分配類似哩簿，由于hashmap的存儲結(jié)構(gòu)是數(shù)組+鏈表宵蕉，所以真正刪除key僅僅是將對應(yīng)的slot設(shè)置為empty，并沒有減少內(nèi)存节榜；如下：
6. 擴容 - growWork
首先羡玛，判斷是否需要擴容的邏輯是
func (h *hmap) growing() bool {
return h.oldbuckets != nil
}
何時h.oldbuckets不為nil呢？在分配assign邏輯中宗苍，當沒有位置給key使用稼稿，而且滿足測試條件(裝載因子>6.5或有太多溢出通)時亿遂，會觸發(fā)hashGrow邏輯：
func hashGrow(t *maptype, h *hmap) {
//判斷是否需要sameSizeGrow，否則"真"擴
bigger := uint8(1)
if !overLoadFactor(int64(h.count), h.B) {
bigger = 0
h.flags |= sameSizeGrow
}
// 下面將buckets復(fù)制給oldbuckets
oldbuckets := h.buckets
newbuckets := newarray(t.bucket, 1<<(h.B+bigger))
flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
flags |= oldIterator
}
// 更新hmap的變量
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets
h.buckets = newbuckets
h.nevacuate = 0
h.noverflow = 0
// 設(shè)置溢出桶
if h.overflow != nil {
if h.overflow[1] != nil {
throw("overflow is not nil")
}
// 交換溢出桶
h.overflow[1] = h.overflow[0]
h.overflow[0] = nil
}
}
OK渺杉，下面正式進入重點蛇数，擴容階段；在assign和delete操作中是越，都會觸發(fā)擴容growWork：
func growWork(t *maptype, h *hmap, bucket uintptr) {
// 搬遷舊桶耳舅，這樣assign和delete都直接在新桶集合中進行
evacuate(t, h, bucket&h.oldbucketmask())
//再搬遷一次搬遷過程中的桶
if h.growing() {
evacuate(t, h, h.nevacuate)
}
}
6.1 搬遷過程
一般來說，新桶數(shù)組大小是原來的2倍(在!sameSizeGrow()條件下)倚评，新桶數(shù)組前半段可以"類比"為舊桶浦徊，對于一個key，搬遷后落入哪一個索引中呢天梧？
假設(shè)舊桶數(shù)組大小為2^B盔性， 新桶數(shù)組大小為2*2^B，對于某個hash值X
若 X & (2^B) == 0呢岗，說明 X < 2^B冕香，那么它將落入與舊桶集合相同的索引xi中；
否則后豫，它將落入xi + 2^B中悉尾。
例如，對于舊B = 3時挫酿，hash1 = 4构眯，hash2 = 20，其搬遷結(jié)果類似這樣早龟。
源碼中有些變量的命名比較簡單惫霸，容易擾亂思路，我們注明一下便于理解葱弟。
| 變量 | 釋義 |
|---|---|
| x *bmap | 桶x表示與在舊桶時相同的位置壹店，即位于新桶前半段 |
| y *bmap | 桶y表示與在舊桶時相同的位置+舊桶數(shù)組大小，即位于新桶后半段 |
| xi int | 桶x的slot索引 |
| yi int | 桶y的slot索引 |
| xk unsafe.Pointer | 索引xi對應(yīng)的key地址 |
| yk unsafe.Pointer | 索引yi對應(yīng)的key地址 |
| xv unsafe.Pointer | 索引xi對應(yīng)的value地址 |
| yv unsafe.Pointer | 索引yi對應(yīng)的value地址 |
搬遷過程如下：
總結(jié)
到目前為止翘悉，Golang的map實現(xiàn)細節(jié)已經(jīng)分析完畢茫打，但不包含迭代器相關(guān)操作居触。通過分析妖混，我們了解了map是由數(shù)組+鏈表實現(xiàn)的HashTable，其大小和B息息相關(guān)轮洋，同時也了解了map的創(chuàng)建制市、查詢、分配弊予、刪除以及擴容搬遷原理祥楣。總的來說，Golang通過hashtop快速試錯加快了查找過程误褪，利用空間換時間的思想解決了擴容的問題责鳍，利用將8個key(8個value)依次放置減少了padding空間等等。
