声明

1. 本文采用版本为： go1.17.5
2. 本文仅供自己学习使用， 不做商业用途。

map 的结构：

hmap

hmap结构体定义

golang 中 map的实现结构为： 哈希表 + 链表。 其中链表，作用是当发生hash冲突时，拉链法生成的结点。

// A header for a Go map.
type hmap struct {
    // map中的元素个数
    count     int 
    // map当前的状态， 如： 正在写， 正在遍历
    flags     uint8
    // map中 buckets的对数 log_2， 如 buckets的容量为 2^B
    B         uint8  
    // overflow 的数量
    noverflow  uint16
    // hash种子， 用来生成hash值
    hash0     uint32 // hash seed
    // 指向map的 hash table。 hash table的长度为2^B
    buckets    unsafe.Pointer 
    // 指向扩容时的原 buckets， 新的buckets会申请新的空间。
    // 扩容的时候，buckets 长度会是 oldbuckets 的两倍
    oldbuckets unsafe.Pointer
    // 当前map的扩容进度（扩容搬迁到哪一个cell了）
    nevacuate  uintptr 

    extra *mapextra // optional fields
}

hmap 结构示意图

map 结构图

可以看到， []bmap 是一个hash table， 每一个 bmap是我们常说的“桶”。 经过hash 函数计算出来相同的hash值， 放到相同的桶中。 一个 bmap中可以存放 8个 元素， 如果多出8个，则生成新的结点，尾接到队尾。

bmap

bmap 结构定义

// A bucket for a Go map.
type bmap struct {
   // tophash generally contains the top byte of the hash value
   // for each key in this bucket. If tophash[0] < minTopHash,
   // tophash[0] is a bucket evacuation state instead.
   tophash [bucketCnt]uint8
   // Followed by bucketCnt keys and then bucketCnt elems.
   // NOTE: packing all the keys together and then all the elems together makes the
   // code a bit more complicated than alternating key/elem/key/elem/... but it allows
   // us to eliminate padding which would be needed for, e.g., map[int64]int8.
   // Followed by an overflow pointer.

   // 编译过程中会在后续中添加
   //keys       8个key
   //values     8个 value
   //padding    填充部分
   //overflow   指向后续结点
}

以上是只是静态文件 src/runtime/map.go 中的定义。 实际上编译期间会给它加料，动态地创建一个新的结构：

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

bmap 结构示意图

bmap

上图就是 bmap的内存模型，HOB Hash 指的就是 top hash。 注意到 key 和 value 是各自放在一起的，并不是 key/value/key/value/... 这样的形式。源码里说明这样的好处是在某些情况下可以省略掉 padding 字段，节省内存空间。

每个 bmap设计成最多只能放 8 个 key-value 对，如果有第 9 个 key-value 落入当前的 bmap，那就需要再构建一个 bmap，通过 overflow 指针连接起来。

创建map

map创建方法:

ageMp := make(map[string]int)
// 指定 map 长度
ageMp := make(map[string]int, 8)

// ageMp 为 nil，不能向其添加元素，会直接panic
var ageMp map[string]int

我们实际上是通过调用的 makemap ，来创建map的。实际工作只是初始化了hmap中的各种字段，如：设置B的大小， 设置hash 种子 hash 0.

// makemap implements Go map creation for make(map[k]v, hint).
// If the compiler has determined that the map or the first bucket
// can be created on the stack, h and/or bucket may be non-nil.
// If h != nil, the map can be created directly in h.
// If h.buckets != nil, bucket pointed to can be used as the first bucket.
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 Hmap
    if h == nil {
        h = new(hmap)
    }
    // 初始化时， 随机生成hash种子
    h.hash0 = fastrand()

    // Find the size parameter B which will hold the requested # of elements.
    // For hint < 0 overLoadFactor returns false since hint < bucketCnt.
    // 初始化合适的B的大小，
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B

    // allocate initial hash table
    // if B == 0, the buckets field is allocated lazily later (in mapassign)
    // If hint is large zeroing this memory could take a while.
    // 初始化hash table
    if h.B != 0 {
        var nextOverflow *bmap
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }

    return h
}


