The source code is available at runtime/map.go with 1300+ lines of code

Golang map bottom using hash table implementation, the source corresponding is a structure, details are as follows

// A header for a Go map.
type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/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  // Identifies whether the map is currently being read or written. This value is updated with each operation
	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items) Number of buckets
	noverflow uint16 // approximate number of overflow buckets; See incrNoverFlow for Details Number of overflow buckets
	hash0     uint32 // hash seed The hash seed. The random value generated by the method is different in each map, so the same key will be different in different map positions
	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0. An address pointer to a bucket array that points to the initial location of the bucket's contiguous storage address
	oldbuckets unsafe.Pointer // Previous bucket array of half the size, non-nil only when growing Old bucket array pointer
	nevacuate  uintptr        // evacuation (buckets less than this have been evacuated

	extra *mapextra // Optional fields Records overflow information
}
Copy the code

There are several buckets in each map. Hmap only records the address of the bucket. To find the specific elements in the bucket, you need to know the structure of the bucket

// A bucket for a Go map.Type bmap struct {topHash [bucketCnt]uint8 # bucketCnt =8Store the height of the hash value8A data byte [1]  //key value data :key/key/key/... /value/value/value...
    overflow *bmap   // Overflow bucket address
}
Copy the code

According to the hash function, the key generates a hash value, where the low hash is used to determine the location of the bucket, and the high hash is used to determine which cell is in the bucket. For example, B in the HMAP structure is 5, 2^5=32, that is, there are 32 buckets in the map. You only need to take the lower 5 bits of the hash value to determine which bucket the current key-value falls in. The high hash is the tophash, which refers to the highest 8bits of the hash value. The tophash is used to determine the position of the key in the bucket. Each bucket can store eight key-value pairs. The storage structure is not key/value/key/value… , but the key/key.. Value /value, which avoids padding in byte alignment and saves memory.

The overflow Pointer field is used when hash collisions occur with tophash and low hash values for different keys. When a bucket overflows, you need to store the key-value pair on overflow Bucket (Overflow Bucket). Overflow Pointer is a pointer to overflow bucket. What if the Overflow bucket also overflows? Create a new Overflow Bucket with a chain of Pointers

To initialize the map

// makemap implements Go map creation for make(map[k]v, hint).
// If the compiler has determined that the map or the first bucket
// can be created on the stack, h and/or bucket may be non-nil.
// If h ! = nil, the map can be created directly in h.
// If h.buckets ! = nil, bucket pointed to can be used as the first bucket.
func makemap(t *maptype, hint int, h *hmap) *hmap {
	mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
	if overflow || mem > maxAlloc {
		hint = 0
	}

	// initialize Hmap
	if h == nil {
		h = new(hmap)
	}
	h.hash0 = fastrand()// Assign a random value

	// Find the size parameter B which will hold the requested # of elements.
	// For hint < 0 overLoadFactor returns false since hint < bucketCnt.
	B := uint8(0)
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B// The number is assigned

	// allocate initial hash table
	// if B == 0, the buckets field is allocated lazily later (in mapassign)
	// If hint is large zeroing this memory could take a while.
	ifh.B ! =0 {
		var nextOverflow *bmap
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		ifnextOverflow ! = nil { h.extra =new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}
Copy the code

Find elements in the map

// mapaccess1 returns a pointer to h[key]. Never returns nil, instead
// it will return a reference to the zero object for the elem type if
// the key is not in the map.
// NOTE: The returned pointer may keep the whole map live, so don't
// hold onto it for very long.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	ifraceenabled && h ! = nil {callerpc := getcallerpc()
		pc := funcPC(mapaccess1)
		racereadpc(unsafe.Pointer(h), callerpc, pc)
		raceReadObjectPC(t.key, key, callerpc, pc)
	}
	ifmsanenabled && h ! = nil { msanread(key, t.key.size) }if h == nil || h.count == 0 {
		if t.hashMightPanic() {
			t.hasher(key, 0) // see issue 23734
		}
		return unsafe.Pointer(&zeroVal[0])}ifh.flags&hashWriting ! =0 {// Some current flags are write, and panic cannot be read and written concurrently
		throw("concurrent map read and map write")}hash := t.hasher(key, uintptr(h.hash0))// Calculate the hash value of key
	m := bucketMask(h.B)// Calculate the first address of the bucket chain
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	ifc := h.oldbuckets; c ! = nil {if! h.sameSizeGrow() {// There used to be half as many buckets; mask down one more power of two.
			m >>= 1
		}
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
		if !evacuated(oldb) {
			b = oldb
		}
	}
	top := tophash(hash)// Calculates the tophash value
bucketloop:
	for; b ! = nil; b = b.overflow(t) {// Walk through each bucket
		for i := uintptr(0); i < bucketCnt; i++ {// Find the elements in the bucket according to the height of 8 bits
			ifb.tophash[i] ! = top {// TopHash has 8 elements and stores key information 8 bits high
				if b.tophash[i] == emptyRest {
					break bucketloop
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			if t.key.equal(key, k) {// The key is equal
				e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				if t.indirectelem() {
					e = *((*unsafe.Pointer)(e))
				}
				return e// Return directly if found}}}return unsafe.Pointer(&zeroVal[0])// Return zero of the corresponding type
}

Copy the code

Mapaccess1 = mapAccess1 = mapAccess1 = mapAccess1 = mapAccess1 = mapAccess1

m := make(map[string]int)

print(m["1"] -- the result is:0(Returns the default value of int)Copy the code

The corresponding source code, quite simply, calls mapAccess1 and returns

func mapaccess1_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) unsafe.Pointer {
	e := mapaccess1(t, h, key)
	if e == unsafe.Pointer(&zeroVal[0]) {
		return zero
	}
	return e
}
Copy the code

The second parameter indicates whether the map has the key, which does not, and the first parameter specifies the default zero value

m := make(map[string]int)

val, ok := m["1"] print(val, ok)0.false
Copy the code

If the default value is zero, return false, otherwise return true

func mapaccess2_fat(t *maptype, h *hmap, key, zero unsafe.Pointer) (unsafe.Pointer, bool) {
	e := mapaccess1(t, h, key)
	if e == unsafe.Pointer(&zeroVal[0]) {
		return zero, false
	}
	return e, true
}
Copy the code

The source code of the above two USES mapaccess1_fat, and mapaccess2_fat is my guess, see the source code you need to be like that, no validation

The for range is used to traverse map elements. One of the problems is that the map is out of order. 1. The underlying hash table of the Map will be re-hashed in capacity expansion scenarios, and the traversal order will change

Map Capacity expansion policy Load factor = Number of keys/Number of buckets If the hash factor is too small, the space usage is low. If the hash factor is too large, serious conflicts exist, resulting in low access efficiency

Refer to www.bilibili.com/read/cv5588… Blog.csdn.net/fengshenyun…