😥 整理不易,此资源只针对正式星主开放,
还请入驻星球后再来观看。

GOLANG ROADMAP

阅读模式

  • 沉浸
  • 自动
  • 日常
首页
Go友会
  • 城市
  • 校园
Go学院
  • Go小课
  • Go小考
  • Go实战
  • 精品课
Go求职
  • 求职辅导🔥
  • Offer收割社群
  • 企业题库
  • 面试宝典
Go宝典
  • 在线宝典
  • B站精选
  • 推荐图书
  • 每日博文
Go仓库
实验区
  • Go周边
  • Go下载
  • Go月刊
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
author-avatar

GOLANG ROADMAP


首页
Go友会
  • 城市
  • 校园
Go学院
  • Go小课
  • Go小考
  • Go实战
  • 精品课
Go求职
  • 求职辅导🔥
  • Offer收割社群
  • 企业题库
  • 面试宝典
Go宝典
  • 在线宝典
  • B站精选
  • 推荐图书
  • 每日博文
Go仓库
实验区
  • Go周边
  • Go下载
  • Go月刊
消息
更多
  • 用户中心

    • 我的信息
    • 推广返利
  • 玩转星球

    • 星球介绍
    • 角色体系
    • 星主权益
  • 支持与服务

    • 联系星主
    • 成长记录
    • 常见问题
    • 吐槽专区
  • 合作交流

    • 渠道合作
    • 课程入驻
    • 友情链接
  • Go真实面试题汇总系列

    • 《Map篇》
  • 宝典内容

    • 33. 如何实现一个线程安全的 map?
    • 35. Go map 的底层实现 ?
    • 37. map的key可以是哪些类型?可以嵌套map吗?
    • 39. 讲一下set的原理,Java 的HashMap和 go 的map底层原理
    • 53. go的map是线程安全的吗?
    • 87. go map并发安全问题,如何解决
    • 150. map遍历的时候每次顺序都是固定的吗?为什么?
    • 159. go的sync.Map了解吗
    • 166. golang中两个map对象如何比较。
    • 206. map如何顺序读取?
    • 227. gomap结构,并发安全否
    • 231. go的hashmap如何实现的
    • 243. go 的 map 与 sync.map
    • 250. sync.map与map的区别
    • 255. Go map的底层原理
    • 265. Map是线程安全的吗?怎么解决并发安全问题?
    • 266. sync.Map 怎么解决线程安全问题?看过源码吗?
    • 272. 问了sync.Map(我说我对sync.Pool比较熟,就说Pool了)
    • 278. map什么内容不能为key
    • 279. map和sync.Map
    • 287. 说一说go中的map
    • 288. map的优缺点,以及改进?
    • 290. go中的map?分段锁拆了几个分片?
    • 345. 借助额外的数据结构比如slice等,对key进行排序,遍历slice得到顺序输出
    • 351. go的map的底层数据结构,查询复杂度
    • 397. Go一般怎么取map?
    • 398.如果一个map没申请空间,去向里面取值,会发生什么情况
    • 401. go中如何使遍历map变得有序
    • 427. map取一个key,然后修改这个值,原map数据的值会不会变化,根据map存储的类型回答
    • 432. 实现map的方法除了哈希还有哪些?
    • 468. go map slice 实现(内存泄漏分析)

😥 整理不易,此资源只针对正式星主开放,
还请入驻星球后再来观看。

35. Go map 的底层实现 ?


企业题库解析小组

题目序号:(67,94,6832,2995,858,1036,1048,1380,1507,1859)

题目来源:好未来、小米、腾讯、小米、滴滴、腾讯、字节跳动、畅天游

频次:13

答案1:(栾龙生)

Go语言的map使用Hash表和搜索树作为底层实现,一个Hash表可以有多个bucket,而每个bucket保存了map中的一个或一组键值对。

源码:runtime/map.go:hmap

