深入理解Go语言中的map

// 方式一： 使用var关键字声明Map，然后使用make函数初始化
var myMap map[string]int
myMap = make(map[string]int)

// 方式二： 使用make函数直接声明并初始化Map
myMap := make(map[string]int)

// 方式三： 使用Map字面量初始化Map，这在创建预填充的Map时非常有用
myMap := map[string]int{
    "apple":  5,
    "banana": 10,
}

// 增（Insert）： 向Map中添加新的键值对； 如果key已存在，则更新value
myMap["orange"] = 15

// 删（Delete）： 从Map中删除键值对； 如果key不存在，delete函数不会执行任何操作。
delete(myMap, "apple")

// 改（Update）： 更新Map中的键值对; 如果key已经存在，这将替换原来的值。如果key不存在，这将添加一个新的键值对
myMap["banana"] = 20

// 查（Lookup）：查找Map中的键对应的值；
value, exists := myMap["banana"] // 这里value是与键关联的值，exists是一个布尔值，如果键存在于Map中，则为true；如果键不存在，则为false，并且value将是类型的零值。
value := myMap["banana"] // 如果你只关心值，可以忽略第二个返回值

myMap := map[string]int{
    "apple":  5,
    "banana": 10,
    "cherry": 15,
}

for key, value := range myMap {
    fmt.Printf("Key: %s, Value: %d\n", key, value)
}

for key := range myMap {

for _, value := range myMap {

// runtime/map.go
// A header for a Go map.
type hmap struct {
	count     int // 当前哈希表中的元素数量
	flags     uint8
	B         uint8  // 当前哈希表持有的 buckets 数量, 因为哈希表中桶的数量都按2倍扩容,改字段存储对数，也就是 len(buckets) == 2^B
	noverflow uint16 // 溢出桶的大致数量
	hash0     uint32 // hash seed

	buckets    unsafe.Pointer // 存储 2^B 个桶的数组
	oldbuckets unsafe.Pointer // 扩容时用于保存之前 buckets 的字段 , 大小事buckets的一般
	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

	extra *mapextra // optional fields
}

// mapextra 主要维护，当hmap中的buckets中有一些桶发生溢出，但有达不到扩容阈值时，存储溢出的桶
type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap

	// nextOverflow holds a pointer to a free overflow bucket.
	nextOverflow *bmap
}

func MapType(t *types.Type) *types.Type {
	if t.MapType().Hmap != nil {
		return t.MapType().Hmap
	}

	bmap := MapBucketType(t)  // 构建bmap类型

	fields := []*types.Field{
		makefield("count", types.Types[types.TINT]),
		makefield("flags", types.Types[types.TUINT8]),
		makefield("B", types.Types[types.TUINT8]),
		makefield("noverflow", types.Types[types.TUINT16]),
		makefield("hash0", types.Types[types.TUINT32]), // Used in walk.go for OMAKEMAP.
		makefield("buckets", types.NewPtr(bmap)),       // Used in walk.go for OMAKEMAP.
		makefield("oldbuckets", types.NewPtr(bmap)),
		makefield("nevacuate", types.Types[types.TUINTPTR]),
		makefield("extra", types.Types[types.TUNSAFEPTR]),
	}

	hmap := types.NewStruct(types.NoPkg, fields)
	hmap.SetNoalg(true)
	types.CalcSize(hmap)

	// The size of hmap should be 48 bytes on 64 bit
	// and 28 bytes on 32 bit platforms.
	if size := int64(8 + 5*types.PtrSize); hmap.Size() != size {
		base.Fatalf("hmap size not correct: got %d, want %d", hmap.Size(), size)
	}

	t.MapType().Hmap = hmap
	hmap.StructType().Map = t
	return hmap
}

// runtime.bmap
type bmap struct {
	tophash [bucketCnt]uint8
}

// MapBucketType makes the map bucket type given the type of the map.
func MapBucketType(t *types.Type) *types.Type {
	if t.MapType().Bucket != nil {
		return t.MapType().Bucket
	}

	keytype := t.Key()
	elemtype := t.Elem()
	types.CalcSize(keytype)
	types.CalcSize(elemtype)
	if keytype.Size() > MAXKEYSIZE {
		keytype = types.NewPtr(keytype)
	}
	if elemtype.Size() > MAXELEMSIZE {
		elemtype = types.NewPtr(elemtype)
	}

	field := make([]*types.Field, 0, 5)

	// The first field is: uint8 topbits[BUCKETSIZE].
	arr := types.NewArray(types.Types[types.TUINT8], BUCKETSIZE)
	field = append(field, makefield("topbits", arr))

	arr = types.NewArray(keytype, BUCKETSIZE)
	arr.SetNoalg(true)
	keys := makefield("keys", arr)
	field = append(field, keys)

	arr = types.NewArray(elemtype, BUCKETSIZE)
	arr.SetNoalg(true)
	elems := makefield("elems", arr)
	field = append(field, elems)

	// If keys and elems have no pointers, the map implementation
	// can keep a list of overflow pointers on the side so that
	// buckets can be marked as having no pointers.
	// Arrange for the bucket to have no pointers by changing
	// the type of the overflow field to uintptr in this case.
	// See comment on hmap.overflow in runtime/map.go.
	otyp := types.Types[types.TUNSAFEPTR]
	if !elemtype.HasPointers() && !keytype.HasPointers() {
		otyp = types.Types[types.TUINTPTR]
	}
	overflow := makefield("overflow", otyp)
	field = append(field, overflow)

	// link up fields
	bucket := types.NewStruct(types.NoPkg, field[:])
	bucket.SetNoalg(true)
	types.CalcSize(bucket)
	
	// ......
	
	return bucket
}

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    elems    [8]elemtype
    overflow uintptr
}

myMap := make(map[string]int, initialCapacity)

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
	// If we hit the max load factor or we have too many overflow buckets,
	// and we're not already in the middle of growing, start growing.
	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.
func overLoadFactor(count int, B uint8) bool {
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	if B > 15 {
		B = 15
	}
	return noverflow >= uint16(1)<<(B&15)
}

func hashGrow(t *maptype, h *hmap) {
	...
	// 原有桶设置给oldbuckets
	oldbuckets := h.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
	h.nevacuate = 0
	h.noverflow = 0

	...
}

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
	if h.growing() {
		growWork(t, h, bucket)
	}
...
}

func growWork(t *maptype, h *hmap, bucket uintptr) {
	// make sure we evacuate the oldbucket corresponding
	// to the bucket we're about to use
	evacuate(t, h, bucket&h.oldbucketmask())

	// evacuate one more oldbucket to make progress on growing
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}