1. map的使用
golang中的map是一種數據類型，將鍵與值綁定到一起，底層是用哈希表實現的，可以快速的通過鍵找到對應的值。
類型表示：map[keyType][valueType] key一定要是可比較的類型（可以理解為支持==的操作），value可以是任意類型。
初始化：map只能使用make來初始化，聲明的時候默認為一個為nil的map，此時進行取值，返回的是對應類型的零值（不存在也是返回零值）。添加元素無任何意義，還會導致運行時錯誤。向未初始化的map賦值引起 panic: assign to entry in nil map。
1 package main
2
3 import (
4 "fmt"
5 )
6
7 // bool 的零值是false
8 var m map[int]bool
9 a, ok := m[1]
10 fmt.Println(a, ok) // false false
11
12 // int 的零值是0
13 var m map[int]int
14 a, ok := m[1]
15 fmt.Println(a, ok) // 0 false
16
17
18 func main() {
19 var agemap[string]int
20 if age== nil {
21 fmt.Println("map is nil.")
22 age= make(map[string]int)
23 }
24 }
清空map：對於一個有一定數據的集合 exp，清空的辦法就是再次初始化: exp = make(map[string]int)，如果後期不再使用該map，則可以直接：exp= nil 即可，但是如果還需要重複使用，則必須進行make初始化，否則無法為nil的map添加任何內容。
屬性：與切片一樣，map 是引用類型。當一個 map 賦值給一個新的變量，它們都指向同一個內部數據結構。因此改變其中一個也會反映到另一個。作為形參或返回參數的時候，傳遞的是地址的拷貝，擴容時也不會改變這個地址。
1 func main() {
2 exp := map[string]int{
3 "steve": 20,
4 "jamie": 80,
5 }
6 fmt.Println("Ori exp", age)
7 newexp:= exp
8 newexp["steve"] = 18
9 fmt.Println("exp changed", exp)
10 }
11
12 //Ori age map[steve:20 jamie:80]
13 //age changed map[steve:18 jamie:80]
遍歷map：map本身是無序的，在遍歷的時候並不會按照你傳入的順序，進行傳出。
1 //正常遍歷：
2 for k, v := range exp {
3 fmt.Println(k, v)
4 }
5
6 //有序遍歷
7 import "sort"
8 var keys []string
9 // 把key單獨抽取出來，放在數組中
10 for k, _ := range exp {
11 keys = append(keys, k)
12 }
13 // 進行數組的排序
14 sort.Strings(keys)
15 // 遍曆數組就是有序的了
16 for _, k := range keys {
17 fmt.Println(k, m[k])
18 }
2. map的結構
Go中的map在可以在 $GOROOT/src/runtime/map.go找到它的實現。哈希表的數據結構中一些關鍵的域如下所示：
1 type hmap struct {
2 count int //元素個數
3 flags uint8
4 B uint8 //擴容常量
5 noverflow uint16 //溢出 bucket 個數
6 hash0 uint32 //hash 種子
7 buckets unsafe.Pointer //bucket 數組指針
8 oldbuckets unsafe.Pointer //擴容時舊的buckets 數組指針
9 nevacuate uintptr //擴容搬遷進度
10 extra *mapextra //記錄溢出相關
11 }
12
13 type bmap struct {
14 tophash [bucketCnt]uint8
15 // Followed by bucketCnt keys
16 //and then bucketan Cnt values
17 // Followed by overflow pointer.
18 }
說明：每個map的底層都是hmap結構體，它是由若干個描述hmap結構體的元素、數組指針、extra等組成，buckets數組指針指向由若干個bucket組成的數組，其每個bucket里存放的是key-value數據(通常是8個)和overflow字段（指向下一個bmap），每個key插入時會根據hash算法歸到同一個bucket中，當一個bucket中的元素超過8個的時候，hmap會使用extra中的overflow來擴展存儲key。
圖中len 就是當前map的元素個數，也就是len()返回的值。也是結構體中hmap.count的值。bucket array是指數組指針，指向bucket數組。hash seed 哈希種子。overflow指向下一個bucket。
map的底層主要是由三個結構構成:
- hmap — map的最外層的數據結構，包括了map的各種基礎信息、如大小、bucket，一個大的結構體。
- mapextra — 記錄map的額外信息，hmap結構體里的extra指針指向的結構，例如overflow bucket。
- bmap — 代表bucket，每一個bucket最多放8個kv，最後由一個overflow字段指向下一個bmap，注意key、value、overflow字段都不显示定義，而是通過maptype計算偏移獲取的。
mapextra的結構如下
1 // mapextra holds fields that are not present on all maps.
2 type mapextra struct {
3 // If both key and value do not contain pointers and are inline, then we mark bucket
4 // type as containing no pointers. This avoids scanning such maps.
5 // However, bmap.overflow is a pointer. In order to keep overflow buckets
6 // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
7 // overflow and oldoverflow are only used if key and value do not contain pointers.
8 // overflow contains overflow buckets for hmap.buckets.
9 // oldoverflow contains overflow buckets for hmap.oldbuckets.
10 // The indirection allows to store a pointer to the slice in hiter.
11 overflow *[]*bmap
12 oldoverflow *[]*bmap
13
14 // nextOverflow holds a pointer to a free overflow bucket.
15 nextOverflow *bmap
16 }
其中hmap.extra.nextOverflow指向的是預分配的overflow bucket，預分配的用完了那麼值就變成nil。
bmap的詳細結構如下
在map中出現哈希衝突時，首先
以bmap為最小粒度掛載，一個bmap累積8個kv之後，就會申請一個新的bmap（overflow bucket）掛在這個bmap的後面形成鏈表，優先用預分配的overflow bucket，如果預分配的用完了，那麼就malloc一個掛上去。這樣減少對象數量，減輕管理內存的負擔，利於gc。
注意golang的map不會shrink，內存只會越用越多，overflow bucket中的key全刪了也不會釋放。
bmap中所有key存在一塊，所有value存在一塊，這樣做方便內存對齊。當key大於128字節時，bucket的key字段存儲的會是指針，指向key的實際內容；value也是一樣。
hash值的高8位存儲在bucket中的tophash字段。每個桶最多放8個kv對，所以tophash類型是數組[8]uint8。把高八位存儲起來，這樣不用完整比較key就能過濾掉不符合的key，加快查詢速度。實際上當hash值的高八位小於常量minTopHash時，會加上minTopHash，區間[0, minTophash)的值用於特殊標記。查找key時，計算hash值，用hash值的高八位在tophash中查找，有tophash相等的，再去比較key值是否相同。
1 type typeAlg struct {
2 // function for hashing objects of this type
3 // (ptr to object, seed) -> hash
4 hash func(unsafe.Pointer, uintptr) uintptr
5 // function for comparing objects of this type
6 // (ptr to object A, ptr to object B) -> ==?
7 equal func(unsafe.Pointer, unsafe.Pointer) bool
8
9 // tophash calculates the tophash value for hash.
10 func tophash(hash uintptr) uint8 {
11 top := uint8(hash >> (sys.PtrSize*8 - 8))
12 if top < minTopHash {
13 top += minTopHash
14 }
15 return top
16 }
golang為每個類型定義了類型描述器_type，並實現了hashable類型的_type.alg.hash和_type.alg.equal，以支持map的范型，定義了這類key用什麼hash函數、bucket的大小、怎麼比較之類的，通過這個變量來實現范型。
3. map的基本操作
3.1 map的創建
1 //makemap為make（map [k] v，hint）實現Go map創建。
2 //如果編譯器已確定映射或第一個存儲桶,可以在堆棧上創建，hmap或bucket可以為非nil。
3 //如果h！= nil，則可以直接在h中創建map。
4 //如果h.buckets！= nil，則指向的存儲桶可以用作第一個存儲桶。
5 func makemap(t *maptype, hint int, h *hmap) *hmap {
6 if hint < 0 || hint > int(maxSliceCap(t.bucket.size)) {
7 hint = 0
8 }
9
10 // 初始化Hmap
11 if h == nil {
12 h = new(hmap)
13 }
14 h.hash0 = fastrand()
15
16 // 查找將保存請求的元素數的size參數
17 B := uint8(0)
18 for overLoadFactor(hint, B) {
19 B++
20 }
21 h.B = B
22
23 // 分配初始哈希表
24 // if B == 0, 稍後會延遲分配buckets字段（在mapassign中）
25 //如果提示很大，則將內存清零可能需要一段時間。
26 if h.B != 0 {
27 var nextOverflow *bmap
28 h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
29 if nextOverflow != nil {
30 h.extra = new(mapextra)
31 h.extra.nextOverflow = nextOverflow
32 }
33 }
34
35 return h
36 }
hint是一個啟發值，啟發初建map時創建多少個bucket，如果hint是0那麼就先不分配bucket，lazy分配。大概流程就是初始化hmap結構體、設置一下hash seed、bucket數量、實際申請bucket、申請mapextra結構體之類的。 申請buckets的過程：
1 // makeBucketArray初始化地圖存儲區的後備數組。
2 // 1 << b是要分配的最小存儲桶數。
3 // dirtyalloc之前應該為nil或bucket數組
4 //由makeBucketArray使用相同的t和b參數分配。
5 //如果dirtyalloc為零，則將分配一個新的支持數組，dirtyalloc將被清除並作為後備數組重用。
6 func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
7 base := bucketShift(b)
8 nbuckets := base
9 // 對於小b，溢出桶不太可能出現。
10 // 避免計算的開銷。
11 if b >= 4 {
12 //加上估計的溢出桶數
13 //插入元素的中位數
14 //與此值b一起使用。
15 nbuckets += bucketShift(b - 4)
16 sz := t.bucket.size * nbuckets
17 up := roundupsize(sz)
18 if up != sz {
19 nbuckets = up / t.bucket.size
20 }
21 }
22 if dirtyalloc == nil {
23 buckets = newarray(t.bucket, int(nbuckets))
24 } else {
25 // dirtyalloc先前是由上面的newarray（t.bucket，int（nbuckets）），但不能為空。
26 buckets = dirtyalloc
27 size := t.bucket.size * nbuckets
28 if t.bucket.kind&kindNoPointers == 0 {
29 memclrHasPointers(buckets, size)
30 } else {
31 memclrNoHeapPointers(buckets, size)
32 }
33 }
34
35 if base != nbuckets {
36 //我們預先分配了一些溢出桶。
37 //為了將跟蹤這些溢出桶的開銷降至最低，我們使用的約定是，如果預分配的溢出存儲桶發生了溢出指針為零，則通過碰撞指針還有更多可用空間。
38 //對於最後一個溢出存儲區，我們需要一個安全的非nil指針；只是用bucket。
39 nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
40 last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
41 last.setoverflow(t, (*bmap)(buckets))
42 }
43 return buckets, nextOverflow
44 }
默認創建2
b個bucket，如果
b大於等於4，那麼就預先額外創建一些overflow bucket。除了最後一個overflow bucket，其餘overflow bucket的overflow指針都是nil，最後一個overflow bucket的overflow指針指向bucket數組第一個元素，作為哨兵，說明到了到結尾了。
3.2 查詢操作
1 // mapaccess1返回指向h [key]的指針。從不返回nil，而是 如果值類型為零，它將返回對零對象的引用,該鍵不在map中。
2 //注意：返回的指針可能會使整個map保持活動狀態，因此請不要堅持很長時間。
3 func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
4 if raceenabled && h != nil { //raceenabled是否啟用數據競爭檢測。
5 callerpc := getcallerpc()
6 pc := funcPC(mapaccess1)
7 racereadpc(unsafe.Pointer(h), callerpc, pc)
8 raceReadObjectPC(t.key, key, callerpc, pc)
9 }
10 if msanenabled && h != nil {
11 msanread(key, t.key.size)
12 }
13 if h == nil || h.count == 0 {
14 return unsafe.Pointer(&zeroVal[0])
15 }
16 // 併發訪問檢查
17 if h.flags&hashWriting != 0 {
18 throw("concurrent map read and map write")
19 }
20
21 // 計算key的hash值
22 alg := t.key.alg
23 hash := alg.hash(key, uintptr(h.hash0)) // alg.hash
24
25 // hash值對m取餘數得到對應的bucket
26 m := uintptr(1)<<h.B - 1
27 b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
28
29 // 如果老的bucket還沒有遷移，則在老的bucket裏面找
30 if c := h.oldbuckets; c != nil {
31 if !h.sameSizeGrow() {
32 m >>= 1
33 }
34 oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
35 if !evacuated(oldb) {
36 b = oldb
37 }
38 }
39
40 // 計算tophash，取高8位
41 top := uint8(hash >> (sys.PtrSize*8 - 8))
42
43 for {
44 for i := uintptr(0); i < bucketCnt; i++ {
45 // 檢查top值，如高8位不一樣就找下一個
46 if b.tophash[i] != top {
47 continue
48 }
49
50 // 取key的地址
51 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
52
53 if alg.equal(key, k) { // alg.equal
54 // 取value得地址
55 v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
56 }
57 }
58
59 // 如果當前bucket沒有找到，則找bucket鏈的下一個bucket
60 b = b.overflow(t)
61 if b == nil {
62 // 返回零值
63 return unsafe.Pointer(&zeroVal[0])
64 }
65 }
66 }
-
先定位出bucket，如果正在擴容，並且這個bucket還沒搬到新的hash表中，那麼就從老的hash表中查找。
-
在bucket中進行順序查找，使用高八位進行快速過濾，高八位相等，再比較key是否相等，找到就返回value。如果當前bucket找不到，就往下找overflow bucket，都沒有就返回零值。
訪問的時候，並不進行擴容的數據搬遷。並且併發有寫操作時拋異常。
注意，t.bucketsize並不是bmap的size，而是bmap加上存儲key、value、overflow指針，所以查找bucket的時候時候用的不是bmap的szie。
3.3 更新/插入過程
1 // 與mapaccess類似，但是如果map中不存在密鑰，則為該密鑰分配一個插槽
2 func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
3 ...
4 //設置hashWriting調用alg.hash，因為alg.hash可能出現緊急情況后，在這種情況下，我們實際上並沒有進行寫操作.
5 h.flags |= hashWriting
6
7 if h.buckets == nil {
8 h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
9 }
10
11 again:
12 bucket := hash & bucketMask(h.B)
13 if h.growing() {
14 growWork(t, h, bucket)
15 }
16 b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
17 top := tophash(hash)
18
19 var inserti *uint8
20 var insertk unsafe.Pointer
21 var val unsafe.Pointer
22 for {
23 for i := uintptr(0); i < bucketCnt; i++ {
24 if b.tophash[i] != top {
25 if b.tophash[i] == empty && inserti == nil {
26 inserti = &b.tophash[i]
27 insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
28 val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
29 }
30 continue
31 }
32 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
33 if t.indirectkey {
34 k = *((*unsafe.Pointer)(k))
35 }
36 if !alg.equal(key, k) {
37 continue
38 }
39 // 已經有一個 mapping for key. 更新它.
40 if t.needkeyupdate {
41 typedmemmove(t.key, k, key)
42 }
43 val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
44 goto done
45 }
46 ovf := b.overflow(t)
47 if ovf == nil {
48 break
49 }
50 b = ovf
51 }
52 //// 如果已經達到了load factor的最大值，就繼續擴容。
53 //找不到鍵的映射。分配新單元格並添加條目。
54 //如果達到最大負載係數或溢出桶過多，並且我們還沒有處於成長的中間，就開始擴容。
55 if !h.growing() && (overLoadFactor(h.count+1, h.B) ||
56 tooManyOverflowBuckets(h.noverflow, h.B)) {
57 hashGrow(t, h)
58 goto again // //擴大表格會使所有內容無效， so try again
59 }
60 if inserti == nil {
61 // 當前所有存儲桶已滿，請分配一個新的存儲桶
62 newb := h.newoverflow(t, b)
63 inserti = &newb.tophash[0]
64 insertk = add(unsafe.Pointer(newb), dataOffset)
65 val = add(insertk, bucketCnt*uintptr(t.keysize))
66 }
67
68 // 在插入的位置，存儲鍵值
69 if t.indirectkey {
70 kmem := newobject(t.key)
71 *(*unsafe.Pointer)(insertk) = kmem
72 insertk = kmem
73 }
74 if t.indirectvalue {
75 vmem := newobject(t.elem)
76 *(*unsafe.Pointer)(val) = vmem
77 }
78 typedmemmove(t.key, insertk, key)
79 *inserti = top
80 h.count++
81
82 done:
83 if h.flags&hashWriting == 0 {
84 throw("concurrent map writes")
85 }
86 h.flags &^= hashWriting
87 if t.indirectvalue {
88 val = *((*unsafe.Pointer)(val))
89 }
90 return val
91 }
-
hash表如果正在擴容，並且這次要操作的bucket還沒搬到新hash表中，那麼先進行搬遷（擴容細節下面細說）。
-
在buck中尋找key，同時記錄下第一個空位置，如果找不到，那麼就在空位置中插入數據；如果找到了，那麼就更新對應的value；
-
找不到key就看下需不需要擴容，需要擴容並且沒有正在擴容，那麼就進行擴容，然後回到第一步。
-
找不到key，不需要擴容，但是沒有空slot，那麼就分配一個overflow bucket掛在鏈表結尾，用新bucket的第一個slot放存放數據。
3.5 刪除的過程
1 func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
2 ...
3 // Set hashWriting after calling alg.hash, since alg.hash may panic,
4 // in which case we have not actually done a write (delete).
5 h.flags |= hashWriting
6
7 bucket := hash & bucketMask(h.B)
8 if h.growing() {
9 growWork(t, h, bucket)
10 }
11 b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
12 top := tophash(hash)
13 search:
14 for ; b != nil; b = b.overflow(t) {
15 for i := uintptr(0); i < bucketCnt; i++ {
16 if b.tophash[i] != top {
17 continue
18 }
19 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
20 k2 := k
21 if t.indirectkey {
22 k2 = *((*unsafe.Pointer)(k2))
23 }
24 if !alg.equal(key, k2) {
25 continue
26 }
27 // 如果其中有指針，則僅清除鍵。
28 if t.indirectkey {
29 *(*unsafe.Pointer)(k) = nil
30 } else if t.key.kind&kindNoPointers == 0 {
31 memclrHasPointers(k, t.key.size)
32 }
33 v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
34 if t.indirectvalue {
35 *(*unsafe.Pointer)(v) = nil
36 } else if t.elem.kind&kindNoPointers == 0 {
37 memclrHasPointers(v, t.elem.size)
38 } else {
39 memclrNoHeapPointers(v, t.elem.size)
40 }
41 // 若找到把對應的tophash裏面的打上空的標記
42 b.tophash[i] = empty
43 h.count--
44 break search
45 }
46 }
47
48 if h.flags&hashWriting == 0 {
49 throw("concurrent map writes")
50 }
51 h.flags &^= hashWriting
52 }
-
如果正在擴容，並且操作的bucket還沒搬遷完，那麼搬遷bucket。
-
找出對應的key，如果key、value是包含指針的那麼會清理指針指向的內存，否則不會回收內存。
3.6 map的擴容
通過上面的過程我們知道了，插入、刪除過程都會觸發擴容，判斷擴容的函數如下：
1 // overLoadFactor 判斷放置在1 << B個存儲桶中的計數項目是否超過loadFactor。
2 func overLoadFactor(count int, B uint8) bool {
3 return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
4 //return 元素個數>8 && count>bucket數量*6.5,其中loadFactorNum是常量13，loadFactorDen是常量2,所以是6.5,bucket數量不算overflow bucket.
5 }
6
7 // tooManyOverflowBuckets 判斷noverflow存儲桶對於1 << B存儲桶的map是否過多。
8 // 請注意，大多數這些溢出桶必須稀疏使用。如果使用密集，則我們已經觸發了常規map擴容。
9 func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
10 // 如果閾值太低，我們會做多餘的工作。如果閾值太高，則增大和縮小的映射可能會保留大量未使用的內存。
11 //“太多”意味着（大約）溢出桶與常規桶一樣多。有關更多詳細信息，請參見incrnoverflow。
12 if B > 15 {
13 B = 15
14 }
15 // 譯器在這裏看不到B <16;掩碼B生成較短的移位碼。
16 return noverflow >= uint16(1)<<(B&15)
17 }
18
19 {
20 ....
21 // 如果我們達到最大負載率或溢流桶過多，並且我們還沒有處於成長的中間，就開始成長。
22 if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
23 hashGrow(t, h)
24 goto again // 擴大表格會使所有內容失效，so try again
25 }
26 //if (不是正在擴容 && (元素個數/bucket數超過某個值 || 太多overflow bucket)) {
27 進行擴容
28 //}
29 ....
30 }
每次map進行更新或者新增的時候，會先通過以上函數判斷一下load factor。來決定是否擴容。如果需要擴容，那麼第一步需要做的，就是對hash表進行擴容：
1 //僅對hash表進行擴容，這裏不進行搬遷
2 func hashGrow(t *maptype, h *hmap) {
3 // 如果達到負載係數，則增大尺寸。否則，溢出bucket過多，因此，保持相同數量的存儲桶並橫向“增長”。
4 bigger := uint8(1)
5 if !overLoadFactor(h.count+1, h.B) {
6 bigger = 0
7 h.flags |= sameSizeGrow
8 }
9 oldbuckets := h.buckets
10 newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
11
12 flags := h.flags &^ (iterator | oldIterator)
13 if h.flags&iterator != 0 {
14 flags |= oldIterator
15 }
16 // 提交增長（atomic wrt gc）
17 h.B += bigger
18 h.flags = flags
19 h.oldbuckets = oldbuckets
20 h.buckets = newbuckets
21 h.nevacuate = 0
22 h.noverflow = 0
23
24 if h.extra != nil && h.extra.overflow != nil {
25 // 將當前的溢出bucket提升到老一代。
26 if h.extra.oldoverflow != nil {
27 throw("oldoverflow is not nil")
28 }
29 h.extra.oldoverflow = h.extra.overflow
30 h.extra.overflow = nil
31 }
32 if nextOverflow != nil {
33 if h.extra == nil {
34 h.extra = new(mapextra)
35 }
36 h.extra.nextOverflow = nextOverflow
37 }
38
39 //哈希表數據的實際複製是增量完成的，通過growWork（）和evacuate（）。
40 }
如果之前為2^n ，那麼下一次擴容是2^(n+1),每次擴容都是之前的兩倍。擴容后需要重新計算每一項在hash中的位置，新表為老的兩倍，此時前文的oldbacket用上了，用來存同時存在的兩個新舊map，等數據遷移完畢就可以釋放oldbacket了。擴容的函數hashGrow其實僅僅是進行一些空間分配，字段的初始化，實際的搬遷操作是在growWork函數中：
1 func growWork(t *maptype, h *hmap, bucket uintptr) {
2 //確保我們遷移了了對應的oldbucket，到我們將要使用的存儲桶。
3 evacuate(t, h, bucket&h.oldbucketmask())
4
5 // 疏散一箇舊桶以在生長上取得進展
6 if h.growing() {
7 evacuate(t, h, h.nevacuate)
8 }
9 }
evacuate是進行具體搬遷某個bucket的函數，可以看出
growWork會搬遷兩個bucket，一個是入參bucket；另一個是h.nevacuate。這個nevacuate是一個順序累加的值。可以想想如果每次僅僅搬遷進行寫操作（賦值/刪除）的bucket，那麼有可能某些bucket就是一直沒有機會訪問到，那麼擴容就一直沒法完成，總是在擴容中的狀態，因此會額外進行一次順序遷移，理論上，有N個old bucket，最多N次寫操作，那麼必定會搬遷完。在advanceEvacuationMark中進行nevacuate的累加，遇到已經遷移的bucket會繼續累加，一次最多加1024。
優點：均攤擴容時間，一定程度上縮短了擴容時間（和gc的引用計數法類似，都是均攤）overLoadFactor函數中有一個常量6.5（loadFactorNum/loadFactorDen）來進行影響擴容時機。這個值的來源是測試取中的結果。
4. map的併發安全性
map的併發操作不是安全的。併發起兩個goroutine，分別對map進行數據的增加：
1 func main() {
2 test := map[int]int {1:1}
3 go func() {
4 i := 0
5 for i < 10000 {
6 test[1]=1
7 i++
8 }
9 }()
10
11 go func() {
12 i := 0
13 for i < 10000 {
14 test[1]=1
15 i++
16 }
17 }()
18
19 time.Sleep(2*time.Second)
20 fmt.Println(test)
21 }
22
23 //fatal error: concurrent map read and map write
併發讀寫map結構的數據引起了錯誤。
解決方案1：加鎖
1 func main() {
2 test := map[int]int {1:1}
3 var s sync.RWMutex
4 go func() {
5 i := 0
6 for i < 10000 {
7 s.Lock()
8 test[1]=1
9 s.Unlock()
10 i++
11 }
12 }()
13
14 go func() {
15 i := 0
16 for i < 10000 {
17 s.Lock()
18 test[1]=1
19 s.Unlock()
20 i++
21 }
22 }()
23
24 time.Sleep(2*time.Second)
25 fmt.Println(test)
26 }
特點：實現簡單粗暴，好理解。但是鎖的粒度為整個map，存在優化空間。適用場景：all。
解決方案2：sync.Map
1 func main() {
2 test := sync.Map{}
3 test.Store(1, 1)
4 go func() {
5 i := 0
6 for i < 10000 {
7 test.Store(1, 1)
8 i++
9 }
10 }()
11
12 go func() {
13 i := 0
14 for i < 10000 {
15 test.Store(1, 1)
16 i++
17 }
18 }()
19
20 time.Sleep(time.Second)
21 fmt.Println(test.Load(1))
22 }
sync.Map的原理：sync.Map裡頭有兩個map一個是專門用於讀的read map，另一個是才是提供讀寫的dirty map；優先讀read map，若不存在則加鎖穿透讀dirty map，同時記錄一個未從read map讀到的計數，當計數到達一定值，就將read map用dirty map進行覆蓋。
特點：官方出品，通過空間換時間的方式，讀寫分離；不適用於大量寫的場景，會導致read map讀不到數據而進一步加鎖讀取，同時dirty map也會一直晉陞為read map，整體性能較差。適用場景：大量讀，少量寫。
解決方案3：分段鎖
這也是數據庫常用的方法，分段鎖每一個讀寫鎖保護一段區間。sync.Map其實也是相當於表級鎖，只不過多讀寫分了兩個map，本質還是一樣的。
優化方向：將鎖的粒度盡可能降低來提高運行速度。思路：對一個大map進行hash，其內部是n個小map，根據key來來hash確定在具體的那個小map中，這樣加鎖的粒度就變成1/n了。
5. map的GC內存回收
golang里的map是只增不減的一種數組結構，他只會在刪除的時候進行打標記說明該內存空間已經empty了，不會回收。
1 var intMap map[int]int
2
3 func main() {
4 printMemStats("初始化")
5
6 // 添加1w個map值
7 intMap = make(map[int]int, 10000)
8 for i := 0; i < 10000; i++ {
9 intMap[i] = i
10 }
11
12 // 手動進行gc操作
13 runtime.GC()
14 // 再次查看數據
15 printMemStats("增加map數據后")
16
17 log.Println("刪除前數組長度：", len(intMap))
18 for i := 0; i < 10000; i++ {
19 delete(intMap, i)
20 }
21 log.Println("刪除后數組長度：", len(intMap))
22
23 // 再次進行手動GC回收
24 runtime.GC()
25 printMemStats("刪除map數據后")
26
27 // 設置為nil進行回收
28 intMap = nil
29 runtime.GC()
30 printMemStats("設置為nil后")
31 }
32
33 func printMemStats(mag string) {
34 var m runtime.MemStats
35 runtime.ReadMemStats(&m)
36 log.Printf("%v：分配的內存 = %vKB, GC的次數 = %v\n", mag, m.Alloc/1024, m.NumGC)
37 }
38
39 //初始化：分配的內存 = 65KB, GC的次數 = 0
40 //增加map數據后：分配的內存 = 381KB, GC的次數 = 1
41 //刪除前數組長度： 10000
42 //刪除后數組長度： 0
43 //刪除map數據后：分配的內存 = 381KB, GC的次數 = 2
44 //設置為nil后：分配的內存 = 68KB, GC的次數 = 3
可以看到delete是不會真正的把map釋放的，所以要回收map還是需要設為nil
sync.Map的原理詳解：
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※為什麼 USB CONNECTOR 是電子產業重要的元件?
※網頁設計一頭霧水??該從何著手呢? 找到專業技術的網頁設計公司，幫您輕鬆架站!
※想要讓你的商品成為最夯、最多人討論的話題?網頁設計公司讓你強力曝光
※想知道最厲害的台北網頁設計公司推薦、台中網頁設計公司推薦專業設計師”嚨底家”!!
根據德國商業雜誌 Manager Magazin 報導，蘋果與 BMW 正在秘密商議將 BMW 的電動車 i3 提供給蘋果，做為 Apple Car 的原型車使用，這並不是蘋果第一次與 BMW 合作，同時這也讓我們對 Apple Car 的輪廓又更清楚了一些。 蘋果從 2014 年秋天開始和 BMW 研議 Apple Car 的發展計劃，在兩間公司一度中斷協議後，根據報導指出，蘋果執行長 Tim Cook 帶領著高級主管前往德國萊比錫參訪 BMW 工廠的行程，一方面參觀 BMW i3 的生產，一方面重啟合作對話。 這不是蘋果第一次與 BMW 合作，從車用系統 Car Play 到 Apple Watch 專屬 App，BMW 與蘋果有著密切往來，近來對汽車產業動作頻頻的蘋果，也已透過挖角高級主管，和接觸包括特斯拉、福特和通用汽車員工尋覓相關人材等方式開始佈局。 然而，目前關於 Apple Car 的細節仍十分有限，蘋果最後會自己做一輛車出來，還是就直接用改裝的方式，讓 i3 成為 Apple Car 也仍是未知數，不過可以確定的是，內部代號「Project Titan」的蘋果汽車計劃，如果確定可行的話，將有可能在 2020 年登場。 本文全文授權轉載自《科技新報》─〈〉
