Golang源码阅读笔记 - Map

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个核心字段:

  1. count: 记录当前map元素个数
  2. B: 记录当前map的bucket数
  3. 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底层数据结构:

  1. tophash: 记录哈希值的高位部分;(哈希值相同的key,确切的讲是低位相同,会被存储到同一个bucket里,bucket中的tophash数组记录这些哈希值的高位部分,以便后续匹配)
  2. 在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中:

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

所以函数可以理解为:

  1. count > bucketCnt决定,当count <= 8 时,B = 0,即只用一个bucket
  2. 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获取元素值的步骤:

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

Map赋值

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

  1. 找到key对应插入的位置
  2. 如果找到相同的key,update值
  3. 如果找不到相同的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的值,判断等量扩容,还是增量扩容

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

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

上一篇:[Elasticsearch] 聚合中的重要概念 - Buckets(桶)及Metrics(指标)


下一篇:一维装箱问题