// 得到以个 1 << B 的大小的数，同时判断是否超过了负载因子 6.5
func overLoadFactor(count int, B uint8) bool {
    //     13 * （2^B / 2） = 6.5 * 2^B
    //     map的容量count / 桶的数量 2^B  > 6.5
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

注意 :

makemap 返回是*hmap 指针， 即 map 是引用对象， 对map的操作会影响到结构体内部。

查找map元素

使用方式

package main

import "fmt"

func main() {
    // 初始化 map
    ageMap := make(map[string]int)
    // 插入元素
    ageMap["wxx"] = 24

    // 不带 comma 用法
    age1 := ageMap["a"]
    fmt.Println(age1) // 0

    // 带 comma 用法
    age2, ok := ageMap["b"] // 0， false
    fmt.Println(age2, ok)
}

对应的是下面两种方法

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
// mapaccess2 和 mapaccess1 功能相同 但是多返回一个是否搜索到的bool值
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)

hash 函数如何确定

type maptype struct {
    typ    _type
    key    *_type
    elem   *_type
    bucket *_type // internal type representing a hash bucket
    // function for hashing keys (ptr to key, seed) -> hash
    hasher     func(unsafe.Pointer, uintptr) uintptr
    keysize    uint8  // size of key slot
    elemsize   uint8  // size of elem slot
    bucketsize uint16 // size of bucket
    flags      uint32
}

map的key的类型，实现了自己的hash 方式。每种类型实现hash函数方式不一样。

正常定位key

key 经过哈希计算后得到hash值，共 64 个 bit 位。 其中后B 个bit位置， 用来定位当前元素落在哪一个桶里， 高8个bit 为当前 hash 值的top hash。实际上定位key的过程是一个双重循环的过程， 外层循环遍历 所有的overflow， 内层循环遍历 当前bmap 中的 8个元素。

1. 使用 低 B 为定位是在哪一个 bucket
2. 遍历当前结点中的8个 cell是否有满足top hash的。如果有则定位完成，否则进入 第3步
3. 遍历链表的结点， 如果定位到了，则返回值。否则返回零值。

举例说明： 如果当前 B 的值为 5， 那么buckets 的长度 为 2^5 = 32。假设有个key 经过hash函数计算后，得到的hash结果为：

10010111 | 000011110110110010001111001010100010010110010101010 │ 00110

1. 第B位 hash & B == 01010 == 6,定位到6号桶
2. 高8位 tophash 10010111 == 151,遍历匹配bmap 中的tophash

外层遍历bucket 中的链表

双层循环遍历key

内层循环遍历 bmap中的8个 cell

keys定位到桶

扩容时定位key

建议先不看此部分内容，看完后续 修改 map中元素 -> 扩容 操作后 再回头看此部分内容。

扩容前的数据：

扩容前数据

等量扩容后的数据：

等量扩容后，查找方式和原本相同， 不多做赘述。

等量扩容

两倍扩容后的数据

两倍扩容后，oldbuckets 的元素，可能被分配成了两部分。查找顺序如下：

1. 遍历到old buckets的 bucket还没有被搬迁过， 正常查询，返回找到的元素。

2. 遍历到old buckets的 bucket 被搬迁过了，则到新的buckets中寻找元素。

   
   两倍扩容

源码：

此处只分析 mapaccess1,。mapaccess2 相比 mapaccess1多添加了是否找到的bool值， 有兴趣可自行看一下。

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // race 竞争检测
    if raceenabled && h != nil {
        callerpc := getcallerpc()
        pc := funcPC(mapaccess1)
        racereadpc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
    if msanenabled && h != nil {
        msanread(key, t.key.size)
    }
    // 正确性检测
    if h == nil || h.count == 0 {
        if t.hashMightPanic() {
            t.hasher(key, 0) // see issue 23734
        }
        // 返回当前类型的0值
        return unsafe.Pointer(&zeroVal[0])
    }
    // 如果flags为 写 标识， 则同时读写冲突， 抛出panic。非协程安全
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    // 依据hash 种子生成 当前key的 hash值
    hash := t.hasher(key, uintptr(h.hash0))
    // m = 2^B - 1, 实际上的作用是为了 只取低B 位， 来找到相对应桶的位置
    m := bucketMask(h.B)
    // 找到桶的位置
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    // 正在扩容
    if c := h.oldbuckets; c != nil {
        // 非等量扩容（双倍扩容）
        if !h.sameSizeGrow() {
            // There used to be half as many buckets; mask down one more power of two.
            // 先 右移一位 得到原来old bucket的 mask的值
            m >>= 1
        }
        // 找到当前桶对应的 old bucket中的桶的位置
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        // 原来的 oldbucket 还没有搬迁，则在old bucket中找
        if !evacuated(oldb) {
            b = oldb
        }
    }
    top := tophash(hash)
bucketloop:
    // 双重for循环 外层遍历overflow（链表） 内层遍历桶
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
            // 如果tophash 不相等，
            if b.tophash[i] != top {
                // 如果当前为cell 为空， 且当前结点后面没有cell或者overflow，则剪枝， 提前结束
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                // 找下一个cell
                continue
            }
            // 走到此处说明tophash 是相等的了， 需要进一步判断完整的hash值是否相等了。
            // k：key的地址 = 初始地址 + 偏移地址
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            // 如果key类型是指针，则解引用
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            // 判断当前cell的key 和 k的值是否相等
            // 如果key相等，则找到了对应的cell， 取值返回就可以了
            if t.key.equal(key, k) {
                // 找到对应的value的 地址 = 偏移地址 + key的类型大小 * 8 + i * value的类型大小
                e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                if t.indirectelem() {
                    e = *((*unsafe.Pointer)(e))
                }
                return e
            }
        }
    }
    // 遍历完成， 没有找到对应的cell，则返回零值
    return unsafe.Pointer(&zeroVal[0])
}

