Map底层原理学习笔记

发表于： 2023-03-01 分类于： golang

字数： 3100 阅读：≈ 7分钟浏览：评论：

golang Map底层原理学习笔记

map的简单使用

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main

import "fmt"

func f1(key string, mp map[string]int) {
	value, ok := mp[key]
	if ok {
		fmt.Println(value)
	} else {
		fmt.Println(key, "不存在")
	}
}

func main() {
	//创建一个map用来存储姓名和年龄 当然 姓名不可重复
	mp := make(map[string]int)
	mp["xiaoming"] = 12
	mp["xiaohong"] = 13
	f1("xiaoming", mp)
	f1("xiaoming1", mp)

	delete(mp, "xiaohong")
	fmt.Println(mp["xiaohong3"]) //0
}

func delete(m map[Type]Type1, key Type)

The delete built-in function deletes the element with the specified key (m[key]) from the map. If m is nil or there is no such element, delete is a no-op.

delete是针对map的内建函数，如果map为空或者没有对应的元素，则是一个空操作

delete无返回值

map的底层原理

map最大的特点就是查找速度非常快，因为他的底层存储是基于哈希表的

Map的特点：

键不能重复
键必须可哈希（目前我们已学的数据类型中，可哈希的有：int/bool/float/string/array）
无序

map初始化

1
2
// 初始化一个可容纳10个元素的map
info = make(map[string]string,10)

第一步：创建一个hmap结构体对象。
第二步：生成一个哈希因子hash0 并赋值到hmap对象中（用于后续为key创建哈希值）。

第三步：根据hint=10，并根据算法规则来创建 B，当前B应该为1。

1
2
3
4
5
  hint            B
  0~8             0
  9~13            1
  14~26           2
  ...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
B := uint8(0)
for overLoadFactor(hint, B) {
		B++
	}

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
func overLoadFactor(count int, B uint8) bool {
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// bucketShift returns 1<<b, optimized for code generation.
func bucketShift(b uint8) uintptr {
	// Masking the shift amount allows overflow checks to be elided.
	return uintptr(1) << (b & (goarch.PtrSize*8 - 1))
}

第四步：根据B去创建去创建桶（bmap对象）并存放在buckets数组中，当前bmap的数量应为2.
- 当B<4时，根据B创建桶的个数的规则为：2^B（标准桶）
- 当B>=4时，根据B创建桶的个数的规则为：2^B + 2^B-4（标准桶+溢出桶）

注意：每个bmap中可以存储8个键值对，当不够存储时需要使用溢出桶，并将当前bmap中的overflow字段指向溢出桶的位置。

写入数据

1
info["name"] = "Golang"

在map中写入数据时，内部的执行流程为：

第一步：结合哈希因子和键 name生成哈希值。

第二步：获取哈希值的后B位，并根据后B位的值来决定将此键值对存放到哪个桶中（bmap）。将哈希值和桶掩码（长度为B，值全为1的二进制）进行 & 运算，最终得到哈希值的后B位的值。

1
2
3
4
5
6
7
8
9

假设当B为1时 共2个桶 // 所有可能得情况 B为1 只看hash值的最后一位就可以确定进哪个桶
哈希值：011011100011111110111011111
桶掩码：000000000000000000000000001
结果：  000000000000000000000000001 = 1 (确定桶数组的下标为1)

哈希值：011011100011111110111011100
桶掩码：000000000000000000000000001
结果：  000000000000000000000000000 = 0 (确定桶数组的下标为0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

假设当B为2时 共4个桶 // 所有可能得情况
哈希值：011011100011111110111011111
桶掩码：000000000000000000000000011
结果：  000000000000000000000000011 = 3 (确定桶数组的下标为3)

哈希值：011011100011111110111011100
桶掩码：000000000000000000000000011
结果：  000000000000000000000000000 = 0 (确定桶数组的下标为0)

哈希值：011011100011111110111011101
桶掩码：000000000000000000000000011
结果：  000000000000000000000000001 = 1 (确定桶数组的下标为1)

哈希值：011011100011111110111011110
桶掩码：000000000000000000000000011
结果：  000000000000000000000000010 = 2 (确定桶数组的下标为2)

通过示例你会发现，找桶的原则实际上是根据后B为的位运算计算出索引位置，然后再去buckets数组中根据索引找到目标桶（bmap)。

第三步：在上一步确定桶之后，接下来就在桶中写入数据。

1
2
3
4
获取哈希值的tophash（即：哈希值的`高8位`），将tophash、key、value分别写入到桶中的三个数组中。
如果桶已满，则通过overflow找到溢出桶，并在溢出桶中继续写入。

注意：以后在桶中查找数据时，会基于tophash来找（tophash相同则再去比较key）。

第四步：hmap的个数count++（map中的元素个数+1）

读取数据

1
value := info["name"]

在map中读取数据时，内部的执行流程为：

第一步：结合哈希因子和键 name生成哈希值。
第二步：获取哈希值的后B位，并根据后B为的值来决定将此键值对存放到那个桶中（bmap）。
第三步：确定桶之后，再根据key的哈希值计算出tophash（高8位），根据tophash和key去桶中查找数据。当前桶如果没找到，则根据overflow再去溢出桶中找，均未找到则表示key不存在。

扩容

在向map中添加数据时，当达到某个条件，则会引发字典扩容。

扩容条件：

map中 数据总个数 / 桶个数 > 6.5 ，引发翻倍扩容。
使用了太多的溢出桶时（溢出桶使用的太多会导致map处理速度降低）。
- B <=15，已使用的溢出桶个数 >= 2^B 时，引发等量扩容。
- B > 15，已使用的溢出桶个数 >= 2¹⁵ 时，引发等量扩容。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func hashGrow(t *maptype, h *hmap) {
	// If we've hit the load factor, get bigger.
	// Otherwise, there are too many overflow buckets,
	// so keep the same number of buckets and "grow" laterally.
	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)
	...
}

