Go Map 源码分析(一)

Go语言中的map是通过哈希表实现的，其底层结构和实现机制如下：

一、hash 结构

hmap结构体：是map的头部结构，主要字段及含义如下：

• count：表示当前哈希表中的元素数量，与len()函数相对应。
• flags：标记字段，用于标记是否正在进行读写操作，以便实现并发读写的检测。 所以它不是并发安全的
• B：表示当前哈希表持有的buckets数量的对数，即len(buckets) == 2^B。
• noverflow：溢出桶的大致数量。
• hash0：hash种子。
• buckets：存储2^B个桶的数组，是一个unsafe.Pointer，因为Go语言中支持不同类型的键值对，需要在编译时才能确定map的类型。
• oldbuckets：扩容时用于保存之前的buckets的字段，大小是buckets的一半。
• nevacuate：迁移进度计数器，记录buckets中小于该值的bucket已经完成迁移。
• extra：指向mapextra结构体的指针，用于存储一些可选字段。

type hmap struct {
	// 元素个数，调用 len(map) 时，直接返回此值 
	count int
	flags uint8
	// buckets 的对数 log_2
	B uint8
	// overflow 的 bucket 近似数
	noverflow uint16
	// 计算 key 的哈希的时候会传入哈希函数
	hash0 uint32
	// 指向 buckets 数组，大小为 2^B
	// 如果元素个数为 0，就为 nil
	buckets unsafe.Pointer
	// 扩容的时候，buckets 长度会是 oldbuckets 的两倍 
	oldbuckets unsafe.Pointer
	// 指示扩容进度，小于此地址的 buckets 完成迁移 
	nevacuate uintptr
	extra *mapextra
}

bmap结构体：是哈希表中的桶，每个bmap能够存储8个键值对，并且设有一个指针，当某个bmap存满时，就会申请新的bmap进行存储，并与前一个bmap构成链表。其结构如下：

• tophash：数组，用于存储每个key hash之后的高位hash值。
• keys：数组，用于存储key。
• elems：数组，用于存储value。
• overflow：溢出指针，指向下一个bmap的地址。

下面是map 的初始形态,

type bmap struct {
	tophash [bucketCnt]uint8
}

但是编译器会对go 的map 给塞几个字段

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

当 map 的 key 和 value 都不是指针，并且 size 都小于 128 字节的情况下，会把 bmap 标
记为不含指针，这样可以避免 GC 时扫描整个 hmap，提升效率。

但是map 中是包含了一个 overflow 字段的, 这个字段是指针类型的, 这个时候我们可能会把相应的值移动到extra *mapextra 这个字段上来, 并且会开启maxarea的两个字段启用 overflow 和 oldoverflow 字段。

mapextra结构体：主要字段如下：

• overflow：指向当前buckets的溢出桶数组的指针。
• oldoverflow：指向oldbuckets的溢出桶数组的指针。
• nextOverflow：指向还未使用的、提前分配的溢出桶链表。

二、哈希

map 的一个关键点在于哈希函数的选择。在程序启动时，Go 会检测 CPU 是否支持 aes，如果支持， 则使用 aes hash，否则使用 memhash。这在函数 alginit()中完成，源码位于路径 src/runtime/alg.go 下。对于 hash 函数，有加密型和非加密型。加密型的一般用于加密数据、数字摘要等，典型代表 就是 md5、sha1、sha256、aes256 这类;非加密型的一般就是查找，如 MurmurHash 等

Go语言中map的哈希函数会根据键的类型和值来计算一个哈希值，这个哈希值是一个32位或64位的整数。哈希函数的设计目标是尽量使不同的键映射到不同的哈希值，以减少哈希冲突。对于不同的键类型，Go语言会采用不同的哈希算法，例如对于字符串键，会根据字符串的内容计算哈希值；对于整数键，则直接使用整数本身或其某种变换作为哈希值。

但计算它到底要落在哪个 bucket 时，只会用到最后 B 个 bit 位。如果 B = 5，那么桶的数量，也就是 buckets 数组的长度是 2^5 = 32。例如，现在有一个 key 经过哈希函数计算后，得到的哈希结果是:

10010111 | 000011110110110010001111001010100010010110010101010 | 00110

1. 首先会根据后面的5 位去定位到对应的桶的位置, 这里表示第6号桶
2. 然后取hash 值的高8 位, 找到key 在桶里面的位置

因为根据后 B 个 bit 位决定 key 落入的 bucket 编号，也就是桶编号，因此肯定会存在冲突。当两个不同的 key 落在同一个桶中，也就是发生了哈希冲突。冲突的解决手段是用链表法:在 bucket 中，从前往后找到第一个空位，放入新加入的有冲突的 key。之后，在查找某个 key 时，
先找到对应的桶，再去遍历 bucket 中所有的 key

key, value的内存布局其实也是比较有意思的, 它的<key, value> 不是放在一起的:

三、赋值和删除

如果是map 的 assign 的过程情况, 可能又会存在不同, 因为赋值操作可能存在两种情况

• 插入操作: 当前的key 不存在, 我们需要插入
• 修改操作, 当前的key 存在, 我们直接修改即可

1. map 的赋值操作:

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

