一.map的基本介绍

        map又称字典/字段/关联数组,是key-value数据结构.类似于其它编程语言的集合,在编程中进程使用,核心特征包含下述三点：

  • （1）存储基于 key-value 对映射的模式
  • （2）基于 key 维度实现存储数据的去重
  • （3）读、写、删操作控制，时间复杂度 O(1)

二.map的声明

1.基本语法 

var map变量名 map[keytype]valuetype

keytype可以是什么类型?

        go中的map的key可以是多种类型:bool,数字(整数,浮点数),string,指针,channel,还可以是只包含前面几种类型的接口,结构体,数组

        key的类型通常为int,string

注意:  slice,map还有function不可以作为key,因为这几个没法用 == 来判断

valuetype可以是什么类型?

        valuetype的类型和key基本一样,通常为数字(整数,浮点数),string,map,struct

2.map声明举例

 var a map[string]string

 var a map[string]int

 var a map[int]string

 var a map[string]map[string]string 

注意: 声明是不会分配内存的,初始化需要make,分配内存后才能赋值和使用

func main() {
    //map的声明和注意事项
    var a map[string]string
    //当声明map后,直接输出,结果:map[]
    fmt.Println(a)  //map[]
    //如果直接给map赋值,会报错:panic: assignment to entry in nil map(没有给map分配数据空间)
    // a["name"] = "张三"
    //在使用map前,需要先make,make的作用是给map分配数据空间
    a = make(map[string]string, 10)
    a["name"] = "张三"
    a["name1"] = "张三1"
    a["name"] = "李四"
    fmt.Println(a)
}

 对上述代码的说明:

1.map在使用前一定要make进行初始化,倘若 map 未初始化，直接执行写操作会导致 panic

2.map的key是不能重复的,如果重复了,则以最后这个key-value为准

3.map的value可以是相同的

4.map的key-value是无序的

 三.map的使用

package main

import (
    "fmt"
)

func main()  {
    //第一种使用方式:通过 make 关键字进行初始化，同时指定 map 预分配的容量
    var a map[string]string
    //在使用map前,需要先make,make的作用是给map分配数据空间
    a = make(map[string]string, 10)
    a["name"] = "张三"
    a["name1"] = "张三1"
    a["name"] = "李四"
    fmt.Println(a)

    //推荐使用:第二种使用方式, 通过 make 关键字进行初始化，不显式声明容量，因此默认容量 为 0
    cities := make(map[string]string)
    cities["c1"] = "北京"
    cities["c2"] = "上海"
    cities["c3"] = "广州"
    fmt.Println(cities)

    //第三种使用方式:初始化操作连带赋值，一气呵成
    var heros map[string]string = map[string]string{
        "h1":"张三",
        "h2":"李四",  //最后一个逗号不能少
    }
    // heros := map[string]string {
    //  "h1":"张三",
    //  "h2":"李四",
    // }
    heros["h3"] = "王五"
    fmt.Println(heros)
}

练习

    /**
     *  案例: 演示一个key-value:
     *       存放三个学生消息,每个学生有姓名,性别
     *       思路: map[string]map[string]string
     */
    students := make(map[string]map[string]string)
    students["0001"] = make(map[string]string, 2)
    students["0001"]["name"] = "张三"
    students["0001"]["sex"] = "男"
    students["0002"] = make(map[string]string, 2)
    students["0002"]["name"] = "赵敏"
    students["0002"]["sex"] = "女"
    fmt.Println(students)

四.crud操作

package main

import (
    "fmt"
)

func main()  {
    //增加,修改
    cities := make(map[string]string)
    cities["c1"] = "北京"
    cities["c2"] = "上海"
    cities["c3"] = "广州"
    fmt.Println(cities)
    //因为c1这个key已经存在,故下面的是修改
    cities["c1"] = "重庆"
    fmt.Println(cities)

    //删除
    delete(cities, "c1")
    fmt.Println(cities)
    //当delete指定的key不存在时,删除不会操作,也不会报错
    delete(cities, "c4")
    fmt.Println(cities)
}

