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

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

使用實例

測試的主要目的是對于map，當作為函數(shù)傳參時候，函數(shù)內部的改變會不會透傳到外部，以及函數(shù)傳參內外是不是一個map，也就是傳遞的是實例還是指針。(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)
}

運行結果是：

--------------- 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] 

從運行結果我們可以知道：

當傳參為map的時候，其實傳遞的是指針地址。函數(shù)內外map的地址都是一樣的。函數(shù)內部的改變會透傳到函數(shù)外部。

Test Case2：Test Case1的實現(xiàn)其實也有個特殊使用例子，也就是當函數(shù)入參map沒有初始化的時候。

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)
}

運行結果是：

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

從結果可以看出，當入參map沒有初始化的時候，就不一樣了：

• 沒有初始化的map地址都是0；
• 函數(shù)內部初始化map不會透傳到外部map。

其實也好理解，因為map沒有初始化，所以map的地址傳遞到函數(shù)內部之后初始化，會改變map的地址，但是外部地址不會改變。有一種方法，return 新建的map。

內存模型

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

Golang的map從high level的角度來看，采用的是哈希表，并使用鏈表查找法解決沖突。但是golang的map實現(xiàn)在鏈表解決沖突時候有很多優(yōu)化，具體我們在后面看細節(jié)。

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

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

這里B是map的bucket數(shù)組長度的對數(shù)，每個bucket里面存儲了kv對。buckets是一個指針，指向實際存儲的bucket數(shù)組的首地址。 bucket的結構體如下：

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.
}

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

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

bmap 就是我們常說的“bucket”結構，每個 bucket 里面最多存儲 8 個 key，這些 key 之所以會落入同一個桶，是因為它們經過哈希計算后，哈希結果是“一類”的。在桶內，又會根據(jù) key 計算出來的 hash 值的高 8 位來決定 key 到底落入桶內的哪個位置（一個桶內最多有8個位置）。

這里引用網絡上的一張圖：

當 map 的 key 和 value 都不是指針，并且 size 都小于 128 字節(jié)的情況下，會把 bmap 標記為不含指針，這樣可以避免 gc 時掃描整個 hmap。但是，我們看 bmap 其實有一個 overflow 的字段，是指針類型的，破壞了 bmap 不含指針的設想，這時會把 overflow 移動到 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詳細的存儲分布細節(jié)：

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

比如： map[int64]int8

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

每個 bucket 設計成最多只能放 8 個 key-value 對，如果有第 9 個 key-value 落入當前的 bucket，那就需要再構建一個 bucket ，通過 overflow 指針連接起來。

創(chuàng)建map

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

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

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

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

	// 初始化 hash table
	// 如果 B 等于 0，那么 buckets 就會在賦值的時候再分配
	// 如果長度比較大，分配內存會花費長一點
	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
}

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

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

hash函數(shù)

關于hash函數(shù)的細節(jié)，這里就不介紹了。這里需要重點提示的是，哈希函數(shù)的算法與key的類型一一對應的。根據(jù) key 的類型， maptype結構體的 key字段的alg 字段會被設置對應類型的 hash 和 equal 函數(shù)。

key定位和碰撞解決

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

suppose，現(xiàn)在有一個 key 經過哈希函數(shù)計算后，得到的哈希結果是：

10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

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

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

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

下面是檢索的示意圖：

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

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

下面我們通過源碼驗證：

// 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 {
	//......校驗邏輯
	
	//如果 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，低五位二進制是全1
	m := bucketMask(h.B)
	// b 就是 當前key對應的 bucket 的地址
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	// oldbuckets 不為 nil，說明發(fā)生了擴容
	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
		}
	}
	// 計算出高 8 位的 hash
	// 相當于右移 56 位，只取高8位
	top := tophash(hash)

