go map 底层是hash表（hashmap），
hmap结构
go1.17.10.src/src/runtime/map.go
// A header for a Go map.
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/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
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 // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
go1.17.10.src/src/cmd/compile/internal/reflectdata/reflect.go
overflow := makefield("overflow", otyp)
field = append(field, overflow)
// 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.Width > MAXKEYSIZE {
keytype = types.NewPtr(keytype)
}
if elemtype.Width > 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)
// Check invariants that map code depends on.
if !types.IsComparable(t.Key()) {
base.Fatalf("unsupported map key type for %v", t)
}
if BUCKETSIZE < 8 {
base.Fatalf("bucket size too small for proper alignment")
}
if keytype.Align > BUCKETSIZE {
base.Fatalf("key align too big for %v", t)
}
if elemtype.Align > BUCKETSIZE {
base.Fatalf("elem align too big for %v", t)
}
if keytype.Width > MAXKEYSIZE {
base.Fatalf("key size to large for %v", t)
}
if elemtype.Width > MAXELEMSIZE {
base.Fatalf("elem size to large for %v", t)
}
if t.Key().Width > MAXKEYSIZE && !keytype.IsPtr() {
base.Fatalf("key indirect incorrect for %v", t)
}
if t.Elem().Width > MAXELEMSIZE && !elemtype.IsPtr() {
base.Fatalf("elem indirect incorrect for %v", t)
}
if keytype.Width%int64(keytype.Align) != 0 {
base.Fatalf("key size not a multiple of key align for %v", t)
}
if elemtype.Width%int64(elemtype.Align) != 0 {
base.Fatalf("elem size not a multiple of elem align for %v", t)
}
if bucket.Align%keytype.Align != 0 {
base.Fatalf("bucket align not multiple of key align %v", t)
}
if bucket.Align%elemtype.Align != 0 {
base.Fatalf("bucket align not multiple of elem align %v", t)
}
if keys.Offset%int64(keytype.Align) != 0 {
base.Fatalf("bad alignment of keys in bmap for %v", t)
}
if elems.Offset%int64(elemtype.Align) != 0 {
base.Fatalf("bad alignment of elems in bmap for %v", t)
}
// Double-check that overflow field is final memory in struct,
// with no padding at end.
if overflow.Offset != bucket.Width-int64(types.PtrSize) {
base.Fatalf("bad offset of overflow in bmap for %v", t)
}
t.MapType().Bucket = bucket
bucket.StructType().Map = t
return bucket
}
// MapType builds a type representing a Hmap structure for the given map type.
// Make sure this stays in sync with runtime/map.go.
func MapType(t *types.Type) *types.Type {
if t.MapType().Hmap != nil {
return t.MapType().Hmap
}
bmap := MapBucketType(t)
// build a struct:
// type hmap struct {
// count int
// flags uint8
// B uint8
// noverflow uint16
// hash0 uint32
// buckets *bmap
// oldbuckets *bmap
// nevacuate uintptr
// extra unsafe.Pointer // *mapextra
// }
// must match runtime/map.go:hmap.
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.Width != size {
base.Fatalf("hmap size not correct: got %d, want %d", hmap.Width, size)
}
t.MapType().Hmap = hmap
hmap.StructType().Map = t
return hmap
}