map删除

        说明:

                delete(map,key),delete是一个内置函数,如果key存在,就删除该key-value,如果key不存在,就不操作,但也不报错

 细节说明

        如果要删除map的所有key,没有一个专门的方法一次删除,可以遍历一下key,逐个删除或者map = make(...),make一个新的,让原来的成为垃圾,被GC回收

    //如果希望一次性删除所有的key
    //1.变遍历所有的key,再足个删除
    //2.直接make一个新的空间
    cities := make(map[string]string)
    fmt.Println(cities)

 map的查找

    //演示map的查找
    val, ok := cities["c1"]
    if ok {
        fmt.Printf("存在c1这个key,值为%v\n", val)
    } else {
        fmt.Println("不存在c1这个key")
    }

五.遍历

案例演示一个相对复杂的map遍历,该map的value又是一个map

说明:map的遍历使用for-range的结构遍历

package main

import (
    "fmt"
)

func main() {
    //使用for-range遍历
    var a map[string]string
    a = make(map[string]string)
    a["name"] = "张三"
    a["name1"] = "张三1"
    a["name"] = "李四"
    fmt.Println(a)
    for k, v := range a {
        fmt.Printf("k=%v,v=%v\n",k, v)
    }

    //使用for-range遍历比较复杂的map
    /**
     * 案例: 演示一个key-value:
     *       存放三个学生消息,每个学生有姓名,性别
     *       思路: map[string]map[string]string
     */
    students := make(map[string]map[string]string)
    students["0001"] = make(map[string]string, 2)
    students["0001"]["name"] = "张三"
    students["0001"]["sex"] = "男"
    students["0002"] = make(map[string]string, 2)
    students["0002"]["name"] = "赵敏"
    students["0002"]["sex"] = "女"
    fmt.Println(students)
    fmt.Println()
    for key, val := range students {
        fmt.Printf("key=%v\n", key)
        for k, v := range val {
            fmt.Printf("\t k=%v, v=%v\n", k,v)
        }
    }
}

 

    //统计map长度
    a := make(map[int]int,2)
    a[1] = 1
    a[2] = 2
    fmt.Println("a中有", len(a), "对key-value")

六.并发冲突

map不是并发安全的数据结构，倘若存在并发读写行为，会抛出 fatal error

具体规则是：

  • （1）并发读没有问题
  • （2）并发读写中的“写”是广义上的，包含写入、更新、删除等操作
  • （3）读的时候发现其他 goroutine 在并发写，抛出 fatal error
  • （4）写的时候发现其他 goroutine 在并发写，抛出 fatal error
fatal("concurrent map read and map write")
fatal("concurrent map writes")

需要关注，此处并发读写会引发 fatal error，是一种比 panic 更严重的错误，无法使用 recover 操作捕获

 七.map的核心原理

1.原理

map又称为hash map，在算法上基于hash实现key的映射和寻址,在数据结构上基于桶数组实现 key-value 对的存储

以一组 key-value 对写入 map 的流程为例进行简述：

（1）通过哈希方法取得 key 的 hash 值；

（2）hash 值对桶数组长度取模，确定其所属的桶；

（3）在桶中插入 key-value 对

hash 的性质，保证了相同的 key必然产生相同的 hash 值，因此能映射到相同的桶中，通过桶内遍历的方式锁定对应的 key-value 对,因此，只要在宏观流程上，控制每个桶中 key-value 对的数量，就能保证 map 的几项操作都限制为常数级别的时间复杂度

2. hash介绍

hash 译作散列，是一种将任意长度的输入压缩到某一固定长度的输出摘要的过程，由于这种转换属于压缩映射，输入空间远大于输出空间，因此不同输入可能会映射成相同的输出结果. 此外，hash在压缩过程中会存在部分信息的遗失，因此这种映射关系具有不可逆的特质

