美文网首页
Go 源码之 Map

Go 源码之 Map

作者: 五岁小孩 | 来源:发表于2024-03-24 18:41 被阅读0次

go源码之map - Jxy 博客

一、简介

map 是一种非常常见的数据类型,它可以用于快速地检索数据;是一种 key-value 结构的数据类型,key 是唯一的,value 可以重复
●键值对为元素的数据集合
●查询时间复杂度 O (1),最坏情况下 O (N) ,需要遍历溢出桶
●核心 hmap 和 buckets 数组(bmap) 两个结构实现,bmap 存储了八个元素
●map 读写:通过 hmap 中的 hash0 计算 key 的哈希结果:
○根据哈希值的低 8 位确定 key 所在的 buckets 数组中的位置
○根据哈希值的高 8 位 tophash(高八位)找到 bmap 中 key 和 value 数组中的位置
●map 只能用 len() 不能用 cap(),创建 map 不能指定 len,只能指定 cap,并且 cap 不是实际容量,底层根据 cap 算出实际桶(bmap)数量
●键不重复 并且 键必须可哈希(int / bool / float / string / array / 指针类型),slice / struct / interface / map 等引用类型不可哈希

image.png
image.png
image.png

二、源码

/usr/local/go/src/runtime/map.go

(一)数据结构

hmap


type hmap struct {
    count     int                    // map中元素的个数
    flags     uint8                  // Map 的状态标志位,包括迭代器状态和是否是引用类型
                                     // flag的一些状态位
                                     // iterator     = 1 // 有遍历器在遍历桶
                                     // oldIterator  = 2 // 有遍历器在遍历旧桶
                                     // hashWriting  = 4 // 有协程在写map
                                     // sameSizeGrow = 8 // 等量扩容,但不是两倍扩容,而是等量扩容
                                     
    B         uint8                  // bucket 数组的大小,即2^B个bmap
    noverflow uint16                 // 溢出 bucket 的数量,即产生 hash 冲突的 bucket 数量
    hash0     uint32                 // Map 中的哈希种子,用于 hash 函数

    buckets    unsafe.Pointer        // 指向bucket数组的指针,bucket数组可能会在扩容时被重新分配.
    oldbuckets unsafe.Pointer        // 表示先前的 bucket 数组的指针,用于 Map 扩容时进行转移元素的操作
    nevacuate  uintptr               // 表示当前正在进行 Map 扩容时的进度计数器,少于这个数字的buckets都会被回收

    extra *mapextra                  // 表示与 Map 相关的额外信息,包括 溢出桶 信息
}

type mapextra struct {
   overflow    *[]*bmap         // 存放的所有溢出桶的地址。
   oldoverflow *[]*bmap         // 存放的所有老的溢出桶的地址。这个是针对扩容的时候
   nextOverflow *bmap           // 指向的下一个溢出桶的地址。
}

bmap

// 源码中结构
type bmap struct {
    tophash [bucketCnt]uint8
}
// 实际编译后运行时bucket结构
type bmap struct {
  tophash  [8]uint8         // 存储hash值的前几位,如果小于5,则表示上述的tophash状态码
  
  keys     [8]keytype       // key数组,隐藏字段
  values   [8]valuetype     // value数组,隐藏字段
  overflow uintptr          // 溢出buceket指针,隐藏字段
}

(二)创建

// 初始化一个可容纳 10 个元素的map,但不是桶的数量
info = make(map[string]string,10)
底层调用 makemap

● 校验
● 创建一个hmap结构体对象
● 生成一个哈希因子hash0 并赋值到hmap对象中(用于后续为key创建哈希值)
● 根据 hint=10,并根据算法规则来创建 B,当前 B 应该为 1

  • hint B
  • 0~8 0
  • 9~13 1
  • 14~26 2
  • ...
    ● 第四步:根据B去创建去创建桶(bmap对象)并存放在buckets数组中,当前bmap的数量应为2.
  • 当B<4时,根据B创建桶的个数的规则为:2^B(标准桶)
  • 当B>=4时,根据B创建桶的个数的规则为:2^B + 2^{B-4}(标准桶+溢出桶)
    注意:每个bmap中可以存储8个键值对,当不够存储时需要使用溢出桶,并将当前bmap中的overflow字段指向溢出桶的位置。
