Go Map 簡介 和 實作決議

/* 宣告變數，默認 map 是 nil */
var map_variable map[key_data_type]value_data_type

/* 使用 make 函式 */
map_variable := make(map[key_data_type]value_data_type)

   var emptyMap map[string]int
	var initMap = make(map[string]int)
	//emptyMap["ok"]=1
	initMap["init"] = 2
	initMap["ok"] = 4
	delete(initMap, "init")
	for k, v := range initMap {
		fmt.Printf("%v  ,%v\n", k, v)
	}
	_,texist := initMap["fine"]
	fmt.Printf("exists find key is %v\n",texist)
	fmt.Printf("%v ,%v,not init map is nil %v \n", emptyMap, initMap, emptyMap == nil)

[1 ok [2 3 4]]
ok  ,4
exists find key is false
map[] ,map[ok:4],not init map is nil true 

// A header for a Go map.

const ( // 關鍵的變數
    bucketCntBits = 3
	bucketCnt     = 1 << bucketCntBits  // 一個桶最多存盤8個key-value對
	loadFactorNum = 13 // 擴散因子：loadFactorNum / loadFactorDen = 6.5，
	loadFactorDen = 2  // 即元素數量 >= (hash桶數量(2^hmp.B) * 6.5 / 8) 時，觸發擴容
)


type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
	// Make sure this stays in sync with the compiler's definition.
	count     int // # live cells == size of map.  Must be first (used by len() builtin)
	flags     uint8  // 記錄幾個特殊的位標記，如當前是否有別的執行緒正在寫map、當前是否為相同大小的增長（擴容/縮容？）
	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
	hash0     uint32 // hash seed

	buckets    unsafe.Pointer // 指向2^B個桶組成的陣列的指標，資料存在這里
	oldbuckets unsafe.Pointer // 指向擴容前的舊buckets陣列，只在map增長時有效
	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

	extra *mapextra // 保存溢位桶的鏈表和未使用的溢位桶陣列的首地址
}
// 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  // 為溢位的桶保留鏈表
}

// A bucket for a Go map.
type bmap struct {
	// tophash存盤桶內每個key的hash值的高位元組
	// tophash[0] < minTopHash表示桶的疏散狀態
	// 當前版本bucketCnt的值是8，一個桶最多存盤8個key-value對
	tophash [bucketCnt]uint8
	// 特別注意：
	// 實際分配記憶體時會申請一個更大的記憶體空間A，A的前8位元組為bmap
	// 后面依次跟8個key、8個value、1個溢位指標
	// map的桶結構實際指的是記憶體空間A
}

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	if raceenabled && h != nil {
		callerpc := getcallerpc()
		pc := funcPC(mapaccess1)
		racereadpc(unsafe.Pointer(h), callerpc, pc)
		raceReadObjectPC(t.key, key, callerpc, pc)
	}
	if msanenabled && h != nil {
		msanread(key, t.key.size)
	}
	if h == nil || h.count == 0 {
		if t.hashMightPanic() {
			t.hasher(key, 0) // see issue 23734
		}
		return unsafe.Pointer(&zeroVal[0])
	}
	if h.flags&hashWriting != 0 {
		throw("concurrent map read and map write")
	}
	hash := t.hasher(key, uintptr(h.hash0))
	m := bucketMask(h.B)
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	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
		}
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
		if !evacuated(oldb) {
			b = oldb
		}
	}
	top := tophash(hash)
bucketloop:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break bucketloop
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			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
			}
		}
	}
	return unsafe.Pointer(&zeroVal[0])
}