hash有几大特性:

  • （1）hash的可重入性：相同的 key，必然产生相同的 hash 值
  • （2）hash的离散性：只要两个 key 不相同，不论其相似度的高低，产生的 hash值会在整个输出域内均匀地离散化

  • （3）hash 的单向性：企图通过 hash 值反向映射回 key 是无迹可寻的

  • （4）hash 冲突：由于输入域（key）无穷大，输出域（hash 值）有限，因此必然存在不同 key 映射到相同 hash 值的情况，称之为 hash 冲突

3.桶数组

map 中，会通过长度为 2 的整数次幂的桶数组进行 key-value 对的存储：

  • （1）每个桶固定可以存放 8 个 key-value 对；
  • （2）倘若超过 8 个 key-value 对打到桶数组的同一个索引当中，此时会通过创建桶链表的方式来化解这一问题

 4.map解决hash冲突

由于hash冲突的存在，不同key可能存在相同的 hash 值；而hash值对桶数组长度取模的时候，可能会存在hash值被打到同一个桶中,所以,不同的 key-value 可能被映射到 map 的同一个桶当中.此时最经典的解决手段分为两种：拉链法和开放寻址法

（1）拉链法

拉链法中，将命中同一个桶的元素通过链表的形式进行链接，因此很便于动态扩展

（2）开放寻址法

开放寻址法中，在插入新条目时，会基于一定的探测策略持续寻找，直到找到一个可用于存放数据的空位为止

(3).桶散列法

桶是一能接纳多个记录的节点,缺点:有可能浪费(未占用)存储单元

在 map 解决 hash/分桶 冲突问题时，实际上结合了拉链法和开放寻址法两种思路. 以 map 的插入写流程为例，进行思路阐述：

  • （1）桶数组中的每个桶，严格意义上是一个单向桶链表，以桶为节点进行串联；
  • （2）每个桶固定可以存放 8 个 key-value 对；
  • （3）当 key 命中一个桶时，首先根据开放寻址法，在桶的 8 个位置中寻找空位进行插入；
  • （4）倘若桶的 8 个位置都已被占满，则基于桶的溢出桶指针，找到下一个桶，重复第（3）步；
  • （5）倘若遍历到链表尾部，仍未找到空位，则基于拉链法，在桶链表尾部续接新桶，并插入 key-value 对

5.扩容优化性能

倘若 map 的桶数组长度固定不变，那么随着 key-value 对数量的增长，当一个桶下挂载的 key-value 达到一定的量级，此时操作的时间复杂度会趋于线性，无法满足诉求.因此在实现上，map 桶数组的长度会随着 key-value 对数量的变化而实时调整，以保证每个桶内的 key-value 对数量始终控制在常量级别，满足各项操作为 O(1) 时间复杂度的要求.map 扩容机制的核心点包括：

  • （1）扩容分为增量扩容和等量扩容；
  • （2）当桶内 key-value 总数/桶数组长度 > 6.5 时发生增量扩容，桶数组长度增长为原值的两倍；
  • （3）当桶内溢出桶数量大于等于 2^B 时( B 为桶数组长度的指数，B 最大取 15)，发生等量扩容，桶的长度保持为原值；
  • （4）采用渐进扩容的方式，当桶被实际操作到时，由使用者负责完成数据迁移，避免因为一次性的全量数据迁移引发性能抖动

6.数据结构

hmap

type hmap struct {
    count     int   //map 中的 key-value 总数
    flags     uint8  //map 状态标识，可以标识出 map 是否被 goroutine 并发读写
    B         uint8  //桶数组长度的指数，桶数组长度为 2^B
    noverflow uint16   //map 中溢出桶的数量
    hash0     uint32   //hash 随机因子，生成 key 的 hash 值时会使用到
    buckets    unsafe.Pointer  //桶数组
    oldbuckets unsafe.Pointer //扩容过程中老的桶数组
    nevacuate  uintptr  //扩容时的进度标识，index 小于 nevacuate 的桶都已经由老桶转移到新桶中
    extra *mapextra  //预申请的溢出桶
}

 mapextra