修改map元素

使用方式：

package main

import "fmt"

func main() {
    // 初始化 map
    ageMap := make(map[string]int)
    // 插入元素
    ageMap["wxx"] = 24
}

修改和插入元素

步骤如下：

1. 定位key的位置， 和 map的查询操作一样。
2. 如果定位过程中发现当前map 正在进行扩容， 则帮助进行扩容搬迁。否则当前插入没有意义。
3. 如果当前map中 已经存在该key， 则修改value的值， 返回
4. 如果当前map中 不存在该key，则在找到的第一个空的cell上插入 该元素的 tophash， key， value。 该步骤需要判断是否需要扩容， 如果满足扩容条件则进行扩容

扩容条件 ：

• 每个bucket 中的数量 大于 6.5（map的容量count / 桶的数量 2^B > 6.5）。 此时太拥挤了，hashtable 冲突会比较严重

• overflow的数量太多了了， 查询效率太低。地广人稀， 需要聚集当一起居住。

  • 当 B <= 15时 noverflow >= 2^B

  • 当 B > 15时， noverflow >= 2^15

// Like mapaccess, but allocates a slot for the key if it is not present in the map.
// mapassign 插入元素 修改元素
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 初始化检测
    if h == nil {
        panic(plainError("assignment to entry in nil map"))
    }
    // 竞争检测
    if raceenabled {
        callerpc := getcallerpc()
        pc := funcPC(mapassign)
        racewritepc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
    if msanenabled {
        msanread(key, t.key.size)
    }
    // 安全检测，如果当前有协程正在写，则panic ， 同时写错误
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }
    // 依据hash种子，生成hash值
    hash := t.hasher(key, uintptr(h.hash0))

    // Set hashWriting after calling t.hasher, since t.hasher may panic,
    // in which case we have not actually done a write.
    // 将flags 的标志为改变为正在写
    h.flags ^= hashWriting
    // 如果没有 buckets, 则new 一个
    if h.buckets == nil {
        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
    }

again:
    // 找到对应的桶 索引为 index = hash & 2^B - 1，第index个桶
    bucket := hash & bucketMask(h.B)
    // 如果正在扩容
    if h.growing() {
        // 帮助扩容
        growWork(t, h, bucket)
    }
    // 找到对应桶的地址
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
    // tophash : 取hash值的高八位
    top := tophash(hash)

    // 要插入的cell 的tophash[i] 的地址
    var inserti *uint8
    // 要插入cell 的key 的地址
    var insertk unsafe.Pointer
    // 要插入cell 的value的地址
    var elem unsafe.Pointer