// hint 也就是创建 map 时指定的容量,根据 hint 计算出 B,然后创建 2^B 个桶
func makemap(t *maptype, hint int, h *hmap) *hmap {
  -------------------- 内存溢出校验 -------------------- 
    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
    if overflow || mem > maxAlloc {
        hint = 0
    }
    --------------------  初始化一个hmap,如果h为nil则重新初始化 -------------------- 
    if h == nil {
        h = new(hmap)
    }
    -------------------- 生成哈希种子 -------------------- 
    h.hash0 = fastrand()
    -------------------- 根据 hint 初始化B的大小 -------------------- 
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B

    -------------------- 根据 B 创建 bmap 和 溢出桶 nextOverflow -------------------- 
    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
}

(三)新增

var info=make(map[string]string)
info["name"] = "xj"
底层调用 mapassign

● 校验
● 根据哈希因子 hash0 计算 key 的哈希值; 如计算 name 哈希结果:011011100011111110111011011
● 根据一定条件判断是否进行 扩容 、迁移 操作,也就是 rehash
● 根据哈希值的后 B 位的值来决定将此键值对存放到那个桶中(bmap),实际上计算出来的是 buckets 的下标:
将哈希值和桶掩码(B个为1的二进制)进行 & 运算,最终得到哈希值的后B位的值。假设当B为1时,其结果为 0 :
哈希值:011011100011111110111011010
桶掩码:000000000000000000000000001
结果: 000000000000000000000000000 = 0
通过示例你会发现,找桶的原则实际上是根据后B为的位运算计算出 索引位置,然后再去buckets数组中根据索引找到目标桶(bmap)
● 确定 bmap 之后,将 tophash、key、value分别写入到桶中的三个数组中,后续会根据 tophash 比较相同则再去比较key
● 如果桶已满,则通过 overflow 找到溢出桶,并在溢出桶中继续写入
● hmap的个数count++(map中的元素个数+1)

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 值 -------------------- 
    hash := t.hasher(key, uintptr(h.hash0))
    h.flags ^= hashWriting                                          // 标记为正在写

again:
    bucket := hash & bucketMask(h.B)
    -------------------- 根据一定条件判断是否需要扩容 -------------------- 
    if h.growing() {
        growWork(t, h, bucket)
    }
    -------- 根据哈希值的后 B 位的值对应 buckets 数组的下标,然后将 tophash、key、value 写入 bmap 中 --------- 
    -------- 如果桶已满,则通过 overflow 找到溢出桶,并在溢出桶中继续写入    -------- 
    ................
    
    -------------------- hmap的个数count++  -------------------- 
    h.count++

    return elem
}

(四)查询

var name=info["name"] 

● 校验
● 根据哈希因子 hash0 计算 key 的哈希值; 如计算 name 哈希结果:011011100011111110111011011
● 根据哈希值的后 B 位的值来决定将此键值对存放到那个桶中(bmap),实际上计算出来的是 buckets 的下标
● 确定 bmap 后,再根据 key 的哈希值计算 出tophash(高 8 位),快速比较 tophash 确定元素下标,然后再去 key 和 value 中 获取元素
● 当前桶如果没找到,则根据 overflow 再去溢出桶中找,均未找到则表示 key 不存在

(五)扩容

在向 map 中添加数据时,当达到某个条件,则会引发 map 扩容,调用 h.growing() 判断,执行 growWork() 扩容:
● 翻倍扩容:map中数据总个数 / 桶个数 > 6.5
● 等量扩容:使用了太多的溢出桶时(溢出桶使用的太多会导致map处理速度降低)

  • B <=15,已使用的溢出桶个数 >= 2^B 时,引发等量扩容
  • B > 15,已使用的溢出桶个数 >= 2^{15} 时,引发等量扩容
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)
    ...
}

扩容后
● B会根据扩容后新桶的个数进行增加(翻倍扩容新B=旧B+1,等量扩容 新B=旧B)
● oldbuckets指向原来的桶(旧桶)
● buckets指向新创建的桶(新桶中暂时还没有数据)
● nevacuate设置为0,表示如果数据迁移的话,应该从原桶(旧桶)中的第0个位置开始迁移
● noverflow设置为0,扩容后新桶中已使用的溢出桶为0
● extra.oldoverflow设置为原桶(旧桶)已使用的所有溢出桶。即:h.extra.oldoverflow = h.extra.overflow
● extra.overflow设置为nil,因为新桶中还未使用溢出桶
● extra.nextOverflow设置为新创建的桶中的第一个溢出桶的位置。

image.png

