Map實(shí)踐以及實(shí)現(xiàn)原理

使用實(shí)例內(nèi)存模型創(chuàng)建maphash函數(shù)key定位和碰撞解決擴(kuò)容元素訪問刪除迭代核心點(diǎn)：

使用實(shí)例

測(cè)試的主要目的是對(duì)于map，當(dāng)作為函數(shù)傳參時(shí)候，函數(shù)內(nèi)部的改變會(huì)不會(huì)透?jìng)鞯酵獠?，以及函?shù)傳參內(nèi)外是不是一個(gè)map，也就是傳遞的是實(shí)例還是指針。(golang里面的傳參都是值傳遞)。

Test Case1：傳參為map。

func main(){
	fmt.Println("--------------- m ---------------")
	m := make(map[string]string)
	m["1"] = "0"
	fmt.Printf("m outer address %p, m=%v \n", m, m)
	passMap(m)
	fmt.Printf("post m outer address %p, m=%v \n", m, m)
}
func passMap(m map[string]string) {
	fmt.Printf("m inner address %p \n", m)
	m["11111111"] = "11111111"
	fmt.Printf("post m inner address %p \n", m)
}

運(yùn)行結(jié)果是：

--------------- m ---------------
m outer address 0xc0000b0000, m=map[1:0] 
m inner address 0xc0000b0000 
post m inner address 0xc0000b0000 
post m outer address 0xc0000b0000, m=map[1:0 11111111:11111111] 

從運(yùn)行結(jié)果我們可以知道：

當(dāng)傳參為map的時(shí)候，其實(shí)傳遞的是指針地址。函數(shù)內(nèi)外map的地址都是一樣的。函數(shù)內(nèi)部的改變會(huì)透?jìng)鞯胶瘮?shù)外部。

Test Case2：Test Case1的實(shí)現(xiàn)其實(shí)也有個(gè)特殊使用例子，也就是當(dāng)函數(shù)入?yún)ap沒有初始化的時(shí)候。

func main(){
	fmt.Println("--------------- m2 ---------------")
	var m2 map[string]string//未初始化
	fmt.Printf("m2 outer address %p, m=%v \n", m2, m2)
	passMapNotInit(m2)
	fmt.Printf("post m2 outer address %p, m=%v \n", m2, m2)
}
func passMapNotInit(m map[string]string)  {
	fmt.Printf("inner: %v, %p\n",m, m)
	m = make(map[string]string, 0)
	m["a"]="11"
	fmt.Printf("inner: %v, %p\n",m, m)
}

運(yùn)行結(jié)果是：

--------------- m2 ---------------
m2 outer address 0x0, m=map[] 
inner: map[], 0x0
inner: map[a:11], 0xc0000ac120
post m2 outer address 0x0, m=map[] 

從結(jié)果可以看出，當(dāng)入?yún)ap沒有初始化的時(shí)候，就不一樣了：

• 沒有初始化的map地址都是0；
• 函數(shù)內(nèi)部初始化map不會(huì)透?jìng)鞯酵獠縨ap。

其實(shí)也好理解，因?yàn)閙ap沒有初始化，所以map的地址傳遞到函數(shù)內(nèi)部之后初始化，會(huì)改變map的地址，但是外部地址不會(huì)改變。有一種方法，return 新建的map。

內(nèi)存模型

我這邊的源碼版本是：go 1.13

Golang的map從high level的角度來看，采用的是哈希表，并使用鏈表查找法解決沖突。但是golang的map實(shí)現(xiàn)在鏈表解決沖突時(shí)候有很多優(yōu)化，具體我們?cè)诤竺婵醇?xì)節(jié)。

數(shù)據(jù)結(jié)構(gòu)最能說明原理，我們先看map的數(shù)據(jù)結(jié)構(gòu)：

// A header for a Go map.
type hmap struct {
	//map 中的元素個(gè)數(shù)，必須放在 struct 的第一個(gè)位置，因?yàn)閮?nèi)置的 len 函數(shù)會(huì)通過unsafe.Pointer會(huì)從這里讀取
	count     int 
	flags     uint8
	// bucket的數(shù)量是2^B, 最多可以放 loadFactor * 2^B 個(gè)元素，再多就要 hashGrow 了
	B         uint8
	//overflow 的 bucket 近似數(shù)
	noverflow uint16
	hash0     uint32 // hash seed
	//2^B 大小的數(shù)組，如果 count == 0 的話，可能是 nil
	buckets    unsafe.Pointer 
	// 擴(kuò)容的時(shí)候，buckets 長(zhǎng)度會(huì)是 oldbuckets 的兩倍,只有在 growing 時(shí)候?yàn)榭铡?
	oldbuckets unsafe.Pointer
	// 指示擴(kuò)容進(jìn)度，小于此地址的 buckets 遷移完成
	nevacuate  uintptr // progress counter for evacuation (buckets less than this have been evacuated)
	// 當(dāng) key 和 value 都可以 inline 的時(shí)候，就會(huì)用這個(gè)字段
	extra *mapextra // optional fields 
}

這里B是map的bucket數(shù)組長(zhǎng)度的對(duì)數(shù)，每個(gè)bucket里面存儲(chǔ)了kv對(duì)。buckets是一個(gè)指針，指向?qū)嶋H存儲(chǔ)的bucket數(shù)組的首地址。 bucket的結(jié)構(gòu)體如下：

type bmap struct {
	// tophash generally contains the top byte of the hash value
	// for each key in this bucket. If tophash[0] < minTopHash,
	// tophash[0] is a bucket evacuation state instead.
	tophash [bucketCnt]uint8
	// Followed by bucketCnt keys and then bucketCnt elems.
	// NOTE: packing all the keys together and then all the elems together makes the
	// code a bit more complicated than alternating key/elem/key/elem/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
}

上面這個(gè)數(shù)據(jù)結(jié)構(gòu)并不是 golang runtime 時(shí)的結(jié)構(gòu)，在編譯時(shí)候編譯器會(huì)給它動(dòng)態(tài)創(chuàng)建一個(gè)新的結(jié)構(gòu)，如下：

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

bmap 就是我們常說的“bucket”結(jié)構(gòu)，每個(gè) bucket 里面最多存儲(chǔ) 8 個(gè) key，這些 key 之所以會(huì)落入同一個(gè)桶，是因?yàn)樗鼈兘?jīng)過哈希計(jì)算后，哈希結(jié)果是“一類”的。在桶內(nèi)，又會(huì)根據(jù) key 計(jì)算出來的 hash 值的高 8 位來決定 key 到底落入桶內(nèi)的哪個(gè)位置（一個(gè)桶內(nèi)最多有8個(gè)位置）。

這里引用網(wǎng)絡(luò)上的一張圖：

當(dāng) map 的 key 和 value 都不是指針，并且 size 都小于 128 字節(jié)的情況下，會(huì)把 bmap 標(biāo)記為不含指針，這樣可以避免 gc 時(shí)掃描整個(gè) hmap。但是，我們看 bmap 其實(shí)有一個(gè) overflow 的字段，是指針類型的，破壞了 bmap 不含指針的設(shè)想，這時(shí)會(huì)把 overflow 移動(dòng)到 extra 字段來。

// mapextra holds fields that are not present on all maps.
type mapextra struct {
	// If both key and elem do not contain pointers and are inline, then we mark bucket
	// type as containing no pointers. This avoids scanning such maps.
	// However, bmap.overflow is a pointer. In order to keep overflow buckets
	// alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
	// overflow and oldoverflow are only used if key and elem do not contain pointers.
	// overflow contains overflow buckets for hmap.buckets.
	// oldoverflow contains overflow buckets for hmap.oldbuckets.
	// The indirection allows to store a pointer to the slice in hiter.
	overflow    *[]*bmap
	oldoverflow *[]*bmap

	// nextOverflow holds a pointer to a free overflow bucket.
	nextOverflow *bmap
}

bmap 是存放 k-v 的地方，我們看看bmap詳細(xì)的存儲(chǔ)分布細(xì)節(jié)：