bucketloop:
    // 双重for 循环，寻找对应的cell
    // 外层for循环 遍历overflow
    // 内层for 循环， 遍历bucket
    for {
        for i := uintptr(0); i < bucketCnt; i++ {
            // tophash 不相等
            if b.tophash[i] != top {
                // 如果当前cell为空，且inserti == nil  ===》 找到的第一个可以容纳当前元素的cell，记录当前cell 的 i key value 的地址
                if isEmpty(b.tophash[i]) && inserti == nil {
                    // 记录tophash[] 中的i的地址
                    inserti = &b.tophash[i]
                    // 记录key 的地址
                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                    // 记录 value 的地址
                    elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                }
                // 如果当前cell为空， 且后面的没有cell 或 overflow了， 则说明后面不可能找了，直接跳出循环，
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
            }
            // 走到这里，说明tophash 相等了， 现在要比较完整hash了
            // 取到当前cell的key的地址
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            // 解应用
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            // 如果key 和 k不相等，则continue， 继续往后找
            if !t.key.equal(key, k) {
                continue
            }
            // already have a mapping for key. Update it.
            // 如果map中 已经有了当前元素， 需要更新一下value
            if t.needkeyupdate() {
                typedmemmove(t.key, k, key)
            }
            // 取到value的 地址
            elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
            // 完成修改
            goto done
        }
        ovf := b.overflow(t)
        // 遍历完成了， 跳出循环。
        // 遍历完所有的cell 都没有找到。
        if ovf == nil {
            break
        }
        b = ovf
    }

    // Did not find mapping for key. Allocate new cell & add entry.

    // If we hit the max load factor or we have too many overflow buckets,
    // and we're not already in the middle of growing, start growing.
    // 判断一下 是否需要扩容
    // 扩容条件： 1. 当前map 没有在扩容
    //          2. 满足两个扩容条件中的一个
    //扩容条件 1：每个bucket 中的数量 大于 6.5（map的容量count / 桶的数量 2^B  > 6.5）。 此时太拥挤了，hashtable 冲突会比较严重
    //扩容条件 2：overflow的数量太多了， 查询效率太低。地广人稀， 需要聚集当一起居住
    //          当 B <= 15时 noverflow >= 2^B
    //          当 B > 15时， noverflow >= 2^15
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        // 标识一下 开始扩容。 hashGrow()只进行分配空间， 具体扩容在growWork()中
        hashGrow(t, h)
        // 扩容后，元素的位置可能会改变，需要重新遍历一次
        goto again // Growing the table invalidates everything, so try again
    }
    // 此时的情况， 遍历完了全部的Overflow的cell， 仍然没有找到合适的位置（前面的位置都满了）， 则新建一个overflow 放置在第一个cell里
    if inserti == nil {
        // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
        // 新建一个overflow
        newb := h.newoverflow(t, b)
        // tophash的 i 的地址
        inserti = &newb.tophash[0]
        // key的地址
        insertk = add(unsafe.Pointer(newb), dataOffset)
        // value的地址
        elem = add(insertk, bucketCnt*uintptr(t.keysize))
    }

    // store new key/elem at insert position
    // 解引用
    if t.indirectkey() {
        kmem := newobject(t.key)
        *(*unsafe.Pointer)(insertk) = kmem
        insertk = kmem
    }
    // 解引用
    if t.indirectelem() {
        vmem := newobject(t.elem)
        *(*unsafe.Pointer)(elem) = vmem
    }
    // 设置key的值
    typedmemmove(t.key, insertk, key)
    // 设置tophash的值
    *inserti = top
    // map容量 + 1
    h.count++

done:
    // 判断是否有修改了 flag的协程，如果有则panic
    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    // 恢复flag标识位
    h.flags &^= hashWriting
    // 解引用
    if t.indirectelem() {
        elem = *((*unsafe.Pointer)(elem))
    }
    // 返回value的值
    return elem
}

扩容

源码

扩容的标识 ：h.oldbuckets ！= nil

// 扩容，hashGrow 函数值是申请了新的内存， 以及将oldbucket上的flags 标识赋值给 新的buckets
func hashGrow(t *maptype, h *hmap) {
    // If we've hit the load factor, get bigger.
    // Otherwise, there are too many overflow buckets,
    // so keep the same number of buckets and "grow" laterally.
    bigger := uint8(1)
    if !overLoadFactor(h.count+1, h.B) {
        bigger = 0
        h.flags |= sameSizeGrow
    }
    oldbuckets := h.buckets
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

    flags := h.flags &^ (iterator | oldIterator)
    if h.flags&iterator != 0 {
        flags |= oldIterator
    }
    // commit the grow (atomic wrt gc)
    h.B += bigger
    h.flags = flags
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    h.nevacuate = 0
    h.noverflow = 0

    if 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")
        }
        h.extra.oldoverflow = h.extra.overflow
        h.extra.overflow = nil
    }
    if nextOverflow != nil {
        if h.extra == nil {
            h.extra = new(mapextra)
        }
        h.extra.nextOverflow = nextOverflow
    }

    // the actual copying of the hash table data is done incrementally
    // by growWork() and evacuate().
}

