彭诗亮的博客

0%

GO MAP原理

发表于

GO MAP原理

hmap结构

1
2
3
4
5
6
7
8
9
10
11
type hmap struct {
	count     int    // map的元素数量
	flags     uint8  //状态标识，用于控制goroutine写入和扩容的状态
	B         uint8  // 用于计算buckets数量，计算公式2^B
	noverflow uint16 // 溢出桶数量
	hash0     uint32 // hash 种子
	buckets    unsafe.Pointer // 2^B Buckets count ==0时可能为nil(此处是万能指针类型，实际是对应下面的bmap)
	oldbuckets unsafe.Pointer // 扩容后的旧bucket数组
	nevacuate  uintptr        // 迁移计数器，此指针之前的所有桶已被迁移，即nevacuate指向桶数组已迁移桶的最高下标
	extra *mapextra //溢出桶结构
}
1
2
3
type bmap struct {
	tophash [bucketCnt]uint8 // bucketCnt == 8每个桶固定8个元素
}

初始化

make

通过make函数和hint指定元素数量来初始化map

1
hash := make(map[string]int, hint)

字面量

目前的现代编程语言基本都支持使用字面量的方式初始化哈希，一般都会使用 key: value 的语法来表示键值对，Go 语言中也不例外：

1
2
3
4
5
hash := map[string]int{
	"1": 2,
	"3": 4,
	"5": 6,
}

当哈希表中的元素数量少于或者等于 25 个时，编译器会将字面量初始化的结构体转换成以下的代码，将所有的键值对一次加入到哈希表中：

1
2
3
4
hash := make(map[string]int, 3)
hash["1"] = 2
hash["3"] = 4
hash["5"] = 6

一旦哈希表中元素的数量超过了 25 个，编译器会创建两个数组分别存储键和值，这些键值对会通过如下所示的 for 循环加入哈希：

1
2
3
4
5
6
hash := make(map[string]int, 26)
vstatk := []string{"1", "2", "3", ... ， "26"}
vstatv := []int{1, 2, 3, ... , 26}
for i := 0; i < len(vstak); i++ {
    hash[vstatk[i]] = vstatv[i]
}

无论是字面量或是make方式map底层都是通过makemap函数来创建

