深入理解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)
 }
}