上圖就是 bucket 的內(nèi)存模型，HOB Hash 指的就是 top hash字段。我們可以看到bucket的kv分布分開的，沒有按照我們常規(guī)的kv/kv/kv…這種。源碼里說明這樣的好處是在某些情況下可以省略掉 padding 字段，節(jié)省內(nèi)存空間。

比如： map[int64]int8

如果按照 key/value/key/value/… 這樣的模式存儲(chǔ)，那在每一個(gè) key/value pair 之后都要額外 padding 7 個(gè)字節(jié)；而將所有的 key，value 分別綁定到一起，這種形式 key/key/…/value/value/…，則只需要在最后添加 padding。

每個(gè) bucket 設(shè)計(jì)成最多只能放 8 個(gè) key-value 對(duì)，如果有第 9 個(gè) key-value 落入當(dāng)前的 bucket，那就需要再構(gòu)建一個(gè) bucket ，通過 overflow 指針連接起來。

創(chuàng)建map

map的創(chuàng)建非常簡(jiǎn)單，比如下面的語句：

m := make(map[string]string)
// 指定 map 長(zhǎng)度
m := make(map[string]string, 10)

make函數(shù)實(shí)際上會(huì)被編譯器定位到調(diào)用 runtime.makemap()，主要做的工作就是初始化 hmap 結(jié)構(gòu)體的各種字段，例如計(jì)算 B 的大小，設(shè)置哈希種子 hash0 等等。

// 這里的hint就是我們 make 時(shí)候后面指定的初始化長(zhǎng)度.
func makemap(t *maptype, hint int, h *hmap) *hmap {
	//......省略各種檢查的邏輯
	
	// 找到一個(gè) B，使得 map 的裝載因子在正常范圍內(nèi)。
	B := uint8(0)
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B

	// 初始化 hash table
	// 如果 B 等于 0，那么 buckets 就會(huì)在賦值的時(shí)候再分配
	// 如果長(zhǎng)度比較大，分配內(nèi)存會(huì)花費(fèi)長(zhǎng)一點(diǎn)
	if h.B != 0 {
		var nextOverflow *bmap
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		if nextOverflow != nil {
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

注意，這個(gè)函數(shù)返回的結(jié)果：*hmap 是一個(gè)指針，而我們之前講過的 makeslice 函數(shù)返回的是 Slice 結(jié)構(gòu)體對(duì)象。這也是 makemap 和 makeslice 返回值的區(qū)別所帶來一個(gè)不同點(diǎn)：當(dāng) map 和 slice 作為函數(shù)參數(shù)時(shí)，在函數(shù)參數(shù)內(nèi)部對(duì) map 的操作會(huì)影響 map 自身；而對(duì) slice 卻不會(huì)（之前講 slice 的文章里有講過）。

主要原因：一個(gè)是指針（*hmap），一個(gè)是結(jié)構(gòu)體（slice）。Go 語言中的函數(shù)傳參都是值傳遞，在函數(shù)內(nèi)部，參數(shù)會(huì)被 copy 到本地。*hmap指針 copy 完之后，仍然指向同一個(gè) map，因此函數(shù)內(nèi)部對(duì) map 的操作會(huì)影響實(shí)參。而 slice 被 copy 后，會(huì)成為一個(gè)新的 slice，對(duì)它進(jìn)行的操作不會(huì)影響到實(shí)參。

hash函數(shù)

關(guān)于hash函數(shù)的細(xì)節(jié)，這里就不介紹了。這里需要重點(diǎn)提示的是，哈希函數(shù)的算法與key的類型一一對(duì)應(yīng)的。根據(jù) key 的類型， maptype結(jié)構(gòu)體的 key字段的alg 字段會(huì)被設(shè)置對(duì)應(yīng)類型的 hash 和 equal 函數(shù)。

key定位和碰撞解決

對(duì)于 hashmap 來說，最重要的就是根據(jù)key定位實(shí)際存儲(chǔ)位置。key 經(jīng)過哈希計(jì)算后得到哈希值，哈希值是 64 個(gè) bit 位（針對(duì)64位機(jī)）。根據(jù)hash值的最后B個(gè)bit位來確定這個(gè)key落在哪個(gè)桶。如果 B = 5，那么桶的數(shù)量，也就是 buckets 數(shù)組的長(zhǎng)度是 2^5 = 32。

suppose，現(xiàn)在有一個(gè) key 經(jīng)過哈希函數(shù)計(jì)算后，得到的哈希結(jié)果是：

10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

用最后的 5 個(gè) bit 位，也就是 01010，值為 10，也就是 10 號(hào)桶。這個(gè)操作實(shí)際上就是取余操作，但是取余開銷太大，所以代碼實(shí)現(xiàn)上用的位操作代替。

再用哈希值的高 8 位，找到此 key 在 bucket 中的位置，這是在尋找已有的 key。最開始桶內(nèi)還沒有 key，新加入的 key 會(huì)找到第一個(gè)空位，放入。

buckets 編號(hào)就是桶編號(hào)，當(dāng)兩個(gè)不同的 key 落在同一個(gè)桶中，也就是發(fā)生了哈希沖突。沖突的解決手段是用鏈表法：在 bucket 中，從前往后找到第一個(gè)空位。這樣，在查找某個(gè) key 時(shí)，先找到對(duì)應(yīng)的桶，再去遍歷 bucket 中的 key。

下面是檢索的示意圖：

上圖中，假定 B = 5，所以 bucket 總數(shù)就是 2^5 = 32。首先計(jì)算出待查找 key 的哈希，使用低 5 位 00110，找到對(duì)應(yīng)的 6 號(hào) bucket，使用高 8 位 10010111，對(duì)應(yīng)十進(jìn)制 151，在 6 號(hào) bucket 中 遍歷bucket 尋找 tophash 值（HOB hash）為 151 的 key，找到了 2 號(hào)槽位，這樣整個(gè)查找過程就結(jié)束了。

如果在 bucket 中沒找到，并且 overflow 不為空，還要繼續(xù)去 overflow bucket 中尋找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。(這里需要遍歷bucket數(shù)組中某個(gè)槽位的bucket鏈表的所有bucket)

下面我們通過源碼驗(yàn)證：

// mapaccess1 returns a pointer to h[key].  Never returns nil, instead
// it will return a reference to the zero object for the elem type if
// the key is not in the map.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	//......校驗(yàn)邏輯
	
	//如果 h 什么都沒有，返回value類型的零值
	if h == nil || h.count == 0 {
		if t.hashMightPanic() {
			t.key.alg.hash(key, 0) // see issue 23734
		}
		return unsafe.Pointer(&zeroVal[0])
	}
	
	// 并發(fā)寫沖突
	if h.flags&hashWriting != 0 {
		throw("concurrent map read and map write")
	}
	// 不同類型 key 使用的 hash 算法在編譯期確定
	alg := t.key.alg
	hash := alg.hash(key, uintptr(h.hash0))
	
	// 求低 B 位的掩碼.
	// 比如 B=5，那 m 就是31，低五位二進(jìn)制是全1
	m := bucketMask(h.B)
	// b 就是 當(dāng)前key對(duì)應(yīng)的 bucket 的地址
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	// oldbuckets 不為 nil，說明發(fā)生了擴(kuò)容
	if c := h.oldbuckets; c != nil {
		if !h.sameSizeGrow() {
			// There used to be half as many buckets; mask down one more power of two.
			m >>= 1
		}
		// 求出 key 在老的 map 中的 bucket 位置
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
		// 如果 oldb 沒有搬遷到新的 bucket
		// 那就在老的 bucket 中尋找
		if !evacuated(oldb) {
			b = oldb
		}
	}
	// 計(jì)算出高 8 位的 hash
	// 相當(dāng)于右移 56 位，只取高8位
	top := tophash(hash)

// 這里進(jìn)入bucket的二層循環(huán)找到對(duì)應(yīng)的kv(第一層是bucket,第二層是bucket內(nèi)部的8個(gè)slot)
bucketloop:
	// 遍歷bucket以及overflow鏈表
	for ; b != nil; b = b.overflow(t) {
		//遍歷bucket的8個(gè)slot
		for i := uintptr(0); i < bucketCnt; i++ {
			// tophash 不匹配
			if b.tophash[i] != top {
				// 標(biāo)識(shí)當(dāng)前bucket剩下的slot都是empty
				if b.tophash[i] == emptyRest {
					break bucketloop
				}
				continue
			}
			// 獲取bucket的key
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			if alg.equal(key, k) {
				//定位到 value 的位置
				e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				// value 解引用
				if t.indirectelem() {
					e = *((*unsafe.Pointer)(e))
				}
				return e
			}
		}
	}
	// overflow bucket 也找完了，說明沒有目標(biāo) key
	// 返回零值
	return unsafe.Pointer(&zeroVal[0])
}

函數(shù)返回 h[key] 的指針，如果 h 中沒有此 key，那就會(huì)返回一個(gè) key 相應(yīng)類型的零值，不會(huì)返回 nil。

代碼整體比較直接，沒什么難懂的地方。跟著上面的注釋一步步理解就好了。

這里，說一下定位 key 和 value 的方法以及整個(gè)循環(huán)的寫法。

// key 定位公式
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))

