1.7 map

This is a historical learning note and may contain outdated or incomplete understanding.

1. What Is a map

Access key-value pairs with O(1) efficiency.

2. Usage

func testMap() {
	maps := map[int]string{
		1: "a",
		2: "b",
	}

	fmt.Println(maps)

	s, ok := maps[1]
	if ok {
		fmt.Println(s)
	}

	delete(maps, 1)
	fmt.Println(maps)

}

3. How a map Is Implemented

An array. Each element in the array is called a bucket.

3.1. Write

3.2. Read

4. How to Find the Bucket a key Belongs To

First method: modulo operation: hash % m
Second method: bitwise AND: hash & (m-1)
- Here m must be a power of 2

5. What to Do When There Is a Collision

Open addressing
- Write: look backward for the next free bucket
- Read: keep searching until an empty bucket is found or the key is equal
Separate chaining:
- Write: linked list
- Read: traverse the linked list until the end or until the key is equal

6. When to Expand

When the load factor reaches a certain value
- loadFactor = keyCount (number of kv pairs) / bucketCount (number of buckets)

7. How to Expand

Directly allocate more buckets and move the key-value pairs from the old buckets -> the new buckets.

7.1. How to Migrate

One-time expansion
- When expansion is triggered, move all key-value pairs to the new buckets at once
- Disadvantage: each expansion takes too long and can cause an obvious instantaneous performance fluctuation
Incremental expansion
- After expansion is triggered, first allocate new buckets and mark the table as expanding. During hash-table reads/writes, if expansion is in progress, migrate part of the key-value pairs into the new buckets
- Advantage: spreads the cost of expansion over multiple operations

8. Golang map Source Code

8.1. Bucket Design

8.2. Overflow Buckets

8.3. key

8.4. Same-size Expansion

9. Implementation

9.1. Data Structures

Go uses a hash lookup table and uses linked lists to resolve hash collisions.

// A header for a Go map.
type hmap struct {
    // Number of elements. len(map) directly returns this value
	count     int
	// State. Indicates whether this map is being read or written
	flags     uint8
	// Number of buckets. This is a logarithm
	B         uint8
	// Number of overflow buckets. In Go, one bucket can hold only 8 keys. If there are more than 8, a new bucket is added; this new bucket is an overflow bucket
	noverflow uint16
	// Passed to the hash function when calculating the hash of a key
	hash0     uint32
    // Points to the buckets array, whose size is 2^B
    // nil if the number of elements is 0
	buckets    unsafe.Pointer
	// During expansion, oldbuckets points to the original buckets, and buckets will be twice the length of oldbuckets
	oldbuckets unsafe.Pointer
	// Indicates expansion progress. Buckets below this address have completed migration
	// For example, if B is 5, there are 2^5 = 32 buckets. If this value equals 4, buckets 0-3 have already been moved
	nevacuate  uintptr
	extra *mapextra // optional fields
}

B is the logarithm of the length of the bucket array, so the length of the buckets array is 2^B

9.1.1. Bucket

buckets is a pointer to an array, and each element in the array is:

type bmap struct {
	tophash [bucketCnt]uint8
}

The compiler adds fields to it during compilation and dynamically creates a new structure:

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

It can be seen that each bmap is composed of consecutive keys followed by consecutive values, rather than key, value, key, value. The benefit is that in some cases the padding field can be omitted, saving memory space. It can also be seen that each bmap can hold at most 8 key-value pairs. If a ninth key-value pair falls into the current bucket, another bucket needs to be created and linked through the overflow pointer.

The alg field is a pointer to:

// src/runtime/alg.go
type typeAlg struct {
	// (ptr to object, seed) -> hash
	hash func(unsafe.Pointer, uintptr) uintptr
	// (ptr to object A, ptr to object B) -> ==?
	equal func(unsafe.Pointer, unsafe.Pointer) bool
}

The hash function calculates the type’s hash value, while the equal function determines whether two values are “hash-equal.”

9.2. Creation

It calls the makemap function.

