Golang源码阅读笔记 - Map

2021-09-02 04:13:06

Map底层数据结构

type hmap struct {
	count     int  // map中元素个数，len()函数返回
	flags     uint8
	B         uint8  // map中的bucket的对数值，真实bucket数为2 ^ B个
	noverflow uint16 // 溢出bucket的数量
	hash0     uint32 // hash seed

	buckets    unsafe.Pointer // Buckets数组的指针，count = 0时，值为nil
	oldbuckets unsafe.Pointer // 前bucket数组指针，只在map扩容过程中非nil
	nevacuate  uintptr        // map扩容过程中，记录已迁移bucket的计数值（小于该值已转移）
	extra *mapextra // optional fields
}

Map底层数据结构有3个核心字段：

count: 记录当前map元素个数
B: 记录当前map的bucket数
buckets：当前buckets数组地址。元素经过哈希后，先确定落到哪个bucket上

Bucket底层数据结构

type bmap struct {
	tophash [bucketCnt]uint8   // bucketCnt默认值为8
	// 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.
}

Bucket底层数据结构：

tophash: 记录哈希值的高位部分；（哈希值相同的key，确切的讲是低位相同，会被存储到同一个bucket里，bucket中的tophash数组记录这些哈希值的高位部分，以便后续匹配）
在tophash数组后存在一段注释，大致意思为：
- bucket中的数据存储，使用 key/key/key…value/value/value的方式；虽然增加了代码复杂度，但可以对齐内存，节省空间
- bucket后面会有一个溢出指针，指向下一个bucket

Map创建

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()

	B := uint8(0)
	for overLoadFactor(hint, B) {       // 计算B的大小
		B++
	}
	h.B = B

	if h.B != 0 {
		var nextOverflow *bmap
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil) // 分配bucket Array内存空间
		if nextOverflow != nil {
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

bucket计数

// 确定bucket数目因子B，是否可以承载元素个数count
// Args:
// 	count: map元素个数
// 	B: map中bucket数目因子，bucket数为 2 ^ B
// Return:
// 	是否可以承载
// 
// 补充：
// bucketCnt = 8
// loadFactorNum = 13
// loadFactorDen = 2
// bucketShirt(B) => 1 << B
func overLoadFactor(count int, B uint8) bool {
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

需要注意的是，golang中：

每个bucket可以存放8个map元素
golang默认的承载因子是6.5，即一个bucket平均可以存放6.5个元素，再多需要扩容

所以函数可以理解为：

count > bucketCnt决定，当count <= 8 时，B = 0，即只用一个bucket
loadFactorNum*(bucketShift(B)/loadFactorDen) => loadFactorNum/loadFactorDen * bucketShift(B)
- loadFactorNum/loadFactorDen = 6.5，即一个bucket平均承载元素数，原函数中的表达式，是避免了整除
- bucketShift(B)，表示1 << B，即bucket数量

bucket数组初始化

// 创建bucket列表
// Args:
// 	b: map.B
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
	base := bucketShift(b)
	nbuckets := base // bucket 数
	if b >= 4 {
		nbuckets += bucketShift(b - 4)
		sz := t.bucket.size * nbuckets
		up := roundupsize(sz)
		if up != sz {
			nbuckets = up / t.bucket.size
		}
	}

	if dirtyalloc == nil {
		buckets = newarray(t.bucket, int(nbuckets))
	} else {
		buckets = dirtyalloc
		size := t.bucket.size * nbuckets
		if t.bucket.ptrdata != 0 {
			memclrHasPointers(buckets, size)
		} else {
			memclrNoHeapPointers(buckets, size)
		}
	}

	if base != nbuckets {
		nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
		last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
		last.setoverflow(t, (*bmap)(buckets))
	}
	return buckets, nextOverflow
}

Map获取元素

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	// map为nil或者没有元素时，返回零值
	if h == nil || h.count == 0 {
		return unsafe.Pointer(&zeroVal[0])
	}
	// 并发读写
	if h.flags&hashWriting != 0 {
		throw("concurrent map read and map write")
	}
	// 获取key的哈希值，找到对应的bucket
	hash := t.hasher(key, uintptr(h.hash0))
	m := bucketMask(h.B)
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	
	// 找到哈希值的高位（被哈希到同一个bucket的多个元素，通过哈希值高位不同匹配元素）
	top := tophash(hash)
	
	// 下面这个loop
	// 1. 从当前bucket中查找匹配key值的value
	// 2. 如果当前bucket没有，则从overflow(t)中查找，overflow为bucket的溢出桶。当一个bucket的坑位(8个）不够存储当前哈希值的元素，会新建用溢出bucket，通过链表的方式连接（**链地址法解决哈希冲突**）
bucketloop:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				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) {
				e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				if t.indirectelem() {
					e = *((*unsafe.Pointer)(e))
				}
				return e
			}
		}
	}
	return unsafe.Pointer(&zeroVal[0])
}

map获取元素值的步骤：

计算key的哈希值
通过哈希值，找到key所在的bucket
计算哈希值的高位，并在bucket中查找匹配的key的位置
3.1 如果匹配成功，则返回key对应的value
3.2 如果匹配不成功，则从overflow中继续查找，重复第三步

Map赋值

map赋值和map查询有类似步骤

找到key对应插入的位置
如果找到相同的key，update值
如果找不到相同的key对应的map，需要插入新元素
- 此时会判断是否需要扩容，扩容有两个条件：
  - 一是count + 1后，bucket平均负载因子大于6.5
  - 二是如果存在大量的溢出bucket

Map扩容

func hashGrow(t *maptype, h *hmap) {
	bigger := uint8(1)
	
	// 判断是增量扩容，还是等量扩容
	if !overLoadFactor(h.count+1, h.B) {
		bigger = 0
		h.flags |= sameSizeGrow
	}
	oldbuckets := h.buckets
	newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

	flags := h.flags &^ (iterator | oldIterator)
	if h.flags&iterator != 0 {
		flags |= oldIterator
	}
	h.B += bigger
	h.flags = flags
	h.oldbuckets = oldbuckets
	h.buckets = newbuckets
	h.nevacuate = 0
	h.noverflow = 0

	if h.extra != nil && h.extra.overflow != nil {
		if h.extra.oldoverflow != nil {
			throw("oldoverflow is not nil")
		}
		h.extra.oldoverflow = h.extra.overflow
		h.extra.overflow = nil
	}
	if nextOverflow != nil {
		if h.extra == nil {
			h.extra = new(mapextra)
		}
		h.extra.nextOverflow = nextOverflow
	}
}
// the actual copying of the hash table data is done incrementally
// by growWork() and evacuate().

hashGrow函数会根据当前count数量和B的值，判断等量扩容，还是增量扩容

等量扩容：bucket负载率不高，但是溢出bucket过多（当个bucket的overflow较多），此时需要重新排列bucket中的元素，使元素分布更紧凑
增量扩容：bucket负载较高（>6.5）,此时需要新增B = B + 1, 需要新增bucket数

hashGrow函数仅为Map设置扩容的前置条件，如flags，新bucket array，赋值老bucketoldbuckets… 但不会直接赋值map数据；map数据的迁移，会分布在每一次字典数据的获取和赋值中；具体赋值过程在growWork() and evacuate()两个函数

码农公寓