// value 定位公式
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))

b 是 bmap 的地址，這里 bmap 還是源碼里定義的結(jié)構(gòu)體，只包含一個(gè) tophash 數(shù)組，經(jīng)編譯器擴(kuò)充之后的結(jié)構(gòu)體才包含 key，value，overflow 這些字段。dataOffset 是 key 相對(duì)于 bmap 起始地址的偏移：

dataOffset = unsafe.Offsetof(struct {
		b bmap
		v int64
	}{}.v)

因此 bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset。第 i 個(gè) key 的地址就要在此基礎(chǔ)上跨過 i 個(gè) key 的大??；而我們又知道，value 的地址是在所有 key 之后，因此第 i 個(gè) value 的地址還需要加上所有 key 的偏移。理解了這些，上面 key 和 value 的定位公式就很好理解了。

當(dāng)定位到一個(gè)具體的 bucket 時(shí)，里層循環(huán)就是遍歷這個(gè) bucket 里所有的 cell，或者說所有的槽位，也就是 bucketCnt=8 個(gè)槽位。整個(gè)循環(huán)過程：

再說一下 minTopHash，當(dāng)一個(gè) cell 的 tophash 值小于 minTopHash 時(shí)，標(biāo)志這個(gè) cell 的遷移狀態(tài)。因?yàn)檫@個(gè)狀態(tài)值是放在 tophash 數(shù)組里，為了和正常的哈希值區(qū)分開，會(huì)給 key 計(jì)算出來的哈希值一個(gè)增量：minTopHash。這樣就能區(qū)分正常的 top hash 值和表示狀態(tài)的哈希值。

下面的這幾種狀態(tài)就表征了 bucket 的情況：

emptyRest      = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows.
emptyOne       = 1 // this cell is empty
// 擴(kuò)容相關(guān)
evacuatedX     = 2 // key/elem is valid.  Entry has been evacuated to first half of larger table.
// 擴(kuò)容相關(guān)
evacuatedY     = 3 // same as above, but evacuated to second half of larger table.
evacuatedEmpty = 4 // cell is empty, bucket is evacuated.
minTopHash     = 5 // minimum tophash for a normal filled cell.

源碼里判斷這個(gè) bucket 是否已經(jīng)搬遷完畢，用到的函數(shù)：

func evacuated(b *bmap) bool {
	h := b.tophash[0]
	return h > emptyOne && h < minTopHash
}

只取了 tophash 數(shù)組的第一個(gè)值，判斷它是否在 1-5 之間。對(duì)比上面的常量，當(dāng) top hash 是 evacuatedEmpty、evacuatedX、evacuatedY 這三個(gè)值之一，說明此 bucket 中的 key 全部被搬遷到了新 bucket。

擴(kuò)容

使用 key 的 hash 值可以快速定位到目標(biāo) key，然而，隨著向 map 中添加的 key 越來越多，key 發(fā)生碰撞的概率也越來越大。bucket 中的 8 個(gè) cell 會(huì)被逐漸塞滿，查找、插入、刪除 key 的效率也會(huì)越來越低。最理想的情況是一個(gè) bucket 只裝一個(gè) key，這樣，就能達(dá)到 O(1) 的效率，但這樣空間消耗太大，用空間換時(shí)間的代價(jià)太高。

Go 語言采用一個(gè) bucket 里裝載 8 個(gè) key，定位到某個(gè) bucket 后，還需要再定位到具體的 key，這實(shí)際上又用了時(shí)間換空間。

當(dāng)然，這樣做，要有一個(gè)度，不然所有的 key 都落在了同一個(gè) bucket 里，直接退化成了鏈表，各種操作的效率直接降為 O(n)，是不行的。

因此，需要有一個(gè)指標(biāo)來衡量前面描述的情況，這就是裝載因子。Go 源碼里這樣定義 裝載因子：

loadFactor := count / (2^B)

count 就是 map 的元素個(gè)數(shù)，2^B 表示 bucket 數(shù)量。

再來說觸發(fā) map 擴(kuò)容的時(shí)機(jī)：在向 map 插入新 key 的時(shí)候，會(huì)進(jìn)行條件檢測(cè)，符合下面這 2 個(gè)條件，就會(huì)觸發(fā)擴(kuò)容：

載因子超過閾值，源碼里定義的閾值是 6.5。overflow 的 bucket 數(shù)量過多，這有兩種情況：（1）當(dāng) B 大于15時(shí)，也就是 bucket 總數(shù)大于 2^15 時(shí)，如果overflow的bucket數(shù)量大于2^15，就觸發(fā)擴(kuò)容。（2）當(dāng)B小于15時(shí)，如果overflow的bucket數(shù)量大于2^B 也會(huì)觸發(fā)擴(kuò)容。

通過匯編語言可以找到賦值操作對(duì)應(yīng)源碼中的函數(shù)是 mapassign，對(duì)應(yīng)擴(kuò)容條件的源碼如下：

// src/runtime/hashmap.go/mapassign

// 觸發(fā)擴(kuò)容時(shí)機(jī)
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
	hashGrow(t, h)
	goto again // Growing the table invalidates everything, so try again
}

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
// 裝載因子超過 6.5
func overLoadFactor(count int, B uint8) bool {
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1<<B buckets.
// Note that most of these overflow buckets must be in sparse use;
// if use was dense, then we'd have already triggered regular map growth.
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	// If the threshold is too low, we do extraneous work.
	// If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.
	// "too many" means (approximately) as many overflow buckets as regular buckets.
	// See incrnoverflow for more details.
	if B > 15 {
		B = 15
	}
	// The compiler doesn't see here that B < 16; mask B to generate shorter shift code.
	// overflow buckets 太多
	return noverflow >= uint16(1)<<(B&15)
}

這里解釋一下這種觸發(fā)擴(kuò)容的原理：

第 1 點(diǎn)：我們知道，每個(gè) bucket 有 8 個(gè)空位，在沒有溢出，且所有的桶都裝滿了的情況下，裝載因子算出來的結(jié)果是 8。因此當(dāng)裝載因子超過 6.5 時(shí)，表明很多 bucket 都快要裝滿了，查找效率和插入效率都變低了。在這個(gè)時(shí)候進(jìn)行擴(kuò)容是有必要的。

第 2 點(diǎn)：是對(duì)第 1 點(diǎn)的補(bǔ)充。就是說在裝載因子比較小的情況下，這時(shí)候 map 的查找和插入效率也很低，而第 1 點(diǎn)識(shí)別不出來這種情況。表面現(xiàn)象就是計(jì)算裝載因子的分子比較小，即 map 里元素總數(shù)少，但是 bucket 數(shù)量多（真實(shí)分配的 bucket 數(shù)量多，包括大量的 overflow bucket）。