(六)迁移 rehash

增量式 rehash 的策略:
● 将新数组的容量设置为旧数组的两倍或一半,并且将哈希表的增量计数器加一
● 在对哈希表进行操作时,如果发现增量计数器的值达到了一个阈值,就会开始进行增量式 rehash 操作,将一部分元素从旧数组中复制到新数组中,并且重新计算这些元素的哈希值
● 在完成一次增量式 rehash 操作后,会将哈希表的增量计数器清零。
通过增量式 rehash 的策略,Go 标准库中的哈希表实现可以在保证较短的 rehash 时间的同时,避免一次性处理过多元素导致性能下降。
rehash 操作会创建一个新的哈希表,同时保留旧的哈希表不变。然后,它会依次遍历旧哈希表中的每个桶,将桶中的所有键值对复制到新哈希表中对应的桶中。在遍历每个桶时,如果桶中的元素已经被删除,则跳过这些元素。
当遍历到一个桶时,Map 实现会首先获取旧哈希表中该桶的互斥锁,以确保在复制元素时不会有并发访问的问题。然后,它会遍历桶中的所有键值对,对于每个键值对,它会计算键在新哈希表中的位置,并将键值对插入到对应的桶中。插入过程中,如果新哈希表中对应的桶已经存在元素,则会将新元素插入到该桶的链表的尾部。
在整个 rehash 过程中,新哈希表会保持为空,直到所有元素都被复制完毕。复制完成后,Map 实现会用新哈希表替换旧哈希表,并释放旧哈希表占用的内存空间。这样,Map 中的所有元素都被迁移到了新哈希表中。

翻倍扩容
如果是翻倍扩容,那么迁移规就是将旧桶中的数据分流至新的两个桶中(比例不定),并且桶编号的位置为:同编号位置 和 翻倍后对应编号位置。

等量扩容
如果是等量扩容(溢出桶太多引发的扩容),那么数据迁移机制就会比较简单,就是将旧桶(含溢出桶)中的值迁移到新桶中。
这种扩容和迁移的意义在于:当溢出桶比较多而每个桶中的数据又不多时,可以通过等量扩容和迁移让数据更紧凑,从而减少溢出桶

三、常见问题

1.bmap 的数量为什么是 2^B 次方?
方便位运算,bitmap

2.为什么要进行等量扩容?
让元素更加紧凑,刚好利用内存,比如 map 中有 1000 个 元素,但是可能存在一些删除的元素,应该将溢出桶的元素迁移到删除的元素的位置

3.bmap 中的 tophash 是什么有什么作用?
tophash 是 key 哈希值的高八位,主要用来快速比较两个键是否相同
比如现在 插入 key name ,则在确定桶之后, 获取 name 的哈希值的高八位和 bmap 中的 tophash 快速判断比较 key 是否存在,存在的下标
从而到 key 和 value 数组中根据下标获取数据,
不直接比较 key 是因为 key 可能会很大,tophash 比较会快速很多

4.map 的 value 为什么不可寻址?
key 通过 hash 算出具体的 bucket,然后将 key 和 value 复制 到 bucket,不是指针引用,所以不可寻址,
如果用指针寻址的话,在扩容迁移时, map 进行了扩容或者重新分配内存,原来的指针地址无效,发送程序错误,因此设计为不可寻址

5.map 是如何解决哈希冲突的?
哈希冲突碰撞:多个 key 的 hash 结果一致,hash 到同一个 bucket,解决方法:
● 链表法: 将一个 bucket 实现成一个链表,落在同一个 bucket 中的 key 都会插入这个链表
● 开放寻址法: 则是碰撞发生后,通过一定的规律,在数组的后面挑选“空位”,用来放置新的 key
go map 采用的是 链表法,使用 溢出桶 来存放 相同 hash 结果的 value

6.为什么 map 是无序的?
● hash 结果本身就是无序的
● map 扩容之后,key 会发生迁移
● map底层在遍历的时候也是无序遍历的,并不是从第一个桶开始依次遍历

7.map 使用时需要注意哪些问题?
● key 必须是可比较的类型,如整数、字符串和指针等,但是切片、函数和结构体等类型是不可比较的,因此不能用作键
● Map 中的元素是无序的
● 如果使用未初始化的 Map,会导致运行时错误。需要使用 make() 函数来初始化 Map。
● Map 在并发环境下不是安全的