在map初始化时，倘若容量过大，会提前申请好一批溢出桶，以供后续使用，这部分溢出桶存放在 hmap.mapextra 当中

type mapextra struct {
    overflow    *[]*bmap  //供桶数组 buckets 使用的溢出桶
    oldoverflow *[]*bmap  //扩容流程中，供老桶数组 oldBuckets 使用的溢出桶


    nextOverflow *bmap  //下一个可用的溢出桶
}
mapextra.overflow：；

 bmap

bmap 就是 map 中的桶,可以存储 8 组 key-value 对的数据，以及一个指向下一个溢出桶的指针；每组 key-value 对数据包含key高8位 hash 值 tophash，key 和 val 三部分,在代码层面只展示了 tophash 部分，但由于 tophash、key 和 val 的数据长度固定，因此可以通过内存地址偏移的方式寻找到后续的 key 数组、val 数组以及溢出桶指针

const bucketCnt = 8
type bmap struct {
    tophash [bucketCnt]uint8
}

完整的bmap参考:

type bmap struct {
    tophash [bucketCnt]uint8
    keys [bucketCnt]T
    values [bucketCnt]T
    overflow uint8
}

7.初始化map

makemap 

创建 map 时，实际上会调用 runtime/map.go 文件中的 makemap 方法,代码以及步骤如下:

func makemap(t *maptype, hint int, h *hmap) *hmap {
    //1.hint 为 map 拟分配的容量；在分配前，会提前对拟分配的内存大小进行判断，倘若超限，会将 hint 置为零
    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
    if overflow || mem > maxAlloc {
        hint = 0
    }

    //2.通过 new 方法初始化 hmap
    if h == nil {
        h = new(hmap)
    }
    //3.调用 fastrand，构造 hash 因子：hmap.hash0
    h.hash0 = fastrand()

    //4.大致上基于 log2(B) >= hint 的思路，计算桶数组的容量 B
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B


    if h.B != 0 {
        //5.调用 makeBucketArray 方法，初始化桶数组 hmap.buckets
        var nextOverflow *bmap
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        //6.倘若 map 容量较大，会提前申请一批溢出桶 hmap.extra
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }


    return

makeBucketArray

makeBucketArray 方法会进行桶数组的初始化，并根据桶的数量决定是否需要提前作溢出桶的初始化. 方法主干代码如下：

func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
    base := bucketShift(b)
    nbuckets := base
    if b >= 4 {
        nbuckets += bucketShift(b - 4)
    }
    
    buckets = newarray(t.bucket, int(nbuckets))
   
    if base != nbuckets {
        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
}

makeBucketArray 会为 map 的桶数组申请内存，在桶数组的指数 b >= 4时（桶数组的容量 >= 52 ），会需要提前创建溢出桶.

通过 base 记录桶数组的长度，不包含溢出桶；通过 nbuckets 记录累加上溢出桶后，桶数组的总长度.

base := bucketShift(b)
nbuckets := base
if b >= 4 {
   nbuckets += bucketShift(b - 4)
}

调用 newarray 方法为桶数组申请内存空间，连带着需要初始化的溢出桶：

buckets = newarray(t.bucket, int(nbuckets))

倘若 base != nbuckets，说明需要创建溢出桶，会基于地址偏移的方式，通过 nextOverflow 指向首个溢出桶的地址.

if base != nbuckets {
   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

倘若需要创建溢出桶，会在将最后一个溢出桶的 overflow 指针指向 buckets 数组，以此来标识申请的溢出桶已经用完.

func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
    *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-goarch.PtrSize)) = ovf
}

8.读取数据流程

(1).步骤