不難想像造成這種情況的原因：不停地插入、刪除元素。先插入很多元素，導(dǎo)致創(chuàng)建了很多 bucket，但是裝載因子達(dá)不到第 1 點(diǎn)的臨界值，未觸發(fā)擴(kuò)容來緩解這種情況。之后，刪除元素降低元素總數(shù)量，再插入很多元素，導(dǎo)致創(chuàng)建很多的 overflow bucket，但就是不會(huì)觸犯第 1 點(diǎn)的規(guī)定，你能拿我怎么辦？**overflow bucket 數(shù)量太多，導(dǎo)致 key 會(huì)很分散，查找插入效率低得嚇人，**因此出臺(tái)第 2 點(diǎn)規(guī)定。這就像是一座空城，房子很多，但是住戶很少，都分散了，找起人來很困難。

對(duì)于命中條件 1，2 的限制，都會(huì)發(fā)生擴(kuò)容。但是擴(kuò)容的策略并不相同，畢竟兩種條件應(yīng)對(duì)的場(chǎng)景不同。

對(duì)于條件 1，元素太多，而 bucket 數(shù)量太少，很簡(jiǎn)單：將 B 加 1，bucket 最大數(shù)量 (2^B) 直接變成原來 bucket 數(shù)量的 2 倍。于是，就有新老 bucket 了。注意，這時(shí)候元素都在老 bucket 里，還沒遷移到新的 bucket 來。而且，新 bucket 只是最大數(shù)量變?yōu)樵瓉碜畲髷?shù)量（2^B）的 2 倍（2^B * 2）。

對(duì)于條件 2，其實(shí)元素沒那么多，但是 overflow bucket 數(shù)特別多，說明很多 bucket 都沒裝滿。解決辦法就是開辟一個(gè)新 bucket 空間，將老 bucket 中的元素移動(dòng)到新 bucket，使得同一個(gè) bucket 中的 key 排列地更緊密。這樣，原來，在 overflow bucket 中的 key 可以移動(dòng)到 bucket 中來。結(jié)果是節(jié)省空間，提高 bucket 利用率，map 的查找和插入效率自然就會(huì)提升。

對(duì)于條件 2 的解決方案，有一個(gè)極端的情況：如果插入 map 的 key 哈希都一樣，就會(huì)落到同一個(gè) bucket 里，超過 8 個(gè)就會(huì)產(chǎn)生 overflow bucket，結(jié)果也會(huì)造成 overflow bucket 數(shù)過多。移動(dòng)元素其實(shí)解決不了問題，因?yàn)檫@時(shí)整個(gè)哈希表已經(jīng)退化成了一個(gè)鏈表，操作效率變成了 O(n)。

前面說了擴(kuò)容的條件，下面看一下擴(kuò)容到底是怎么做的：由于 map 擴(kuò)容需要將原有的 key/value 重新搬遷到新的內(nèi)存地址，如果有大量的 key/value 需要搬遷，在搬遷過程中map會(huì)阻塞，非常影響性能。因此 Go map 的擴(kuò)容采取了一種稱為 “漸進(jìn)式” 的方式，原有的 key 并不會(huì)一次性搬遷完畢，每次最多只會(huì)搬遷 2 個(gè)bucket。

上面說的 hashGrow() 函數(shù)實(shí)際上并沒有真正地“搬遷”，它只是分配好了新的 buckets，并將老的 buckets 掛到了新的map的 oldbuckets 字段上。真正搬遷 buckets 的動(dòng)作在 growWork() 函數(shù)中，而調(diào)用 growWork() 函數(shù)的動(dòng)作是在 mapassign 和 mapdelete 函數(shù)中。也就是插入或修改、刪除 key 的時(shí)候，都會(huì)嘗試進(jìn)行搬遷 buckets 的工作。先檢查 oldbuckets 是否搬遷完畢，具體來說就是檢查 oldbuckets 是否為 nil。

我們先看 hashGrow() 函數(shù)所做的工作，再來看具體的搬遷 buckets 是如何進(jìn)行的。

func hashGrow(t *maptype, h *hmap) {
	// B+1 相當(dāng)于是原來 2 倍的空間
	bigger := uint8(1)
	
	// 對(duì)應(yīng)于等容擴(kuò)容
	if !overLoadFactor(h.count+1, h.B) {
		// 進(jìn)行等量的內(nèi)存擴(kuò)容，所以 B 不變
		bigger = 0
		h.flags |= sameSizeGrow
	}
	oldbuckets := h.buckets
	// 申請(qǐng)新的 buckets 空間
	newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

	flags := h.flags &^ (iterator | oldIterator)
	if h.flags&iterator != 0 {
		flags |= oldIterator
	}
	// commit the grow (atomic wrt gc)
	h.B += bigger
	h.flags = flags
	h.oldbuckets = oldbuckets
	h.buckets = newbuckets
	// 當(dāng)前搬遷進(jìn)度為0
	h.nevacuate = 0
	h.noverflow = 0

	//......
}

主要是申請(qǐng)到了新的 buckets 空間，把相關(guān)的標(biāo)志位都進(jìn)行了處理：例如標(biāo)志 nevacuate 被置為 0， 表示當(dāng)前搬遷進(jìn)度為 0。

需要特別提一下的是h.flags的操作：

flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
	flags |= oldIterator
}

這里得先說下運(yùn)算符：&^。這叫按位置 0運(yùn)算符。例如：

x = 01010011
y = 01010100
z = x &^ y = 00000011

如果 y bit 位為 1，那么結(jié)果 z 對(duì)應(yīng) bit 位就為 0，否則 z 對(duì)應(yīng) bit 位就和 x 對(duì)應(yīng) bit 位的值相同。

所以上面那段對(duì) flags 一頓操作的代碼的意思是：先把 h.flags 中 iterator 和 oldIterator 對(duì)應(yīng)位清 0，然后如果發(fā)現(xiàn) iterator 位為 1，那就把它轉(zhuǎn)接到 oldIterator 位，使得 oldIterator 標(biāo)志位變成 1。潛臺(tái)詞就是：buckets 現(xiàn)在掛到了 oldBuckets 名下了，對(duì)應(yīng)的標(biāo)志位也轉(zhuǎn)接過去。

幾個(gè)標(biāo)志位如下：

// 可能有迭代器使用 buckets
iterator     = 1
// 可能有迭代器使用 oldbuckets
oldIterator  = 2
// 有協(xié)程正在并發(fā)的向 map 中寫入 key
hashWriting  = 4
// 等量擴(kuò)容（對(duì)應(yīng)條件 2）
sameSizeGrow = 8

再來看看真正執(zhí)行搬遷工作的 growWork() 函數(shù)。

func growWork(t *maptype, h *hmap, bucket uintptr) {
	// 確認(rèn)搬遷老的 bucket 對(duì)應(yīng)正在使用的 bucket
	evacuate(t, h, bucket&h.oldbucketmask())

	// 再搬遷一個(gè) bucket，以加快搬遷進(jìn)程
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

h.growing() 函數(shù)非常簡(jiǎn)單：

func (h *hmap) growing() bool {
	return h.oldbuckets != nil
}

如果 oldbuckets 不為空，說明還沒有搬遷完畢，還得繼續(xù)搬。

bucket&h.oldbucketmask() 這行代碼，如源碼注釋里說的，是為了確認(rèn)搬遷的 bucket 是我們正在使用的 bucket。oldbucketmask() 函數(shù)返回?cái)U(kuò)容前的 map 的 bucketmask。

所謂的 bucketmask，作用就是將 key 計(jì)算出來的哈希值與 bucketmask 相&，得到的結(jié)果就是 key 應(yīng)該落入的桶。比如 B = 5，那么 bucketmask 的低 5 位是 11111，其余位是 0，hash 值與其相與的意思是，只有 hash 值的低 5 位決策 key 到底落入哪個(gè) bucket。

接下來，重點(diǎn)放在搬遷的關(guān)鍵函數(shù) evacuate。源碼如下：