// 实际扩容
func growWork(t *maptype, h *hmap, bucket uintptr) {
    // make sure we evacuate the oldbucket corresponding
    // to the bucket we're about to use
    // 搬迁元素， 将老bucket上的元素 搬迁到心bucket上
    evacuate(t, h, bucket&h.oldbucketmask())

    // evacuate one more oldbucket to make progress on growing
    // 如果仍在扩容，则继续帮助扩容
    if h.growing() {
        evacuate(t, h, h.nevacuate)
    }
}


// evacuate 将oldbuckets上的元素 搬迁到 新的buckets上
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
    // 找到oldbuckets 的 bucket的地址
    b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
    // 计算oldbucket 的bucket的数量 2^B  B == 2  1 00. 高位1
    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.
        // 如果是双倍扩容，则会由两个长为newbit（oldbuckets的长度）的数组， 低位为x 部分， 高位为 y 部分
        // 比如 原本是长度为2， 扩容后的长度为 2 + 2（4） 前一部分的长度为2的数组为 x 部分， 后一部分长度为2的数组为 y 部分
        var xy [2]evacDst
        // 默认只使用 x 部分
        x := &xy[0]
        // x部分的起始位置， 实际上是tophash[] 的起始位置
        x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
        // x部分的key 的起始位置
        x.k = add(unsafe.Pointer(x.b), dataOffset)
        // x部分的value 的起始位置
        x.e = add(x.k, bucketCnt*uintptr(t.keysize))
        // 双倍扩容才需要使用到 y 部分。 等量扩容只需要使用 x 部分
        if !h.sameSizeGrow() {
            // Only calculate y pointers if we're growing bigger.
            // Otherwise GC can see bad pointers.
            y := &xy[1]
            // y 部分 和 x部分的对应的位置相差的距离 为一个 newbit的长度
            y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
            // y 部分的keys 的起始位置
            y.k = add(unsafe.Pointer(y.b), dataOffset)
            // y 部分的values 的起始位置
            y.e = add(y.k, bucketCnt*uintptr(t.keysize))
        }

        for ; b != nil; b = b.overflow(t) {
            // keys的起始位置
            k := add(unsafe.Pointer(b), dataOffset)
            // values的起始位置
            e := add(k, bucketCnt*uintptr(t.keysize))
            // 遍历bucket中的每一个 cell
            for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
                // oldbucket 的 tophash[i] 的tophash
                top := b.tophash[i]
                if isEmpty(top) {
                    // 做一下标记 当前cell 已经搬迁过了，继续下一个cell
                    b.tophash[i] = evacuatedEmpty
                    continue
                }
                // tophash 的状态由问题。 [0, minTopHash]是给用来标识cell状态的， 正常结点的tophash 不能 小于 minTopHash
                if top < minTopHash {
                    throw("bad map state")
                }
                k2 := k
                if t.indirectkey() {
                    k2 = *((*unsafe.Pointer)(k2))
                }
                var useY uint8
                // 双倍扩容
                if !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))
                    // 如果key 存的是一个 NaN ，重新计算hash。 但是没有意义， 每次重新计算可能hash值都会改变，不可唯一确定。
                    if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
                        // If key != key (NaNs), then the hash could be (and probably
                        // will be) entirely different from the old hash. Moreover,
                        // it isn't reproducible. Reproducibility is required in the
                        // presence of iterators, as our evacuation decision must
                        // match whatever decision the iterator made.
                        // Fortunately, we have the freedom to send these keys either
                        // way. Also, tophash is meaningless for these kinds of keys.
                        // We let the low bit of tophash drive the evacuation decision.
                        // We recompute a new random tophash for the next level so
                        // these keys will get evenly distributed across all buckets
                        // after multiple grows.
                        useY = top & 1
                        top = tophash(hash)
                    } else {
                        // 放置在 y 部分。
                        // 假设 b == 2，则newbit == 1 00 ， 即只需要和高位1 比较，即可确定元素最终是x、 y部分了。
                        // 高位 1 在 y 部分， 地位 0 在 x 部分
                        if hash&newbit != 0 {
                            useY = 1
                        }
                    }
                }
                // 状态错误， panic
                if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
                    throw("bad evacuatedN")
                }
                // evacuatedX + 0/1
                b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
                // 最终存放地址
                dst := &xy[useY] // evacuation destination

                // 新的bucket满了，则分配一个新的overflow 放在一个cell上
                if dst.i == bucketCnt {
                    dst.b = h.newoverflow(t, dst.b)
                    dst.i = 0
                    dst.k = add(unsafe.Pointer(dst.b), dataOffset)
                    dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
                }
                // 更新top hash值
                dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
                // key 指针类型 则 copy 指针， 否则copy 值
                if 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)
                }
                // 索引 + 1
                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.
                // key 地址更新
                dst.k = add(dst.k, uintptr(t.keysize))
                // value 地址更新
                dst.e = add(dst.e, uintptr(t.elemsize))
            }
        }
        // Unlink the overflow buckets & clear key/elem to help GC.
        // 清除掉old bucket中的指针关系， 方便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) - dataOffset
            memclrHasPointers(ptr, n)
        }
    }

    // oldbucket == nevacuate 标识oldbucket的最后一个cell的搬迁工作完成了，即扩容完成
    if oldbucket == h.nevacuate {
        // 检查， 确保扩容完成了。 修改oldbucket == nil， 扩容完成
        advanceEvacuationMark(h, t, newbit)
    }
}

