本文作者：刘代明（常用网名:行如风，常用游戏名:学长的棉被），一个文艺青年（纳尼？青年？是的，你没看错：世界卫生组织（2020年）对青年的定义：18-65周岁[来自百度百科]）。现在奇虎360搜索技术部任web服务端技术专家职位。 本文为作者原创，祝大家阅读愉快。前言之前在《openresty协程调度对比go协程调度》文章中分析了go程序启动过程(从go程序开始执行到用户的main程序执行前发生了些什么)，今天结合一个简短例子说下go map的底层实现（顺便看下在编译阶段发生了什么），同时对比下php的map实现go map实现说明：go版本：1.15.6，平台：linux一段简单的代码如下：package main
import (
"fmt"
)
func main() {
m := make(map[string]int64, 53)
m["a"] = 111111111
m["b"] = 111111111
delete(m, "a")
fmt.Println(m["a"], m["b"])
}为了定位到其底层实现，我们先看下go语言的编译过程。编译其实，作为一个编译型语言，go程序会在编译阶段经过一系列处理后最终生成机器码解析阶段源码地址：cmd/compile/internal/syntax1.词法分析解析成token，我们可以通过go提供的这两个package:"go/scanner"和"go/token"模拟func TestToken(t *testing.T) {
src := []byte(`package main
import "fmt"
func main() {
m := make(map[string]int64, 53)
m["a"] = 111111111
fmt.Println(m["a"])
}
`)
var s scanner.Scanner
fset := token.NewFileSet()
file := fset.AddFile("", fset.Base(), len(src))
s.Init(file, src, nil, 0)
for {
pos, tok, lit := s.Scan()
if tok == token.EOF {
break
}
fmt.Printf("%s\t%s\t%q\n", fset.Position(pos), tok, lit)
}
}最终结果截取：1:1 package "package"
1:9 IDENT "main"
…
7:13 IDENT "Println"
7:20 ( ""
7:21 IDENT "m"
…2.语法分析将扫描后生成的token转化为抽象语法树，每个go源码文件被构造为独立的语法树。同样，我们可以通过go提供的包：go/parser和go/ast来看下ASTfunc TestParser(t *testing.T) {
src := []byte(`package main
import "fmt"
func main() {
m := make(map[string]int64, 53)
m["a"] = 111111111
fmt.Println(m["a"])
}
`)
fset := token.NewFileSet()
file, err := parser.ParseFile(fset, "", src, 0)
if err != nil {
log.Fatal(err)
}
ast.Print(fset, file)
}输出结果截取： 0 *ast.File {
1 . Package: 1:1
…
6 . Decls: []ast.Decl (len = 2) {
…
151 . }
…
166 }类型检查源码地址：cmd/compile/internal/gc在这个阶段，会对上面生成的每个文件对应的AST进行节点遍历，对每个节点类型进行检查,去掉声明但未使用，消除dead code等生成中间代码源码地址：cmd/compile/internal/gc（AST转换成SSA）cmd/compile/internal/ssa（SSA多轮传递及规则）在这个阶段，AST会被转换为SSA（静态单赋值，Static Single Assignment）形式的中间代码，同时关键字，操作符会被转换成runtime函数。如我们今天要说的map这个关键字及其操作就会在这个阶段进行转换。我们可以通过执行下面命令产生ssa文件：GOSSAFUNC=func go build go file 如：GOSSAFUNC=maps go build main.go说明: 笔者当前版本为1.15.6，如果对main方法执行ssa生成会报panic这个issue会在1.16版本进行修复生成ssa文件内容如下，选择源码某行，可以看到对应的各阶段过程：最终生成机器码定位通过编译过程，我们看到map的底层实现是在编译阶段将map关键字及其操作进行了运行时转换。而我们想要定位到这段代码map的相关实现，可以有多种方式：1.借助go tool工具生成反汇编代码：go build -gcflags "-S" main.go或go tool compile -S main.go2.gdb或dlv调试看反汇编代码3.看中间代码（SSA生成）由此我们可以定位到，map的底层实现。数据结构：// A header for a Go map.
type hmap struct {
count int // map中有效元素的个数
flags uint8
B uint8 // buckets个数为2^B，可装的元素个数为：负载因子 * 2^B，负载因子为6.5
noverflow uint16 // 溢出的bmap数量（近似值）
hash0 uint32 // hash seed
buckets unsafe.Pointer // 指向第一个bucket
oldbuckets unsafe.Pointer // 在扩容的时候使用，为之前的buckets
nevacuate uintptr // 搬迁计数器,在扩容阶段使用
extra *mapextra // optional fields
}
// mapextra holds fields that are not present on all maps.
type mapextra struct {
overflow *[]*bmap // 存储溢出的bmap
oldoverflow *[]*bmap // 扩容阶段使用，为之前的overflow
nextOverflow *bmap // 下一个待使用的空闲bmap，溢出时使用
}
// A bucket for a Go map.
type bmap struct {
tophash [bucketCnt]uint8 // key的hash值高8位
}需要指出的是bmap作为真正存储map数据的地方，为什么只有tophash字段，其key和value呢？其实我们知道map的key和value有多种类型，go作为强类型语言，在定义后其类型就确定了，所以bmap的key和value字段类型就可以在编译阶段确定，避免了穷举，减少代码复杂度。bmap中key和value类型通过func bmap(t types.Type) types.Type确定。bmap结构为：type bmap struct {
topbits [8]uint // key的hash高8位
keys [8]keytype // key
elems [8]elemtype // value
overflow uintptr // 溢出后下一个bmap
}go map实现总览先上总结，大家在学习的时候根据总结来看源码，更容易理解。1.编译器会根据key类型，位数来映射不同的运行时函数，但他们实现大体是一致的。如访问运行时函数：mapaccess，mapaccess1_fast32，mapaccess2_fast64，mapaccess1_faststr等，所以大家看到不同的文章中有对不同函数的解析2.go使用bmap数据结构来存储key和value3.查找时先定位key属于哪个bucket，再查看位于bmap的哪个位置4.go的map使用开放地址法来解决hash冲突，并放入bmap的overflow字段指向的bmap回到最开始的代码，来分别看下初始化，赋值，删除，扩容过程代码比较多，我仅贴出部分，函数我会给出链接，大家可以跳进去看源码，如果看不到，可到我的博客中看：https://www.imflybird.cn/。初始化make(map[k]v, hint)或map[k]v{}初始化函数家族:func makemap_small() *hmap 在 hint <= 8 或不提供hint时编译器会使用这个函数用来初始化func makemap64(t maptype, hint int64, h hmap) *hmapfunc makemap(t maptype, hint int, h hmap) *hmap其实除了上面外，还有可能在汇编层面看不到makemap相关函数，其实编译器还会根据逃逸分析结果，来确定map初始化，相关函数位置在这里我们主要看makemap的实现。1.h.hash0 = fastrand() //初始化hash0使用随机数对hash0进行初始化。内部使用xorshift64进行随机数生成，我们之前介绍的分布式唯一ID生成文章中的实现也是使用这种高效的随机数生成算法。而fastrandseed正是我们在openresty协程调度对比go协程调度文章中提到的runtime.args初始化阶段由startupRandomData字段生成的2.使用func overLoadFactor(count int, B uint8) bool 函数初始化h.BB从0开始，不断增加，直到找到B使得 负载因子 * 2^B >= count，其中负载因子为6.5。对于我们上面这段代码，count就是53.得到的B就是4.3.初始化h.buckets,h.extra.nextOverflow至此，初始化完成，如下图所示：赋值赋值家族函数：mapassign*。同样，我们结合本例，看下赋值过程。在本例中，赋值函数为：func mapassign_faststr(t maptype, h hmap, s string) unsafe.Pointer1.again标签内：bucket := hash & bucketMask(h.B) // hash值的低2^h.B-1位来定位到这个key属于哪个bucketb := (bmap)(unsafe.Pointer(uintptr(h.buckets) + bucketuintptr(t.bucketsize))) // 这个bucket内的bmaptop := tophash(hash) // hash的高8位为tophash2.bucketloop标签内：for {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if isEmpty(b.tophash[i]) && insertb == nil {
insertb = b
inserti = i
}
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+i*2*sys.PtrSize))
if k.len != key.len {
continue
}
if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) {
continue
}
// already have a mapping for key. Update it.
inserti = i
insertb = b
goto done
}
ovf := b.overflow(t)
if ovf == nil {
break
}
b = ovf
}双重for循环寻找合适插入点遍历顺序：从当前bmap开始，从前往后遍历，如果找不到，会从overflow的bmap中继续查找我们考虑两种情况：1.刚初始化完毕：此时每个bmap的tophash均为emptyRest(即0值)，所以找到了当前的插入点直接跳出bucketloop标签。2.被删除过,则tophash值为emptyOne(即1值)，如当前bmap的tophash为：|1|1|1|76|0|0|0|0|，则会优先插入到第一个值为1的位置。此时还要继续遍历看是否有和计算出的top值相等的tophash值没，如果有，且key值相等，则更新插入点。可以看出插入赋值是一个紧凑的过程（有空位时优先往插入前面的）if insertb == nil {
// all current buckets are full, allocate a new one.
insertb = h.newoverflow(t, b)
inserti = 0 // not necessary, but avoids needlessly spilling inserti
}如果没找到插入点，则会创建溢出的bmap（拉链法）：1.会优先使用之前预分配的bucket（h.extra.nextOverflow）如果当前h.extra.nextOverflow不是预分配的最后一位，则把h.extra.nextOverflow往后移一位（之前介绍数据结构时提到，nextOverflow就是下一个待分配的bmap）如果是最后一位，则把其overflow置为nil（初始化时我们看到最后一个bucket的overflow指向了第一个bucket）,同时h.extra.nextOverflow无可用bucket，置为nil2.如果无可用的nextOverflow，则新建一个对于m[k]=v，我们看到赋值函数并没有接收v，而是返回了v的内存指针其实，是编译器生成的汇编指令来完成值的存储的，我们用gdb来看下反汇编代码： 0x00000000004999e0 <+160>: callq 0x4117c0 <runtime.mapassign_faststr>
0x00000000004999e5 <+165>: mov 0x20(%rsp),%rax
0x00000000004999ea <+170>: mov %rax,0x60(%rsp)
0x00000000004999ef <+175>: test %al,(%rax)
0x00000000004999f1 <+177>: movq $0x69f6bc7,(%rax) // 寄存器间接寻址，rax存储的是v的内存地址，把 111111111放入这个内存地址
0x00000000004999f8 <+184>: lea 0xe841(%rip),%rax # 0x4a8240当然在赋值过程中会出现需要扩容的情况，我们后面说访问访问家族函数：mapaccess*。同样，我们结合本例，看下访问过程。本例中访问函数为：func mapaccess1_faststr(t maptype, h hmap, ky string) unsafe.Pointer上面讲了赋值过程的查找，访问也是一样的过程。访问函数中区分了只有一个bucket和多bucket情况，我们看下多bucket情况。1.同样需要先计算key的hash值2.使用hash值的低2^B-1位定位出key所在bucket3.使用hash值的高8位来匹配tophash4.依次在当前bucket所在的bmap中寻找，没有的话在overflow中寻找，循环寻找，直到结束删除删除家族函数：mapdelete*。本例中删除函数为：func mapdelete_faststr(t maptype, h hmap, ky string)1.删除前同样需要先查找到该key的位置，查找过程同上面的访问过程2.b.tophash[i] = emptyOne // 删除仅需把tophash值设为13.每删除一个key，需要查看当前key位置的下一位tophash值是否是emptyRest(即是否是0值)，如果是0值的话，需要把下一位前的emptyOne变更为emptyRest，直到遇到非emptyOne为止。for {
b.tophash[i] = emptyRest
if i == 0 {
if b == bOrig {
break // beginning of initial bucket, we're done.
}
// 从当前bucket的第一个bmap查找，直到当前bmap的前一个停止
c := b
for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
}
i = bucketCnt – 1
} else {
i–
}
if b.tophash[i] != emptyOne {
break
}
}我们通过一个示例来看下这个过程：扩容由编译器确定选用哪个函数进行增量式扩容： growWork*。在赋值阶段，可能会触发扩容，触发条件为：1.本次元素如果插入，负载将达到临界点：插入的元素数量 > 负载因子*2^B；此时容量需扩大一倍2.bmap的overflow过多，overflow数量 >= 2^(B&15)的数量。此时容量不变，目的仅是使排除删除造成的空洞，减少overflow，使数据结构更紧凑我们看下过程：1.扩容开始，使用func hashGrow(t maptype, h hmap)进行扩容准备：判断是否需要容量翻倍，并设置h.oldbuckets为h.buckets，新建buckets和nextOverflow2.增量搬迁：搬迁家族函数为evacuate*,在赋值和删除时，定位到key所属的bucket，则对该bucket内的bmap及其overflow的bmap进行搬迁。 对于我们这个例子中，如果不停增加元素直至扩容，则搬迁函数为 func evacuate_faststr(t maptype, h hmap, oldbucket uintptr)3.直至搬迁完毕。搬迁使用的数据结构为:type evacDst struct {
b *bmap // current destination bucket
i int // key/elem index into b
k unsafe.Pointer // pointer to current key storage
e unsafe.Pointer // pointer to current elem storage
}我们可用把上面这个看作一个箱子。我们看下搬迁过程：1.如果扩容是等量扩容，则使用一个箱子搬迁；如果是双倍扩容，则使用两个箱子进行搬迁。 2.从旧bucket中bmap第一个开始，顺序搬迁直至overflow也搬迁完毕停止。3.如果是双倍扩容，则会分为高和低两部分（两部分容量相等），并使用两个exacDst：y和x分别对应高位和低位。计算落到高位还是低位。4.搬迁过程中tophash值不变。这样在赋值和删除时，仍通过高八位定位bmap中的位置。双倍扩容后，如何确定key所属的bucket呢，我们看到双倍扩容会使用两个exacDst进行分流，我们看到确定是使用x还是y时，计算方式为：hash := t.hasher(k, uintptr(h.hash0))
if hash&newbit != 0 {
useY = 1
}而定位bucket计算方式为：bucket := hash & bucketMask(h.B)其中newbit为原来的2^B，如果得到useY=1，则说明高位为1，最终的bucket为2^h.B（原来的B）+原来的bucket。举个例子：扩容前：h.B为4（即100），原来的bucket为：hash&11，假设为2，即10扩容后：8(1000),现在的bucket为：hash&111useY=1，则说明hash值后三位为1??，现在的bucket=110,即 2^h.B（原来的B）+原来的bucket=4+2=6。等量扩容如下图：双倍扩容如下图：PHP的map实现php版本:7.4.15其实在php中，在语言层面，准确来说叫数组，而数组底层实现了map的功能。我们知道，map的key定位是需要hash函数来实现O(1)查询的，是无序的，而php中是如何兼顾数组的有序及hash函数的映射呢？我们看其数据结构，定义在Zend/zend_types.h文件里：typedef struct _Bucket {
zval val;
zend_ulong h; /* hash value (or numeric index) */
zend_string *key; /* string key or NULL for numerics */
} Bucket;
typedef struct _zend_array HashTable;
struct _zend_array {
zend_refcounted_h gc; // 引用计数,gc使用
union { // 辅助信息
struct {
ZEND_ENDIAN_LOHI_4(
zend_uchar flags,
zend_uchar _unused,
zend_uchar nIteratorsCount,
zend_uchar _unused2)
} v;
uint32_t flags;
} u;
uint32_t nTableMask; // 哈希值计算掩码，等于nTableSize的负值(nTableMask = -nTableSize)
Bucket *arData; // 指向数组的第一个Bucket
uint32_t nNumUsed; // 已使用的Buckets数量
uint32_t nNumOfElements; // 有效元素数量
uint32_t nTableSize; // 数组总容量,2^n
uint32_t nInternalPointer; // 内部遍历使用指针
zend_long nNextFreeElement; // 下一个可用数字索引
dtor_func_t pDestructor; //析构函数
};在php中，分为两部分：1.数组元素表，每个数组内都是一个Buckets。容量为2^n，插入元素时顺序插入，新插入的元素索引idx为ht->nNumUsed++,nNumUsed是递增的，表示已使用的Buckets数量。2.索引表，其和数组元素容量等长。存储每个key在数组元素中的索引idx。 如果插入时出现了hash冲突，通过拉链法解决hash冲突，新插入的这个元素的val.u2.next为该key所在索引表内存储的索引值。索引计算方法：nIndex = h | ht->nTableMask;其中h为key经过times 33算法后的值，对应计算函数为：zend_inline_hash_func(const char *str, size_t len)如：一个容量为4，有两个元素的数组结构图总览如下图：添加对应函数：zend_hash_index_add_or_update()zend_hash_str_add_or_update()数组元素表顺序插入，更新索引表对应位置数据。值得注意的是，php中并没有对hash冲突进行特殊处理，而是每个key插入数组中的Bucket时，都让其val.u2.next为当前索引表中的值，然后再更新索引表中的值。这样如果没有冲突产生，则val.u2.next值就为-1。无需特殊处理。如下图，新增一个元素，且出现了hash冲突：查找先在索引表中拿到数组元素的idx，然后拿到数据，如果key不等，在其val.u2.next中进行比较，直至结束。删除先找到该元素，然后将该位置数据val.type置为IS_UNDEF，并不移动数据。扩容在添加的过程中，如果已使用的buckets数量到达元素数组总容量，则触发扩容，对应函数为zend_hash_do_resize()。1.如果ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)，则不更改容量，仅重新hash2.如果ht->nTableSize < HT_MAX_SIZE，则会进行双倍扩容。此时会申请双倍容量内存，并把之前的数据全部拷贝到新地址，释放旧内存，然后重新hash重新hash时，如果存在空洞（删除导致元素数组空洞），则需要从前往后，把删除的元素往前移，把空洞给填满（使数据更紧凑）。对应函数为zend_hash_rehash(HashTable *ht)对比1.php使用索引表和元素数组两部分来实现map和数组的功能；而go使用元素数组部分，每个数组内最多可装8个数据，使用负载因子控制扩容，两者的实现各有千秋。2.两者都使用拉链法来处理hash冲突。3.在插入时，如果出现过空洞（删除导致），go更倾向往前插入来使得结构更紧凑，而php是顺序插入，在扩容阶段来处理空洞。4.在扩容时，go使用增量扩容，而php是全量。参考：go源码1.15golang-notes/map.mdphp源码7.4.15