var mp map[string]interface{} // 声明fmt.Println(mp, mp == nil, len(mp)) // 输出：nil true 0mp := make(map[string]interface{}) // make初始化mp := make(map[string]interface{}, 1) // make初始化并指定容量fmt.Println(mp, mp == nil, len(mp)) // 输出：[] false 0mp = map[string]interface{}{} // 等同于 make(map[string]interface{})mp = map[string]interface{}{ // 字面量初始化"aa": 11,"bb": 22,}
map可以使用make和字面量的方式进行初始化，初始化的时候可以指定容量，也可以不指定容量(建议如果知道map的容量要提前指定，map本身也有扩容和缩容机制，频繁扩缩也会对map读写性能造成影响，下文会讲解)，如果map不进行初始化则不能直接使用，否则可能会造成panic。
1.2map增删改查
var m1 map[int]intm1Res, ok := m1[1] // 取值时第一个为key对应的val,第二个是map中是否存在keyfmt.Println(m1Res, ok) // 输出: 0，false 未初始化的map获得类型的零值m1[1] = 1 // 运行时报panic: assignment to entry in nil map// 增加数据, len()参数是map类型时获取的是map中存储的键值对数量m1 = make(map[int]int)m1[1] = 1fmt.Println(m1, len(m1)) // 输出： [1:1] 1m1[2] = 2fmt.Println(m1, len(m1)) // 输出：[1:1 2:2] 2// 删除数据delete(m1, 1)fmt.Println(m1, len(m1)) // 输出：[2:2] 1// 修改数据m1[2] = 3fmt.Println(m1, len(m1)) // 输出：[2:3] 1// 遍历mapm1[4] = 4m1[5] = 5m1[6] = 6// Map是无序的，每次遍历的顺序都不一样for key, val := range m1 {fmt.Printf("%d:%dn", key, val)}
map的增、改、查均没有提供相应的操作函数，使用起来非常方便（在编译时会由编译器进行代码优化，运行时动态调用/map.go对应的方法完成对map内存分配、增、删、改、查、遍历等操作），除此之外，map的key一定要是比较的，不能是slice、map和func等数据类型。
由于map这种的数据类型十分灵活，同时借助于go中特有的空接口类型，所以在生产实践中，在对不同结构体对象操作时，我们经常会将和map进行转换，方便数据传输。
type person struct {Name string `json:"name"`Age int `json:"age"`}p := person{Name: "zhangsan",Age: 25,}// 作为反序列的输出地址，此时不用初始化mapvar m2 map[string]interface{}bytes, _ := json.Marshal(p)json.Unmarshal(bytes, &m2)fmt.Println(m2, len(m2)) // 输出：[age:25 name:zhangsan] 2
同时go中的map还可以作为set集合使用，实现一个无重复元素的集合，并且增删改查的时间复杂度都是O(1)。
// struct{}不占用空间// 可以作为一个空的占位符，在go中的使用场景非常广泛var set map[string]struct{}set["aa"] = struct{}set["bb"] = struct{}if _, ok := set["cc"]; ok{...}
2. map源码剖析
2.1 map底层数据结构
map的底层是一个hash桶的结构，用于存储key-val键值对数据（本文中的map源码剖析基于go1.19），map的核心数据和代码位于 /map.go中。
// map的运行时数据结构type hmap struct {count int // 当前map中键值对的数量flags uint8 // 标记map的状态，并发状态等B uint8 // buckets数量的对数 buckets = 2^Bnoverflow uint16 // 溢出桶的数量hash0 uint32 // hash seedbuckets unsafe.Pointer // 当前map对应桶(bucket)的指针// map扩容时用于存储旧桶的数据，扩容完成则为niloldbuckets unsafe.Pointer// 扩容时使用，用于标识旧桶中小于nevacuate的数据都已经转移到新桶nevacuate uintptr// 存储map溢出桶extra *mapextra // optional fields}// bucket运行时数据结构，根据tophash定位key-val键值对type bmap struct {tophash [bucketCnt]uint8}
map底层的核心数据结构是hmap和bmap，hmap中包含键值对数量count、hash桶、hash桶数量B等关键参数，其中的类型是. 底层引用的数据结构是bmap，bmap是用来查找key-val键值对的数据结构，内部只存储了键值对的。
虽然bmap结构体没有直接存储key-val键值对信息，但是我们依然可以通过找到key-val键值对的位置。让我们从头过一下通过key定位key-val的大致过程。首先map运行时会根据用户传入的key根据hash函数计算出hash值，bmap中的数组存储的正是hash值的高8位，在根据hash值对长度取余求出该key所在数组中的的位置，在通过遍历该的可以大致确定是否存在key，不存在直接返回，相等的话map.entry，在判断对应位置的key是否相等，key相等的话再通过内存偏移即可找到对应val（map的key和val数据类型是既定的，内存空间也是已知的，并且key-val键值对存储在中一片连续的内存，因此可以通过内存偏移间接找到key-val键值对的存储位置）。接下来让我们先来看看map内存分配的源码。
2.2 map内存分配
func makemap(t *maptype, hint int, h *hmap) *hmap {// 内存溢出判断mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)if overflow || mem > maxAlloc {hint = 0}// initialize Hmapif h == nil {h = new(hmap)}// 生成hash因子h.hash0 = fastrand()// 找到满足bucket不过载的最小BB := uint8(0)for overLoadFactor(hint, B) {B++}h.B = Bif h.B != 0 {var nextOverflow *bmap// 根据B创建buckets和溢出bucketsh.buckets, nextOverflow = makeBucketArray(t, h.B, nil)if nextOverflow != nil {h.extra = new(mapextra)h.extra.nextOverflow = nextOverflow}}return h}// 判断bucket是否过载 count > 6.5 * 2^Bfunc overLoadFactor(count int, B uint8) bool {return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)}// 创建hash桶和溢出桶func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {base := bucketShift(b)nbuckets := base// 如果make(map[int]int, hint)时指定的容量 hint > 52 则会创建溢出桶if b >= 4 {// Add on the estimated number of overflow buckets// required to insert the median number of elements// used with this value of b.nbuckets += bucketShift(b - 4)sz := t.bucket.size * nbucketsup := roundupsize(sz)if up != sz {nbuckets = up / t.bucket.size}}if dirtyalloc == nil {// 分配连续空间的内存buckets = newarray(t.bucket, int(nbuckets))} else {// dirtyalloc was previously generated by// the above newarray(t.bucket, int(nbuckets))// but may not be empty.buckets = dirtyallocsize := t.bucket.size * nbucketsif t.bucket.ptrdata != 0 {memclrHasPointers(buckets, size)} else {memclrNoHeapPointers(buckets, size)}}if base != nbuckets {// 通过内存偏移找到溢出桶的位置，并把最后一个溢出桶指向buckets开头的位置nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))last.setoverflow(t, (*bmap)(buckets))}return buckets, nextOverflow}
map初始化的对应源码是/map.go:()函数，核心流程就是：根据用户初始化map时指定的容量hint确定保证map不过载的最小B(即hint > 6.5 * 2^B)，然后计算出需要创建的和溢出的数量，其中是一片连续的内存(桶数组)，溢出桶放在数组最后面的位置。
2.3map数据读取
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {...// map未初始化或者map中没有键值对，直接返回val类型零值if h == nil || h.count == 0 {if t.hashMightPanic() {t.hasher(key, 0) // see issue 23734}return unsafe.Pointer(&zeroVal[0])}// 校验flag是否是4，是的话说明该map正在被写入if h.flags&hashWriting != 0 {fatal("concurrent map read and map write")}// 根据hash因子，计算key的哈希值hash := t.hasher(key, uintptr(h.hash0))// m = 2^B-1m := bucketMask(h.B)// 通过内存偏移找到key对应的bucket的位置// hash & m 就是key落在的hash桶的位置b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))if c := h.oldbuckets; c != nil { // 说明map正在迁移中// h.flag == 8说明map在等量扩容，否则是增量扩容if !h.sameSizeGrow() {// 增量扩容下m = m / 2m >>= 1}// 获得该key对应的旧桶的位置oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))// 该旧桶为迁移完成，就从旧桶中遍历数据if !evacuated(oldb) {b = oldb}}// 获得hash的top8位top := tophash(hash)bucketloop:// 大循环遍历桶和溢出桶链表，如果有溢出桶的话，没有就只遍历一个桶for ; b != nil; b = b.overflow(t) {// 小循环遍历每个桶内的8个数据，根据tophash定位for i := uintptr(0); i < bucketCnt; i++ {if b.tophash[i] != top {// 当前位置的tophash是emptyReset代表后续槽内都没有值了// 直接退出遍历if b.tophash[i] == emptyRest {break bucketloop}// 否则遍历下一个tophashcontinue}// 找到key的内存地址k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))if t.indirectkey() {k = *((*unsafe.Pointer)(k))}if t.key.equal(key, k) {// 找到val的内存地址e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))if t.indirectelem() {e = *((*unsafe.Pointer)(e))}return e}}}// 桶和溢出桶都遍历完，没找到数据，返回val类型零值return unsafe.Pointer(&zeroVal[0])}// 根据桶的第一个hash的值判断是否迁移完成 1<h<5代表已迁移完成func evacuated(b *bmap) bool {h := b.tophash[0]return h > emptyOne && h < minTopHash}
map读数据的核心源码是/map.go:()函数，总体流程就是：首先判断是否有map写冲突，然后根据key计算hash值，对桶数组长度取余找到key所存储的hash桶的对应位置(取余通过hash & m实现)，然后根据遍历桶上的，通过内存偏移找到对应的key-val键值对数据，没找到返回val类型零值。需要注意的是，如果读map时，map正在迁移或者重建，则会判断是否需要去旧桶上读数据。
2.4 map数据写流程
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {// 空map执行写操作直接panicif h == nil {panic(plainError("assignment to entry in nil map"))}...// 如果有同时对map的写操作，直接fatal errorif h.flags&hashWriting != 0 {fatal("concurrent map writes")}// 根据key获得hash因子hash := t.hasher(key, uintptr(h.hash0))// map写操作需要设置flag状态位h.flags ^= hashWriting// 如果初始化map时容量<=6,则会lazy initializeif h.buckets == nil {h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)}again:bucket := hash & bucketMask(h.B)// 如果map正在扩容，会先执行一部分扩容工作if h.growing() {growWork(t, h, bucket)}// 获得需要分配的hash桶, 并计算tophashb := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))top := tophash(hash)var inserti *uint8var insertk unsafe.Pointervar elem unsafe.Pointerbucketloop:// 大循环遍历该位置的hash桶链表for {// 小循环遍历每个桶的tophashfor i := uintptr(0); i < bucketCnt; i++ {if b.tophash[i] != top {if isEmpty(b.tophash[i]) && inserti == nil {// 找到一个空的槽，记录一下，当inserti为空时inserti = &b.tophash[i]insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))}// 如果后续所有槽都为空，包含溢出桶的槽，则直接退出遍历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))}// key不相等，则遍历下一个槽if !t.key.equal(key, k) {continue}// already have a mapping for key. Update it.if t.needkeyupdate() {typedmemmove(t.key, k, key)}// key相等，找到对应位置的valelem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))goto done}ovf := b.overflow(t)if ovf == nil {break}b = ovf}// 没找当相同的key,会在插入前，判断是否需要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}// 没有找到插入位置，则创建溢出桶，接收新的key和valif inserti == nil {// 获得一个溢出桶newb := h.newoverflow(t, b)inserti = &newb.tophash[0]insertk = add(unsafe.Pointer(newb), dataOffset)elem = add(insertk, bucketCnt*uintptr(t.keysize))}...// 将key放到指定的位置typedmemmove(t.key, insertk, key)// 将tophash放到指定的位置上*inserti = top// map数量加一h.count++// 判断并发标记、设置写状态位、返回key位置的valdone:if h.flags&hashWriting == 0 {fatal("concurrent map writes")}// flags恢复初始状态h.flags &^= hashWritingif t.indirectelem() {elem = *((*unsafe.Pointer)(elem))}return elem}
map写流程的核心源码位于/map.go:()中，总体流程是：nil map直接返回，求出key对应的hash值，设置写map状态位flag，如果map处于扩容中会完成一部分扩容任务，然后遍历hash桶链表中的每一个，存在key则会返回key对应val所在的位置，后续更新，不存在则会记录下，key和val要插入的位置，判断是否需要对map进行扩容和重建，以及是否需要创建溢出桶去承载新的key-val键值对，后续对和key执行插入动作，val对应的位置进行返回。
func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {var ovf *bmapif h.extra != nil && h.extra.nextOverflow != nil {// 已存在溢出桶，直接获取ovf = h.extra.nextOverflowif ovf.overflow(t) == nil {// 存在后续的溢出桶// 将当前溢出桶指向下一个溢出桶，因为溢出桶分配的时候是以数组的形式分配，放置在buckets数组的尾部h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))} else {// 不存在后续的溢出桶ovf.setoverflow(t, nil)h.extra.nextOverflow = nil}} else {// extra中没有溢出桶，新建ovf = (*bmap)(newobject(t.bucket))}// 溢出桶数量加1h.incrnoverflow()if t.bucket.ptrdata == 0 {h.createOverflow()*h.extra.overflow = append(*h.extra.overflow, ovf)}// 将溢出桶放在当前桶的尾部b.setoverflow(t, ovf)return ovf}
获取溢出桶的逻辑是：先从hmap的extra中获取(初始化时会根据容量动态设置)，获取到的话，设置extra的指向，获取不到就新建一个溢出桶，最后会将溢出桶数量加1，并将其设置在当前桶的位置，形成桶链表。
2.5 map删除key-val流程
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {...// 空map或者map键值对数量为0, 直接返回if h == nil || h.count == 0 {if t.hashMightPanic() {t.hasher(key, 0) // see issue 23734}return}// 校验flag状态为是否有写冲突if h.flags&hashWriting != 0 {fatal("concurrent map writes")}// 根据hash种子计算哈希函数hash := t.hasher(key, uintptr(h.hash0))// 设置flag状态位为正在写h.flags ^= hashWriting// 求出key所在bucket的桶位置(index)bucket := hash & bucketMask(h.B)if h.growing() {// 如果正在扩容，会先完成一部分扩容工作，再删除growWork(t, h, bucket)}// 得到bucket位置的hash桶b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))bOrig := b// 得到key的tophash 即hash值的前8位top := tophash(hash)search:// 大循环遍历当前bucket和溢出bucket链表for ; b != nil; b = b.overflow(t) {// 小循环遍历每个桶中的hash槽for i := uintptr(0); i < bucketCnt; i++ {if b.tophash[i] != top {// 一旦发现某个tophash槽中的值是emptyRest，// 则直接退出循环if b.tophash[i] == emptyRest {break search}// 找下一个tophash槽continue}// 找到key的位置k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))k2 := kif t.indirectkey() {k2 = *((*unsafe.Pointer)(k2))}if !t.key.equal(key, k2) {// key不相等，直接判断下一个tophash槽的keycontinue}// 删除key和valif t.indirectkey() {*(*unsafe.Pointer)(k) = nil} else if t.key.ptrdata != 0 {memclrHasPointers(k, t.key.size)}e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))if t.indirectelem() {*(*unsafe.Pointer)(e) = nil} else if t.elem.ptrdata != 0 {memclrHasPointers(e, t.elem.size)} else {memclrNoHeapPointers(e, t.elem.size)}// 删除的key对应位置的tophash会被置为emptyone或emptyResetb.tophash[i] = emptyOne// 删除时会向前回溯，将需要的状态位置为emptyReset, 加速查找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}}// 当 i==bucketCnt-1 当前bucket没有溢出桶，或者溢出桶的第一个// tophash已经是emptyReset时；或者i != bucketCnt-1 当前位置// 的下一个tophash是emptyReset时 进入这个for循环for {// 将emptyOne更改为emptyResetb.tophash[i] = emptyRest// 如果是当前桶链表的第一个桶的第一个tophash槽，直接结束if i == 0 {if b == bOrig {break // beginning of initial bucket, we're done.}c := b// 向前回溯，找到桶链表当前位置的上一个桶for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {}// 从桶的尾部开始向前遍历i = bucketCnt - 1} else {i--}// 只有tophash的状态是emptyOne才能转换为emptyReset，否则直接结束if b.tophash[i] != emptyOne {break}}// 将count-- 重置hash因子，notLast:h.count--// Reset the hash seed to make it more difficult for attackers to// repeatedly trigger hash collisions. See issue 25237.if h.count == 0 {h.hash0 = fastrand()}break search}}// 判断是否有并发map写冲突if h.flags&hashWriting == 0 {fatal("concurrent map writes")}// 将map flag状态位恢复初始状态h.flags &^= hashWriting}
map删除key-val键值对的核心源码位于/map.go:()方法中，核心流程是：通过hash函数和位运算找到key对应的hash桶的位置，如果map在扩容中会先完成一部分扩容工作，然后遍历溢出桶链表中的每一个hash槽，一旦发现直接结束遍历(加速遍历)，否则的话，如果找到了key，将当前置为，key和val内存或者指针清空，然后回从当前当前桶链表的当前位置开始向前遍历，判断是否设置状态位(还是为了加速遍历，放到中做这个事比较合适) ，最后会将map的count--，判断没有并发写冲突后，并恢复flag状态位。
2.6 map遍历流程
// 核心数据结构type hiter struct {key unsafe.Pointer // 遍历到key的指针elem unsafe.Pointer // 遍历到val的指针t *maptype // map类型h *hmap // hmapbuckets unsafe.Pointer // map桶数组bptr *bmap // 当前遍历到的桶overflow *[]*bmap // 新map的溢出桶oldoverflow *[]*bmap // 老map的溢出桶startBucket uintptr // 遍历起始位置的桶索引offset uint8 // 遍历起始位置的key-val对索引wrapped bool // 遍历是否穿越了桶数组尾部返回到了头部B uint8 // 桶数组长度指数i uint8 // 当前遍历到key-val对的在桶中的索引bucket uintptr // 当前遍历到的bucket 索引checkBucket uintptr // 扩容时需要额外检查的桶}
map遍历时通过设置一个随机数，找到起始遍历的位置和中起始遍历的hash槽的位置，然后按上图规则遍历，由于每次遍历随机因子的不同，也保证了每次遍历顺序的不同。
2.7 map的扩容和重建
map扩容分为增量扩容和等量重建，会在增加key-val键值对时对map判断，满足条件后触发。
增量扩容：map的桶数组的长度会增长到原来的两倍，以保证整体数组的负载不要太高。触发方式：hmap.count > 6.5 * 2 ^B。
func overLoadFactor(count int, B uint8) bool {return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)}
等量重建：为避免map在多次增删操作后，内部hash槽的空洞太多(会导致内存泄漏)，桶链表过长，对map桶数组进行等容量，提升空间利用率。触发方式：hmap. > 2^B。
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {if B > 15 {B = 15}return noverflow >= uint16(1)<<(B&15)}
开启扩容的时机是map新增数据时，开始扩容的源代码位于为/map.go:()中。
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}func hashGrow(t *maptype, h *hmap) {// bigger：1 增量扩容 bigger:0 等量重建bigger := uint8(1)if !overLoadFactor(h.count+1, h.B) {bigger = 0h.flags |= sameSizeGrow}// 当前buckets赋值给oldbucketsoldbuckets := h.buckets// 创建新的buckets和溢出bucketsnewbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)flags := h.flags &^ (iterator | oldIterator)if h.flags&iterator != 0 {flags |= oldIterator}// 字符重新初始化h.B += biggerh.flags = flagsh.oldbuckets = oldbucketsh.buckets = newbucketsh.nevacuate = 0h.noverflow = 0if h.extra != nil && h.extra.overflow != nil {// Promote current overflow buckets to the old generation.if h.extra.oldoverflow != nil {throw("oldoverflow is not nil")}// 存量可用的溢出桶赋值给oldoverflowh.extra.oldoverflow = h.extra.overflowh.extra.overflow = nil}if nextOverflow != nil {if h.extra == nil {h.extra = new(mapextra)}// 存在下一个可用的溢出桶，则赋值给nextOverflowh.extra.nextOverflow = nextOverflow}// the actual copying of the hash table data is done incrementally// by growWork() and evacuate().}
可以看到，()函数只是做了新分配内存和一些字段的初始化的工作，也间接说明了map采用渐进式扩容的策略，在插入、更新和删除时执行真正的数据迁移动作。
func growWork(t *maptype, h *hmap, bucket uintptr) {// 第一次迁移当前bucket对应的oldbucketevacuate(t, h, bucket&h.oldbucketmask())// evacuate one more oldbucket to make progress on growingif h.growing() {// 第二次迁移当前未迁移桶中索引最小的桶evacuate(t, h, h.nevacuate)}}func evacuate(t *maptype, h *hmap, oldbucket uintptr) {b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))newbit := h.noldbuckets()if !evacuated(b) {// TODO: reuse overflow buckets instead of using new ones, if there// is no iterator using the old buckets. (If !oldIterator.)// xy contains the x and y (low and high) evacuation destinations.var xy [2]evacDstx := &xy[0]x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))x.k = add(unsafe.Pointer(x.b), dataOffset)x.e = add(x.k, bucketCnt*uintptr(t.keysize))if !h.sameSizeGrow() {// Only calculate y pointers if we're growing bigger.// Otherwise GC can see bad pointers.y := &xy[1]y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))y.k = add(unsafe.Pointer(y.b), dataOffset)y.e = add(y.k, bucketCnt*uintptr(t.keysize))}for ; b != nil; b = b.overflow(t) {k := add(unsafe.Pointer(b), dataOffset)e := add(k, bucketCnt*uintptr(t.keysize))for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {top := b.tophash[i]if isEmpty(top) {b.tophash[i] = evacuatedEmptycontinue}if top < minTopHash {throw("bad map state")}k2 := kif t.indirectkey() {k2 = *((*unsafe.Pointer)(k2))}var useY uint8if !h.sameSizeGrow() {// Compute hash to make our evacuation decision (whether we need// to send this key/elem to bucket x or bucket y).hash := t.hasher(k2, uintptr(h.hash0))if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {useY = top & 1top = tophash(hash)} else {if hash&newbit != 0 {useY = 1}}}if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {throw("bad evacuatedN")}b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedYdst := &xy[useY] // evacuation destinationif dst.i == bucketCnt {dst.b = h.newoverflow(t, dst.b)dst.i = 0dst.k = add(unsafe.Pointer(dst.b), dataOffset)dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))}dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds checkif t.indirectkey() {*(*unsafe.Pointer)(dst.k) = k2 // copy pointer} else {typedmemmove(t.key, dst.k, k) // copy elem}if t.indirectelem() {*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)} else {typedmemmove(t.elem, dst.e, e)}dst.i++// These updates might push these pointers past the end of the// key or elem arrays. That's ok, as we have the overflow pointer// at the end of the bucket to protect against pointing past the// end of the bucket.dst.k = add(dst.k, uintptr(t.keysize))dst.e = add(dst.e, uintptr(t.elemsize))}}// Unlink the overflow buckets & clear key/elem to help GC.if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))// Preserve b.tophash because the evacuation// state is maintained there.ptr := add(b, dataOffset)n := uintptr(t.bucketsize) - dataOffsetmemclrHasPointers(ptr, n)}}if oldbucket == h.nevacuate {advanceEvacuationMark(h, t, newbit)}}
3.总结
map是go语言使用十分方便的key-val键值对数据结构，增删改查的时间复杂度可以看作是O(1），但是其内部实现原理确并不简单。日常使用中map.entry，如果提前已知map的存储容量，初始化时指定容量大小，可以减少频繁扩容带来的读写性能抖动影响。
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。