map 读流程主要分为以下几步：

  • （1）根据 key 取 hash 值
  • （2）根据 hash值对桶数组取模，确定所在的桶
  • （3）沿着桶链表依次遍历各个桶内的 key-value 对
  • （4）命中相同的 key，则返回 value；倘若 key 不存在，则返回零值

(2).mapaccess

map 读操作最终会走进 runtime/map.go 的 mapaccess 方法

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    if h == nil || h.count == 0 {
        return unsafe.Pointer(&zeroVal[0])
    }
    if h.flags&hashWriting != 0 {
        fatal("concurrent map read and map write")
    }
    hash := t.hasher(key, uintptr(h.hash0))
    m := bucketMask(h.B)
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    if c := h.oldbuckets; c != nil {
        if !h.sameSizeGrow() {
            m >>= 1
        }
        oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {
            b = oldb
        }
    }
    top := tophash(hash)
bucketloop:
    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 bucketloop
                }
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            if t.key.equal(key, k) {
                e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
                if t.indirectelem() {
                    e = *((*unsafe.Pointer)(e))
                }
                return e
            }
        }
    }
    return unsafe.Pointer(&zeroVal[0])
}


func (h *hmap) sameSizeGrow() bool {
    return h.flags&sameSizeGrow != 0
}


func evacuated(b *bmap) bool {
    h := b.tophash[0]
    return h > emptyOne && h < minTopHash
}

1）倘若 map 未初始化，或此时存在 key-value 对数量为 0，直接返回零值；

if h == nil || h.count == 0 {
    return unsafe.Pointer(&zeroVal[0])
}

（2）倘若发现存在其他 goroutine 在写 map，直接抛出并发读写的 fatal error；其中，并发写标记，位于 hmap.flags 的第 3 个 bit 位；

const hashWriting  = 4
 
 if h.flags&hashWriting != 0 {
        fatal("concurrent map read and map write")
 }

（3）通过 maptype.hasher() 方法计算得到 key 的 hash 值，并对桶数组长度取模，取得对应的桶. 关于 hash 方法的内部实现，golang 并未暴露.

hash := t.hasher(key, uintptr(h.hash0))
 m := bucketMask(h.B)
 b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))

其中，bucketMast 方法会根据 B 求得桶数组长度 - 1 的值，用于后续的 & 运算，实现取模的效果：

func bucketMask(b uint8) uintptr {
    return bucketShift(b) - 1
}

（4）在取桶时，会关注当前 map 是否处于扩容的流程，倘若是的话，需要在老的桶数组 oldBuckets 中取桶，通过 evacuated 方法判断桶数据是已迁到新桶还是仍存留在老桶，倘若仍在老桶，需要取老桶进行遍历.

if c := h.oldbuckets; c != nil {
    if !h.sameSizeGrow() {
        m >>= 1
    }
    oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
    if !evacuated(oldb) {
        b = oldb
    }
 }

在取老桶前，会先判断 map 的扩容流程是否是增量扩容，倘若是的话，说明老桶数组的长度是新桶数组的一半，需要将桶长度值 m 除以 2.

const (
    sameSizeGrow = 8
)


func (h *hmap) sameSizeGrow() bool {
    return h.flags&sameSizeGrow != 0
}

取老桶时，会调用 evacuated 方法判断数据是否已经迁移到新桶. 判断的方式是，取桶中首个 tophash 值，倘若该值为 2,3,4 中的一个，都代表数据已经完成迁移.

const emptyOne = 1
const evacuatedX = 2
const evacuatedY = 3
const evacuatedEmpty = 4 
const minTopHash = 5


func evacuated(b *bmap) bool {
    h := b.tophash[0]
    return h > emptyOne && h < minTopHash
}

（5）取 key hash 值的高 8 位值 top. 倘若该值 < 5，会累加 5，以避开 0 ~ 4 的取值. 因为这几个值会用于枚举，具有一些特殊的含义.

const minTopHash = 5


top := tophash(hash)