makemap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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()

	// 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

	// 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.
	if h.B != 0 {
		var nextOverflow *bmap
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		if nextOverflow != nil {
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

makemap 函数通过指定hint来通过B计算bucket数量
计算公式

1
hint ≤ 2^B * 6.5

通过B数量指定hmap会创建2^B个桶和一些溢出桶

1
2
3
4
5
6
7
8
9
10
11
if b >= 4 {
	// Add on the estimated number of overflow buckets
	// required to insert the median number of elements
	// used with this value of b.
	nbuckets += bucketShift(b - 4)
	sz := t.bucket.size * nbuckets
	up := roundupsize(sz)
	if up != sz {
		nbuckets = up / t.bucket.size
	}
}
  • 当桶的数量小于 2^4 时，由于数据较少、使用溢出桶的可能性较低，会省略创建的过程以减少额外开销；
  • 当桶的数量多于 2^4 时，会额外创建 2^𝐵−4 个溢出桶；

扩容

为什么需要扩容，当溢出桶承装元素超过8个时，溢出桶的mapextra指向新的溢出桶，直到能够满足承装元素数目,此时，hash查找会退化成链表查找，时间复杂度为O(n)
扩容判断条件:

  • 当前未在扩容状态并且负载因子>=6.5
  • 有太多的溢出桶
    1
    2
    3
    4
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again // Growing the table invalidates everything, so try again
    }
    map扩容为渐进式扩容，只在map操作当前桶时才对当前桶进行扩容
    扩容步骤分为hashGrow和growWork
  • hashGrow不做桶元素迁移，只是将当前桶指向oldbuckets，然后创建等量的buckets和溢出桶作为newbuckets指向hmap.buckets
    1
    2
    3
    4
    5
    6
    h.B += bigger #更新B
    h.flags = flags #更新扩容状态
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    h.nevacuate = 0 #扩容计数器
    h.noverflow = 0 #溢出桶数量
  • growWork会在元素赋值是触发当前桶操作，然后对当前桶进行扩容,将将旧桶数据驱逐到新桶,操作步骤在growWork.evacuate

evacuate里的扩容方式分为等量扩容和非等量扩容

1
2
3
4
5
6
7
8
if !h.sameSizeGrow() {
    // Only calculate y pointers if we're growing bigger.
    // Otherwise GC can see bad pointers.
    y := &xy[1]
    y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
    y.k = add(unsafe.Pointer(y.b), dataOffset)
    y.e = add(y.k, bucketCnt*uintptr(t.keysize))
}

等量扩容

对hash后的key后B位计算桶号，然后将元素等量分配

例如：hash(a)的二进制为0101110001010110，扩容前B=2，桶号为10=2，扩容后桶号为110，桶号为110=6，将元素平均分配到这两个桶

非等量扩容

非等量扩容不扩容桶的数量，由于之前产生过很多溢出桶，但是溢出桶的元素很稀疏，所以只是将桶序号重新整理，清到多余的溢出桶，然后整理到新的buckets，

##查找和写入

查找

  • 查找主要分为mapaccess1和mapaccess2两个函数，区别就是mapaccess2在找到目标值时会多返回一个true，在未找到时会返回false
  • 查找流程hmap里通过tophash找到对应buckets桶号,再到bmap里区寻找tophash高8位对应的key,如果不在当前桶就去溢出桶里找，如果溢出桶找不到说明元素不在map,返回false
  • 如果查找时正在扩容，会判断oldbucktes是否为nil，不为nil找旧桶，缩减m找到旧桶编号去找旧桶元素位置
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
     //hash&m找到桶编号作为偏移值找到对应的bmap结构体
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    if c := h.oldbuckets; c != nil { 	//存在旧桶，说明正在扩容状态中
    	if !h.sameSizeGrow() { 			//判断是否翻倍扩容
    		m >>= 1 //翻倍扩容时，新的桶数是旧的2倍，m需要减半才能找到旧桶编号
    	}
    	oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) //找到对应的旧桶位置
    	if !evacuated(oldb) {
    		b = oldb //如果旧桶没有完成数据迁移，那么更新b指向旧桶bmap
    	}
    }
    top := tophash(hash) //取hash值高八位，因为bmp.tophash中0-4是标志位，所以hash值小于5的自动加5
     bucketloop:
     //遍历当前bmp和溢出桶
     ...

写入

  • 函数首先会检查 map 的标志位 flags。如果 flags 的写标志位此时被置 1 了，说明有其他协程在执行“写”操作，进而导致程序 panic。这也说明了 map 对协程是不安全的。
  • 扩容是渐进式的，如果 map 处在扩容的过程中，那么当 key 定位到了某个 bucket 后，需要确保这个 bucket 对应的老 bucket 完成了迁移过程。即老 bucket 里的 key 都要迁移到新的 bucket 中来（分裂到 2 个新 bucket），才能在新的 bucket 中进行插入或者更新的操作。
    上面说的操作是在函数靠前的位置进行的，只有进行完了这个搬迁操作后，我们才能放心地在新 bucket 里定位 key 要安置的地址，再进行之后的操作。
  • 如果这个 bucket 的 8 个 key 都已经放置满了，那在跳出循环后，发现 inserti 和 insertk 都是空，这时候需要在 bucket 后面挂上 overflow bucket。当然，也有可能是在 overflow bucket 后面再挂上一个 overflow bucket。这就说明，太多 key hash 到了此 bucket。
    在正式安置 key 之前，还要检查 map 的状态，看它是否需要进行扩容。如果满足扩容的条件，就主动触发一次扩容操作。

删除

  • 首先会检查 h.flags 标志，如果发现写标位是 1，直接 panic，因为这表明有其他协程同时在进行写操作。
  • 计算 key 的哈希，找到落入的 bucket。检查此 map 如果正在扩容的过程中，直接触发一次搬迁操作。
  • 删除操作同样是两层循环，核心还是找到 key 的具体位置。寻找过程都是类似的，在 bucket 中挨个 cell 寻找。
  • 找到对应位置后，对 key 或者 value 进行“清零”操作： 最后，将 count 值减 1，将对应位置的 tophash 值置成 Empty。