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 赋值

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

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

map 的赋值操作:

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

整体而言，map的赋值流程十分简洁。首先对key计算hash值，依据该值按照既定流程确定赋值位置，可能是插入新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)

// 判断当前的 hmap 是否在增长中
if h.growing() {
	growWork(t, h, bucket)
}

扩容完成就是核心的两层循环:

// 首先是一层循环:
for {
	// 然后是遍历所有的map
	for i := uintptr(0); i < abi.MapBucketCounter; i++ {}
}

1. 未匹配

在循环的过程中, 首先判断一下当前的 tophash[i] 是不是和 key 的hash 相等, 如果不相等继续判断inserti 是不是为null, 如果为null, 说明当前这个位置是一个空的位置,

if b.tophash[i] != top {
	if isEmpty(b.tophash[i]) && inserti == nil {
	}
}

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

inserti = &b.tophash[i]
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))

如果在之后的过程中依然没有在map 中发现匹配的key, 就会跳出循环, 在inserti, insertk, elem 这个位置插入对应的值

2. 匹配

如果我们在遍历的过程中匹配了对应的top hash,

首先会使用 t.IndirectKey() 检查是否需要间接访问键。如果键的大小超过指针大小（通常是 8 字节），Go 的 map 实现会使用间接存储（即存储指针而不是直接存储键值）如果需要间接访问，k 被更新为指向实际键的指针。

if t.IndirectKey() {
	k = *((*unsafe.Pointer)(k))
}

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

if t.NeedKeyUpdate() {
	typedmemmove(t.Key, k, key)
}

跳出循环后如果满足扩容条件，则会主动触发一次扩容操作, 扩容的时候还需要重新走一遍上面的过程, 这是因为扩容之后 key 分布出现在新的位置。

// 判断当前map 存储的元素是否过多
if !h.growing() && (overLoadFactor(h.count + 1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
    hashGrow(t, h)
    goto again
}

如果不满足对应的扩容条件，我们会判断 inserti 是否为 nil, 如果为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))

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

typedmemmove(t.Key, insertk, key)
*inserti = top
h.count++