func tophash(hash uintptr) uint8 {
    top := uint8(hash >> (goarch.PtrSize*8 - 8))
    if top < minTopHash {
        top += minTopHash
    }
    return top

（6）开启两层 for 循环进行遍历流程，外层基于桶链表，依次遍历首个桶和后续的每个溢出桶，内层依次遍历一个桶内的 key-value 对.

bucketloop:
for ; b != nil; b = b.overflow(t) {
    for i := uintptr(0); i < bucketCnt; i++ {
        // ...
    }
}
return unsafe.Pointer(&zeroVal[0])

内存遍历时，首先查询高 8 位的 tophash 值，看是否和 key 的 top 值匹配.

倘若不匹配且当前位置 tophash 值为 0，说明桶的后续位置都未放入过元素，当前 key 在 map 中不存在，可以直接打破循环，返回零值.

const emptyRest = 0
if b.tophash[i] != top {
    if b.tophash[i] == emptyRest {
          break bucketloop
    }
    continue
}

倘若找到了相等的 key，则通过地址偏移的方式取到 value 并返回.

其中 dataOffset 为一个桶中 tophash 数组所占用的空间大小.

if t.key.equal(key, k) {
     e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
     return e
}

倘若遍历完成，仍未找到匹配的目标，返回零值

 9.写入数据流程

(1).步骤

map 写流程主要分为以下几步：

  • （1）根据 key 取 hash 值
  • （2）根据 hash 值对桶数组取模，确定所在的桶
  • （3）倘若 map 处于扩容，则迁移命中的桶，帮助推进渐进式扩容
  • （4）沿着桶链表依次遍历各个桶内的 key-value 对
  • （5）倘若命中相同的 key，则对 value 中进行更新
  • （6）倘若 key 不存在，则插入 key-value 对
  • （7）倘若发现 map 达成扩容条件，则会开启扩容模式，并重新返回第（2）步

(2).mapassign

map 写操作最终会走进 runtime/map.go 的 mapassign 方法中

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    if h == nil {
        panic(plainError("assignment to entry in nil map"))
    }
    if h.flags&hashWriting != 0 {
        fatal("concurrent map writes")
    }
    hash := t.hasher(key, uintptr(h.hash0))


    h.flags ^= hashWriting


    if h.buckets == nil {
        h.buckets = newobject(t.bucket) 
    }


again:
    bucket := hash & bucketMask(h.B)
    if h.growing() {
        growWork(t, h, bucket)
    }
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
    top := tophash(hash)


    var inserti *uint8
    var insertk unsafe.Pointer
    var elem unsafe.Pointer
bucketloop:
    for {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                if isEmpty(b.tophash[i]) && inserti == nil {
                    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))
            }
            if !t.key.equal(key, k) {
                continue
            }
            if t.needkeyupdate() {
                typedmemmove(t.key, k, key)
            }
            elem = 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
    }


    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again 
    }


    if inserti == nil {
        newb := h.newoverflow(t, b)
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        elem = add(insertk, bucketCnt*uintptr(t.keysize))
    }


    if t.indirectkey() {
        kmem := newobject(t.key)
        *(*unsafe.Pointer)(insertk) = kmem
        insertk = kmem
    }
    if t.indirectelem() {
        vmem := newobject(t.elem)
        *(*unsafe.Pointer)(elem) = vmem
    }
    typedmemmove(t.key, insertk, key)
    *inserti = top
    h.count++




done:
    if h.flags&hashWriting == 0 {
        fatal("concurrent map writes")
    }
    h.flags &^= hashWriting
    if t.indirectelem() {
        elem = *((*unsafe.Pointer)(elem))
    }
    retur

（1）写操作时，倘若 map 未初始化，直接 panic；

if h == nil {
        panic(plainError("assignment to entry in nil map"))
}

（2）倘若其他 goroutine 在进行写或删操作，抛出并发写 fatal error；

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

（3）通过 maptype.hasher() 方法求得 key 对应的 hash 值；

