从源码理解Go：map · 青蛙小白

map的内部结构

Go中的map使用哈希表实现的，在源码go runtime/hashmap.go中可以看到对应实现。

// A header for a Go map.
type hmap struct {
	// Note: the format of the Hmap is encoded in ../../cmd/internal/gc/reflect.go and
	// ../reflect/type.go. Don't change this structure without also changing that code!
	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)

	// If both key and value 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.overflow.
	// Overflow is used only if key and value do not contain pointers.
	// overflow[0] contains overflow buckets for hmap.buckets.
	// overflow[1] contains overflow buckets for hmap.oldbuckets.
	// The first indirection allows us to reduce static size of hmap.
	// The second indirection allows to store a pointer to the slice in hiter.
	overflow *[2]*[]*bmap
}

// A bucket for a Go map.
type bmap struct {
	// tophash generally contains the top byte of the hash value
	// for each key in this bucket. If tophash[0] < minTopHash,
	// tophash[0] is a bucket evacuation state instead.
	tophash [bucketCnt]uint8
	// Followed by bucketCnt keys and then bucketCnt values.
	// NOTE: packing all the keys together and then all the values together makes the
	// code a bit more complicated than alternating key/value/key/value/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
}

先删掉代码原有注释，以便于查看：

// A header for a Go map.
type hmap struct {
	count     int 
	flags     uint8
	B         uint8
	noverflow uint16
	hash0     uint32
	buckets    unsafe.Pointer
	oldbuckets unsafe.Pointer
	nevacuate  uintptr
	overflow *[2]*[]*bmap
}

hmap和bmap是两个关键的结构，其中hmap是go内部map的实现，hmap是由桶数组buckets组成，bmap是桶bucket的结构。

const (
	// Maximum number of key/value pairs a bucket can hold.
	bucketCntBits = 3
	bucketCnt     = 1 << bucketCntBits
)

// A bucket for a Go map.
type bmap struct {
	tophash [bucketCnt]uint8
}

bucketCnt为常量8，也就是说每个桶最大持有8个key/value键值对。

Go in Action中给出了map的内部结构的示意图：

与map中的kev/value交互，首先要定位到桶bucket。根据key的具体类型的hash函数计算key的hash值假设为h，h%len(buckets)得到 LOB HASH(哈希值低位)，假设为hl，buckets[hl]则为此key的桶，每个桶最多持有8个key/value，如果桶被装满，造成了桶溢出，也就是发生了hash碰撞，则会形成overflow bucket链表。hash值的高位字节HOB HASH用于定位桶中的key/value。

const (
	// Maximum average load of a bucket that triggers growth.
	loadFactor = 6.5
)

hashmap.go中的负载因子loadFactor为常量6.5，这是个经验值，每个桶的大小为8，也就是一般情况下不会被装满。

map的内部结构

参考