go map数据结构和源码详解

#go map数据结构和源码详解| 来源: 网络整理| 查看: 265

目录1. 前言2. go map的数据结构2.1 核心结体体2.2 数据结构图3. go map的常用操作3.1 创建3.2 插入或更新3.3 删除3.4 查找3.5 range迭代3.5.1 初始化迭代器mapiterinit()3.5.2 迭代过程mapiternext()4. go map的扩容缩容4.1 扩容缩容的基本原理4.2 为什么叫“伪缩容”？如何实现“真缩容”？5 Q&A关键知识点5.1 基本原理5.2 时间复杂度和空间复杂度分析

1. 前言

本文以go1.12.5版本分析，map相关的源码在runtime包的map开头的几个文件中，主要为map.go。 go的map底层实现方式是hash表（C++的map是红黑树实现，而C++ 11新增的unordered_map则与go的map类似，都是hash实现）。go map的数据被置入一个由桶组成的有序数组中，每个桶最多可以存放8个key/value对。key的hash值(32位)的低阶位用于在该数组中定位到桶，而高8位则用于在桶中区分key/value对。 go map的hash表中的基本单位是桶，每个桶最多存8个键值对，超了，则会链接到额外的溢出桶。所以go map是基本数据结构是hash数组+桶内的key-value数组+溢出的桶链表当hash表超过阈值需要扩容增长时，会分配一个新的数组，新数组的大小一般是旧数组的2倍。这里从旧数组将数据迁移到新数组，不会一次全量拷贝，go会在每次读写Map时以桶为单位做动态搬迁疏散。

2. go map的数据结构

我们先了解基本的数据结构，后面再看源码就简单多了。

2.1 核心结体体

map主要由两个核心的结构，即基础结构和桶实现：