hash := t.hasher(key, uintptr(h.hash0))

（4）通过异或位运算，将 map.flags 的第 3 个 bit 位置为 1，添加写标记；

h.flags ^= hashWriting

（5）倘若 map 的桶数组 buckets 未空，则对其进行初始化；

if h.buckets == nil {
     h.buckets = newobject(t.bucket) 
}

（6）找到当前 key 对应的桶索引 bucket；

bucket := hash & bucketMask(h.B)

（7）倘若发现当前 map 正处于扩容过程，则帮助其渐进扩容，具体内容在第 9 节中再作展开；

if h.growing() {
        growWork(t, h, bucket)
  }

（8）从 map 的桶数组 buckets 出发，结合桶索引和桶容量大小，进行地址偏移，获得对应桶 b；

b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))

（9）取得 key 的高 8 位 tophash：

top := tophash(hash)

（10）提前声明好的三个指针，用于指向存放 key-value 的空槽:

inserti：tophash 拟插入位置；

insertk：key 拟插入位置 ；

elem：val 拟插入位置；

var inserti *uint8
var insertk unsafe.Pointer
var elem unsafe.Pointer

（11）开启两层 for 循环，外层沿着桶链表依次遍历，内层依次遍历桶内的 key-value 对：

bucketloop:
    for {
        for i := uintptr(0); i < bucketCnt; i++ {
            // ...
        }
        ovf := b.overflow(t)
        if ovf == nil {
            break
        }
        b = ovf
     }

(12）倘若 key 的 tophash 和当前位置 tophash 不同，则会尝试将 inserti、insertk elem 调整指向首个空位，用于后续的插入操作.

倘若发现当前位置 tophash 标识为 emtpyRest（0），则说明当前桶链表后续位置都未空，无需继续遍历，直接 break 遍历流程即可.

if b.tophash[i] != top {
      if isEmpty(b.tophash[i]) && inserti == nil {
                    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
         }
}

倘若桶中某个位置的 tophash 标识为 emptyOne（1），说明当前位置未放入元素，倘若为 emptyRest（0），说明包括当前位置在内，此后的位置都为空.

const emptyRest = 0 
const emptyOne = 1 


func isEmpty(x uint8) bool {
    return x <= emptyOne
}

（13）倘若找到了相等的 key，则执行更新操作，并且直接跳转到方法的 done 标志位处，进行收尾处理；

k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
    if t.indirectkey() {
         k = *((*unsafe.Pointer)(k))
    }
    if !t.key.equal(key, k) {
        continue
    }
    elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
    goto done

（14）倘若没找到相等的 key，会在执行插入操作前，判断 map 是否需要开启扩容模式. 这部分内容在第 9 节中作展开.

倘若需要扩容，会在开启扩容模式后，跳转回 again 标志位，重新开始桶的定位以及遍历流程.

if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again 
    }

（15）倘若遍历完桶链表，都没有为当前待插入的 key-value 对找到空位，则会创建一个新的溢出桶，挂载在桶链表的尾部，并将 inserti、insertk、elem 指向溢出桶的首个空位：

if inserti == nil {
        newb := h.newoverflow(t, b)
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        elem = add(insertk, bucketCnt*uintptr(t.keysize))
    }

10.溢出桶

11.删除数据流程

 (1).步骤

  • map 删除 kv 对流程主要分为以下几步：
  • （1）根据 key 取 hash 值；
  • （2）根据 hash 值对桶数组取模，确定所在的桶；
  • （3）倘若 map 处于扩容，则迁移命中的桶，帮助推进渐进式扩容；
  • （4）沿着桶链表依次遍历各个桶内的 key-value 对；
  • （5）倘若命中相同的 key，删除对应的 key-value 对；并将当前位置的 tophash 置为 emptyOne，表示为空；
  • （6）倘若当前位置为末位，或者下一个位置的 tophash 为 emptyRest，则沿当前位置向前遍历，将毗邻的 emptyOne 统一更新为 emptyRest.