// oldbucket是
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
	//  獲取old bucket 的地址
	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
	newbit := h.noldbuckets()
	if !evacuated(b) {
		// TODO: reuse overflow buckets instead of using new ones, if there
		// is no iterator using the old buckets.  (If !oldIterator.)

		// xy contains the x and y (low and high) evacuation destinations.
		// X和Y分別代表，如果是2倍擴(kuò)容時(shí)，對(duì)應(yīng)的前半部分和后半部分
		var xy [2]evacDst
		x := &xy[0]
		// 默認(rèn)是等 size 擴(kuò)容，前后 bucket 序號(hào)不變
		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
		x.k = add(unsafe.Pointer(x.b), dataOffset)
		x.e = add(x.k, bucketCnt*uintptr(t.keysize))
		
		if !h.sameSizeGrow() {
			// Only calculate y pointers if we're growing bigger.
			// Otherwise GC can see bad pointers.
			// 如果不是等 size 擴(kuò)容，前后 bucket 序號(hào)有變
			// 使用 y 來進(jìn)行搬遷
			y := &xy[1]
			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
			y.k = add(unsafe.Pointer(y.b), dataOffset)
			y.e = add(y.k, bucketCnt*uintptr(t.keysize))
		}
		// 遍歷所有的 bucket，包括 overflow buckets
		// b 是老的 bucket 地址
		for ; b != nil; b = b.overflow(t) {
			k := add(unsafe.Pointer(b), dataOffset)
			e := add(k, bucketCnt*uintptr(t.keysize))
			for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
				// 當(dāng)前 cell 的 top hash 值
				top := b.tophash[i]
				// 如果 cell 為空，即沒有 key
				if isEmpty(top) {
					b.tophash[i] = evacuatedEmpty
					continue
				}
				// 正常不會(huì)出現(xiàn)這種情況
				// 未被搬遷的 cell 只可能是 empty 或是
				// 正常的 top hash（大于 minTopHash）
				if top < minTopHash {
					throw("bad map state")
				}
				k2 := k
				if t.indirectkey() {
					k2 = *((*unsafe.Pointer)(k2))
				}
				var useY uint8
				// 如果不是等量擴(kuò)容，說明要移動(dòng)到Y(jié) part
				if !h.sameSizeGrow() {
					// Compute hash to make our evacuation decision (whether we need
					// to send this key/elem to bucket x or bucket y).
					hash := t.key.alg.hash(k2, uintptr(h.hash0))
					// // 如果有協(xié)程正在遍歷 map 且出現(xiàn) 相同的 key 值，算出來的 hash 值不同
					if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.alg.equal(k2, k2) {
						// If key != key (NaNs), then the hash could be (and probably
						// will be) entirely different from the old hash. Moreover,
						// it isn't reproducible. Reproducibility is required in the
						// presence of iterators, as our evacuation decision must
						// match whatever decision the iterator made.
						// Fortunately, we have the freedom to send these keys either
						// way. Also, tophash is meaningless for these kinds of keys.
						// We let the low bit of tophash drive the evacuation decision.
						// We recompute a new random tophash for the next level so
						// these keys will get evenly distributed across all buckets
						// after multiple grows.
						useY = top & 1
						top = tophash(hash)
					} else {
						if hash&newbit != 0 {
							useY = 1
						}
					}
				}

				if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
					throw("bad evacuatedN")
				}

				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
				// 找到實(shí)際的目的bucket.
				dst := &xy[useY]                 // evacuation destination

				if dst.i == bucketCnt {
					dst.b = h.newoverflow(t, dst.b)
					dst.i = 0
					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
					dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
				}
				dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
				// 執(zhí)行實(shí)際的復(fù)制操作.
				if t.indirectkey() {
					*(*unsafe.Pointer)(dst.k) = k2 // copy pointer
				} else {
					typedmemmove(t.key, dst.k, k) // copy elem
				}
				if t.indirectelem() {
					*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
				} else {
					typedmemmove(t.elem, dst.e, e)
				}
				// 定位到下一個(gè) cell
				dst.i++
				// These updates might push these pointers past the end of the
				// key or elem arrays.  That's ok, as we have the overflow pointer
				// at the end of the bucket to protect against pointing past the
				// end of the bucket.
				dst.k = add(dst.k, uintptr(t.keysize))
				dst.e = add(dst.e, uintptr(t.elemsize))
			}
		}
		// 如果沒有協(xié)程在使用老的 buckets，就把老 buckets 清除掉，幫助gc
		if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
			// Preserve b.tophash because the evacuation
			// state is maintained there.
			ptr := add(b, dataOffset)
			n := uintptr(t.bucketsize) - dataOffset
			memclrHasPointers(ptr, n)
		}
	}

	if oldbucket == h.nevacuate {
		advanceEvacuationMark(h, t, newbit)
	}
}

搬遷的目的就是將老的 buckets 搬遷到新的 buckets。而通過前面的說明我們知道，應(yīng)對(duì)條件 1，新的 buckets 數(shù)量是之前的一倍，應(yīng)對(duì)條件 2，新的 buckets 數(shù)量和之前相等。

對(duì)于條件 1，從老的 buckets 搬遷到新的 buckets，由于 bucktes 數(shù)量不變，因此可以按序號(hào)來搬，比如原來在 0 號(hào) bucktes，到新的地方后，仍然放在 0 號(hào) buckets。

對(duì)于條件 2，就沒這么簡(jiǎn)單了。要重新計(jì)算 key 的哈希，才能決定它到底落在哪個(gè) bucket。例如，原來 B = 5，計(jì)算出 key 的哈希后，只用看它的低 5 位，就能決定它落在哪個(gè) bucket。擴(kuò)容后，B 變成了 6，因此需要多看一位，它的低 6 位決定 key 落在哪個(gè) bucket。這稱為 rehash。

因此，某個(gè) key 在搬遷前后 bucket 序號(hào)可能和原來相等，也可能是相比原來加上 2^B（原來的 B 值），取決于 hash 值 第 6 bit 位是 0 還是 1。

理解了上面 bucket 序號(hào)的變化，我們就可以回答另一個(gè)問題了：為什么遍歷 map 是無序的？

map 在擴(kuò)容后，會(huì)發(fā)生 key 的搬遷，原來落在同一個(gè) bucket 中的 key，搬遷后，有些 key 就要遠(yuǎn)走高飛了（bucket 序號(hào)加上了 2^B）。而遍歷的過程，就是按順序遍歷 bucket，同時(shí)按順序遍歷 bucket 中的 key。搬遷后，key 的位置發(fā)生了重大的變化，有些 key 飛上高枝，有些 key 則原地不動(dòng)。這樣，遍歷 map 的結(jié)果就不可能按原來的順序了。

當(dāng)然，如果我就一個(gè) hard code 的 map，我也不會(huì)向 map 進(jìn)行插入刪除的操作，按理說每次遍歷這樣的 map 都會(huì)返回一個(gè)固定順序的 key/value 序列吧。的確是這樣，但是 Go 杜絕了這種做法，因?yàn)檫@樣會(huì)給新手程序員帶來誤解，以為這是一定會(huì)發(fā)生的事情，在某些情況下，可能會(huì)釀成大錯(cuò)。

當(dāng)然，Go 做得更絕，當(dāng)我們?cè)诒闅v map 時(shí)，并不是固定地從 0 號(hào) bucket 開始遍歷，每次都是從一個(gè)隨機(jī)值序號(hào)的 bucket 開始遍歷，并且是從這個(gè) bucket 的一個(gè)隨機(jī)序號(hào)的 cell 開始遍歷。這樣，即使你是一個(gè)寫死的 map，僅僅只是遍歷它，也不太可能會(huì)返回一個(gè)固定序列的 key/value 對(duì)了。

再明確一個(gè)問題：如果擴(kuò)容后，B 增加了 1，意味著 buckets 總數(shù)是原來的 2 倍，原來 1 號(hào)的桶“裂變”到兩個(gè)桶。