// 這里進入bucket的二層循環(huán)找到對應的kv(第一層是bucket,第二層是bucket內部的8個slot)
bucketloop:
	// 遍歷bucket以及overflow鏈表
	for ; b != nil; b = b.overflow(t) {
		//遍歷bucket的8個slot
		for i := uintptr(0); i < bucketCnt; i++ {
			// tophash 不匹配
			if b.tophash[i] != top {
				// 標識當前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 也找完了，說明沒有目標 key
	// 返回零值
	return unsafe.Pointer(&zeroVal[0])
}

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

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

這里，說一下定位 key 和 value 的方法以及整個循環(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 還是源碼里定義的結構體，只包含一個 tophash 數(shù)組，經編譯器擴充之后的結構體才包含 key，value，overflow 這些字段。dataOffset 是 key 相對于 bmap 起始地址的偏移：

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

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

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

再說一下 minTopHash，當一個 cell 的 tophash 值小于 minTopHash 時，標志這個 cell 的遷移狀態(tài)。因為這個狀態(tài)值是放在 tophash 數(shù)組里，為了和正常的哈希值區(qū)分開，會給 key 計算出來的哈希值一個增量：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
// 擴容相關
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.

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

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

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

擴容

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

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

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

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

loadFactor := count / (2^B)

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

再來說觸發(fā) map 擴容的時機：在向 map 插入新 key 的時候，會進行條件檢測，符合下面這 2 個條件，就會觸發(fā)擴容：

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

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

// src/runtime/hashmap.go/mapassign

// 觸發(fā)擴容時機
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ā)擴容的原理：

第 1 點：我們知道，每個 bucket 有 8 個空位，在沒有溢出，且所有的桶都裝滿了的情況下，裝載因子算出來的結果是 8。因此當裝載因子超過 6.5 時，表明很多 bucket 都快要裝滿了，查找效率和插入效率都變低了。在這個時候進行擴容是有必要的。

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

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

對于命中條件 1，2 的限制，都會發(fā)生擴容。但是擴容的策略并不相同，畢竟兩種條件應對的場景不同。

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

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

對于條件 2 的解決方案，有一個極端的情況：如果插入 map 的 key 哈希都一樣，就會落到同一個 bucket 里，超過 8 個就會產生 overflow bucket，結果也會造成 overflow bucket 數(shù)過多。移動元素其實解決不了問題，因為這時整個哈希表已經退化成了一個鏈表，操作效率變成了 O(n)。

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

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

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

func hashGrow(t *maptype, h *hmap) {
	// B+1 相當于是原來 2 倍的空間
	bigger := uint8(1)
	
	// 對應于等容擴容
	if !overLoadFactor(h.count+1, h.B) {
		// 進行等量的內存擴容，所以 B 不變
		bigger = 0
		h.flags |= sameSizeGrow
	}
	oldbuckets := h.buckets
	// 申請新的 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
	// 當前搬遷進度為0
	h.nevacuate = 0
	h.noverflow = 0

	//......
}

主要是申請到了新的 buckets 空間，把相關的標志位都進行了處理：例如標志 nevacuate 被置為 0， 表示當前搬遷進度為 0。

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

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

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

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

如果 y bit 位為 1，那么結果 z 對應 bit 位就為 0，否則 z 對應 bit 位就和 x 對應 bit 位的值相同。

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

幾個標志位如下：

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

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

func growWork(t *maptype, h *hmap, bucket uintptr) {
	// 確認搬遷老的 bucket 對應正在使用的 bucket
	evacuate(t, h, bucket&h.oldbucketmask())

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

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

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

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

bucket&h.oldbucketmask() 這行代碼，如源碼注釋里說的，是為了確認搬遷的 bucket 是我們正在使用的 bucket。oldbucketmask() 函數(shù)返回擴容前的 map 的 bucketmask。

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

接下來，重點放在搬遷的關鍵函數(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倍擴容時，對應的前半部分和后半部分
		var xy [2]evacDst
		x := &xy[0]
		// 默認是等 size 擴容，前后 bucket 序號不變
		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 擴容，前后 bucket 序號有變
			// 使用 y 來進行搬遷
			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)) {
				// 當前 cell 的 top hash 值
				top := b.tophash[i]
				// 如果 cell 為空，即沒有 key
				if isEmpty(top) {
					b.tophash[i] = evacuatedEmpty
					continue
				}
				// 正常不會出現(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
				// 如果不是等量擴容，說明要移動到Y 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
				// 找到實際的目的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í)行實際的復制操作.
				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)
				}
				// 定位到下一個 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。而通過前面的說明我們知道，應對條件 1，新的 buckets 數(shù)量是之前的一倍，應對條件 2，新的 buckets 數(shù)量和之前相等。

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

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

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

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

map 在擴容后，會發(fā)生 key 的搬遷，原來落在同一個 bucket 中的 key，搬遷后，有些 key 就要遠走高飛了（bucket 序號加上了 2^B）。而遍歷的過程，就是按順序遍歷 bucket，同時按順序遍歷 bucket 中的 key。搬遷后，key 的位置發(fā)生了重大的變化，有些 key 飛上高枝，有些 key 則原地不動。這樣，遍歷 map 的結果就不可能按原來的順序了。

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

當然，Go 做得更絕，當我們在遍歷 map 時，并不是固定地從 0 號 bucket 開始遍歷，每次都是從一個隨機值序號的 bucket 開始遍歷，并且是從這個 bucket 的一個隨機序號的 cell 開始遍歷。這樣，即使你是一個寫死的 map，僅僅只是遍歷它，也不太可能會返回一個固定序列的 key/value 對了。

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

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

理解了這個，后面講 map 迭代的時候會用到。

再來講搬遷函數(shù)中的幾個關鍵點：

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

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

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

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

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

確定了要搬遷到的目標 bucket 后，搬遷操作就比較好進行了。將源 key/value 值 copy 到目的地相應的位置。

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

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

擴容前，B = 2，共有 4 個 buckets，lowbits 表示 hash 值的低位。假設我們不關注其他 buckets 情況，專注在 2 號 bucket。并且假設 overflow 太多，觸發(fā)了等量擴容（對應于前面的條件 2）。

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

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

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

元素訪問

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

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

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

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

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

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

我這里會針對這個過程提幾點重要的。

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

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

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

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

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

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

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

這之后，整個之前的查找定位 key 的過程，還得再重新走一次。因為擴容之后，key 的分布都發(fā)生了變化。

最后，會更新 map 相關的值，如果是插入新 key，map 的元素數(shù)量字段 count 值會加 1；在函數(shù)之初設置的 hashWriting 寫標志出會清零。

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

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

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

刪除

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

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

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

當然，我們只關心 mapdelete 函數(shù)。它首先會檢查 h.flags 標志，如果發(fā)現(xiàn)寫標位是 1，直接 panic，因為這表明有其他協(xié)程同時在進行寫操作。

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

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

找到對應位置后，對 key 或者 value 進行“清零”操作。

迭代

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

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

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

我先寫一個簡單的代碼樣例，假裝不知道遍歷過程具體調用的是什么函數(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

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

關鍵的幾行匯編代碼如下：

// ......
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

// ......

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

迭代器的結構體定義：

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 就是對 hiter 結構體里的字段進行初始化賦值操作。

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

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

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

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

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

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

這時，我們對此 map 進行遍歷。假設經過初始化后，startBucket = 3，offset = 2。于是，遍歷的起點將是 3 號 bucket 的 2 號 cell，下面這張圖就是開始遍歷時的狀態(tài)：

標紅的表示起始位置，bucket 遍歷順序為：3 -> 0 -> 1 -> 2。

因為 3 號 bucket 對應老的 1 號 bucket，因此先檢查老 1 號 bucket 是否已經被搬遷過。判斷方法就是：

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

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

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 號 bucket 已經被搬遷過了。所以它的 tophash[0] 值在 (1,5) 范圍內，因此只用遍歷新的 3 號 bucket。

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

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

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

遍歷結果集也因此壯大：

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

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

因此，lowbits == 00 的將進入遍歷結果集：

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

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

這樣，遍歷結果集變成：

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

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

map 遍歷的核心在于理解 2 倍擴容時，老 bucket 會分裂到 2 個新 bucket 中去。而遍歷操作，會按照新 bucket 的序號順序進行，碰到老 bucket 未搬遷的情況時，要在老 bucket 中找到將來要搬遷到新 bucket 來的 key。

核心點：

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

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

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

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

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

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

最后說結論：float 型可以作為 key，但是由于精度的問題，會導致一些詭異的問題，慎用之。

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

通過 key 的哈希值將 key 散落到不同的桶中，每個桶中有 8 個 cell。哈希值的低位決定桶序號，高位標識同一個桶中的不同 key。

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

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

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

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

最新評論