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

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

不難想像造成這種情況的原因：不停地插入、刪除元素。先插入很多元素，導(dǎo)致創(chuàng)建了很多 bucket，但是裝載因子達(dá)不到第 1 點(diǎn)的臨界值，未觸發(fā)擴(kuò)容來(lái)緩解這種情況。之后，刪除元素降低元素總數(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ī)定。這就像是一座空城，房子很多，但是住戶很少，都分散了，找起人來(lái)很困難。

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

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

對(duì)于條件 2，其實(shí)元素沒那么多，但是 overflow bucket 數(shù)特別多，說(shuō)明很多 bucket 都沒裝滿。解決辦法就是開辟一個(gè)新 bucket 空間，將老 bucket 中的元素移動(dòng)到新 bucket，使得同一個(gè) bucket 中的 key 排列地更緊密。這樣，原來(lái)，在 overflow bucket 中的 key 可以移動(dòng)到 bucket 中來(lái)。結(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)。

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

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

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

func hashGrow(t *maptype, h *hmap) {
	// B+1 相當(dāng)于是原來(lái) 2 倍的空間
	bigger := uint8(1)

	// 對(duì)應(yīng)條件 2
	if !overLoadFactor(int64(h.count), h.B) {
		// 進(jìn)行等量的內(nèi)存擴(kuò)容，所以 B 不變
		bigger = 0
		h.flags |= sameSizeGrow
	}
	// 將老 buckets 掛到 buckets 上
	oldbuckets := h.buckets
	// 申請(qǐng)新的 buckets 空間
	newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger)

	flags := h.flags &^ (iterator | oldIterator)
	if h.flags&iterator != 0 {
		flags |= oldIterator
	}
	// 提交 grow 的動(dòng)作
	h.B += bigger
	h.flags = flags
	h.oldbuckets = oldbuckets
	h.buckets = newbuckets
	// 搬遷進(jìn)度為 0
	h.nevacuate = 0
	// overflow buckets 數(shù)為 0
	h.noverflow = 0

	// ……
}

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

值得一說(shuō)的是對(duì) h.flags 的處理：

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

這里得先說(shuō)下運(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é)程正在向 map 中寫入 key
hashWriting  = 4
// 等量擴(kuò)容（對(duì)應(yīng)條件 2）
sameSizeGrow = 8