搬迁过程

搬迁过程中 搬迁中的查找

假设当前定位到了新的buckets的3号桶中，首先会判断oldbuckets中的对应的桶有没有被搬迁过。 如果搬迁过了，不需要看原来的桶了，直接遍历新的buckets的3号桶。

内存对比图

扩容前：

扩容前数据

等量扩容结果

等量扩容
两倍扩容：

双倍扩容会将old buckets上的元素分配到x， y两个部key & 1 << B == 0 分配到x部分，key & 1 << B == 1 分配到y部分

两倍扩容

举例说明

注意： 当前只对双倍扩容描述， 等量扩容只是重新填充了一下元素， 相对位置没有改变。

假设当前map 的B == 5，原本元素经过hash函数计算的 hash 值为：

10010111 | 000011110110110010001111001010100010010110010101011 │ 00110

rehash.png

因为双倍扩容之后 B = B + 1，此时B == 6。key & 1 << B == 1, 即 当前元素rehash到高位，新buckets中 y 部分. 否则 key & 1 << B == 0 则rehash到低位，即x 部分。

删除map元素

1. 定位key，和查找过程相似。

2. 判断删除元素后当前元素的个数， 如果个数为0， 则重置hash种子， 使得map 和 以前的map更加的不同

3. 当前overflow中只有当前元素了，要删除当前元素时， 需要考虑一下后面overflow的cell的状态， 将后续的状态全部修改

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
    // race 检测
    if raceenabled && h != nil {
        callerpc := getcallerpc()
        pc := funcPC(mapdelete)
        racewritepc(unsafe.Pointer(h), callerpc, pc)
        raceReadObjectPC(t.key, key, callerpc, pc)
    }
    if msanenabled && h != nil {
        msanread(key, t.key.size)
    }
    // map没有初始化 或者 容量位0 直接返回
    if h == nil || h.count == 0 {
        if t.hashMightPanic() {
            t.hasher(key, 0) // see issue 23734
        }
        return
    }
    // 写 标志位检查， 如果有协程正在写map， 则panic 同时写错误
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }
    // 依据hash种子 生成 hash值
    hash := t.hasher(key, uintptr(h.hash0))

    // Set hashWriting after calling t.hasher, since t.hasher may panic,
    // in which case we have not actually done a write (delete).
    // 置为 写 标志位
    h.flags ^= hashWriting
    // 找到是第几个桶
    bucket := hash & bucketMask(h.B)
    // 正在扩容，则帮助搬迁
    if h.growing() {
        growWork(t, h, bucket)
    }
    // 找到对应桶的 地址
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
    bOrig := b
    top := tophash(hash)
