特殊类型源码详解

golang version 1.24.0

Map 原理

Source Code : src/runtime/map_noswiss.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)
	clearSeq   uint64

	extra *mapextra // optional fields
}

// 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 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 [abi.OldMapBucketCount]uint8
	// Followed by bucketCnt keys and then bucketCnt elems.
	// NOTE: packing all the keys together and then all the elems together makes the
	// code a bit more complicated than alternating key/elem/key/elem/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
}

Map structure

Image source: https://juejin.cn/post/7029679896183963678

From the structure, we can see that the underlying structure of the Map is hmap. In hmap, buckets are used to store data, and one hmap maintains several buckets.

Warning

• Each bucket stores 8 key-value pairs. If there are more than 8 key-value pairs, an overflow bucket will be created and connected through overflow.
• tophash stores the first 8 bits of the hash value, so the Uint8 type is used.

Info

The number of buckets = 2^B

Retrieving Data

The process of retrieving data (Get Value):

Info

1. Calculate the hash value of the key.
2. Get the last B bits of the hash value, and determine the number of the bucket to place the data according to the value of the last B bits (for example, if B = 4 and the last B bits are 1001, then the bucket number is 9).
3. Determine the position of the key within the bucket according to the first 8 bits of the hash value.
4. If the corresponding hash value is found, compare whether the complete hash values are the same. If they are not the same, look downwards.
5. If it is still not found, look for it in the overflow bucket through overflow.

Inserting Data

The process of inserting data (Put):

Info

1. Calculate the hash value of the key.
2. Get the last B bits of the hash value, and determine the number of the bucket to place the data according to the value of the last B bits (for example, if B = 4 and the last B bits are 1001, then the bucket number is 9).
3. Determine the position of the key within the bucket according to the first 8 bits of the hash value.
4. If the corresponding position is empty, place the KV pair. If it is not empty, place it in the next empty position.
5. If the bucket is full, create an overflow bucket and place the data in the overflow bucket.

Expansion Strategy

Warning

LoadFactor = count / 2^B

That is, the number of elements / the number of buckets

Expansion Conditions

1. Load factor > 6.5
2. If B < 15 and the number of overflow buckets > 2^B
3. If B >= 15 and the number of overflow buckets > 2^15

Equal Expansion (Solving the problem of too many overflow buckets in conditions 2 and 3 for expansion)

1. Move the buckets to oldBuckets.
2. Create all the buckets, including the overflow buckets, that are the same as oldBuckets.
3. Move the data in oldBuckets to buckets. The bucket where the elements are located remains unchanged, but the position will be re-placed according to the hash value to increase the utilization rate.
4. After the data is successfully moved, set the element at the corresponding position in oldBuckets to nil

Equal Expansion

Incremental Expansion (Solving the problem of too many elements in condition 1 for expansion)

1. Move the buckets to oldBuckets.
2. Increase B and create 2^B number of buckets.
3. Determine the position of the new bucket for the elements in oldBuckets according to the original hash value. Since B has changed, the sequence number (the last B bits) of the new bucket also changes, resulting in a change in the bucket where the elements are located.
4. After the data is successfully moved, set the element at the corresponding position in oldBuckets to nil