func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap {
	// Omit various condition checks...

	// Find a B such that the map's load factor is within the normal range
	B := uint8(0)
	for ; overLoadFactor(hint, B); B++ {
	}

	// Initialize the hash table
	// If B equals 0, buckets will be allocated when assignment occurs
	// If the length is relatively large, allocating memory will take a little longer
	buckets := bucket
	var extra *mapextra
	if B != 0 {
		var nextOverflow *bmap
		buckets, nextOverflow = makeBucketArray(t, B)
		if nextOverflow != nil {
			extra = new(mapextra)
			extra.nextOverflow = nextOverflow
		}
	}

	// Initialize hmap
	if h == nil {
		h = (*hmap)(newobject(t.hmap))
	}
	h.count = 0
	h.B = B
	h.extra = extra
	h.flags = 0
	h.hash0 = fastrand()
	h.buckets = buckets
	h.oldbuckets = nil
	h.nevacuate = 0
	h.noverflow = 0

	return h
}

9.3. Lookup

How is the bucket determined?
- Modulo method: hash % m
- AND operation: hash & (m-1)
  - m is a power of 2

9.3.1. Without comma

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	// ……
	
	// If h contains nothing, return the zero value
	if h == nil || h.count == 0 {
		return unsafe.Pointer(&zeroVal[0])
	}
	
	// Write/read conflict
	if h.flags&hashWriting != 0 {
		throw("concurrent map read and map write")
	}
	
	// The hash algorithm used by keys of different types is determined at compile time
	alg := t.key.alg
	
	// Calculate the hash value and add hash0 to introduce randomness
	hash := alg.hash(key, uintptr(h.hash0))
	
	// For example, if B=5, m is 31, whose binary representation is all 1s
	// When calculating the bucket number, AND hash with m,
	// so that the bucket number is determined by the low 8 bits of hash
	m := uintptr(1)<<h.B - 1
	
	// b is the address of the bucket
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	
	// oldbuckets is not nil, indicating that expansion has occurred
	if c := h.oldbuckets; c != nil {
	    // If this is not a same-size expansion (see the expansion section later)
	    // Corresponding solution for condition 1
		if !h.sameSizeGrow() {
			// The number of new buckets is twice the old number
			m >>= 1
		}
		
		// Find the bucket position of the key in the old map
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
		
		// If oldb has not been moved to the new bucket
		// then search in the old bucket
		if !evacuated(oldb) {
			b = oldb
		}
	}
	
	// Calculate the high 8 bits of hash
	// Equivalent to shifting right by 56 bits and taking only the high 8 bits
	top := uint8(hash >> (sys.PtrSize*8 - 8))
	
	// Add minTopHash
	if top < minTopHash {
		top += minTopHash
	}
	for {
	    // Traverse 8 buckets
		for i := uintptr(0); i < bucketCnt; i++ {
		    // tophash does not match, continue
			if b.tophash[i] != top {
				continue
			}
			// tophash matches; locate the key
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			// key is a pointer
			if t.indirectkey {
			    // Dereference
				k = *((*unsafe.Pointer)(k))
			}
			// If the keys are equal
			if alg.equal(key, k) {
			    // Locate the value
				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
				// Dereference value
				if t.indirectvalue {
					v = *((*unsafe.Pointer)(v))
				}
				return v
			}
		}
		
		// After searching the bucket without finding it, continue searching in the overflow bucket
		b = b.overflow(t)
		// If the overflow bucket is also exhausted, the target key does not exist
		// Return the zero value
		if b == nil {
			return unsafe.Pointer(&zeroVal[0])
		}
	}
}

9.3.2. With comma

func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)

9.4. Add

9.4.1. Expansion Logic

Incremental expansion: spread the time required to migrate key-value pairs across multiple hash-table operations
Load factor calculation: loadFactor := count / (2^B), where count is the number of elements in the map and 2^B is the number of buckets.
Expansion is triggered in two situations:
- The load factor exceeds the threshold; the threshold defined in the source code is 6.5
- There are too many overflow buckets: when B is less than 15, meaning the total number of buckets 2^B is less than 2^15, expansion occurs if the number of overflow buckets exceeds 2^B; when B >= 15, meaning the total number of buckets 2^B is at least 2^15, expansion occurs if the number of overflow buckets exceeds 2^15.

9.5. Delete

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)

First find the location, then clear it.

// Clear the key
if t.indirectkey {
	*(*unsafe.Pointer)(k) = nil
} else {
	typedmemclr(t.key, k)
}

// Clear the value
if t.indirectvalue {
	*(*unsafe.Pointer)(v) = nil
} else {
	typedmemclr(t.elem, v)
}