由于本文篇幅較長，故将目錄整理如下
什麼是Map
維基百科的定義
In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.
說明：在計算機科學中，包含鍵值對（key-value）集合的抽象資料結構（關聯數組、符号表或字典），其每個可能的鍵在該集合中最多出現一次，這樣的資料結構就是一種Map。
操作
對Map的操作主要是增删改查：
- 在集合中增加鍵值對
- 在集合中移除鍵值對
- 修改某個存在的鍵值對
- 根據特定的鍵尋找對應的值
實作
Map的實作主要有兩種方式：哈希表（hash table）和搜尋樹（search tree）。例如Java中的hashMap是基于哈希表實作，而C++中的Map是基于一種平衡搜尋二叉樹——紅黑樹而實作的。以下是不同實作方式的時間複雜度對比。
可以看到，對于元素查找而言，二叉搜尋樹的平均和最壞效率都是O(log n)，哈希表實作的平均效率是O(1)，但最壞情況下能達到O(n)，不過如果哈希表設計優秀，最壞情況基本不會出現（是以，讀者不想知道Go是如何設計的Map嗎）。另外二叉搜尋樹傳回的key是有序的，而哈希表則是亂序。
哈希表
由于Go中map的基于哈希表（也被稱為散清單）實作，本文不探讨搜尋樹的map實作。以下是Go官方部落格對map的說明。
One of the most useful data structures in computer science is the hash table. Many hash table implementations exist with varying properties, but in general they offer fast lookups, adds, and deletes. Go provides a built-in map type that implements a hash table.
學習哈希表首先要了解兩個概念：哈希函數和哈希沖突。
哈希函數
哈希函數（常被稱為散列函數）是可以用于将任意大小的資料映射到固定大小值的函數，常見的包括MD5、SHA系列等。
一個設計優秀的哈希函數應該包含以下特性：
- 均勻性 ：一個好的哈希函數應該在其輸出範圍内盡可能均勻地映射，也就是說，應以大緻相同的機率生成輸出範圍内的每個哈希值。
- 效率高 ：哈希效率要高，即使很長的輸入參數也能快速計算出哈希值。
- 可确定性 ：哈希過程必須是确定性的，這意味着對于給定的輸入值，它必須始終生成相同的哈希值。
- 雪崩效應 ：微小的輸入值變化也會讓輸出值發生巨大的變化。
- 不可逆 ：從哈希函數的輸出值不可反向推導出原始的資料。
哈希沖突
重複一遍，哈希函數是将任意大小的資料映射到固定大小值的函數。那麼，我們可以預見到，即使哈希函數設計得足夠優秀，幾乎每個輸入值都能映射為不同的哈希值。但是，當輸入資料足夠大，大到能超過固定大小值的組合能表達的最大數量數，沖突将不可避免！（參見抽屜原理）
抽屜原理：桌上有十個蘋果，要把這十個蘋果放到九個抽屜裡，無論怎樣放，我們會發現至少會有一個抽屜裡面放不少于兩個蘋果。抽屜原理有時也被稱為鴿巢原理。
如何解決哈希沖突
比較常用的Has沖突解決方案有鍊位址法和開放尋址法。
在講鍊位址法之前，先說明兩個概念。
- 哈希桶。哈希桶（也稱為槽，類似于抽屜原理中的一個抽屜）可以先簡單了解為一個哈希值，所有的哈希值組成了哈希空間。
- 裝載因子。裝載因子是表示哈希表中元素的填滿程度。它的計算公式：裝載因子=填入哈希表中的元素個數/哈希表的長度。裝載因子越大，填入的元素越多，空間使用率就越高，但發生哈希沖突的幾率就變大。反之，裝載因子越小，填入的元素越少，沖突發生的幾率減小，但空間浪費也會變得更多，而且還會提高擴容操作的次數。裝載因子也是決定哈希表是否進行擴容的關鍵名額，在java的HashMap的中，其預設裝載因子為0.75；Python的dict預設裝載因子為2/3。
鍊位址法
鍊位址法的思想就是将映射在一個桶裡的所有元素用連結清單串起來。
下面以一個簡單的哈希函數 H(key) = key MOD 7（除數取餘法）對一組元素 [50, 700, 76, 85, 92, 73, 101] 進行映射，通過圖示來了解鍊位址法處理Hash沖突的處理邏輯。
鍊位址法解決沖突的方式與圖的鄰接表存儲方式在樣式上很相似，發生沖突，就用單連結清單組織起來。
開放尋址法
對于鍊位址法而言，槽位數m與鍵的數目n是沒有直接關系的。但是對于開放尋址法而言，所有的元素都是存儲在Hash表當中的，是以無論任何時候都要保證哈希表的槽位數m大于或等于鍵的資料n（必要時，需要對哈希表進行動态擴容）。
開放尋址法有多種方式：線性探測法、平方探測法、随機探測法和雙重哈希法。這裡以線性探測法來幫助讀者了解開放尋址法思想。
- 線性探測法
設
Hash(key)
表示關鍵字
key
的哈希值， 表示哈希表的槽位數（哈希表的大小）。
線性探測法則可以表示為：
如果
Hash(x) % M
已經有資料，則嘗試
(Hash(x) + 1) % M
;
如果
(Hash(x) + 1) % M
也有資料了，則嘗試
(Hash(x) + 2) % M
;
如果
(Hash(x) + 2) % M
也有資料了，則嘗試
(Hash(x) + 3) % M
;
......
我們同樣以哈希函數
H(key) = key MOD 7
（除數取餘法）對
[50, 700, 76, 85, 92, 73, 101]
進行映射，通過圖示來了解線性探測法處理 Hash 碰撞。
其中，empty代表槽位為空，occupied代表槽位已被占（後續映射到該槽，則需要線性向下繼續探測），而lazy delete則代表将槽位裡面的資料清除，并不釋放存儲空間。
兩種解決方案比較
對于開放尋址法而言，它隻有數組一種資料結構就可完成存儲，繼承了數組的優點，對CPU緩存友好，易于序列化操作。但是它對記憶體的使用率不如鍊位址法，且發生沖突時代價更高。當資料量明确、裝載因子小，适合采用開放尋址法。
連結清單節點可以在需要時再建立，不必像開放尋址法那樣事先申請好足夠記憶體，是以鍊位址法對于記憶體的使用率會比開方尋址法高。鍊位址法對裝載因子的容忍度會更高，并且适合存儲大對象、大資料量的哈希表。而且相較于開放尋址法，它更加靈活，支援更多的優化政策，比如可采用紅黑樹代替連結清單。但是鍊位址法需要額外的空間來存儲指針。
值得一提的是，在Python中dict在發生哈希沖突時采用的開放尋址法，而java的HashMap采用的是鍊位址法。
Go Map實作
同python與java一樣，Go語言中的map是也基于哈希表實作的，它解決哈希沖突的方式是鍊位址法，即通過使用數組+連結清單的資料結構來表達map。
注意：本文後續出現的map統一代指Go中實作的map類型。
map資料結構
map中的資料被存放于一個數組中的，數組的元素是桶（bucket），每個桶至多包含8個鍵值對資料。
哈希值低位（low-order bits）用于選擇桶，哈希值高位（high-order bits）用于在一個獨立的桶中差別出鍵。哈希值高低位示意圖如下
本文基于go 1.15.2 darwin/amd64分析，源碼位于src/runtime/map.go.
- map的結構體為hmap
// A header for a Go map.
type hmap struct {
count int // 代表哈希表中的元素個數，調用len(map)時，傳回的就是該字段值。
flags uint8 // 狀态标志，下文常量中會解釋四種狀态位含義。
B uint8 // buckets（桶）的對數log_2（哈希表元素數量最大可達到裝載因子*2^B）
noverflow uint16 // 溢出桶的大概數量。
hash0 uint32 // 哈希種子。
buckets unsafe.Pointer // 指向buckets數組的指針，數組大小為2^B，如果元素個數為0，它為nil。
oldbuckets unsafe.Pointer // 如果發生擴容，oldbuckets是指向老的buckets數組的指針，老的buckets數組大小是新的buckets的1/2。非擴容狀态下，它為nil。
nevacuate uintptr // 表示擴容進度，小于此位址的buckets代表已搬遷完成。
extra *mapextra // 這個字段是為了優化GC掃描而設計的。當key和value均不包含指針，并且都可以inline時使用。extra是指向mapextra類型的指針。
- mapextra的結構體
// mapextra holds fields that are not present on all maps.
type mapextra struct {
// 如果 key 和 value 都不包含指針，并且可以被 inline(<=128 位元組)
// 就使用 hmap的extra字段 來存儲 overflow buckets，這樣可以避免 GC 掃描整個 map
// 然而 bmap.overflow 也是個指針。這時候我們隻能把這些 overflow 的指針
// 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
// overflow 包含的是 hmap.buckets 的 overflow 的 buckets
// oldoverflow 包含擴容時的 hmap.oldbuckets 的 overflow 的 bucket
overflow *[]*bmap
oldoverflow *[]*bmap
// 指向空閑的 overflow bucket 的指針
nextOverflow *bmap
}
- bmap結構體
// A bucket for a Go map.
type bmap struct {
// tophash包含此桶中每個鍵的哈希值最高位元組（高8位）資訊（也就是前面所述的high-order bits）。
// 如果tophash[0] < minTopHash，tophash[0]則代表桶的搬遷（evacuation）狀态。
tophash [bucketCnt]uint8
}
bmap也就是bucket（桶）的記憶體模型圖解如下（相關代碼邏輯可檢視src/cmd/compile/internal/gc/reflect.go中的bmap()函數）。
在以上圖解示例中，該桶的第7位cell和第8位cell還未有對應鍵值對。需要注意的是，key和value是各自存儲起來的，并非想象中的key/value/key/value...的形式。這樣做雖然會讓代碼組織稍顯複雜，但是它的好處是能讓我們消除例如map[int64]int所需要的填充（padding）。此外，在8個鍵值對資料後面有一個overflow指針，因為桶中最多隻能裝8個鍵值對，如果有多餘的鍵值對落到了目前桶，那麼就需要再建構一個桶（稱為溢出桶），通過overflow指針連結起來。
- 重要常量标志
const (
// 一個桶中最多能裝載的鍵值對（key-value）的個數為8
bucketCntBits = 3
bucketCnt = 1 << bucketCntBits
// 觸發擴容的裝載因子為13/2=6.5
loadFactorNum = 13
loadFactorDen = 2
// 鍵和值超過128個位元組，就會被轉換為指針
maxKeySize = 128
maxElemSize = 128
// 資料偏移量應該是bmap結構體的大小，它需要正确地對齊。
// 對于amd64p32而言，這意味着：即使指針是32位的，也是64位對齊。
dataOffset = unsafe.Offsetof(struct {
b bmap
v int64
}{}.v)
// 每個桶（如果有溢出，則包含它的overflow的連結桶）在搬遷完成狀态（evacuated* states）下，要麼會包含它所有的鍵值對，要麼一個都不包含（但不包括調用evacuate()方法階段，該方法調用隻會在對map發起write時發生，在該階段其他goroutine是無法檢視該map的）。簡單的說，桶裡的資料要麼一起搬走，要麼一個都還未搬。
// tophash除了放置正常的高8位hash值，還會存儲一些特殊狀态值（标志該cell的搬遷狀态）。正常的tophash值，最小應該是5，以下列出的就是一些特殊狀态值。
emptyRest = 0 // 表示cell為空，并且比它高索引位的cell或者overflows中的cell都是空的。（初始化bucket時，就是該狀态）
emptyOne = 1 // 空的cell，cell已經被搬遷到新的bucket
evacuatedX = 2 // 鍵值對已經搬遷完畢，key在新buckets數組的前半部分
evacuatedY = 3 // 鍵值對已經搬遷完畢，key在新buckets數組的後半部分
evacuatedEmpty = 4 // cell為空，整個bucket已經搬遷完畢
minTopHash = 5 // tophash的最小正常值
// flags
iterator = 1 // 可能有疊代器在使用buckets
oldIterator = 2 // 可能有疊代器在使用oldbuckets
hashWriting = 4 // 有協程正在向map寫人key
sameSizeGrow = 8 // 等量擴容
// 用于疊代器檢查的bucket ID
noCheck = 1<<(8*sys.PtrSize) - 1
)
綜上，我們以B等于4為例，展示一個完整的map結構圖。
建立map
map初始化有以下兩種方式
make(map[k]v)
// 指定初始化map大小為hint
make(map[k]v, hint)
對于不指定初始化大小，和初始化值hint<=8（bucketCnt）時，go會調用makemap_small函數（源碼位置src/runtime/map.go），并直接從堆上進行配置設定。
func makemap_small() *hmap {
h := new(hmap)
h.hash0 = fastrand()
return h
}
當hint>8時，則調用makemap函數
// 如果編譯器認為map和第一個bucket可以直接建立在棧上，h和bucket可能都是非空
// 如果h != nil，那麼map可以直接在h中建立
// 如果h.buckets != nil，那麼h指向的bucket可以作為map的第一個bucket使用
func makemap(t *maptype, hint int, h *hmap) *hmap {
// math.MulUintptr傳回hint與t.bucket.size的乘積，并判斷該乘積是否溢出。
mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
// maxAlloc的值，根據平台系統的差異而不同，具體計算方式參照src/runtime/malloc.go
if overflow || mem > maxAlloc {
hint = 0
}
// initialize Hmap
if h == nil {
h = new(hmap)
}
// 通過fastrand得到哈希種子
h.hash0 = fastrand()
// 根據輸入的元素個數hint，找到能裝下這些元素的B值
B := uint8(0)
for overLoadFactor(hint, B) {
B++
}
h.B = B
// 配置設定初始哈希表
// 如果B為0，那麼buckets字段後續會在mapassign方法中lazily配置設定
if h.B != 0 {
var nextOverflow *bmap
// makeBucketArray建立一個map的底層儲存buckets的數組，它最少會配置設定h.B^2的大小。
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
配置設定buckets數組的makeBucketArray函數
// makeBucket為map建立用于儲存buckets的數組。
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
base := bucketShift(b)
nbuckets := base
// 對于小的b值（小于4），即桶的數量小于16時，使用溢出桶的可能性很小。對于此情況，就避免計算開銷。
if b >= 4 {
// 當桶的數量大于等于16個時，正常情況下就會額外建立2^(b-4)個溢出桶
nbuckets += bucketShift(b - 4)
sz := t.bucket.size * nbuckets
up := roundupsize(sz)
if up != sz {
nbuckets = up / t.bucket.size
}
}
// 這裡，dirtyalloc分兩種情況。如果它為nil，則會配置設定一個新的底層數組。如果它不為nil，則它指向的是曾經配置設定過的底層數組，該底層數組是由之前同樣的t和b參數通過makeBucketArray配置設定的，如果數組不為空，需要把該數組之前的資料清空并複用。
if dirtyalloc == nil {
buckets = newarray(t.bucket, int(nbuckets))
} else {
buckets = dirtyalloc
size := t.bucket.size * nbuckets
if t.bucket.ptrdata != 0 {
memclrHasPointers(buckets, size)
} else {
memclrNoHeapPointers(buckets, size)
}
}
// 即b大于等于4的情況下，會預配置設定一些溢出桶。
// 為了把跟蹤這些溢出桶的開銷降至最低，使用了以下約定：
// 如果預配置設定的溢出桶的overflow指針為nil，那麼可以通過指針碰撞（bumping the pointer）獲得更多可用桶。
// （關于指針碰撞：假設記憶體是絕對規整的，所有用過的記憶體都放在一邊，空閑的記憶體放在另一邊，中間放着一個指針作為分界點的訓示器，那所配置設定記憶體就僅僅是把那個指針向空閑空間那邊挪動一段與對象大小相等的距離，這種配置設定方式稱為“指針碰撞”）
// 對于最後一個溢出桶，需要一個安全的非nil指針指向它。
if base != nbuckets {
nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
last.setoverflow(t, (*bmap)(buckets))
}
return buckets, nextOverflow
}
根據上述代碼，我們能确定在正常情況下，正常桶和溢出桶在記憶體中的存儲空間是連續的，隻是被
hmap
中的不同字段引用而已。
哈希函數
在初始化go程式運作環境時（src/runtime/proc.go中的schedinit），就需要通過alginit方法完成對哈希的初始化。
func schedinit() {
lockInit(&sched.lock, lockRankSched)
...
tracebackinit()
moduledataverify()
stackinit()
mallocinit()
fastrandinit() // must run before mcommoninit
mcommoninit(_g_.m, -1)
cpuinit() // must run before alginit
// 這裡調用alginit()
alginit() // maps must not be used before this call
modulesinit() // provides activeModules
typelinksinit() // uses maps, activeModules
itabsinit() // uses activeModules
...
goargs()
goenvs()
parsedebugvars()
gcinit()
...
}
對于雜湊演算法的選擇，程式會根據目前架構判斷是否支援AES，如果支援就使用AES hash，其實作代碼位于src/runtime/asm_{386,amd64,arm64}.s中；若不支援，其hash算法則根據xxhash算法（https://code.google.com/p/xxhash/）和cityhash算法（https://code.google.com/p/cityhash/）啟發而來，代碼分别對應于32位（src/runtime/hash32.go）和64位機器（src/runtime/hash32.go）中，對這部分内容感興趣的讀者可以深入研究。
func alginit() {
// Install AES hash algorithms if the instructions needed are present.
if (GOARCH == "386" || GOARCH == "amd64") &&
cpu.X86.HasAES && // AESENC
cpu.X86.HasSSSE3 && // PSHUFB
cpu.X86.HasSSE41 { // PINSR{D,Q}
initAlgAES()
return
}
if GOARCH == "arm64" && cpu.ARM64.HasAES {
initAlgAES()
return
}
getRandomData((*[len(hashkey) * sys.PtrSize]byte)(unsafe.Pointer(&hashkey))[:])
hashkey[0] |= 1 // make sure these numbers are odd
hashkey[1] |= 1
hashkey[2] |= 1
hashkey[3] |= 1
}
上文在建立map的時候，我們可以知道map的哈希種子是通過h.hash0 = fastrand()得到的。它是在以下maptype中的hasher中被使用到，在下文内容中會看到hash值的生成。
type maptype struct {
typ _type
key *_type
elem *_type
bucket *_type
// hasher的第一個參數就是指向key的指針，h.hash0 = fastrand()得到的hash0，就是hasher方法的第二個參數。
// hasher方法傳回的就是hash值。
hasher func(unsafe.Pointer, uintptr) uintptr
keysize uint8 // size of key slot
elemsize uint8 // size of elem slot
bucketsize uint16 // size of bucket
flags uint32
}
map操作
假定key經過哈希計算後得到64bit位的哈希值。如果B=5，buckets數組的長度，即桶的數量是32（2的5次方）。
例如，現要置一key于map中，該key經過哈希後，得到的哈希值如下：
前面我們知道，哈希值低位（low-order bits）用于選擇桶，哈希值高位（high-order bits）用于在一個獨立的桶中差別出鍵。當B等于5時，那麼我們選擇的哈希值低位也是5位，即01010，它的十進制值為10，代表10号桶。再用哈希值的高8位，找到此key在桶中的位置。最開始桶中還沒有key，那麼新加入的key和value就會被放入第一個key空位和value空位。
注意：對于高低位的選擇，該操作的實質是取餘，但是取餘開銷很大，在實際代碼實作中采用的是位操作。以下是tophash的實作代碼。
func tophash(hash uintptr) uint8 {
top := uint8(hash >> (sys.PtrSize*8 - 8))
if top < minTopHash {
top += minTopHash
}
return top
}
當兩個不同的key落在了同一個桶中，這時就發生了哈希沖突。go的解決方式是鍊位址法：在桶中按照順序尋到第一個空位，若有位置，則将其置于其中；否則，判斷是否存在溢出桶，若有溢出桶，則去該桶的溢出桶中尋找空位，如果沒有溢出桶，則添加溢出桶，并将其置溢出桶的第一個空位（非擴容的情況）。
上圖中的B值為5，是以桶的數量為32。通過哈希函數計算出待插入key的哈希值，低5位哈希00110，對應于6号桶；高8位10010111，十進制為151，由于桶中前6個cell已經有正常哈希值填充了(周遊)，是以将151對應的高位哈希值放置于第7位cell，對應将key和value分别置于相應的第七個空位。
如果是查找key，那麼我們會根據高位哈希值去桶中的每個cell中找，若在桶中沒找到，并且overflow不為nil，那麼繼續去溢出桶中尋找，直至找到，如果所有的cell都找過了，還未找到，則傳回key類型的預設值（例如key是int類型，則傳回0）。
查找key
對于map的元素查找，其源碼實作如下
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// 如果開啟了競态檢測 -race
if raceenabled && h != nil {
callerpc := getcallerpc()
pc := funcPC(mapaccess1)
racereadpc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.key, key, callerpc, pc)
}
// 如果開啟了memory sanitizer -msan
if msanenabled && h != nil {
msanread(key, t.key.size)
}
// 如果map為空或者元素個數為0，傳回零值
if h == nil || h.count == 0 {
if t.hashMightPanic() {
t.hasher(key, 0) // see issue 23734
}
return unsafe.Pointer(&zeroVal[0])
}
// 注意，這裡是按位與操作
// 當h.flags對應的值為hashWriting（代表有其他goroutine正在往map中寫key）時，那麼位計算的結果不為0，是以抛出以下錯誤。
// 這也表明，go的map是非并發安全的
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
// 不同類型的key，會使用不同的hash算法，可詳見src/runtime/alg.go中typehash函數中的邏輯
hash := t.hasher(key, uintptr(h.hash0))
m := bucketMask(h.B)
// 按位與操作，找到對應的bucket
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
// 如果oldbuckets不為空，那麼證明map發生了擴容
// 如果有擴容發生，老的buckets中的資料可能還未搬遷至新的buckets裡
// 是以需要先在老的buckets中找
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
m >>= 1
}
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
// 如果在oldbuckets中tophash[0]的值，為evacuatedX、evacuatedY，evacuatedEmpty其中之一
// 則evacuated()傳回為true，代表搬遷完成。
// 是以，隻有當搬遷未完成時，才會從此oldbucket中周遊
if !evacuated(oldb) {
b = oldb
}
}
// 取出目前key值的tophash值
top := tophash(hash)
// 以下是查找的核心邏輯
// 雙重循環周遊：外層循環是從桶到溢出桶周遊；内層是桶中的cell周遊
// 跳出循環的條件有三種：第一種是已經找到key值；第二種是目前桶再無溢出桶；
// 第三種是目前桶中有cell位的tophash值是emptyRest，這個值在前面解釋過，它代表此時的桶後面的cell還未利用，是以無需再繼續周遊。
bucketloop:
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
// 判斷tophash值是否相等
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
// 因為在bucket中key是用連續的存儲空間存儲的，是以可以通過bucket位址+資料偏移量（bmap結構體的大小）+ keysize的大小，得到k的位址
// 同理，value的位址也是相似的計算方法，隻是再要加上8個keysize的記憶體位址
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
// 判斷key是否相等
if t.key.equal(key, k) {
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
if t.indirectelem() {
e = *((*unsafe.Pointer)(e))
}
return e
}
}
}
// 所有的bucket都未找到，則傳回零值
return unsafe.Pointer(&zeroVal[0])
}
以下是mapaccess1的查找過程圖解
map的元素查找，對應go代碼有兩種形式
// 形式一
v := m[k]
// 形式二
v, ok := m[k]
形式一的代碼實作，就是上述的mapaccess1方法。此外，在源碼中還有個mapaccess2方法，它的函數簽名如下。
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {}
與mapaccess1相比，mapaccess2多了一個bool類型的傳回值，它代表的是是否在map中找到了對應的key。因為和mapaccess1基本一緻，是以詳細代碼就不再貼出。
同時，源碼中還有mapaccessK方法，它的函數簽名如下。
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {}
與mapaccess1相比，mapaccessK同時傳回了key和value，其代碼邏輯也一緻。
指派key
對于寫入key的邏輯，其源碼實作如下
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// 如果h是空指針，指派會引起panic
// 例如以下語句
// var m map[string]int
// m["k"] = 1
if h == nil {
panic(plainError("assignment to entry in nil map"))
}
// 如果開啟了競态檢測 -race
if raceenabled {
callerpc := getcallerpc()
pc := funcPC(mapassign)
racewritepc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.key, key, callerpc, pc)
}
// 如果開啟了memory sanitizer -msan
if msanenabled {
msanread(key, t.key.size)
}
// 有其他goroutine正在往map中寫key，會抛出以下錯誤
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}
// 通過key和哈希種子，算出對應哈希值
hash := t.hasher(key, uintptr(h.hash0))
// 将flags的值與hashWriting做按位或運算
// 因為在目前goroutine可能還未完成key的寫入，再次調用t.hasher會發生panic。
h.flags ^= hashWriting
if h.buckets == nil {
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
again:
// bucketMask傳回值是2的B次方減1
// 是以，通過hash值與bucketMask傳回值做按位與操作，傳回的在buckets數組中的第幾号桶
bucket := hash & bucketMask(h.B)
// 如果map正在搬遷（即h.oldbuckets != nil）中,則先進行搬遷工作。
if h.growing() {
growWork(t, h, bucket)
}
// 計算出上面求出的第幾号bucket的記憶體位置
// post = start + bucketNumber * bucketsize
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
top := tophash(hash)
var inserti *uint8
var insertk unsafe.Pointer
var elem unsafe.Pointer
bucketloop:
for {
// 周遊桶中的8個cell
for i := uintptr(0); i < bucketCnt; i++ {
// 這裡分兩種情況，第一種情況是cell位的tophash值和目前tophash值不相等
// 在 b.tophash[i] != top 的情況下
// 理論上有可能會是一個空槽位
// 一般情況下 map 的槽位分布是這樣的，e 表示 empty:
// [h0][h1][h2][h3][h4][e][e][e]
// 但在執行過 delete 操作時，可能會變成這樣:
// [h0][h1][e][e][h5][e][e][e]
// 是以如果再插入的話，會盡量往前面的位置插
// [h0][h1][e][e][h5][e][e][e]
// ^
// ^
// 這個位置
// 是以在循環的時候還要順便把前面的空位置先記下來
// 因為有可能在後面會找到相等的key，也可能找不到相等的key
if b.tophash[i] != top {
// 如果cell位為空，那麼就可以在對應位置進行插入
if isEmpty(b.tophash[i]) && inserti == nil {
inserti = &b.tophash[i]
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
}
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
// 第二種情況是cell位的tophash值和目前的tophash值相等
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
// 注意，即使目前cell位的tophash值相等，不一定它對應的key也是相等的，是以還要做一個key值判斷
if !t.key.equal(key, k) {
continue
}
// 如果已經有該key了，就更新它
if t.needkeyupdate() {
typedmemmove(t.key, k, key)
}
// 這裡擷取到了要插入key對應的value的記憶體位址
// pos = start + dataOffset + 8*keysize + i*elemsize
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
// 如果順利到這，就直接跳到done的結束邏輯中去
goto done
}
// 如果桶中的8個cell周遊完，還未找到對應的空cell或覆寫cell，那麼就進入它的溢出桶中去周遊
ovf := b.overflow(t)
// 如果連溢出桶中都沒有找到合适的cell，跳出循環。
if ovf == nil {
break
}
b = ovf
}
// 在已有的桶和溢出桶中都未找到合适的cell供key寫入，那麼有可能會觸發以下兩種情況
// 情況一：
// 判斷目前map的裝載因子是否達到設定的6.5門檻值，或者目前map的溢出桶數量是否過多。如果存在這兩種情況之一，則進行擴容操作。
// hashGrow()實際并未完成擴容，對哈希表資料的搬遷（複制）操作是通過growWork()來完成的。
// 重新跳入again邏輯，在進行完growWork()操作後，再次周遊新的桶。
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
}
// 情況二：
// 在不滿足情況一的條件下，會為目前桶再建立溢出桶，并将tophash，key插入到建立溢出桶的對應記憶體的0号位置
if inserti == nil {
// all current buckets are full, allocate a new one.
newb := h.newoverflow(t, b)
inserti = &newb.tophash[0]
insertk = add(unsafe.Pointer(newb), dataOffset)
elem = add(insertk, bucketCnt*uintptr(t.keysize))
}
// 在插入位置存入新的key和value
if t.indirectkey() {
kmem := newobject(t.key)
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
if t.indirectelem() {
vmem := newobject(t.elem)
*(*unsafe.Pointer)(elem) = vmem
}
typedmemmove(t.key, insertk, key)
*inserti = top
// map中的key數量+1
h.count++
done:
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
h.flags &^= hashWriting
if t.indirectelem() {
elem = *((*unsafe.Pointer)(elem))
}
return elem
}
通過對mapassign的代碼分析之後，發現該函數并沒有将插入key對應的value寫入對應的記憶體，而是傳回了value應該插入的記憶體位址。為了弄清楚value寫入記憶體的操作是發生在什麼時候，分析如下map.go代碼。
package main
func main() {
m := make(map[int]int)
for i := 0; i < 100; i++ {
m[i] = 666
}
}
m[i] = 666對應的彙編代碼
$ go tool compile -S map.go
...
0x0098 00152 (map.go:6) LEAQ type.map[int]int(SB), CX
0x009f 00159 (map.go:6) MOVQ CX, (SP)
0x00a3 00163 (map.go:6) LEAQ ""..autotmp_2+184(SP), DX
0x00ab 00171 (map.go:6) MOVQ DX, 8(SP)
0x00b0 00176 (map.go:6) MOVQ AX, 16(SP)
0x00b5 00181 (map.go:6) CALL runtime.mapassign_fast64(SB) // 調用函數runtime.mapassign_fast64，該函數實質就是mapassign（上文示例源代碼是該mapassign系列的通用邏輯）
0x00ba 00186 (map.go:6) MOVQ 24(SP), AX 24(SP), AX // 傳回值，即 value 應該存放的記憶體位址
0x00bf 00191 (map.go:6) MOVQ $666, (AX) // 把 666 放入該位址中
...
指派的最後一步實際上是編譯器額外生成的彙編指令來完成的，可見靠 runtime 有些工作是沒有做完的。是以，在go中，編譯器和 runtime 配合，才能完成一些複雜的工作。同時說明，在平時學習go的源代碼實作時，必要時還需要看一些彙編代碼。
删除key
了解了指派key的邏輯，删除key的邏輯就比較簡單了。本文就不再讨論該部分内容了，讀者感興趣可以自行檢視src/runtime/map.go的mapdelete方法邏輯。
周遊map
結論：疊代 map 的結果是無序的m := make(map[int]int)
for i := 0; i < 10; i++ {
m[i] = i
}
for k, v := range m {
fmt.Println(k, v)
}
運作以上代碼，我們會發現每次輸出順序都是不同的。
map周遊的過程，是按序周遊bucket，同時按需周遊bucket中和其overflow bucket中的cell。但是map在擴容後，會發生key的搬遷，這造成原來落在一個bucket中的key，搬遷後，有可能會落到其他bucket中了，從這個角度看，周遊map的結果就不可能是按照原來的順序了（詳見下文的map擴容内容）。
但其實，go為了保證周遊map的結果是無序的，做了以下事情：map在周遊時，并不是從固定的0号bucket開始周遊的，每次周遊，都會從一個
随機值序号的bucket，再從其中
随機的cell開始周遊。然後再按照桶序周遊下去，直到回到起始桶結束。
上圖的例子，是周遊一個處于未擴容狀态的map。如果map正處于擴容狀态時，需要先判斷目前周遊bucket是否已經完成搬遷，如果資料還在老的bucket，那麼就去老bucket中拿資料。
注意：在下文中會講解到增量擴容和等量擴容。當發生了增量擴容時，一個老的bucket資料可能會分裂到兩個不同的bucket中去，那麼此時，如果需要從老的bucket中周遊資料，例如1号，則不能将老1号bucket中的資料全部取出，僅僅隻能取出老 1 号 bucket 中那些在裂變之後，配置設定到新 1 号 bucket 中的那些 key（這個内容，請讀者看完下文map擴容的講解之後再回頭了解）。
鑒于篇幅原因，本文不再對map周遊的詳細源碼進行注釋貼出。讀者可自行檢視源碼src/runtime/map.go的
mapiterinit()
和
mapiternext()
方法邏輯。
這裡注釋一下
mapiterinit()
中随機保證的關鍵代碼
// 生成随機數
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
r += uintptr(fastrand()) << 31
}
// 決定了從哪個随機的bucket開始
it.startBucket = r & bucketMask(h.B)
// 決定了每個bucket中随機的cell的位置
it.offset = uint8(r >> h.B & (bucketCnt - 1))
map擴容
在文中講解裝載因子時，我們提到裝載因子是決定哈希表是否進行擴容的關鍵名額。在go的map擴容中，除了裝載因子會決定是否需要擴容，溢出桶的數量也是擴容的另一關鍵名額。
為了保證通路效率，當map将要添加、修改或删除key時，都會檢查是否需要擴容，擴容實際上是以空間換時間的手段。在之前源碼mapassign中，其實已經注釋map擴容條件，主要是兩點:
- 判斷已經達到裝載因子的臨界點，即元素個數 >= 桶（bucket）總數 * 6.5，這時候說明大部分的桶可能都快滿了（即平均每個桶存儲的鍵值對達到6.5個），如果插入新元素，有大機率需要挂在溢出桶（overflow bucket）上。
func overLoadFactor(count int, B uint8) bool {
return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
- 判斷溢出桶是否太多，當桶總數 < 2 ^ 15 時，如果溢出桶總數 >= 桶總數，則認為溢出桶過多。當桶總數 >= 2 ^ 15 時，直接與 2 ^ 15 比較，當溢出桶總數 >= 2 ^ 15 時，即認為溢出桶太多了。
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
if B > 15 {
B = 15
}
return noverflow >= uint16(1)<<(B&15)
}
對于第2點，其實算是對第 1 點的補充。因為在裝載因子比較小的情況下，有可能 map 的查找和插入效率也很低，而第 1 點識别不出來這種情況。表面現象就是計算裝載因子的分子比較小，即 map 裡元素總數少，但是桶數量多（真實配置設定的桶數量多，包括大量的溢出桶）。
在某些場景下，比如不斷的增删，這樣會造成overflow的bucket數量增多，但負載因子又不高，未達不到第 1 點的臨界值，就不能觸發擴容來緩解這種情況。這樣會造成桶的使用率不高，值存儲得比較稀疏，查找插入效率會變得非常低，是以有了第 2 點判斷名額。這就像是一座空城，房子很多，但是住戶很少，都分散了，找起人來很困難。
如上圖所示，由于對map的不斷增删，以0号bucket為例，該桶鍊中就造成了大量的稀疏桶。
兩種情況官方采用了不同的解決方案
- 針對 1，将 B + 1，建立一個buckets數組，新的buckets大小是原來的2倍，然後舊buckets資料搬遷到新的buckets。該方法我們稱之為 增量擴容 。
- 針對 2，并不擴大容量，buckets數量維持不變，重新做一遍類似增量擴容的搬遷動作，把松散的鍵值對重新排列一次，以使bucket的使用率更高，進而保證更快的存取。該方法我們稱之為 等量擴容 。
對于 2 的解決方案，其實存在一個極端的情況：如果插入 map 的 key 哈希都一樣，那麼它們就會落到同一個 bucket 裡，超過 8 個就會産生 overflow bucket，結果也會造成 overflow bucket 數過多。移動元素其實解決不了問題，因為這時整個哈希表已經退化成了一個連結清單，操作效率變成了
O(n)
。但 Go 的每一個 map 都會在初始化階段的 makemap時定一個随機的哈希種子，是以要構造這種沖突是沒那麼容易的。
在源碼中，和擴容相關的主要是
hashGrow()
函數與
growWork()
函數。
hashGrow()
函數實際上并沒有真正地“搬遷”，它隻是配置設定好了新的 buckets，并将老的 buckets 挂到了 oldbuckets 字段上。真正搬遷 buckets 的動作在
growWork()
函數中，而調用
growWork()
函數的動作是在
mapassign()
和
mapdelete()
函數中。也就是插入（包括修改）、删除 key 的時候，都會嘗試進行搬遷 buckets 的工作。它們會先檢查 oldbuckets 是否搬遷完畢（檢查 oldbuckets 是否為 nil），再決定是否進行搬遷工作。
hashGrow()
函數
func hashGrow(t *maptype, h *hmap) {
// 如果達到條件 1，那麼将B值加1，相當于是原來的2倍
// 否則對應條件 2，進行等量擴容，是以 B 不變
bigger := uint8(1)
if !overLoadFactor(h.count+1, h.B) {
bigger = 0
h.flags |= sameSizeGrow
}
// 記錄老的buckets
oldbuckets := h.buckets
// 申請新的buckets空間
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
// 注意&^ 運算符，這塊代碼的邏輯是轉移标志位
flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
flags |= oldIterator
}
// 送出grow (atomic wrt gc)
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets
h.buckets = newbuckets
// 搬遷進度為0
h.nevacuate = 0
// overflow buckets 數為0
h.noverflow = 0
// 如果發現hmap是通過extra字段 來存儲 overflow buckets時
if h.extra != nil && h.extra.overflow != nil {
if h.extra.oldoverflow != nil {
throw("oldoverflow is not nil")
}
h.extra.oldoverflow = h.extra.overflow
h.extra.overflow = nil
}
if nextOverflow != nil {
if h.extra == nil {
h.extra = new(mapextra)
}
h.extra.nextOverflow = nextOverflow
}
}
growWork()
函數
func growWork(t *maptype, h *hmap, bucket uintptr) {
// 為了确認搬遷的 bucket 是我們正在使用的 bucket
// 即如果目前key映射到老的bucket1，那麼就搬遷該bucket1。
evacuate(t, h, bucket&h.oldbucketmask())
// 如果還未完成擴容工作，則再搬遷一個bucket。
if h.growing() {
evacuate(t, h, h.nevacuate)
}
}
從
growWork()
函數可以知道，搬遷的核心邏輯是
evacuate()
函數。這裡讀者可以思考一個問題：為什麼每次至多搬遷2個bucket？這其實是一種性能考量，如果map存儲了數以億計的key-value，一次性搬遷将會造成比較大的延時，是以才采用逐漸搬遷政策。
在講解該邏輯之前，需要讀者先了解以下兩個知識點。
- 知識點1：bucket序号的變化
前面講到，增量擴容（條件1）和等量擴容（條件2）都需要進行bucket的搬遷工作。對于等量擴容而言，由于buckets的數量不變，是以可以按照序号來搬遷。例如老的的0号bucket，仍然搬至新的0号bucket中。
但是，對于增量擴容而言，就會有所不同。例如原來的B=5，那麼增量擴容時，B就會變成6。那麼決定key值落入哪個bucket的低位哈希值就會發生變化（從取5位變為取6位），取新的低位hash值得過程稱為rehash。
是以，在增量擴容中，某個 key 在搬遷前後 bucket 序号可能和原來相等，也可能是相比原來加上 2^B（原來的 B 值），取決于低 hash 值第倒數第B+1位是 0 還是 1。
如上圖所示，當原始的B = 3時，舊buckets數組長度為8，在編号為2的bucket中，其2号cell和5号cell，它們的低3位哈希值相同（不相同的話，也就不會落在同一個桶中了），但是它們的低4位分别是0010、1010。當發生了增量擴容，2号就會被搬遷到新buckets數組的2号bucket中去，5号被搬遷到新buckets數組的10号bucket中去，它們的桶号差距是2的3次方。
- 知識點2：确定搬遷區間
在源碼中，有bucket x 和bucket y的概念，其實就是增量擴容到原來的 2 倍，桶的數量是原來的 2 倍，前一半桶被稱為bucket x，後一半桶被稱為bucket y。一個 bucket 中的 key 可能會分裂到兩個桶中去，分别位于bucket x的桶，或bucket y中的桶。是以在搬遷一個 cell 之前，需要知道這個 cell 中的 key 是落到哪個區間（而對于同一個桶而言，搬遷到bucket x和bucket y桶序号的差别是老的buckets大小，即2^old_B）。
這裡留一個問題：為什麼确定key落在哪個區間很重要？
确定了要搬遷到的目标 bucket 後，搬遷操作就比較好進行了。将源 key/value 值 copy 到目的地相應的位置。設定 key 在原始 buckets 的 tophash 為
evacuatedX
或是
evacuatedY
，表示已經搬遷到了新 map 的bucket x或是bucket y，新 map 的 tophash 則正常取 key 哈希值的高 8 位。
下面正式解讀搬遷核心代碼
evacuate()
函數。
evacuate()
函數
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
// 首先定位老的bucket的位址
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
// newbit代表擴容之前老的bucket個數
newbit := h.noldbuckets()
// 判斷該bucket是否已經被搬遷
if !evacuated(b) {
// 官方TODO，後續版本也許會實作
// TODO: reuse overflow buckets instead of using new ones, if there
// is no iterator using the old buckets. (If !oldIterator.)
// xy 包含了高低區間的搬遷目的地記憶體資訊
// x.b 是對應的搬遷目的桶
// x.k 是指向對應目的桶中存儲目前key的記憶體位址
// x.e 是指向對應目的桶中存儲目前value的記憶體位址
var xy [2]evacDst
x := &xy[0]
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))
// 隻有當增量擴容時才計算bucket y的相關資訊（和後續計算useY相呼應）
if !h.sameSizeGrow() {
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))
}
// evacuate 函數每次隻完成一個 bucket 的搬遷工作，是以要周遊完此 bucket 的所有的 cell，将有值的 cell copy 到新的地方。
// bucket 還會連結 overflow bucket，它們同樣需要搬遷。
// 是以同樣會有 2 層循環，外層周遊 bucket 和 overflow bucket，内層周遊 bucket 的所有 cell。
// 周遊目前桶bucket和其之後的溢出桶overflow bucket
// 注意：初始的b是待搬遷的老bucket
for ; b != nil; b = b.overflow(t) {
k := add(unsafe.Pointer(b), dataOffset)
e := add(k, bucketCnt*uintptr(t.keysize))
// 周遊桶中的cell，i，k，e分别用于對應tophash，key和value
for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
top := b.tophash[i]
// 如果目前cell的tophash值是emptyOne或者emptyRest，則代表此cell沒有key。并将其标記為evacuatedEmpty，表示它“已經被搬遷”。
if isEmpty(top) {
b.tophash[i] = evacuatedEmpty
continue
}
// 正常不會出現這種情況
// 未被搬遷的 cell 隻可能是emptyOne、emptyRest或是正常的 top hash（大于等于 minTopHash）
if top < minTopHash {
throw("bad map state")
}
k2 := k
// 如果 key 是指針，則解引用
if t.indirectkey() {
k2 = *((*unsafe.Pointer)(k2))
}
var useY uint8
// 如果是增量擴容
if !h.sameSizeGrow() {
// 計算哈希值，判斷目前key和vale是要被搬遷到bucket x還是bucket y
hash := t.hasher(k2, uintptr(h.hash0))
if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
// 有一個特殊情況：有一種 key，每次對它計算 hash，得到的結果都不一樣。
// 這個 key 就是 math.NaN() 的結果，它的含義是 not a number，類型是 float64。
// 當它作為 map 的 key時，會遇到一個問題：再次計算它的哈希值和它當初插入 map 時的計算出來的哈希值不一樣！
// 這個 key 是永遠不會被 Get 操作擷取的！當使用 m[math.NaN()] 語句的時候，是查不出來結果的。
// 這個 key 隻有在周遊整個 map 的時候，才能被找到。
// 并且，可以向一個 map 插入多個數量的 math.NaN() 作為 key，它們并不會被互相覆寫。
// 當搬遷碰到 math.NaN() 的 key 時，隻通過 tophash 的最低位決定配置設定到 X part 還是 Y part（如果擴容後是原來 buckets 數量的 2 倍）。如果 tophash 的最低位是 0 ，配置設定到 X part；如果是 1 ，則配置設定到 Y part。
useY = top & 1
top = tophash(hash)
// 對于正常key，進入以下else邏輯
} else {
if hash&newbit != 0 {
useY = 1
}
}
}
if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
throw("bad evacuatedN")
}
// evacuatedX + 1 == evacuatedY
b.tophash[i] = evacuatedX + useY
// useY要麼為0，要麼為1。這裡就是選取在bucket x的起始記憶體位置，或者選擇在bucket y的起始記憶體位置（隻有增量同步才會有這個選擇可能）。
dst := &xy[useY]
// 如果目的地的桶已經裝滿了（8個cell），那麼需要建立一個溢出桶，繼續搬遷到溢出桶上去。
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
// 如果待搬遷的key是指針，則複制指針過去
if t.indirectkey() {
*(*unsafe.Pointer)(dst.k) = k2 // copy pointer
// 如果待搬遷的key是值，則複制值過去
} else {
typedmemmove(t.key, dst.k, k) // copy elem
}
// value和key同理
if t.indirectelem() {
*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
} else {
typedmemmove(t.elem, dst.e, e)
}
// 将目前搬遷目的桶的記錄key/value的索引值（也可以了解為cell的索引值）加一
dst.i++
// 由于桶的記憶體布局中在最後還有overflow的指針，多以這裡不用擔心更新有可能會超出key和value數組的指針位址。
dst.k = add(dst.k, uintptr(t.keysize))
dst.e = add(dst.e, uintptr(t.elemsize))
}
}
// 如果沒有協程在使用老的桶，就對老的桶進行清理，用于幫助gc
if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
// 隻清除bucket 的 key,value 部分，保留 top hash 部分，訓示搬遷狀态
ptr := add(b, dataOffset)
n := uintptr(t.bucketsize) - dataOffset
memclrHasPointers(ptr, n)
}
}
// 用于更新搬遷進度
if oldbucket == h.nevacuate {
advanceEvacuationMark(h, t, newbit)
}
}
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
// 搬遷桶的進度加一
h.nevacuate++
// 實驗表明，1024至少會比newbit高出一個數量級（newbit代表擴容之前老的bucket個數）。是以，用目前進度加上1024用于確定O(1)行為。
stop := h.nevacuate + 1024
if stop > newbit {
stop = newbit
}
// 計算已經搬遷完的桶數
for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
h.nevacuate++
}
// 如果h.nevacuate == newbit，則代表所有的桶都已經搬遷完畢
if h.nevacuate == newbit {
// 搬遷完畢，是以指向老的buckets的指針置為nil
h.oldbuckets = nil
// 在講解hmap的結構中，有過說明。如果key和value均不包含指針，則都可以inline。
// 那麼儲存它們的buckets數組其實是挂在hmap.extra中的。是以，這種情況下，其實我們是搬遷的extra的buckets數組。
// 是以，在這種情況下，需要在搬遷完畢後，将hmap.extra.oldoverflow指針置為nil。
if h.extra != nil {
h.extra.oldoverflow = nil
}
// 最後，清除正在擴容的标志位，擴容完畢。
h.flags &^= sameSizeGrow
}
}
代碼比較長，但是文中注釋已經比較清晰了，如果對map的擴容還不清楚，可以參見以下圖解。
針對上圖的map，其B為3，是以原始buckets數組為8。當map元素數變多，加載因子超過6.5，是以引起了增量擴容。
以3号bucket為例，可以看到，由于B值加1，是以在新選取桶時，需要取低4位哈希值，這樣就會造成cell會被搬遷到新buckets數組中不同的桶（3号或11号桶）中去。注意，在一個桶中，搬遷cell的工作是有序的：它們是依序填進對應新桶的cell中去的。
當然，實際情況中3号桶很可能還有溢出桶，在這裡為了簡化繪圖，假設3号桶沒有溢出桶，如果有溢出桶，則相應地添加到新的3号桶和11号桶中即可，如果對應的3号和11号桶均裝滿，則給新的桶添加溢出桶來裝載。
對于上圖的map，其B也為3。假設整個map中的overflow過多，觸發了等量擴容。注意，等量擴容時，新的buckets數組大小和舊buckets數組是一樣的。
以6号桶為例，它有一個bucket和3個overflow buckets，但是我們能夠發現桶裡的資料非常稀疏，等量擴容的目的就是為了把松散的鍵值對重新排列一次，以使bucket的使用率更高，進而保證更快的存取。搬遷完畢後，新的6号桶中隻有一個基礎bucket，暫時并不需要溢出桶。這樣，和原6号桶相比，資料變得緊密，使後續的資料存取變快。
最後回答一下上文中留下的問題：為什麼确定key落在哪個區間很重要？因為對于增量擴容而言，原本一個bucket中的key會被分裂到兩個bucket中去，它們分别處于bucket x和bucket y中，但是它們之間存在關系 bucket x + 2^B = bucket y （其中，B是老bucket對應的B值）。假設key所在的老bucket序号為n，那麼如果key落在新的bucket x，則它應該置入 bucket x起始位置 + n*bucket 的記憶體中去；如果key落在新的bucket y，則它應該置入 bucket y起始位置 + n*bucket的記憶體中去。是以，确定key落在哪個區間，這樣就很友善進行記憶體位址計算，快速找到key應該插入的記憶體位址。
總結
Go語言的map，底層是哈希表實作的，通過鍊位址法解決哈希沖突，它依賴的核心資料結構是數組加連結清單。
map中定義了2的B次方個桶，每個桶中能夠容納8個key。根據key的不同哈希值，将其散落到不同的桶中。哈希值的低位（哈希值的後B個bit位）決定桶序号，高位（哈希值的前8個bit位）辨別同一個桶中的不同 key。
當向桶中添加了很多 key，造成元素過多，超過了裝載因子所設定的程度，或者多次增删操作，造成溢出桶過多，均會觸發擴容。
擴容分為增量擴容和等量擴容。增量擴容，會增加桶的個數（增加一倍），把原來一個桶中的 keys 被重新配置設定到兩個桶中。等量擴容，不會更改桶的個數，隻是會将桶中的資料變得緊湊。不管是增量擴容還是等量擴容，都需要建立新的桶數組，并不是原地操作的。
擴容過程是漸進性的，主要是防止一次擴容需要搬遷的 key 數量過多，引發性能問題。觸發擴容的時機是增加了新元素， 桶搬遷的時機則發生在指派、删除期間，每次最多搬遷兩個 桶。查找、指派、删除的一個很核心的内容是如何定位到 key 所在的位置，需要重點了解。一旦了解，關于 map 的源碼就可以看懂了。
使用建議
從map設計可以知道，它并不是一個并發安全的資料結構。同時對map進行讀寫時，程式很容易出錯。是以，要想在并發情況下使用map，請加上鎖（sync.Mutex或者sync.RwMutex）。其實，Go标準庫中已經為我們實作了并發安全的map——sync.Map，我之前寫過文章對它的實作進行講解，詳情可以檢視公号：Golang技術分享——《深入了解sync.Map》一文。
周遊map的結果是無序的，在使用中，應該注意到該點。
通過map的結構體可以知道，它其實是通過指針指向底層buckets數組。是以和slice一樣，盡管go函數都是值傳遞，但是，當map作為參數被函數調用時，在函數内部對map的操作同樣會影響到外部的map。
另外，有個特殊的key值math.NaN，它每次生成的哈希值是不一樣的，這會造成m[math.NaN]是拿不到值的，而且多次對它指派，會讓map中存在多個math.NaN的key。不過這個基本用不到，知道有這個特殊情況就可以了。
參考連結
https://en.wikipedia.org/wiki/Associative_array
https://blog.golang.org/maps
https://mp.weixin.qq.com/s/OHROn0ya_nWR6qkaSFmacw
https://www.cse.cuhk.edu.hk/irwin.king/_media/teaching/csc2100b/tu6.pdf
https://github.com/cch123/golang-notes/blob/master/map.md
https://zhuanlan.zhihu.com/p/66676224
https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/
https://github.com/talkgo/night/issues/332
https://my.oschina.net/renhc/blog/2208417