// go 1.17
type hmap struct {
    count      int            //元素个数,调用len(map)时直接返回
    flags      uint8          //标志map当前状态,正在删除元素、添加元素.....
    B          uint8          //单元(buckets)的对数 B=5表示能容纳32个元素
    noverflow  uint16        //单元(buckets)溢出数量,如果一个单元能存8个key,此时存储了9个,溢出了,就需要再增加一个单元
    hash0      uint32         //哈希种子
    buckets    unsafe.Pointer //指向单元(buckets)数组,大小为2^B,可以为nil
    oldbuckets unsafe.Pointer //扩容的时候,buckets长度会是oldbuckets的两倍
    nevacute   uintptr        //指示扩容进度,小于此buckets迁移完成
    extra      *mapextra      //与gc相关 可选字段
}
1
2
3
4
5
6
7
8
9
10
11
12

下图展示了一个拥有4个bucket的map。

image-20220403085916040

本例中,hmap.B=2,hmap.buckets数组的长度是4 (2^B^)。元素经过Hash运算后会落到某个bucket中进行存储。

bucket的数据结构

数据结构源码:runtime/map.go/bmap

// A bucket for a Go map.
type bmap struct {
	tophash [bucketCnt]uint8
}
//实际上编译期间会生成一个新的数据结构
type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}
1
2
3
4
5
6
7
8
9
10
11
12

bmp也就是bucket,由初始化的结构体可知,里面最多存8个key,每个key落在桶的位置有hash出来的结果的高8位决定。

其中tophash是一个长度为8的整型数组,Hash值相同的键存入当前bucket时会将Hash值的高位存储在该数组中,以便后续匹配。

整体图如下

image-20220403092625292

答案2:(小小)

底层结构

Map 底层是由hmap和bmap两个结构体实现的。

// A header for a Go map.
type hmap struct {
    // 元素个数,调用 len(map) 时,直接返回此值
	count     int
	flags     uint8
	// buckets 的对数 log_2
	B         uint8
	// overflow 的 bucket 近似数
	noverflow uint16
	// 计算 key 的哈希的时候会传入哈希函数
	hash0     uint32
    // 指向 buckets 数组,大小为 2^B
    // 如果元素个数为0,就为 nil
	buckets    unsafe.Pointer
	// 扩容的时候,buckets 长度会是 oldbuckets 的两倍
	oldbuckets unsafe.Pointer
	// 指示扩容进度,小于此地址的 buckets 迁移完成
	nevacuate  uintptr
	extra *mapextra // optional fields
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

其中,B是buckets数组的长度的对数,也就是说buckets数组的长度就是2^B。buckets里面存储了 key 和 value,后面会再讲。buckets指向bmap结构体:

type bmap struct {
	tophash [bucketCnt]uint8
}
1
2
3

编译期间bmap会变成一个新的结构:

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}
1
2
3
4
5
6
7

bmap被称之为“桶”。一个桶里面会最多装 8 个 key,key 经过哈希计算后,哈希结果是“一类”的将会落入到同一个桶中。在桶内,会根据key计算出来的hash值的高 8 位来决定key到底落入桶内的哪个位置。注:一个桶内最多有8个位置。 这也是为什么map无法使用cap()来求容量的关键原因:map的容量是编译器进行计算后得出的一个结果,由于桶的存在,map在内存中实际存放的大小不一定同make出来后的map的大小一致。 有一点需要注意:当map的key和value都不是指针,并且size都小于 128 字节的情况下,会把 bmap标记为不含指针,这样可以避免gc时扫描整个hmap。尽管如此,但如图所示,bmap是有一个overflow的字段,该字段是指针类型,这就破坏了bmap不含指针的设想,这时会把overflow移动到extra字段来。

type mapextra struct {
	// overflow[0] contains overflow buckets for hmap.buckets.
	// overflow[1] contains overflow buckets for hmap.oldbuckets.
	overflow [2]*[]*bmap

	// nextOverflow 包含空闲的 overflow bucket,这是预分配的 bucket
	nextOverflow *bmap
}
1
2
3
4
5
6
7
8

参考文章 (opens new window)