再來(lái)看看真正執(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 不為空，說(shuō)明還沒有搬遷完畢，還得繼續(xù)搬。

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

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

接下來(lái)，我們集中所有的精力在搬遷的關(guān)鍵函數(shù) evacuate。源碼貼在下面，不要緊張，我會(huì)加上大面積的注釋，通過注釋絕對(duì)是能看懂的。之后，我會(huì)再對(duì)搬遷過程作詳細(xì)說(shuō)明。

源碼如下：

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
	// 定位老的 bucket 地址
	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
	// 結(jié)果是 2^B，如 B = 5，結(jié)果為32
	newbit := h.noldbuckets()
	// key 的哈希函數(shù)
	alg := t.key.alg
	// 如果 b 沒有被搬遷過
	if !evacuated(b) {
		var (
			// 表示bucket 移動(dòng)的目標(biāo)地址
			x, y   *bmap
			// 指向 x,y 中的 key/val
			xi, yi int
			// 指向 x，y 中的 key
			xk, yk unsafe.Pointer
			// 指向 x，y 中的 value
			xv, yv unsafe.Pointer
		)
		// 默認(rèn)是等 size 擴(kuò)容，前后 bucket 序號(hào)不變
		// 使用 x 來(lái)進(jìn)行搬遷
		x = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
		xi = 0
		xk = add(unsafe.Pointer(x), dataOffset)
		xv = add(xk, bucketCnt*uintptr(t.keysize))、

		// 如果不是等 size 擴(kuò)容，前后 bucket 序號(hào)有變
		// 使用 y 來(lái)進(jìn)行搬遷
		if !h.sameSizeGrow() {
			// y 代表的 bucket 序號(hào)增加了 2^B
			y = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
			yi = 0
			yk = add(unsafe.Pointer(y), dataOffset)
			yv = add(yk, bucketCnt*uintptr(t.keysize))
		}

		// 遍歷所有的 bucket，包括 overflow buckets
		// b 是老的 bucket 地址
		for ; b != nil; b = b.overflow(t) {
			k := add(unsafe.Pointer(b), dataOffset)
			v := add(k, bucketCnt*uintptr(t.keysize))

			// 遍歷 bucket 中的所有 cell
			for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {
				// 當(dāng)前 cell 的 top hash 值
				top := b.tophash[i]
				// 如果 cell 為空，即沒有 key
				if top == empty {
					// 那就標(biāo)志它被"搬遷"過
					b.tophash[i] = evacuatedEmpty
					// 繼續(xù)下個(gè) cell
					continue
				}
				// 正常不會(huì)出現(xiàn)這種情況
				// 未被搬遷的 cell 只可能是 empty 或是
				// 正常的 top hash（大于 minTopHash）
				if top < minTopHash {
					throw("bad map state")
				}

				k2 := k
				// 如果 key 是指針，則解引用
				if t.indirectkey {
					k2 = *((*unsafe.Pointer)(k2))
				}

				// 默認(rèn)使用 X，等量擴(kuò)容
				useX := true
				// 如果不是等量擴(kuò)容
				if !h.sameSizeGrow() {
					// 計(jì)算 hash 值，和 key 第一次寫入時(shí)一樣
					hash := alg.hash(k2, uintptr(h.hash0))

					// 如果有協(xié)程正在遍歷 map
					if h.flags&iterator != 0 {
						// 如果出現(xiàn) 相同的 key 值，算出來(lái)的 hash 值不同
						if !t.reflexivekey && !alg.equal(k2, k2) {
							// 只有在 float 變量的 NaN() 情況下會(huì)出現(xiàn)
							if top&1 != 0 {
								// 第 B 位置 1
								hash |= newbit
							} else {
								// 第 B 位置 0
								hash &^= newbit
							}
							// 取高 8 位作為 top hash 值
							top = uint8(hash >> (sys.PtrSize*8 - 8))
							if top < minTopHash {
								top += minTopHash
							}
						}
					}

					// 取決于新哈希值的 oldB+1 位是 0 還是 1
					// 詳細(xì)看后面的文章
					useX = hash&newbit == 0
				}

				// 如果 key 搬到 X 部分
				if useX {
					// 標(biāo)志老的 cell 的 top hash 值，表示搬移到 X 部分
					b.tophash[i] = evacuatedX
					// 如果 xi 等于 8，說(shuō)明要溢出了
					if xi == bucketCnt {
						// 新建一個(gè) bucket
						newx := h.newoverflow(t, x)
						x = newx
						// xi 從 0 開始計(jì)數(shù)
						xi = 0
						// xk 表示 key 要移動(dòng)到的位置
						xk = add(unsafe.Pointer(x), dataOffset)
						// xv 表示 value 要移動(dòng)到的位置
						xv = add(xk, bucketCnt*uintptr(t.keysize))
					}
					// 設(shè)置 top hash 值
					x.tophash[xi] = top
					// key 是指針
					if t.indirectkey {
						// 將原 key（是指針）復(fù)制到新位置
						*(*unsafe.Pointer)(xk) = k2 // copy pointer
					} else {
						// 將原 key（是值）復(fù)制到新位置
						typedmemmove(t.key, xk, k) // copy value
					}
					// value 是指針，操作同 key
					if t.indirectvalue {
						*(*unsafe.Pointer)(xv) = *(*unsafe.Pointer)(v)
					} else {
						typedmemmove(t.elem, xv, v)
					}

					// 定位到下一個(gè) cell
					xi++
					xk = add(xk, uintptr(t.keysize))
					xv = add(xv, uintptr(t.valuesize))
				} else { // key 搬到 Y 部分，操作同 X 部分
					// ……
					// 省略了這部分，操作和 X 部分相同
				}
			}
		}
		// 如果沒有協(xié)程在使用老的 buckets，就把老 buckets 清除掉，幫助gc
		if h.flags&oldIterator == 0 {
			b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
			// 只清除bucket 的 key,value 部分，保留 top hash 部分，指示搬遷狀態(tài)
			if t.bucket.kind&kindNoPointers == 0 {
				memclrHasPointers(add(unsafe.Pointer(b), dataOffset), uintptr(t.bucketsize)-dataOffset)
			} else {
				memclrNoHeapPointers(add(unsafe.Pointer(b), dataOffset), uintptr(t.bucketsize)-dataOffset)
			}
		}
	}

	// 更新搬遷進(jìn)度
	// 如果此次搬遷的 bucket 等于當(dāng)前進(jìn)度
	if oldbucket == h.nevacuate {
		// 進(jìn)度加 1
		h.nevacuate = oldbucket + 1
		// Experiments suggest that 1024 is overkill by at least an order of magnitude.
		// Put it in there as a safeguard anyway, to ensure O(1) behavior.
		// 嘗試往后看 1024 個(gè) bucket
		stop := h.nevacuate + 1024
		if stop > newbit {
			stop = newbit
		}
		// 尋找沒有搬遷的 bucket
		for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
			h.nevacuate++
		}
		
		// 現(xiàn)在 h.nevacuate 之前的 bucket 都被搬遷完畢
		
		// 所有的 buckets 搬遷完畢
		if h.nevacuate == newbit {
			// 清除老的 buckets
			h.oldbuckets = nil
			// 清除老的 overflow bucket
			// 回憶一下：[0] 表示當(dāng)前 overflow bucket
			// [1] 表示 old overflow bucket
			if h.extra != nil {
				h.extra.overflow[1] = nil
			}
			// 清除正在擴(kuò)容的標(biāo)志位
			h.flags &^= sameSizeGrow
		}
	}
}