// make(map[k]v, hint), hint即預分配大小
// 不傳hint時，如用new創建個預設容量為0的map時，makemap只初始化hmap結構，不分配hash陣列
func makemap(t *maptype, hint int, h *hmap) *hmap {
	// 省略部分代碼
	// 隨機hash種子
	h.hash0 = fastrand()

	// 2^h.B 為大于hint*6.5(擴容因子)的最小的2的冪
	B := uint8(0)
	// overLoadFactor(hint, B)只有一行代碼：return hint > bucketCnt && uintptr(hint) > loadFactorNum*(bucketShift(B)/loadFactorDen)
	// 即B的大小應滿足 hint <= (2^B) * 6.5
	// 一個桶能存8對key-value，所以這就表示B的初始值是保證這個map不需要擴容即可存下hint個元素對的最小的B值
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B

	// 這里分配hash陣列
	if h.B != 0 {
		var nextOverflow *bmap
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		// makeBucketArray()會在hash陣列后面預分配一些溢位桶，
		// h.extra.nextOverflow用來保存上述溢位桶的首地址
		if nextOverflow != nil {
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

// 分配hash陣列
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
	base := bucketShift(b) // base代表用戶預期的桶的數量，即hash陣列的真實大小
	nbuckets := base // nbuckets表示實際分配的桶的數量，>= base，這就可能會追加一些溢位桶作為溢位的預留
	if b >= 4 {
		// 這里追加一定數量的桶，并做記憶體對齊
		nbuckets += bucketShift(b - 4)
		sz := t.bucket.size * nbuckets
		up := roundupsize(sz)
		if up != sz {
			nbuckets = up / t.bucket.size
		}
	}

	// 后面的代碼就是申請記憶體空間了，此處省略
	// 這里大家可以思考下這個陣列空間要怎么分配，其實就是n*sizeof(桶)，所以：
		// 每個桶前面是8位元組的tophash陣列，然后是8個key，再是8個value，最后放一個溢位指標
		// sizeof(桶) = 8 + 8*sizeof(key) + 8*sizeof(value) + 8
	
	return buckets, nextOverflow
}

unc mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 不熟悉指標操作的同學，用指標傳參往往會踩空指標的坑
    // 這里大家可以思考下，為什么h要非空判斷？
    // 如果一定要在這里支持空map并檢測到map為空時自動初始化，應該怎么寫？
    // 提示：指標的指標
	if h == nil {
		panic(plainError("assignment to entry in nil map"))
	}
	// 在這里做并發判斷，檢測到并發寫時，拋例外
	// 注意：go map的并發檢測是偽檢測，并不保證所有的并發都會被檢測出來，而且這玩意是在運行期檢測，
	// 所以對map有并發要求時，應使用sync.map來代替普通map，通過加鎖來阻斷并發沖突
	if h.flags&hashWriting != 0 {
		throw("concurrent map writes")
	}
	hash := alg.hash(key, uintptr(h.hash0)) // 這里得到uint32的hash值
	h.flags ^= hashWriting // 置Writing標志，key寫入buckets后才會清除標志
	if h.buckets == nil { // map不能為空，但hash陣列可以初始是空的，這里會初始化
		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
	}
	
	...

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    
again:
	bucket := hash & bucketMask(h.B) // 這里用hash值的低階位定位hash陣列的下標偏移量
	if h.growing() {
		growWork(t, h, bucket) // 這里是map的擴容縮容操作，我們在第4章單獨講
	}
	// 通過下標bucket，偏移定位到具體的桶
	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
	top := tophash(hash) // 這里取高8位用于在桶內定位鍵值對
	
	...
}

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

    var inserti *uint8          // tophash插入位置
	var insertk unsafe.Pointer  // key插入位置
	var val unsafe.Pointer      // value插入位置
bucketloop:
	for {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if isEmpty(b.tophash[i]) && inserti == nil {
				    // 找到個空位，先記錄下tophash、key、value的插入位置
				    // 但要遍歷完才能確定要不要插入到這個位置，因為后面有可能有重復的元素
					inserti = &b.tophash[i]
					insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
					val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
				}
				if b.tophash[i] == emptyRest {
					break bucketloop // 遍歷完整個溢位鏈表，退出回圈
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			if !alg.equal(key, k) {
				continue
			}
			// 走到這里說明map里找到一個重復的key，更新key-value，跳到第5步
			if t.needkeyupdate() {
				typedmemmove(t.key, k, key)
			}
			val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
			goto done // 更新Key后跳到第5步
		}
		ovf := b.overflow(t)
		if ovf == nil {
			break // 遍歷完整個溢位鏈表，沒找到能插入的空位，結束回圈，下一步再追加一個溢位桶進來
		}
		b = ovf // 繼續遍歷下一個溢位桶
	}

	...
}

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    // 擴容相關
    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
	}

	if inserti == nil { // inserti == nil說明上1步沒找到空位，整個鏈表是滿的，這里添加一個新的溢位桶上去
		newb := h.newoverflow(t, b) // 分配新溢位桶，優先用3.1章節預留的溢位桶，用完了則分配一個新桶記憶體
		inserti = &newb.tophash[0]
		insertk = add(unsafe.Pointer(newb), dataOffset)
		val = add(insertk, bucketCnt*uintptr(t.keysize))
	}

	// 當key或value的型別大小超過一定值時，桶只存盤key或value的指標，這里分配空間并取指標
	if t.indirectkey() {
		kmem := newobject(t.key)
		*(*unsafe.Pointer)(insertk) = kmem
		insertk = kmem
	}
	if t.indirectvalue() {
		vmem := newobject(t.elem)
		*(*unsafe.Pointer)(val) = vmem
	}
	typedmemmove(t.key, insertk, key) // 在桶中對應位置插入key
	*inserti = top // 插入tophash，hash值高8位
	h.count++ // 插入了新的鍵值對，h.count數量+1

	...
}

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    
 done:
	if h.flags&hashWriting == 0 {
		throw("concurrent map writes")
	}
	h.flags &^= hashWriting // 釋放hashWriting標志位
	if t.indirectvalue() {
		val = *((*unsafe.Pointer)(val))
	}
	return val // 回傳value可插入位置的指標，注意，value還沒插入
}

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    
    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()回傳true則觸發擴容，即map的count大于hash桶數量(2^B)*6.5
func overLoadFactor(count int, B uint8) bool {
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// tooManyOverflowBuckets()，顧名思義，溢位桶太多了觸發縮容
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	if B > 15 {
		B = 15
	}
	return noverflow >= uint16(1)<<(B&15)
}

// go map縮容代碼示例
myMap := make(map[int]int, 1000000)

// 假設這里我們對bigMap做了很多次插入，之后又做了很多次洗掉，此時bigMap的元素數量遠小于hash表大小
// 接下來我們開始縮容
smallMap := make(map[int]int, len(myMap))
for k, v := range myMap {
    smallMap[k] = v
}
myMap = smallMap // 縮容完成，原來的map被我們丟棄，交給gc去清理

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

            b.tophash[i] = emptyOne // 先標記洗掉
			// 如果b.tophash[i]不是最后一個元素，則暫時先占著坑，emptyOne標記的位置暫時不能被插入新元素(見3.2章節插入函式)
			if i == bucketCnt-1 {
				if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
					goto notLast
				}
			} else {
				if b.tophash[i+1] != emptyRest {
					goto notLast
				}
			}
			for { // 如果b.tophash[i]是最后一個元素，則把末尾的emptyOne全部清除置為emptyRest
				b.tophash[i] = emptyRest
				if i == 0 {
					if b == bOrig {
						break // beginning of initial bucket, we're done.
					}
					// Find previous bucket, continue at its last entry.
					c := b
					for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
					}
					i = bucketCnt - 1
				} else {
					i--
				}
				if b.tophash[i] != emptyOne {
					break
				}
			}

    ...
}