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

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 实现(内存泄漏分析)

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

351. go的map的底层数据结构,查询复杂度


企业题库解析小组

题目序号:(5328)

题目来源:金山

频次:1

答案1:(Kjj)

map底层数据结构:

map底层数据结构前文已经整理过了,这里不做赘述。

查询复杂度:

空间复杂度:

​ 首先我们不考虑因删除大量元素导致的空间浪费情况(这种情况现在go是留给程序员自己解决),只考虑一个持续增长状态的map的一个空间使用率: ​ 由于溢出桶数量超过hash桶数量时会触发缩容,所以最坏的情况是数据被集中在一条链上,hash表基本是空的,这时空间浪费O(n)。 最好的情况下,数据均匀散列在hash表上,没有元素溢出,这时最好的空间复杂度就是扩散因子决定了,当前go的扩散因子由全局变量决定,即loadFactorNum/loadFactorDen = 6.5。即平均每个hash桶被分配到6.5个元素以上时,开始扩容。所以最小的空间浪费是(8-6.5)/8 = 0.1875,即O(0.1875n)

​ 结论:go map的空间复杂度(指除去正常存储元素所需空间之外的空间浪费)是O(0.1875n) ~ O(n)之间。 ​ 具体细节:https://blog.csdn.net/dongjijiaoxiangqu/article/details/109643025

时间复杂度:

go采用的hash算法应是很成熟的算法,极端情况暂不考虑。所以综合情况下go map的时间复杂度应为O(1)