(2).mapdelete

map 删操作最终会走进 runtime/map.go 的 mapdelete 方法中

12.遍历流程

map 的遍历流程首先会走进 runtime/map.go 的 mapiterinit() 方法当中，初始化用于遍历的迭代器 hiter；接着会调用 runtime/map.go 的 mapiternext() 方法开启遍历流程

13.何时扩容

通过下面判断何时扩容:

  • （1）只有 map 的写流程可能开启扩容模式；
  • （2）写 map 新插入 key-value 对之前，会发起是否需要扩容的逻辑判断
  • （3）根据 hmap 的 oldbuckets 是否空，可以判断 map 此前是否已开启扩容模式
  • （4）倘若此前未进入扩容模式，且 map 中 key-value 对的数量超过 8 个，且大于桶数组长度的 6.5 倍，则进入增量扩容
  • （5）倘若溢出桶的数量大于 2^B 个（即桶数组的长度；B 大于 15 时取15），则进入等量扩容

如何开启扩容模式

开启扩容模式的方法位于 runtime/map.go 的 hashGrow 方法中

扩容规则

增量扩容

  • （1）在等量扩容中，新桶数组长度与原桶数组相同；
  • （2）key-value 对在新桶数组和老桶数组的中的索引号保持一致；
  • （3）在增量扩容中，新桶数组长度为原桶数组的两倍；
  • （4）把新桶数组中桶号对应于老桶数组的区域称为 x 区域，新扩展的区域称为 y 区域.
  • （5）实际上，一个 key 属于哪个桶，取决于其 hash 值对桶数组长度取模得到的结果，因此依赖于其低位的 hash 值结果.；
  • （6）在增量扩容流程中，新桶数组的长度会扩展一位，假定 key 原本从属的桶号为 i，则在新桶数组中从属的桶号只可能是 i （x 区域）或者 i + 老桶数组长度（y 区域）；
  • （7）当 key 低位 hash 值向左扩展一位的 bit 位为 0，则应该迁往 x 区域的 i 位置；倘若该 bit 位为 1，应该迁往 y 区域对应的 i + 老桶数组长度的位置
 渐进式扩容

map 采用的是渐进扩容的方式，避免因为一次性的全量数据迁移引发性能抖动

当每次触发写、删操作时，会为处于扩容流程中的map完成两组桶的数据迁移：

  • （1）一组桶是当前写、删操作所命中的桶
  • （2）另一组桶是，当前未迁移的桶中，索引最小的那个桶
func growWork(t *maptype, h *hmap, bucket uintptr) {
    // make sure we evacuate the oldbucket corresponding
    // to the bucket we're about to use
    evacuate(t, h, bucket&h.oldbucketmask())


    // evacuate one more oldbucket to make progress on growing
    if h.growing() {
        evacuate(t, h, h.nevacuate)
    }
}

参考: Golang map 实现原理

[上一节][go学习笔记.第八章.排序和查找] 3.二维数组练习

[下一节][go学习笔记.第九章.map] 2.map的切片,排序以及注意事项 

# 学习 # golang
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

AI视频特效转场教程：用Nano Banana和Kling 2.1创造病毒式传播效果

avatar 2048 AI社区
cover

结合AI大模型的本地知识库搭建方法总结，大模型入门到精通，收藏这篇就足够了！

avatar 2048 AI社区

Paint API之—— Xfermode与PorterDuff详解(三)

本文详解Android中PorterDuff的18种混合模式，包括ADD、CLEAR、DARKEN等，通过公式解析Alpha通道和颜色通道的计算方式。每种模式都配有组合逻辑、处理方式和效果示例说明，如ADD模式会使颜色叠加变亮，CLEAR模式会完全透明化等。文中还提供了与WebView、Socket集成的实战场景，帮助开发者系统掌握PorterDuff混合模式的应用。

avatar 2048 AI社区