hmap：map的基础结构 bmap：严格来说hmap.buckets指向桶组成的数组，每个桶的头部是bmap，之后是8个key，再是8个value，最后是1个溢出指针。溢出指针指向额外的桶链表，用于存储溢出的数据 const ( // 关键的变量 bucketCntBits = 3 bucketCnt = 1 = (hash桶数量(2^hmp.B) * 6.5 / 8) 时，触发扩容 ) // map的基础数据结构 type hmap struct { count int // map存储的元素对计数，len()函数返回此值，所以map的len()时间复杂度是O(1) flags uint8 // 记录几个特殊的位标记，如当前是否有别的线程正在写map、当前是否为相同大小的增长（扩容/缩容？） B uint8 // hash桶buckets的数量为2^B个 noverflow uint16 // 溢出的桶的数量的近似值 hash0 uint32 // hash种子 buckets unsafe.Pointer // 指向2^B个桶组成的数组的指针，数据存在这里 oldbuckets unsafe.Pointer // 指向扩容前的旧buckets数组，只在map增长时有效 nevacuate uintptr // 计数器，标示扩容后搬迁的进度 extra *mapextra // 保存溢出桶的链表和未使用的溢出桶数组的首地址 } // 桶的实现结构 type bmap struct { // tophash存储桶内每个key的hash值的高字节 // tophash[0] < minTopHash表示桶的疏散状态 // 当前版本bucketCnt的值是8，一个桶最多存储8个key-value对 tophash [bucketCnt]uint8 // 特别注意： // 实际分配内存时会申请一个更大的内存空间A，A的前8字节为bmap // 后面依次跟8个key、8个value、1个溢出指针 // map的桶结构实际指的是内存空间A } // map.go里很多函数的第1个入参是这个结构，从成员来看很明显，此结构标示了键值对和桶的大小等必要信息 // 有了这个结构的信息，map.go的代码就可以与键值对的具体数据类型解耦 // 所以map.go用内存偏移量和unsafe.Pointer指针来直接对内存进行存取，而无需关心key或value的具体类型 type maptype struct { typ _type key *_type elem *_type bucket *_type // internal type representing a hash bucket keysize uint8 // size of key slot valuesize uint8 // size of value slot bucketsize uint16 // size of bucket flags uint32 }

C++使用模板可以根据不同的类型生成map的代码。 golang则通过上述maptype结构体传递键值对的类型大小等信息，从而map.go直接用指针操作对应大小的内存来实现全局一份map代码同时适用于不同类型的键值对。这点上可以认为相比C++用模板实现map的方式，go map的目标文件的代码量会更小。

2.2 数据结构图

map底层创建时，会初始化一个hmap结构体，同时分配一个足够大的内存空间A。其中A的前段用于hash数组，A的后段预留给溢出的桶。于是hmap.buckets指向hash数组，即A的首地址；hmap.extra.nextOverflow初始时指向内存A中的后段，即hash数组结尾的下一个桶，也即第1个预留的溢出桶。所以当hash冲突需要使用到新的溢出桶时，会优先使用上述预留的溢出桶，hmap.extra.nextOverflow依次往后偏移直到用完所有的溢出桶，才有可能会申请新的溢出桶空间。

上图中，当需要分配一个溢出桶时，会优先从预留的溢出桶数组里取一个出来链接到链表后面，这时不需要再次申请内存。但当预留的桶被用完了，则需要申请新的内存给溢出桶。

3. go map的常用操作 3.1 创建

使用make(map[k]v, hint)创建map时会调用makemap()函数，代码逻辑比较简单。值得注意的是，makemap()创建的hash数组，数组的前面是hash表的空间，当hint >= 4时后面会追加2^(hint-4)个桶，之后再内存页帧对齐又追加了若干个桶（参见2.2章节结构图的hash数组部分）所以创建map时一次内存分配既分配了用户预期大小的hash数组，又追加了一定量的预留的溢出桶，还做了内存对齐，一举多得。

// make(map[k]v, hint), hint即预分配大小 // 不传hint时，如用new创建个预设容量为0的map时，makemap只初始化hmap结构，不分配hash数组 func makemap(t *maptype, hint int, h *hmap) *hmap { // 省略部分代码 // 随机hash种子 h.hash0 = fastrand() // 2^h.B 为大于hint*6.5(扩容因子)的最小的2的幂 B := uint8(0) // overLoadFactor(hint, B)只有一行代码：return hint > bucketCnt && uintptr(hint) > loadFactorNum*(bucketShift(B)/loadFactorDen) // 即B的大小应满足 hint = base，这就可能会追加一些溢出桶作为溢出的预留 if b >= 4 { // 这里追加一定数量的桶，并做内存对齐 nbuckets += bucketShift(b - 4) sz := t.bucket.size * nbuckets up := roundupsize(sz) if up != sz { nbuckets = up / t.bucket.size } } // 后面的代码就是申请内存空间了，此处省略 // 这里大家可以思考下这个数组空间要怎么分配，其实就是n*sizeof(桶)，所以： // 每个桶前面是8字节的tophash数组，然后是8个key，再是8个value，最后放一个溢出指针 // sizeof(桶) = 8 + 8*sizeof(key) + 8*sizeof(value) + 8 return buckets, nextOverflow } 3.2 插入或更新

go map的插入操作，调用mapassign()函数。同学们或许在某些资料上了解过：

go map需要初始化才能使用，对空map插入会panic。hmap指针传递的方式，决定了map在使用前必须初始化 go map不支持并发读写，会panic。如果一定要并发，请用sync.Map或自己解决冲突

上述两个限制，在mapassign()函数开头能找到答案：

参数合法性检测，计算hash值 func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { // 不熟悉指针操作的同学，用指针传参往往会踩空指针的坑 // 这里大家可以思考下，为什么h要非空判断？ // 如果一定要在这里支持空map并检测到map为空时自动初始化，应该怎么写？ // 提示：指针的指针 if h == nil { panic(plainError("assignment to entry in nil map")) } // 在这里做并发判断，检测到并发写时，抛异常 // 注意：go map的并发检测是伪检测，并不保证所有的并发都会被检测出来。而且这玩意是在运行期检测。 // 所以对map有并发要求时，应使用sync.map来代替普通map，通过加锁来阻断并发冲突 if h.flags&hashWriting != 0 { throw("concurrent map writes") } hash := alg.hash(key, uintptr(h.hash0)) // 这里得到uint32的hash值 h.flags ^= hashWriting // 置Writing标志，key写入buckets后才会清除标志 if h.buckets == nil { // map不能为空，但hash数组可以初始是空的，这里会初始化 h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) } ... } 定位key在hash表中的位置 func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { ... again: bucket := hash & bucketMask(h.B) // 这里用hash值的低阶位定位hash数组的下标偏移量 if h.growing() { growWork(t, h, bucket) // 这里是map的扩容缩容操作，我们在第4章单独讲 } // 通过下标bucket，偏移定位到具体的桶 b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize))) top := tophash(hash) // 这里取高8位用于在桶内定位键值对 ... } 进一步定位key可以插入的桶及桶中的位置两轮循环，外层循环遍历hash桶及其指向的溢出链表，内层循环则在桶内遍历（一个桶最多8个key-value对）有可能正好链表上的桶都满了，这时inserti为nil，第4步会链接一个新的溢出桶进来 func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { ... var inserti *uint8 // tophash插入位置 var insertk unsafe.Pointer // key插入位置 var val unsafe.Pointer // value插入位置 bucketloop: for { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { if isEmpty(b.tophash[i]) && inserti == nil { // 找到个空位，先记录下tophash、key、value的插入位置 // 但要遍历完才能确定要不要插入到这个位置，因为后面有可能有重复的元素 inserti = &b.tophash[i] insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) } if b.tophash[i] == emptyRest { break bucketloop // 遍历完整个溢出链表，退出循环 } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } if !alg.equal(key, k) { continue } // 走到这里说明map里找到一个重复的key，更新key-value，跳到第5步 if t.needkeyupdate() { typedmemmove(t.key, k, key) } val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) goto done // 更新Key后跳到第5步 } ovf := b.overflow(t) if ovf == nil { break // 遍历完整个溢出链表，没找到能插入的空位，结束循环，下一步再追加一个溢出桶进来 } b = ovf // 继续遍历下一个溢出桶 } ... } 插入key func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { ... // 这里判断要不要扩容，我们第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 } if inserti == nil { // inserti == nil说明上1步没找到空位，整个链表是满的，这里添加一个新的溢出桶上去 newb := h.newoverflow(t, b) // 分配新溢出桶，优先用3.1章节预留的溢出桶，用完了则分配一个新桶内存 inserti = &newb.tophash[0] insertk = add(unsafe.Pointer(newb), dataOffset) val = add(insertk, bucketCnt*uintptr(t.keysize)) } // 当key或value的类型大小超过一定值时，桶只存储key或value的指针。这里分配空间并取指针 if t.indirectkey() { kmem := newobject(t.key) *(*unsafe.Pointer)(insertk) = kmem insertk = kmem } if t.indirectvalue() { vmem := newobject(t.elem) *(*unsafe.Pointer)(val) = vmem } typedmemmove(t.key, insertk, key) // 在桶中对应位置插入key *inserti = top // 插入tophash，hash值高8位 h.count++ // 插入了新的键值对，h.count数量+1 ... } 结束插入 func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { ... done: if h.flags&hashWriting == 0 { throw("concurrent map writes") } h.flags &^= hashWriting // 释放hashWriting标志位 if t.indirectvalue() { val = *((*unsafe.Pointer)(val)) } return val // 返回value可插入位置的指针，注意，value还没插入 } 只插入了tophash和key，就结束了吗？value还没插入呢是的，mapassign()只插入tophash和key，并返回val指针，编译器会在调用mapassign()后用汇编往val插入value google大佬这么骚气的操作，是为了减少value值传递的次数吗？ 3.3 删除删除与插入类似，前面的步骤都是参数和状态判断、定位key-value位置，然后clear对应的内存。不展开说。以下是几个关键点：删除过程中也会置hashWriting标志当key/value过大时，hash表里存储的是指针，这时候用软删除，置指针为nil，数据交给gc去删。当然，这是map的内部处理，外层是无感知的，拿到的都是值拷贝无论Key/value是值类型还是指针类型，删除操作都只影响hash表，外层已经拿到的数据不受影响。尤其是指针类型，外层的指针还能继续使用由于定位key位置的方式是查找tophash，所以删除操作对tophash的处理是关键： map首先将对应位置的tophash[i]置为emptyOne，表示该位置已被删除如果tophash[i]不是整个链表的最后一个，则只置emptyOne标志，该位置被删除但未释放，后续插入操作不能使用此位置如果tophash[i]是链表最后一个有效节点了，则把链表最后面的所有标志为emptyOne的位置，都置为emptyRest。置为emptyRest的位置可以在后续的插入操作中被使用。这种删除方式，以少量空间来避免桶链表和桶内的数据移动。事实上，go 数据一旦被插入到桶的确切位置，map是不会再移动该数据在桶中的位置了。 func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { ... b.tophash[i] = emptyOne // 先标记删除 // 如果b.tophash[i]不是最后一个元素，则暂时先占着坑。emptyOne标记的位置暂时不能被插入新元素(见3.2章节插入函数) if i == bucketCnt-1 { if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { goto notLast } } else { if b.tophash[i+1] != emptyRest { goto notLast } } for { // 如果b.tophash[i]是最后一个元素，则把末尾的emptyOne全部清除置为emptyRest b.tophash[i] = emptyRest if i == 0 { if b == bOrig { break // beginning of initial bucket, we're done. } // Find previous bucket, continue at its last entry. c := b for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { } i = bucketCnt - 1 } else { i-- } if b.tophash[i] != emptyOne { break } } ... } 3.4 查找

查找操作由mapaccess开头的一组函数实现。前面的章节在插入和删除之前都得先定位查找到元素，逻辑是类似的，也比较简单，就不细说了：

mapaccess1()：通过Key查找，返回value指针，用于val := map[key]。未找到时返回value类型的0值。 mapaccess2()：通过key查找，返回value指针，以及bool类型的是否查找成功的标志，用于val, ok := map[key]。未找到时返回value类型的0值。 mapaccessK()：通过key查找，返回key和value指针，用于迭代器(range)。未找到时返回空指针 mapaccess1_fat()，对mapaccess1()的封装，区别是mapaccess1_fat()多了个zero参数，未找到时返回zero mapaccess2_fat()，也是对mapaccess1()的封装。相比mapaccess1_fat()，本函数增加一个是否查找成功的标志 3.5 range迭代

map的迭代是通过hiter结构和对应的两个辅助函数实现的。hiter结构由编译器在调用辅助函数之前创建并传入，每次迭代结果也由hiter结构传回。下方的it即是hiter结构体的指针变量。

3.5.1 初始化迭代器mapiterinit()

mapiterinit()函数主要是决定我们从哪个位置开始迭代，为什么是从哪个位置，而不是直接从hash数组头部开始呢？《go程序设计语言》好像提到过，hash表中数据每次插入的位置是变化的（其实是因为实现的原因，一方面hash种子是随机的，这导致相同的数据在不同的map变量内的hash值不同；另一方面即使同一个map变量内，数据删除再添加的位置也有可能变化，因为在同一个桶及溢出链表中数据的位置不分先后），所以为了防止用户错误的依赖于每次迭代的顺序，map作者干脆让相同的map每次迭代的顺序也是随机的。迭代顺序随机的实现方式也简单，直接从随机的一个位置开始就行了：

it.startBucket：这个是hash数组的偏移量，表示遍历从这个桶开始 it.offset：这个是桶内的偏移量，表示每个桶的遍历都从这个偏移量开始

于是，map的遍历过程如下：

从hash数组中第it.startBucket个桶开始，先遍历hash桶，然后是这个桶的溢出链表。之后hash数组偏移量+1，继续前一步动作。遍历每一个桶，无论是hash桶还是溢出桶，都从it.offset偏移量开始。（如果只是随机一个开始的桶，range结果还是有序的；但每个桶都加it.offset偏移，这个输出结果就有点扑朔迷离，大家可以亲手试下，对同一个map多次range）当迭代器经过一轮循环回到it.startBucket的位置，结束遍历。 func mapiterinit(t *maptype, h *hmap, it *hiter) { ... // 随机一个偏移量来开始 r := uintptr(fastrand()) if h.B > 31-bucketCntBits { r += uintptr(fastrand()) > h.B & (bucketCnt - 1)) ... mapiternext(it) // 初始化迭代器的同时也返回第1对key/value } 3.5.2 迭代过程mapiternext()

上一节迭代循环的过程很清晰了，这里我们说明几个重要的参数：

it.startBucket：开始的桶 it.offset：每个桶开始的偏移量 it.bptr：当前遍历的桶 it.i：it.bptr已经遍历的键值对数量，i初始为0，当i=8时表示这个桶遍历完了，将it.bptr移向下一个桶 it.key：每次迭代的结果 it.value：每次迭代的结果

此外，迭代还需要关注扩容缩容的情况：

如果是在迭代开始后才growing，这种情况当前的逻辑没处理，迭代有可能异常。呃，go map不支持并发。如果是先growing，再开始迭代，这是有可能的。这种情况下，会先到旧hash表中检查key对应的桶有没有被疏散，未疏散则遍历旧桶，已疏散则遍历新hash表里对应的桶。 4. go map的扩容缩容 4.1 扩容缩容的基本原理

go map的扩容缩容都是grow相关的函数，这里扩容是真的，缩容是伪缩容，后面我会解释。我们先看下触发条件：

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { ... 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 } ... } // overLoadFactor()返回true则触发扩容，即map的count大于hash桶数量(2^B)*6.5 func overLoadFactor(count int, B uint8) bool { return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) } // tooManyOverflowBuckets()，顾名思义，溢出桶太多了触发缩容 func tooManyOverflowBuckets(noverflow uint16, B uint8) bool { if B > 15 { B = 15 } return noverflow >= uint16(1)

【本文地址】

公司简介

联系我们