例如，原始 B = 2，1號(hào) bucket 中有 2 個(gè) key 的哈希值低 3 位分別為：010，110。由于原來 B = 2，所以低 2 位 10 決定它們落在 2 號(hào)桶，現(xiàn)在 B 變成 3，所以 010、110 分別落入 2、6 號(hào)桶。

理解了這個(gè)，后面講 map 迭代的時(shí)候會(huì)用到。

再來講搬遷函數(shù)中的幾個(gè)關(guān)鍵點(diǎn)：

evacuate 函數(shù)每次只完成一個(gè) bucket 的搬遷工作，因此要遍歷完此 bucket 的所有的 cell，將有值的 cell copy 到新的地方。bucket 還會(huì)鏈接 overflow bucket，它們同樣需要搬遷。因此會(huì)有 2 層循環(huán)，外層遍歷 bucket 和 overflow bucket，內(nèi)層遍歷 bucket 的所有 cell。這樣的循環(huán)在 map 的源碼里到處都是，要理解透了。

源碼里提到 X, Y part，其實(shí)就是我們說的如果是擴(kuò)容到原來的 2 倍，桶的數(shù)量是原來的 2 倍，前一半桶被稱為 X part，后一半桶被稱為 Y part。一個(gè) bucket 中的 key 可能會(huì)分裂落到 2 個(gè)桶，一個(gè)位于 X part，一個(gè)位于 Y part。所以在搬遷一個(gè) cell 之前，需要知道這個(gè) cell 中的 key 是落到哪個(gè) Part。很簡(jiǎn)單，重新計(jì)算 cell 中 key 的 hash，并向前“多看”一位，決定落入哪個(gè) Part，這個(gè)前面也說得很詳細(xì)了。

有一個(gè)特殊情況是：有一種 key，每次對(duì)它計(jì)算 hash，得到的結(jié)果都不一樣。這個(gè) key 就是 math.NaN() 的結(jié)果，它的含義是 not a number，類型是 float64。當(dāng)它作為 map 的 key，在搬遷的時(shí)候，會(huì)遇到一個(gè)問題：再次計(jì)算它的哈希值和它當(dāng)初插入 map 時(shí)的計(jì)算出來的哈希值不一樣！

你可能想到了，這樣帶來的一個(gè)后果是，這個(gè) key 是永遠(yuǎn)不會(huì)被 Get 操作獲取的！當(dāng)我使用 m[math.NaN()] 語句的時(shí)候，是查不出來結(jié)果的。這個(gè) key 只有在遍歷整個(gè) map 的時(shí)候，才有機(jī)會(huì)現(xiàn)身。所以，可以向一個(gè) map 插入任意數(shù)量的 math.NaN() 作為 key。

當(dāng)搬遷碰到 math.NaN() 的 key 時(shí)，只通過 tophash 的最低位決定分配到 X part 還是 Y part（如果擴(kuò)容后是原來 buckets 數(shù)量的 2 倍）。如果 tophash 的最低位是 0 ，分配到 X part；如果是 1 ，則分配到 Y part。

確定了要搬遷到的目標(biāo) bucket 后，搬遷操作就比較好進(jìn)行了。將源 key/value 值 copy 到目的地相應(yīng)的位置。

設(shè)置 key 在原始 buckets 的 tophash 為 evacuatedX 或是 evacuatedY，表示已經(jīng)搬遷到了新 map 的 x part 或是 y part。新 map 的 tophash 則正常取 key 哈希值的高 8 位。

下面通過圖來宏觀地看一下擴(kuò)容前后的變化。

擴(kuò)容前，B = 2，共有 4 個(gè) buckets，lowbits 表示 hash 值的低位。假設(shè)我們不關(guān)注其他 buckets 情況，專注在 2 號(hào) bucket。并且假設(shè) overflow 太多，觸發(fā)了等量擴(kuò)容（對(duì)應(yīng)于前面的條件 2）。

擴(kuò)容完成后，overflow bucket 消失了，key 都集中到了一個(gè) bucket，更為緊湊了，提高了查找的效率。

假設(shè)觸發(fā)了 2 倍的擴(kuò)容，那么擴(kuò)容完成后，老 buckets 中的 key 分裂到了 2 個(gè) 新的 bucket。一個(gè)在 x part，一個(gè)在 y 的 part。依據(jù)是 hash 的 lowbits。新 map 中 0-3 稱為 x part，4-7 稱為 y part。

注意，上面的兩張圖忽略了其他 buckets 的搬遷情況，表示所有的 bucket 都搬遷完畢后的情形。實(shí)際上，我們知道，搬遷是一個(gè)“漸進(jìn)”的過程，并不會(huì)一下子就全部搬遷完畢。所以在搬遷過程中，oldbuckets 指針還會(huì)指向原來老的 []bmap，并且已經(jīng)搬遷完畢的 key 的 tophash 值會(huì)是一個(gè)狀態(tài)值，表示 key 的搬遷去向。

元素訪問

通過匯編語言可以看到，向 map 中插入或者修改 key，最終調(diào)用的是 mapassign 函數(shù)。

實(shí)際上插入或修改 key 的語法是一樣的，只不過前者操作的 key 在 map 中不存在，而后者操作的 key 存在 map 中。

mapassign 有一個(gè)系列的函數(shù)，根據(jù) key 類型的不同，編譯器會(huì)將其優(yōu)化為相應(yīng)的“快速函數(shù)”。

我們只用研究最一般的賦值函數(shù) mapassign。

整體來看，流程非常得簡(jiǎn)單：對(duì) key 計(jì)算 hash 值，根據(jù) hash 值按照之前的流程，找到要賦值的位置（可能是插入新 key，也可能是更新老 key），對(duì)相應(yīng)位置進(jìn)行賦值。

源碼大體和之前講的類似，核心還是一個(gè)雙層循環(huán)，外層遍歷 bucket 和它的 overflow bucket，內(nèi)層遍歷整個(gè) bucket 的各個(gè) cell。限于篇幅，這部分代碼的注釋我也不展示了，有興趣的可以去看，保證理解了這篇文章內(nèi)容后，能夠看懂。

我這里會(huì)針對(duì)這個(gè)過程提幾點(diǎn)重要的。

函數(shù)首先會(huì)檢查 map 的標(biāo)志位 flags。如果 flags 的寫標(biāo)志位此時(shí)被置 1 了，說明有其他協(xié)程在執(zhí)行“寫”操作，進(jìn)而導(dǎo)致程序 panic。這也說明了 map 對(duì)協(xié)程是不安全的。

通過前文我們知道擴(kuò)容是漸進(jìn)式的，如果 map 處在擴(kuò)容的過程中，那么當(dāng) key 定位到了某個(gè) bucket 后，需要確保這個(gè) bucket 對(duì)應(yīng)的老 bucket 完成了遷移過程。即老 bucket 里的 key 都要遷移到新的 bucket 中來（分裂到 2 個(gè)新 bucket），才能在新的 bucket 中進(jìn)行插入或者更新的操作。

上面說的操作是在函數(shù)靠前的位置進(jìn)行的，只有進(jìn)行完了這個(gè)搬遷操作后，我們才能放心地在新 bucket 里定位 key 要安置的地址，再進(jìn)行之后的操作。

現(xiàn)在到了定位 key 應(yīng)該放置的位置了，所謂找準(zhǔn)自己的位置很重要。準(zhǔn)備兩個(gè)指針，一個(gè)（inserti）指向 key 的 hash 值在 tophash 數(shù)組所處的位置，另一個(gè)(insertk)指向 cell 的位置（也就是 key 最終放置的地址），當(dāng)然，對(duì)應(yīng) value 的位置就很容易定位出來了。這三者實(shí)際上都是關(guān)聯(lián)的，在 tophash 數(shù)組中的索引位置決定了 key 在整個(gè) bucket 中的位置（共 8 個(gè) key），而 value 的位置需要“跨過” 8 個(gè) key 的長(zhǎng)度。