search:
    // 双重循环， 外层遍历链表， 内层遍历bucket
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                if b.tophash[i] == emptyRest {
                    break search
                }
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            k2 := k
            if t.indirectkey() {
                k2 = *((*unsafe.Pointer)(k2))
            }
            if !t.key.equal(key, k2) {
                continue
            }
            // Only clear key if there are pointers in it.
            // 如果是指针， 则将指向内容置为 nil
            if 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)
            }
            // 标识当前cell 为空
            b.tophash[i] = emptyOne
            // If the bucket now ends in a bunch of emptyOne states,
            // change those to emptyRest states.
            // It would be nice to make this a separate function, but
            // for loops are not currently inlineable.
            // 如果当前cell 是bucket的最后一个结点
            if i == bucketCnt-1 {
                // 后续overflow 中还有元素
                if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
                    // 不用继续遍历， 已经找到了
                    goto notLast
                }
            } else {
                // 后一个cell 中有元素， 则说明找到了
                if b.tophash[i+1] != emptyRest {
                    goto notLast
                }
            }

            // 走到这里， 说明当前cell 后面没有元素了
            // 这个for 循环是为了 改变当前cell后面的多余的元素。
            // 如 当前overflow中只有当前元素了，要删除当前元素时， 需要考虑一下后面overflow的cell的状态， 将后续的状态全部修改
            for {
                // 修改状态， 标识当前cell 后面没有元素了
                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
                }
            }
        notLast:
            // 容量 - 1
            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 {
                // 如果 容量为空了，则重新生成hash 种子
                h.hash0 = fastrand()
            }
            break search
        }
    }

    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    h.flags &^= hashWriting
}

遍历map

使用方式：

package main

import "fmt"

func main() {
 ageMp := make(map[string]int)
 ageMp["wxx"] = 1

 for name, age := range ageMp {
 fmt.Println(name, age)
 }
}

源码

// mapiterinit 初始化迭代器
// mapiternext 迭代器遍历
mapiterinit + mapiternext == 遍历

// mapiterinit initializes the hiter struct used for ranging over maps.
// The hiter struct pointed to by 'it' is allocated on the stack
// by the compilers order pass or on the heap by reflect_mapiterinit.
// Both need to have zeroed hiter since the struct contains pointers.
func mapiterinit(t *maptype, h *hmap, it *hiter) {
    // 竞争检测
    if raceenabled && h != nil {
        callerpc := getcallerpc()
        racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiterinit))
    }

    if h == nil || h.count == 0 {
        return
    }

    if unsafe.Sizeof(hiter{})/sys.PtrSize != 12 {
        throw("hash_iter size incorrect") // see cmd/compile/internal/reflectdata/reflect.go
    }
    it.t = t
    it.h = h

    // grab snapshot of bucket state
    it.B = h.B
    it.buckets = h.buckets
    if t.bucket.ptrdata == 0 {
        // Allocate the current slice and remember pointers to both current and old.
        // This preserves all relevant overflow buckets alive even if
        // the table grows and/or overflow buckets are added to the table
        // while we are iterating.
        h.createOverflow()
        it.overflow = h.extra.overflow
        it.oldoverflow = h.extra.oldoverflow
    }

    // decide where to start
    // 随机取一个bucket开始
    r := uintptr(fastrand())
    if h.B > 31-bucketCntBits {
        r += uintptr(fastrand()) << 31
    }
    it.startBucket = r & bucketMask(h.B)
    // 随机取一个cell 开始
    it.offset = uint8(r >> h.B & (bucketCnt - 1))

    // iterator state
    it.bucket = it.startBucket

    // Remember we have an iterator.
    // Can run concurrently with another mapiterinit().
    if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
        atomic.Or8(&h.flags, iterator|oldIterator)
    }

    mapiternext(it)
}

可以看到，每一遍历生成迭代器的时候，会随机选取一个bucket 以及 一个cell开始。 从前往后遍历，再次遍历到起始位置时，遍历完成。

总结

1. map 返回的结构体是指针， 即引用类型

2. map的内存结构是 hash table + 链表

3. map的定位实际上是双重for循环， 在定位到bucket后，外层遍历overflow， 内层遍历8个cell

4. map 扩容的标识 h.oldbuckets != nil

5. map 的扩容分成等量扩容 和 双倍扩容

6. map的扩容条件为 负载因子大于 6.5 或者 overflow 的数量太多（ B <= 15时 noverflow >= 2^B ； B > 15时， noverflow >= 2^15）。前者对应的是元素分配太过于集中，hash冲突严重。后者对应的是元素分配太过于稀疏，地广人稀，查询效率低。

7. map 删除元素后，会重新生成hash种子，使得map 和之前更加得不同

8. map 的遍历是随机的，可能每次的遍历先后顺序不一样。

参考资料

https://www.qcrao.com/2019/05/22/dive-into-go-map/

https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/

https://www.bilibili.com/video/BV1Q4411W7MR?spm_id_from=333.337.search-card.all.click