当扩容之后：

第一步：B会根据扩容后新桶的个数进行增加（翻倍扩容新B=旧B+1，等量扩容新B=旧B）。
第二步：oldbuckets指向原来的桶（旧桶）。
第三步：buckets指向新创建的桶（新桶中暂时还没有数据）。
第四步：nevacuate设置为0，表示如果数据迁移的话，应该从原桶（旧桶）中的第0个位置开始迁移。
第五步：noverflow设置为0，扩容后新桶中已使用的溢出桶为0。
第六步：extra.oldoverflow设置为原桶（旧桶）已使用的所有溢出桶。即：h.extra.oldoverflow = h.extra.overflow
第七步：extra.overflow设置为nil，因为新桶中还未使用溢出桶。
第八步：extra.nextOverflow设置为新创建的桶中的第一个溢出桶的位置。

翻倍扩容

如果是翻倍扩容，那么迁移规就是将旧桶中的数据分流至新的两个桶中（比例不定），并且桶编号的位置为：同编号位置和翻倍后对应编号位置。

首先，我们要知道如果翻倍扩容（数据总个数 / 桶个数 > 6.5），则新桶个数是旧桶的2倍，即：map中的B的值要+1（因为桶的个数等于2^B，而翻倍之后新桶的个数就是2^B * 2 ，也就是2^B+1，所以 新桶的B的值=原桶B的值 + 1 ）。

迁移时会遍历某个旧桶中所有的key（包括溢出桶），并根据key重新生成哈希值，根据哈希值的 低B位 来决定将此键值对分流道那个新桶中。

扩容后，B的值在原来的基础上已加1，也就意味着通过多1位来计算此键值对要分流到新桶位置，如上图：

当新增的位（红色）的值为 0，则数据会迁移到与旧桶编号一致的位置。
当新增的位（红色）的值为 1，则数据会迁移到翻倍后对应编号位置。

例如：

旧桶个数为4个(B为2)，翻倍后新桶的个数为8(B为3)。

假设某个key进行哈希后3为001

旧桶index：001 & 011 = 001 = 1
新桶index：001 & 111 = 001 = 1

假设某个key进行哈希后3为101

旧桶index：101 & 011 = 001 = 1
新桶index：101 & 111 = 101 = 5 正好是(1+4)

通过上面示例可以发现，翻倍扩容后桶的位置只会是旧位置或旧位置+旧桶长度

等量扩容

如果是等量扩容（溢出桶太多引发的扩容），那么数据迁移机制就会比较简单，就是将旧桶（含溢出桶）中的值迁移到新桶中。

这种扩容和迁移的意义在于：当溢出桶比较多而每个桶中的数据又不多时，可以通过等量扩容和迁移让数据更紧凑，从而减少溢出桶。