在循環(huán)的過程中，inserti 和 insertk 分別指向第一個(gè)找到的空閑的 cell。如果之后在 map 沒有找到 key 的存在，也就是說原來 map 中沒有此 key，這意味著插入新 key。那最終 key 的安置地址就是第一次發(fā)現(xiàn)的“空位”（tophash 是 empty）。

如果這個(gè) bucket 的 8 個(gè) key 都已經(jīng)放置滿了，那在跳出循環(huán)后，發(fā)現(xiàn) inserti 和 insertk 都是空，這時(shí)候需要在 bucket 后面掛上 overflow bucket。當(dāng)然，也有可能是在 overflow bucket 后面再掛上一個(gè) overflow bucket。這就說明，太多 key hash 到了此 bucket。

在正式安置 key 之前，還要檢查 map 的狀態(tài)，看它是否需要進(jìn)行擴(kuò)容。如果滿足擴(kuò)容的條件，就主動(dòng)觸發(fā)一次擴(kuò)容操作。

這之后，整個(gè)之前的查找定位 key 的過程，還得再重新走一次。因?yàn)閿U(kuò)容之后，key 的分布都發(fā)生了變化。

最后，會(huì)更新 map 相關(guān)的值，如果是插入新 key，map 的元素?cái)?shù)量字段 count 值會(huì)加 1；在函數(shù)之初設(shè)置的 hashWriting 寫標(biāo)志出會(huì)清零。

另外，有一個(gè)重要的點(diǎn)要說一下。前面說的找到 key 的位置，進(jìn)行賦值操作，實(shí)際上并不準(zhǔn)確。我們看 mapassign 函數(shù)的原型就知道，函數(shù)并沒有傳入 value 值，所以賦值操作是什么時(shí)候執(zhí)行的呢？

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer

答案還得從匯編語言中尋找。我直接揭曉答案，有興趣可以私下去研究一下。mapassign 函數(shù)返回的指針就是指向的 key 所對(duì)應(yīng)的 value 值位置，有了地址，就很好操作賦值了。

刪除

寫操作底層的執(zhí)行函數(shù)是 mapdelete：

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)

根據(jù) key 類型的不同，刪除操作會(huì)被優(yōu)化成更具體的函數(shù)：

當(dāng)然，我們只關(guān)心 mapdelete 函數(shù)。它首先會(huì)檢查 h.flags 標(biāo)志，如果發(fā)現(xiàn)寫標(biāo)位是 1，直接 panic，因?yàn)檫@表明有其他協(xié)程同時(shí)在進(jìn)行寫操作。

計(jì)算 key 的哈希，找到落入的 bucket。檢查此 map 如果正在擴(kuò)容的過程中，直接觸發(fā)一次搬遷操作。

刪除操作同樣是兩層循環(huán)，核心還是找到 key 的具體位置。尋找過程都是類似的，在 bucket 中挨個(gè) cell 尋找。

找到對(duì)應(yīng)位置后，對(duì) key 或者 value 進(jìn)行“清零”操作。

迭代

本來 map 的遍歷過程比較簡(jiǎn)單：遍歷所有的 bucket 以及它后面掛的 overflow bucket，然后挨個(gè)遍歷 bucket 中的所有 cell。每個(gè) bucket 中包含 8 個(gè) cell，從有 key 的 cell 中取出 key 和 value，這個(gè)過程就完成了。

但是，現(xiàn)實(shí)并沒有這么簡(jiǎn)單。還記得前面講過的擴(kuò)容過程嗎？擴(kuò)容過程不是一個(gè)原子的操作，它每次最多只搬運(yùn) 2 個(gè) bucket，所以如果觸發(fā)了擴(kuò)容操作，那么在很長(zhǎng)時(shí)間里，map 的狀態(tài)都是處于一個(gè)中間態(tài)：有些 bucket 已經(jīng)搬遷到新家，而有些 bucket 還待在老地方。

因此，遍歷如果發(fā)生在擴(kuò)容的過程中，就會(huì)涉及到遍歷新老 bucket 的過程，這是難點(diǎn)所在。

我先寫一個(gè)簡(jiǎn)單的代碼樣例，假裝不知道遍歷過程具體調(diào)用的是什么函數(shù)：

package main

import "fmt"

func main() {
	ageMp := make(map[string]int)
	ageMp["qcrao"] = 18

	for name, age := range ageMp {
		fmt.Println(name, age)
	}
}

執(zhí)行命令：

go tool compile -S main.go

得到匯編命令。這里就不逐行講解了，可以去看之前的幾篇文章，說得很詳細(xì)。

關(guān)鍵的幾行匯編代碼如下：

// ......
0x0124 00292 (test16.go:9)      CALL    runtime.mapiterinit(SB)

// ......
0x01fb 00507 (test16.go:9)      CALL    runtime.mapiternext(SB)
0x0200 00512 (test16.go:9)      MOVQ    ""..autotmp_4+160(SP), AX
0x0208 00520 (test16.go:9)      TESTQ   AX, AX
0x020b 00523 (test16.go:9)      JNE     302

// ......

這樣，關(guān)于 map 迭代，底層的函數(shù)調(diào)用關(guān)系一目了然。先是調(diào)用 mapiterinit 函數(shù)初始化迭代器，然后循環(huán)調(diào)用 mapiternext 函數(shù)進(jìn)行 map 迭代。

迭代器的結(jié)構(gòu)體定義：

type hiter struct {
	key         unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/internal/gc/range.go).
	elem        unsafe.Pointer // Must be in second position (see cmd/internal/gc/range.go).
	t           *maptype
	h           *hmap
	buckets     unsafe.Pointer // bucket ptr at hash_iter initialization time
	bptr        *bmap          // current bucket
	overflow    *[]*bmap       // keeps overflow buckets of hmap.buckets alive
	oldoverflow *[]*bmap       // keeps overflow buckets of hmap.oldbuckets alive
	startBucket uintptr        // bucket iteration started at
	offset      uint8          // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
	wrapped     bool           // already wrapped around from end of bucket array to beginning
	B           uint8
	i           uint8
	bucket      uintptr
	checkBucket uintptr
}

mapiterinit 就是對(duì) hiter 結(jié)構(gòu)體里的字段進(jìn)行初始化賦值操作。

前面已經(jīng)提到過，即使是對(duì)一個(gè)寫死的 map 進(jìn)行遍歷，每次出來的結(jié)果也是無序的。下面我們就可以近距離地觀察他們的實(shí)現(xiàn)了。

// 生成隨機(jī)數(shù) r
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
	r += uintptr(fastrand()) << 31
}
// 從哪個(gè) bucket 開始遍歷
it.startBucket = r & bucketMask(h.B)
it.offset = uint8(r >> h.B & (bucketCnt - 1))

例如，B = 2，那 uintptr(1)<<h.B - 1 結(jié)果就是 3，低 8 位為 0000 0011，將 r 與之 & ，就可以得到一個(gè)0~3的 bucket 序號(hào)；bucketCnt - 1 等于 7，低 8 位為 0000 0111，將 r 右移 2 位后，與 7 相與，就可以得到一個(gè) 0~7 號(hào)的 cell。

于是，在 mapiternext 函數(shù)中就會(huì)從 it.startBucket 的 it.offset 號(hào)的 cell 開始遍歷，取出其中的 key 和 value，直到又回到起點(diǎn) bucket，完成遍歷過程。

源碼部分比較好看懂，尤其是理解了前面注釋的幾段代碼后，再看這部分代碼就沒什么壓力了。所以，接下來，我將通過圖形化的方式講解整個(gè)遍歷過程，希望能夠清晰易懂。

假設(shè)我們有下圖所示的一個(gè) map，起始時(shí) B = 1，有兩個(gè) bucket，后來觸發(fā)了擴(kuò)容（這里不要深究擴(kuò)容條件，只是一個(gè)設(shè)定），B 變成 2。并且， 1 號(hào) bucket 中的內(nèi)容搬遷到了新的 bucket，1 號(hào)裂變成 1 號(hào)和 3 號(hào)；0 號(hào) bucket 暫未搬遷。老的 bucket 掛在在 *oldbuckets 指針上面，新的 bucket 則掛在 *buckets 指針上面。