整体而言，map的赋值流程十分简洁。首先对key计算hash值，依据该值按照既定流程确定赋值位置，可能是插入新key，也可能是更新旧key，然后在相应位置执行赋值操作。源码与前面key定位过程大致相同，核心在于一个双层循环：外层循环遍历bucket及overflow bucket，内层循环遍历单个bucket的所有槽位，因篇幅有限，此处不再展开代码注释。

在赋值过程中，有几点关键之处。mapassign函数会先检查map的标志位flags，若flags的写标志位被置为1，意味着有其他协程正在进行写操作，而assign同样是写操作，这将导致并发写冲突，从而使程序直接panic，这也表明map不具备协程安全性。

//当存在并发竞争的时候
if h.flags&hashWriting != 0 {
		fatal("concurrent map writes")
}
// 否则设置为正在读取
h.flags ^= hashWriting

map的扩容采用渐进式方式。当 map 处于扩容阶段，定位 key 到某个 bucket 后，需确保该 bucket 对应的老 bucket 已完成迁移，即老 bucket 中的 key 都已迁移到新 bucket（老bucket中的key会被分散到两个新bucket），之后才能在新bucket中进行插入或更新操作。只有完成迁移，才能安全地在新bucket里确定key的安置地址，进而进行后续赋值操作。

// 定位到对应的bucket
bucket := hash & bucketMask(h.B)
// 如果当前的buckets 已经存在扩容了
if h.growing() {
	growWork(t, h, bucket)
}

接下来是定位 key 放置位置的关键步骤：准备两个指针，inserti 指向 key 的 hash 值在 tophash 数组的位置，insertk 指向 cell 的位置，即 key 最终放置的地址。而对应value的位置则容易计算，tophash数组中的索引位置决定了key在整个bucket中的位置（共8个key），value的位置需“跨过”8个key的长度。

我们直接看源码:

// 首先是一层循环:
for {
	// 然后是遍历所有的map
	for i := uintptr(0); i < abi.MapBucketCounter; i++ {
		//然后定位对应的key, 这里的top 就是对应的 hash 高八位
		//表示当前的tophash 
		if b.tophash[i] != top {
			// block1
		}
		
		// 表示相等, 那么就需要判断
	} 
}

如果不匹配, 我们首先会判断一下当前位置的hash 时候为空, 如果为空, 并且inserti 为null, 我们就对对应的值进行赋值:

//指向对应的tophash
inserti = &b.tophash[i]
//指向对应的value
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))

初始化完成对应的insertk 和 对应的 inserti

下面就是更新map中的键值对的更新操作:

if t.NeedKeyUpdate() {
	// 一个很nb 的操作
	typedmemmove(t.Key, k, key)
}

如果当前bucket的8个key已经全部占用，跳出循环后会发现inserti和insertk指针均为空。这意味着需要在bucket后面挂载一个overflow bucket，甚至可能是在已有的overflow bucket后面再挂载一个。这表明有大量key被哈希到了同一个bucket。在这种情况下，在正式放置key之前，还需要检查map的状态，判断是否需要扩容。如果满足扩容条件，则会主动触发一次扩容操作。

// 判断当前map 存储的元素是否过多
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
}

// 根据上面我们定位的inserti 时候为空, 来判断时候需要创建一个overflow
if inserti == nil {
    // 当前所有overflow 全部被占满了, 那么就需要创建一个新的元素
    newb := h.newoverflow(t, b)
    inserti = & newb.tophash[0]
    insertk = add(unsafe.Pointer(newb), dataOffset)
    elem = add(insertk, abi.MapBucketCount * uintptr(t.KeySize))
}

扩容完成之后，之前的查找定位 key 的过程，还得再重新走一次。因为扩容之后，key 的分 布发生了变化。

if t.IndirectKey() {
    kmem := newobject(t.Key) * ( * unsafe.Pointer)(insertk) = kmem
    insertk = kmem
}
if t.IndirectElem() {
    vmem := newobject(t.Elem) * ( * unsafe.Pointer)(elem) = vmem
}
typedmemmove(t.Key, insertk, key) * inserti = top
h.count++

最后，会更新 map 相关的值，如果是插入新 key，map 的元素数量字段 count 值会加 1;并 且会将 hashWriting 写标志位清零。

2. map 的删除操作:

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

当然，只需关心 mapdelete 函数。它首先会检查 h.flags 标志，如果发现写标志位是 1，直接 panic，因为这表明有其他协程同时在进行写操作。大致的逻辑如下:

1. 检测是否存在并发写操作。
2. 计算 key 的哈希，找到落入的 bucket。
3. 设置写标志位。
4. 检查此 map 是否正在扩容的过程中，如果是则直接触发一次搬迁操作。
5. 两层循环，核心是找到 key 的具体位置。寻找过程都是类似的，在 bucket 中挨个 cell 寻找。
6. 找到对应位置后，对 key 或者 value 进行“清零”操作。
7. 将 count 值减 1，将对应位置的 tophash 值置成 emptyOne。
8. 最后，检测此槽位后面是否都是空，若是将 tophash 改成 emptyRest。
9. 若前一步成功，则继续向前扩大战果:将此 cell 之前的 tophash 值为 emptyOne 的槽位都
   置成 emptyRest。