8.map 是如何进行扩容的?
● 当 Map 中的元素数量超过了负载因子(load factor)和哈希表容量的乘积时,map 就会触发扩容操作。在 Go 中,负载因子默认为 6.5。
● Go Map 在扩容时会创建一个新的哈希表,一次性(非渐进式)将原来的键值对重新散列到新的哈希表中。为了减少哈希冲突,新哈希表的容量是原来的两倍,并且容量一定是 2 的幂次方。
● 在重新散列过程中,Go Map 会根据哈希值将原来的键值对分配到新哈希表中的对应位置上。如果两个键值对的哈希值相同,会使用链式哈希表(chained hash table)的方式进行处理,将它们放在同一个桶(bucket)中。
● 一旦所有的键值对都已经重新散列到新的哈希表中,Go Map 就会将原来的哈希表释放掉,将新的哈希表作为 Map 的内部存储结构。
注意: 由于扩容操作可能会导致大量的重新散列操作,因此在扩容时可能会造成一定的性能影响。为了避免频繁扩容,可以在创建 Map 时指定一个较大的容量,或者手动调用 runtime.GC() 来触发垃圾回收操作,以释放未使用的内存。

9.map 的 panic 能被 recover 吗?
● 不能,直接抛出 throw("concurrent map read and map write")

10.并发使用 map 除了加锁还有其他方案吗?
多读少写的情况,建议使用 sync.Map

11.sync.Map 和加锁有什么区别?
● 不需要显式的加锁/解锁
● 降低锁的粒度,适用 多读少写 场景,读是原子操作,不需要加锁

12.Map 的查询时间复杂度?
正常情况下是 O (1),极端情况下,也就是哈希冲突碰撞严重情况下:O (N),需要遍历溢出桶

13.Map Rehash 的策略是怎样的?什么时机会发生 Rehash?
rehash 也就是 扩容、迁移;在 map 元素达到一定条件的情况下,发生扩容操作:

image.png
rehash 的策略:增量式 rehash,在新增 key 的情况下逐步将 oldbuckets 元素迁移到 buckets

14.Map rehash 具体会影响什么?哈希结果会受到什么影响?
只会影响 key 在 map 中的存储位置,不会改变哈希结果

15.Map Rehash 过程中存放在旧桶的元素如何迁移?
在 新增 key 时 逐步增量迁移

参考资料

Go Map 的 11 连问,你顶得了嘛? - 掘金 (juejin.cn)

有劳各位看官 点赞、关注➕收藏,你们的支持是我最大的动力!!!
接下来会不断更新 golang 的一些底层源码(个人见解)!!!
同时也欢迎大家在评论区提问、分享您的经验和见解!!!

下一期:【 Go 源码之 sync.Map】

相关文章

  • 文章目录

    Go 源码解读篇 《Go源码解读篇》之常见数据结构(list) 《Go源码解读篇》之 Error 工作中知识总结 ...

  • 【go笔记】map结构的简介

    go的hashtable是用map实现。今天简单的整理了map的结构。 1.map的结构 hmap 在源码中, m...

  • 第03天(复合类型)_map的基本使用

    24_map的基本使用.go 25_map赋值.go 26_map遍历.go 27_map删除.go 28_map...

  • 10.map

    Go语言基础之map | Golang Go语言中提供的映射关系容器为map,其内部使用散列表(hash)实现。 ...

  • go之map

    map map是啥?怎么用?这两个问题搞不清楚的,不用往下看了,先弄清楚再说 源码 先看看参考资料深度解密Go语言...

  • 图解Go的unsafe.Pointer

    相信看过Go源码的同学已经对unsafe.Pointer非常的眼熟,因为这个类型可以说在源码中是随处可见:map、...

  • Map

    常见操作:http://www.runoob.com/go/go-map.html 创建Map 赋值 遍历Map ...

  • Go-Map源码解读

    前言 一般的map都是采用数组+链表的数据结构去进行数据存储,在单节点挂载数据过多时,会考虑将链表转换成树结构来提...

  • go源码解析之TCP连接(三)——Read

    go源码解析之TCP连接系列基于go源码1.16.5* 网络数据读取 上一章我们通过跟踪TCPListener的A...

  • go源码解析之TCP连接(四)——Write

    go源码解析之TCP连接系列基于go源码1.16.5 网络数据发送 上一章我们通过跟踪TCPConn的Read方法...

网友评论

      本文标题:Go 源码之 Map

      本文链接:https://www.haomeiwen.com/subject/werltjtx.html