這時(shí)，我們對(duì)此 map 進(jìn)行遍歷。假設(shè)經(jīng)過初始化后，startBucket = 3，offset = 2。于是，遍歷的起點(diǎn)將是 3 號(hào) bucket 的 2 號(hào) cell，下面這張圖就是開始遍歷時(shí)的狀態(tài)：

標(biāo)紅的表示起始位置，bucket 遍歷順序?yàn)椋? -> 0 -> 1 -> 2。

因?yàn)?3 號(hào) bucket 對(duì)應(yīng)老的 1 號(hào) bucket，因此先檢查老 1 號(hào) bucket 是否已經(jīng)被搬遷過。判斷方法就是：

func evacuated(b *bmap) bool {
	h := b.tophash[0]
	return h > emptyOne && h < minTopHash
}

如果 b.tophash[0] 的值在標(biāo)志值范圍內(nèi)，即在 (1,5) 區(qū)間里，說明已經(jīng)被搬遷過了。

emptyRest      = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows.
emptyOne       = 1 // this cell is empty
evacuatedX     = 2 // key/elem is valid.  Entry has been evacuated to first half of larger table.
evacuatedY     = 3 // same as above, but evacuated to second half of larger table.
evacuatedEmpty = 4 // cell is empty, bucket is evacuated.
minTopHash     = 5 // minimum tophash for a normal filled cell.

在本例中，老 1 號(hào) bucket 已經(jīng)被搬遷過了。所以它的 tophash[0] 值在 (1,5) 范圍內(nèi)，因此只用遍歷新的 3 號(hào) bucket。

依次遍歷 3 號(hào) bucket 的 cell，這時(shí)候會(huì)找到第一個(gè)非空的 key：元素 e。到這里，mapiternext 函數(shù)返回，這時(shí)我們的遍歷結(jié)果僅有一個(gè)元素：

由于返回的 key 不為空，所以會(huì)繼續(xù)調(diào)用 mapiternext 函數(shù)。

繼續(xù)從上次遍歷到的地方往后遍歷，從新 3 號(hào) overflow bucket 中找到了元素 f 和 元素 g。

遍歷結(jié)果集也因此壯大：

新 3 號(hào) bucket 遍歷完之后，回到了新 0 號(hào) bucket。0 號(hào) bucket 對(duì)應(yīng)老的 0 號(hào) bucket，經(jīng)檢查，老 0 號(hào) bucket 并未搬遷，因此對(duì)新 0 號(hào) bucket 的遍歷就改為遍歷老 0 號(hào) bucket。那是不是把老 0 號(hào) bucket 中的所有 key 都取出來呢？

并沒有這么簡(jiǎn)單，回憶一下，老 0 號(hào) bucket 在搬遷后將裂變成 2 個(gè) bucket：新 0 號(hào)、新 2 號(hào)。而我們此時(shí)正在遍歷的只是新 0 號(hào) bucket（注意，遍歷都是遍歷的 *bucket 指針，也就是所謂的新 buckets）。所以，我們只會(huì)取出老 0 號(hào) bucket 中那些在裂變之后，分配到新 0 號(hào) bucket 中的那些 key。

因此，lowbits == 00 的將進(jìn)入遍歷結(jié)果集：

和之前的流程一樣，繼續(xù)遍歷新 1 號(hào) bucket，發(fā)現(xiàn)老 1 號(hào) bucket 已經(jīng)搬遷，只用遍歷新 1 號(hào) bucket 中現(xiàn)有的元素就可以了。結(jié)果集變成：

繼續(xù)遍歷新 2 號(hào) bucket，它來自老 0 號(hào) bucket，因此需要在老 0 號(hào) bucket 中那些會(huì)裂變到新 2 號(hào) bucket 中的 key，也就是 lowbit == 10 的那些 key。

這樣，遍歷結(jié)果集變成：

最后，繼續(xù)遍歷到新 3 號(hào) bucket 時(shí)，發(fā)現(xiàn)所有的 bucket 都已經(jīng)遍歷完畢，整個(gè)迭代過程執(zhí)行完畢。

順便說一下，如果碰到 key 是 math.NaN() 這種的，處理方式類似。核心還是要看它被分裂后具體落入哪個(gè) bucket。只不過只用看它 top hash 的最低位。如果 top hash 的最低位是 0 ，分配到 X part；如果是 1 ，則分配到 Y part。據(jù)此決定是否取出 key，放到遍歷結(jié)果集里。

map 遍歷的核心在于理解 2 倍擴(kuò)容時(shí)，老 bucket 會(huì)分裂到 2 個(gè)新 bucket 中去。而遍歷操作，會(huì)按照新 bucket 的序號(hào)順序進(jìn)行，碰到老 bucket 未搬遷的情況時(shí)，要在老 bucket 中找到將來要搬遷到新 bucket 來的 key。

核心點(diǎn)：

（1）可以邊遍歷邊刪除嗎？
map 并不是一個(gè)線程安全的數(shù)據(jù)結(jié)構(gòu)。同時(shí)讀寫一個(gè) map 是未定義的行為，如果被檢測(cè)到，會(huì)直接 panic。

一般而言，這可以通過讀寫鎖來解決：sync.RWMutex。

讀之前調(diào)用 RLock() 函數(shù)，讀完之后調(diào)用 RUnlock() 函數(shù)解鎖；寫之前調(diào)用 Lock() 函數(shù)，寫完之后，調(diào)用 Unlock() 解鎖。

另外，sync.Map 是線程安全的 map，也可以使用。它的實(shí)現(xiàn)原理，這次先不說了。

（2）key 可以是 float 型嗎？
從語法上看，是可以的。Go 語言中只要是可比較的類型都可以作為 key。除開 slice，map，functions 這幾種類型，其他類型都是 OK 的。具體包括：布爾值、數(shù)字、字符串、指針、通道、接口類型、結(jié)構(gòu)體、只包含上述類型的數(shù)組。這些類型的共同特征是支持== 和 != 操作符，k1 == k2 時(shí)，可認(rèn)為 k1 和 k2 是同一個(gè) key。如果是結(jié)構(gòu)體，則需要它們的字段值都相等，才被認(rèn)為是相同的 key。

順便說一句，任何類型都可以作為 value，包括 map 類型。

最后說結(jié)論：float 型可以作為 key，但是由于精度的問題，會(huì)導(dǎo)致一些詭異的問題，慎用之。

（3）總結(jié)
總結(jié)一下，Go 語言中，通過哈希查找表實(shí)現(xiàn) map，用鏈表法解決哈希沖突。

通過 key 的哈希值將 key 散落到不同的桶中，每個(gè)桶中有 8 個(gè) cell。哈希值的低位決定桶序號(hào)，高位標(biāo)識(shí)同一個(gè)桶中的不同 key。

當(dāng)向桶中添加了很多 key，造成元素過多，或者溢出桶太多，就會(huì)觸發(fā)擴(kuò)容。擴(kuò)容分為等量擴(kuò)容和 2 倍容量擴(kuò)容。擴(kuò)容后，原來一個(gè) bucket 中的 key 一分為二，會(huì)被重新分配到兩個(gè)桶中。

擴(kuò)容過程是漸進(jìn)的，主要是防止一次擴(kuò)容需要搬遷的 key 數(shù)量過多，引發(fā)性能問題。觸發(fā)擴(kuò)容的時(shí)機(jī)是增加了新元素，bucket 搬遷的時(shí)機(jī)則發(fā)生在賦值、刪除期間，每次最多搬遷兩個(gè) bucket。

查找、賦值、刪除的一個(gè)很核心的內(nèi)容是如何定位到 key 所在的位置，需要重點(diǎn)理解。一旦理解，關(guān)于 map 的源碼就可以看懂了。

到此這篇關(guān)于Golang map實(shí)踐以及實(shí)現(xiàn)原理的文章就介紹到這了,更多相關(guān)Golang map實(shí)現(xiàn)原理內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論