evacuate 函數(shù)的代碼注釋非常清晰，對(duì)著代碼和注釋是很容易看懂整個(gè)的搬遷過程的，耐心點(diǎn)。

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

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

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

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

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

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

當(dāng)然，如果我就一個(gè) hard code 的 map，我也不會(huì)向 map 進(jìn)行插入刪除的操作，按理說(shuō)每次遍歷這樣的 map 都會(huì)返回一個(gè)固定順序的 key/value 序列吧。的確是這樣，但是 Go 杜絕了這種做法，因?yàn)檫@樣會(huì)給新手程序員帶來(lái)誤解，以為這是一定會(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ì)了。

多說(shuō)一句，“迭代 map 的結(jié)果是無(wú)序的”這個(gè)特性是從 go 1.0 開始加入的。

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

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

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

再來(lái)講搬遷函數(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í)就是我們說(shuō)的如果是擴(kuò)容到原來(lái)的 2 倍，桶的數(shù)量是原來(lái)的 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è)前面也說(shuō)得很詳細(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ì)算出來(lái)的哈希值不一樣！

你可能想到了，這樣帶來(lái)的一個(gè)后果是，這個(gè) key 是永遠(yuǎn)不會(huì)被 Get 操作獲取的！當(dāng)我使用 m[math.NaN()] 語(yǔ)句的時(shí)候，是查不出來(lái)結(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ò)容后是原來(lái) buckets 數(shù)量的 2 倍）。如果 tophash 的最低位是 0 ，分配到 X part；如果是 1 ，則分配到 Y part。

這是通過 tophash 值與新算出來(lái)的哈希值進(jìn)行運(yùn)算得到的：

if top&1 != 0 {
    // top hash 最低位為 1
    // 新算出來(lái)的 hash 值的 B 位置 1
	hash |= newbit
} else {
    // 新算出來(lái)的 hash 值的 B 位置 0
	hash &^= newbit
}

// hash 值的 B 位為 0，則搬遷到 x part
// 當(dāng) B = 5時(shí)，newbit = 32，二進(jìn)制低 6 位為 10 0000
useX = hash&newbit == 0

其實(shí)這樣的 key 我隨便搬遷到哪個(gè) bucket 都行，當(dāng)然，還是要搬遷到上面裂變那張圖中的兩個(gè) bucket 中去。但這樣做是有好處的，在后面講 map 迭代的時(shí)候會(huì)再詳細(xì)解釋，暫時(shí)知道是這樣分配的就行。

確定了要搬遷到的目標(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 位。

下面通過圖來(lái)宏觀地看一下擴(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ì)指向原來(lái)老的 []bmap，并且已經(jīng)搬遷完畢的 key 的 tophash 值會(huì)是一個(gè)狀態(tài)值，表示 key 的搬遷去向。

本來(lái) 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 
            
                     

                 

                                                                                                                    
                         GPU云服務(wù)器
                                             
                         云服務(wù)器
                                                                                                                                                 
                                      
                     
                    
                                                                                               深度之眼gpu租用
                                                                                                           深度學(xué)習(xí)入門之pytorch
                                                                                                           Go 語(yǔ)言
                                                                                                           Go語(yǔ)言
                                                         
                 
               
              
             
               

                   
 文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
                 
                   
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/6843.html
               
                      
               

                 
                                  
上一篇：前端面試每日 3+1 —— 第36天
  
                                                
                                       
下一篇：【Kafka】《Kafka權(quán)威指南》入門