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

GOLANG ROADMAP

阅读模式

  • 沉浸
  • 自动
  • 日常
首页
Go学习
  • Go学院

    • Go小课
    • Go小考
    • Go实战
    • 精品课
  • Go宝典

    • 在线宝典
    • B站精选
    • 推荐图书
    • 精品博文
  • Go开源

    • Go仓库
    • Go月刊
  • Go下载

    • 视频资源
    • 文档资源
Go求职
  • 求职服务

    • 内推互助
    • 求职助力
  • 求职刷题

    • 企业题库
    • 面试宝典
    • 求职面经
Go友会
  • 城市
  • 校园
推广返利 🤑
实验区
  • Go周边
消息
更多
  • 用户中心

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

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

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

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

GOLANG ROADMAP


首页
Go学习
  • Go学院

    • Go小课
    • Go小考
    • Go实战
    • 精品课
  • Go宝典

    • 在线宝典
    • B站精选
    • 推荐图书
    • 精品博文
  • Go开源

    • Go仓库
    • Go月刊
  • 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 实现(内存泄漏分析)

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

255. Go map的底层原理


企业题库解析小组

题目来源:腾讯

频次:高频

# 答案:树枝

这道题需要从两个维度来回答

  1. map的实现原理

    1. go map是基于hash table(哈希表)来实现的,冲突的解决采用拉链法
  2. map的底层结构

    1. hmap(哈希表):每个hmap内含有多个bmap(buckets(桶)、lodbuckets(旧桶)、overflow(溢出桶))可以这样理解,每个哈希表都是由多个桶组成的

      type hmap struct {
          count     int    //元素的个数
          flags     uint8  //状态标志
          B         uint8  //可以最多容纳 6.5 * 2 ^ B 个元素,6.5为装载因子
          noverflow uint16 //溢出的个数
          hash0     uint32 //哈希种子
      
          buckets    unsafe.Pointer //指向一个桶数组
          oldbuckets unsafe.Pointer //指向一个旧桶数组,用于扩容
          nevacuate  uintptr        //搬迁进度,小于nevacuate的已经搬迁
          overflow *[2]*[]*bmap     //指向溢出桶的指针
      }
      
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      • buckets:一个指针,指向一个bmap数组、存储多个桶。
      • oldbuckets: 是一个指针,指向一个bmap数组,存储多个旧桶,用于扩容。
      • overflow:overflow是一个指针,指向一个元素个数为2的数组,数组的类型是一个指针,指向一个slice,slice的元素是桶(bmap)的地址,这些桶都是溢出桶。为什么有两个?因为Go map在哈希冲突过多时,会发生扩容操作。[0]表示当前使用的溢出桶集合,[1]是在发生扩容时,保存了旧的溢出桶集合。overflow存在的意义在于防止溢出桶被gc。
    2. bmap(哈希桶): bmap是一个隶属于hmap的结构体,一个桶(bmap)可以存储8个键值对。如果有第9个键值对被分配到该桶,那就需要再创建一个桶,通过overflow指针将两个桶连接起来。在hmap中,多个bmap桶通过overflow指针相连,组成一个链表。

      type bmap struct {
          //元素hash值的高8位代表它在桶中的位置,如果tophash[0] < minTopHash,表示这个桶的搬迁状态
          tophash [bucketCnt]uint8
          //接下来是8个key、8个value,但是我们不能直接看到;为了优化对齐,go采用了key放在一起,value放在一起的存储方式,
          keys     [8]keytype   //key单独存储
      	values   [8]valuetype //value单独存储
      	pad      uintptr
      	overflow uintptr	  //指向溢出桶的指针
      }
      
      1
      2
      3
      4
      5
      6
      7
      8
      9
  • 答案:树枝