Golang 中 map 探究_ 字节跳动技术团队的博客-CSDN博客
Golang 中 map 探究
字节跳动技术团队
于 2022-08-12 12:00:38 发布
4664
收藏
文章标签：
java
python
golang
数据结构
go
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/ByteDanceTech/article/details/126314053
版权
动手点关注 干货不迷路 👆
简介
本文主要通过探究在golang 中map的数据结构及源码实现来学习和了解map的特性，共包含map的模型探究、存取、扩容等内容。欢迎大家共同讨论。
Map 的底层内存模型
在 golang 的源码中表示 map 的底层 struct 是 hmap，其是 hashmap 的缩写
type hmap struct {
   // map中存入元素的个数， golang中调用len(map)的时候直接返回该字段
   count     int
   // 状态标记位，通过与定义的枚举值进行&操作可以判断当前是否处于这种状态
   flags     uint8
   B         uint8  // 2^B 表示bucket的数量， B 表示取hash后多少位来做bucket的分组
   noverflow uint16 // overflow bucket 的数量的近似数
   hash0     uint32 // hash seed （hash 种子） 一般是一个素数
   buckets    unsafe.Pointer // 共有2^B个 bucket ，但是如果没有元素存入，这个字段可能为nil
   oldbuckets unsafe.Pointer // 在扩容期间，将旧的bucket数组放在这里， 新buckets会是这个的两倍大
   nevacuate  uintptr        // 表示已经完成扩容迁移的bucket的指针， 地址小于当前指针的bucket已经迁移完成
   extra *mapextra // optional fields
B 是 buckets 数组的长度的对数， 即 bucket 数组的长度是 2^B。bucket 的本质上是一个指针，指向了一片内存空间，其指向的 struct 如下所示：
// A bucket for a Go map.
type bmap struct {
   tophash [bucketCnt]uint8
但这只是表面(src/runtime/hashmap.go)的结构，编译期间会给它加料，动态地创建一个新的结构：
type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr        // 内存对齐使用，可能不需要
    overflow uintptr        // 当bucket 的8个key 存满了之后
bmap 就是我们常说的“桶”的底层数据结构， 一个桶中可以存放最多 8 个 key/value, map 使用 hash 函数 得到 hash 值决定分配到哪个桶， 然后又会根据 hash 值的高 8 位来寻找放在桶的哪个位置 具体的 map 的组成结构如下图所示：
Map 的存与取
在 map 中存与取本质上都是在进行一个工作， 那就是:
查询当前 k/v 应该存储的位置。赋值/取值， 所以我们理解了 map 中 key 的定位我们就理解了存取。
底层代码
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
    // map 为空，或者元素数为 0，直接返回未找到
    if h == nil || h.count == 0 {
        return unsafe.Pointer(&zeroVal[0]), false
    }
    // 不支持并发读写
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    // 根据hash 函数算出hash值，注意key的类型不同可能使用的hash函数也不同
    hash := t.hasher(key, uintptr(h.hash0))
    // 如果 B = 5，那么结果用二进制表示就是 11111 ， 返回的是B位全1的值
    m := bucketMask(h.B)
    // 根据hash的后B位，定位在bucket数组中的位置
    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
    // 当 h.oldbuckets 非空时，说明 map 发生了扩容
    // 这时候，新的 buckets 里可能还没有老的内容
    // 所以一定要在老的里面找，否则有可能发生“消失”的诡异现象
    if c := h.oldbuckets; c != nil {
        if !h.sameSizeGrow() {
            // 说明之前只有一半的 bucket，需要除 2
            m >>= 1
        }
        oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {
            b = oldb
        }
    }
    // tophash 取其高 8bit 的值
    top := tophash(hash)
    // 一个 bucket 在存储满 8 个元素后，就再也放不下了，这时候会创建新的 bucket，挂在原来的 bucket 的 overflow 指针成员上
    // 遍历当前bucket的所有链式bucket
    for ; b != nil; b = b.overflow(t) {
        // 在bucket的8个位置上查询
        for i := uintptr(0); i < bucketCnt; i++ {
            // 如果找到了相等的 tophash，那说明就是这个 bucket 了
            if b.tophash[i] != top {
                continue
            }
            // 根据内存结构定位key的位置
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey {
                k = *((*unsafe.Pointer)(k))
            }
            // 校验找到的key是否匹配
            if t.key.equal(key, k) {
                // 定位v的位置
                v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                if t.indirectvalue {
                    v = *((*unsafe.Pointer)(v))
                }
                return v, true
            }
        }
    }
    // 所有 bucket 都没有找到，返回零值和 false
    return unsafe.Pointer(&zeroVal[0]), false
寻址过程
Map 的扩容
在 golang 中 map 和 slice 一样都是在初始化时首先申请较小的内存空间，在 map 的不断存入的过程中，动态的进行扩容。扩容共有两种，增量扩容与等量扩容（重新排列并分配内存）。下面我们来了解一下扩容的触发方式：
负载因子超过阈值，源码里定义的阈值是 6.5。(触发增量扩容)overflow 的 bucket 数量过多：当 B 小于 15，也就是 bucket 总数 2^B 小于 2^15 时，如果 overflow 的 bucket 数量超过 2^B；当 B >= 15，也就是 bucket 总数 2^B 大于等于 2^15，如果 overflow 的 bucket 数量超过 2^15。（触发等量扩容）
第一种情况
第二种情况
Map 的有序性
先说结论，在 golang 中 map 是无序的，准确的说是无法严格保证顺序的， 从上面的源码中我们可以知道，golang 中 map 在扩容后，可能会将部分 key 移至新内存，由于在扩容搬移数据过程中，并未记录原数据位置， 并且在 golang 的数据结构中也并未保存数据的顺序，所以那么这一部分在扩容后实际上就已经是无序的了。
遍历的过程，其实就是按顺序遍历内存地址，同时按顺序遍历内存地址中的 key。但这时已经是无序的了。但是如果我就一个 map，我保证不会对 map 进行修改删除等操作，那么按理说没有扩容就不会发生改变。但也是因为这样，GO 才在源码中 但是有一个有趣的现象，就算不对 map 进行插入删除等操作致使其扩容，其在遍历过程中仍是无序的。
objMap := make(map[string]int)
for i := 0; i < 5; i++ {
   objMap[strconv.Itoa(i)] = i
for i := 0 ; i < 5; i ++ {
   var valStr1, valStr2 string
   for k, v := range objMap {
      fmt.Println(k)
      fmt.Println(v)
      valStr1 += k
   }
   for k, v := range objMap {
      fmt.Println(k)
      fmt.Println(v)
      valStr2 += k
   }
   fmt.Println(valStr1 == valStr2)
   if valStr1 != valStr2 {
      fmt.Println("not equal")
   }
fmt.Println("end")
以上的运行结果是
不难看出，即使不对 map 进行扩容，在多次遍历时也是无序的，这是因为 golang 官方在设计时故意加上随机的元素，将遍历 map 的顺序随机化，用来防止使用者用来顺序遍历。
依赖 map 的顺序进行遍历，这是有风险的代码，在 GO 的严格语法规则下，是坚决不提倡的。所以我们在使用 map 时一定要记得其是无序的，不要依赖其顺序。
Map 的并发
首先我们大家都知道，在 golang 中 map 并不是一个并发安全的数据结构，当几个 goruotine 同时对一个 map 进行读写操作时，就会出现并发写问题：fatal error: concurrent map writes。但是为什么 map 是不支持并发安全的呢， 主要是因为成本与效益。
官方答复原因如下：
典型使用场景：map 的典型使用场景是不需要从多个 goroutine 中进行安全访问。非典型场景（需要原子操作）：map 可能是一些更大的数据结构或已经同步的计算的一部分。
性能场景考虑：若是只是为少数程序增加安全性，导致 map 所有的操作都要处理 mutex，将会降低大多数程序的性能。同时 golang 提供了并发安全的 sync map。
， // 不支持并发读写
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
但是我们又有疑问了，为什么 golang map 并发冲突了不抛一个 error 出来，或者 panic 掉，而是要让程序 panic，选择让程序 crash 崩溃掉。这里是 golang 官方出于权衡风险和 map 使用复杂度场景考虑的，首先 map 在官方中就明确表示不支持并发读写， 所以并发对 map 进行读写操作本身就是不正确的。
场景假设一：如果 map 选择在写入或者读取时增加 error 返回值，会导致程序在使用 map 时就无法像现在一样，需要额外的捕获并判断 err。
场景假设二：如果 map 选择 panic（可被 recover），此时如果出现并发写入数据的场景，就会导致走进 recover 中，如果没有对这种场景进行特殊处理，就会导致 map 中存在脏数据，此时程序在使用 map 时就会引发不可预知的错误，此时排查起来也是很难找到问题的根因的。
所以 golang 在考虑了这些场景后，选择明确的抛出 crash 崩溃异常，使得风险被提前暴露。可以明确的定位到问题点。综上所述我们在使用 map 时，已经要严格保障其是在单线程内使用的，如果有多线程场景，建议使用 sync map 。
字节跳动技术团队
关注
关注
点赞
收藏
评论
Golang 中 map 探究
动手点关注干货不迷路????简介本文主要通过探究在golang 中map的数据结构及源码实现来学习和了解map的特性，共包含map的模型探究、存取、扩容等内容。欢迎大家共同讨论。Map 的底层内存模型在 golang 的源码中表示 map 的底层 struct 是 hmap，其是 hashmap 的缩写typehmapstruct{//map中存入元素的个...
复制链接
扫一扫
评论 2
您还未登录，请先
登录
后发表或查看评论
博客
字节跳动一站式数据治理思考及实践
12-14
202
动手点关注干货不迷路导读：今天的分享主要分四个部分：机遇与挑战、数据治理思路、技术架构演进以及未来展望1. 机遇与挑战数据治理工作有很多挑战，最主要的一点是落地比较困难。首先，治理工作中与业务有一定的矛盾。第二，治理涉及的组织和管理难度大。第三，规范“人”的动作难度大，治理过程中，需要依靠人来推进和执行，人员能力参差不起，组织文化、目标也存在不对齐的情况。第四，缺乏适配性强的产品工具。因为治理工作...
博客
火山引擎 RTC 助力抖音百万并发“云侃球”
12-07
623
动手点关注干货不迷路1. 背景及技术挑战从电视看直播到手机电脑看直播，直播技术的发展让观众可以随时、随地观看自己喜欢的比赛，并且在看比赛时通过发送表情、发文字进行互动。但表情、文字承载的信息量较小、沟通效率低，我们无法像线下一起看比赛那样和好友边看边聊、一起为精彩的比赛呐喊，观赛体验大打折扣。为了让观众获得更好的观赛体验，抖音在 2022 世界杯比赛直播中推出了“边看边聊”的玩法：每个观众都可以邀...
博客
字节跳动数据中台的 Data Catalog 系统搜索实践
11-21
777
动手点关注干货不迷路1. 背景Data Catalog 能够帮助大公司更好地梳理和管理自己的资产，是 Data-drvien 公司的重要平台。一个通用的 Data Catalog 平台通常包含元数据管理，搜索，血缘，标签，术语等功能。其中，搜索是 Data Catalog 的入口功能，承担着让用户“找到数”的主要能力。在字节跳动数据中台的 Data Catalog 系统中，每天有 70% 以上的用...
博客
火山引擎 RTC 视频性能降级策略解析
11-16
445
动手点关注干货不迷路1. 背景随着 RTC 使用场景的不断复杂化，新特性不断增多，同时用户对清晰度提升的诉求也越来越强烈，这些都对客户端机器性能提出了越来越高的要求 (越来越高的分辨率，越来越复杂的编码器等)。但机器性能差异千差万别，同时用户的操作也不可预知，高级特性的使用和机器性能的矛盾客观存在。当用户机器负载过高时，我们需要适当降级视频特性来减轻系统复杂性，确保重要功能正常使用，提升用户体验...
博客
火山引擎工具技术分享：用 AI 完成数据挖掘，零门槛完成 SQL 撰写
11-14
413
动手点关注干货不迷路在使用 BI 工具的时候，经常遇到的问题是：“不会 SQL 怎么生产加工数据、不会算法可不可以做挖掘分析？”而专业算法团队在做数据挖掘时，数据分析及可视化也会呈现相对割裂的现象。流程化完成算法建模和数据分析工作，也是一个提效的好办法。同时，对于专业数仓团队来说，相同主题的数据内容面临“重复建设，使用和管理时相对分散”的问题——究竟有没有办法在一个任务里同时生产，同主题不同内容的...
博客
大规模分布式链路分析计算在字节跳动的实践
11-07
1025
动手点关注干货不迷路1. 综述微服务架构的快速发展使得分布式链路追踪系统成为观测体系中越来越重要的组件。字节跳动的分布式链路追踪系统经历了数年的发展后，已覆盖了字节的绝大部分在线业务，完成了对数万微服务和数百万微服务实例的在线链路追踪。在经典的指标观测分析和单请求链路追踪的基础上，如何从浩瀚如海的分布式链路数据中进一步挖掘出更高层次的信息，为业务的架构优化、服务治理、成本优化等场景提供更高效的数据...
博客
深度解析字节跳动开源数据集成引擎 BitSail
11-01
976
动手点关注干货不迷路1. 导读BitSail 是字节跳动开源数据集成引擎，支持多种异构数据源间的数据同步，并提供离线、实时、全量、增量场景下全域数据集成解决方案，目前支撑了字节内部和火山引擎多个客户的数据集成需求。经过字节跳动各大业务线海量数据的考验，在性能、稳定性上得到较好验证。10 月 26 日，字节跳动宣布 BitSail 项目正式在 GitHub 开源，为更多的企业和开发者带来便利，降低数...
博客
一文了解 DataLeap 中的 Notebook
10-27
1856
动手点关注干货不迷路一、概述Notebook 是一种支持 REPL 模式的开发环境。所谓「REPL」，即「读取-求值-输出」循环：输入一段代码，立刻得到相应的结果，并继续等待下一次输入。它通常使得探索性的开发和调试更加便捷。在 Notebook 环境，你可以交互式地在其中编写你的代码、运行代码、查看输出、可视化数据并查看结果，使用起来非常灵活。在数据开发领域，Notebook 广泛应用于数据清理和...
博客
火山引擎 RTC 全球化架构设计
10-24
1072
动手点关注干货不迷路1. 为什么 RTC 要做全球化RTC（Real Time Communication）是音视频基础设施，它已经融入了大家生活的方方面面：工作中，我们组织视频会议，即使团队成员身处异国，也能保证项目推进；休息时，我们打开抖音，看主播直播连麦；来一局游戏时，我们打开小队语音，大杀四方；学习时，我们相聚线上互动课堂，知识传播不再受距离的桎梏。RTC 拉近了大家的距离，丰富了大家的生...
博客
Spark AQE SkewedJoin 在字节跳动的实践和优化
10-12
1768
动手点关注干货不迷路1. 概述本文将首先介绍 Spark AQE SkewedJoin 的基本原理以及字节跳动在使用 AQE SkewedJoin 的实践中遇到的一些问题；其次介绍针对遇到的问题所做的相关优化和功能增强，以及相关优化在字节跳动的收益；此外，我们还将分享 SkewedJoin 的使用经验。2. 背景首先对 Spark AQE SkewedJoin 做一个简单的介绍。Spark Ada...
博客
深入理解 Android Studio Sync 流程
10-10
1958
动手点关注干货不迷路1. 初识 Sync我们一般会把 Sync 理解为 Android Studio 的准备阶段，包括解析工程配置信息、下载远程依赖到本地、更新代码索引等准备工作，当修改 gradle build 文件后，需要重新 Sync 将 Gradle 构建配置信息同步到 IDE，进而使 IDE 的功能及时应用新的构建配置，这些功能包括项目的 Gradle Task 列表展示、依赖信息展示等...
博客
火山引擎 RTC 自研音频编码器 NICO 实践之路
09-30
1683
动手点关注干货不迷路1. 前言随着互联网技术的不断发展，越来越多的人开始尝试使用或者依赖实时音视频产品解决团队沟通与协作问题。在通话过程中，我们时常会遇到因为网络波动（如拥塞、丢包、延时和抖动等）而导致的音频卡顿、掉字或者杂音等问题，影响工作效率。为解决此类音频弱网问题，业界一般采用前向纠错（Forward Error Correction，FEC）或者重传等网络策略优化方法，但这些方法存在冗余率...
博客
prompt 综述
09-28
1365
动手点关注干货不迷路1. 概述1.1 基本概念用一句话概括模板学习，即将原本的输入文本填入一个带有输入和输出槽位的模板，然后利用预训练语言模型预测整个句子，最终可以利用这个完整的句子导出最终需要的答案。模板学习最吸引人的关键在于其通过已有的预训练模型，定义合适的模板就能完成 few-shot 或者 zero-shot 任务，这样可以使得语言模型可以在预训练阶段利用尽可能多的信息进行训练，后续也能最...
博客
初探自然语言预训练技术演进之路
09-27
879
动手点关注干货不迷路人工智能的三个层次：运算职能：数据的存储和计算能力，机器远胜于人类。感知职能：视觉、听觉等能力，机器在语音识别、图像识别领域已经比肩人类。认知智能：自然语言处理、常识建模与推理等任务，机器还有很长的路要走。自然语言处理属于认知智能范畴，由于自然语言具有抽象性、组合性、歧义性、知识性、演化性等特点，为机器处理带来了极大的挑战，有人将自然语言处理称为人工智能皇冠上的明珠。近些年来，...
博客
Redis 持久化策略浅析
09-26
1298
动手点关注干货不迷路Redis（Remote Dictionary Server )，即远程字典服务，是一个开源的内存高速缓存数据存储服务。使用 ANSI C 语言编写，支持网络、可基于内存亦可持久化的日志型、Key-Value 数据存储，并提供多种语言的 API。▶ 简介Redis 是内存数据库，数据都是存储在内存中，为了避免进程退出导致数据的永久丢失，需要定期将 Redis 中的数据以某种形式...
博客
Babel 插件：30分钟从入门到实战
09-16
1515
动手点关注 干货不迷路 ????Babel 是一个 source to source（源码到源码）的 JavaScript 编译器，简单来说，你为 Babel 提供一些 JavaScript 代码，Babel 可以更改这些代码，然后返回给你新生成的代码。Babel 主要用于将 ECMAScript 2015+ 代码转换为能够向后兼容的 JavaScript 版本。Babel 使用插件系统进行代码转换，因...
博客
HiveServer2 内存泄漏问题定位与优化方案
09-09
1842
动手点关注 干货不迷路 ????前言HiveServer2 属于 Hive 组件的一个服务，主要提供 Hive 访问接口，例如可通过 JDBC 的方式提交 Hive 作业，HiveServer2 基于 Java 开发，整个服务运行过程中，内存的管理回收均由 JVM 进行控制。在 JVM 语言中的内存泄漏与 C/C++ 语言的内存泄漏会有些差异，JVM 的内存泄漏更多的是业务代码逻辑错误引起大量对象引用被...
博客
火山引擎在行为分析场景下的 ClickHouse JOIN 优化
09-05
1090
动手点关注 干货不迷路 ????1. 背景火山引擎增长分析 DataFinder 基于 ClickHouse 来进行行为日志的分析，ClickHouse 的主要版本是基于社区版改进开发的字节内部版本。主要的表结构：事件表：存储用户行为数据，以用户 ID分 shard 存储。--列出了主要的字段信息CREATETABLEtob_apps_all(`tea_app_id`...
博客
飞书 Android 升级 JDK 11 引发的 CI 构建性能问题
09-02
929
动手点关注干货不迷路????一、摘要本文从飞书 Android 升级 JDK 11 意外引发的 CI 构建性能劣化谈起，结合高版本 JDK 在 Docker 容器和 GC 方面的新特性，深挖 JVM 和 Gradle 的源码实现，抽丝剥茧地介绍了分析过程和修复方法，供其他升级 JDK 的团队参考。二、背景最近飞书适配 Android 12 时把 targetSdkVersion 和 compileSd...
博客
春节活动 - 高峰值奖励发放技术方案
08-30
1168
动手点关注 干货不迷路 ????1. 背景2022年春节活动在8款字节系 APP 上线，包含了红包雨、集年味卡和烟火大会等诸多玩法。红包雨、集卡开奖和烟火大会都存在高峰值突发流量。其中，红包雨活动会在10分钟内给几千万甚至上亿用户发放上亿现金奖励，且大多数请求集中在前3分钟。在项目启动时，红包雨活动作为最大的流量来源，预估的发红包峰值流量有180万 QPS 。为了保证用户体验、活动效果和资金安全，红包雨...
“相关推荐”对你有帮助么？
非常没帮助
没帮助
一般
有帮助
非常有帮助
提交
字节跳动技术团队
CSDN认证博客专家
CSDN认证企业博客
238
原创
9690
周排名
1719
总排名
128万+
访问
等级
8466
积分
5913
粉丝
656
获赞
369
评论
2165
收藏
私信
关注
热门文章
抖音品质建设 - iOS启动优化之原理篇
38182
字节跳动自研万亿级图数据库 & 图计算实践
31420
字节跳动技术团队年度 TOP10 技术干货，陪你度过不平凡的 2020
27557
字节跳动自研线上引流回放系统的架构演进
26426
字节跳动开源云原生机器学习平台 Klever
24539
最新评论
浅谈Linux设备虚拟化技术的演进之路
Bill_Xiang:
vdpa将virtio带入了容器领域，容器是说只能用内核驱动的网络设备，没有vdpa之前virtio应该是说只能虚拟机用，有了vdpa之后容器也能用virtio硬件设备了，然后vduse又进一步可以给容器提供软件的virtio设备，总的来说还是用在容器的场景里，可以这么理解吧
Android 系统 Bar 沉浸式完美兼容方案
huaqiangsina:
鸿蒙无效。
字节跳动智能创作团队多篇论文入选 CVPR 2022
小菜鸡加油:
Dressing in the Wild by Watching Dance Videos 这一篇没有代码吗
抖音Android无障碍开发知识总结
qiixiao:
所以，抖音app是和Mac一样，支持按键操作吗？
西瓜视频 iOS Voice Over 无障碍适配实践
LTOVE-CODE:
多音字怎么处理的
您愿意向朋友推荐“博客详情页”吗？
强烈不推荐
不推荐
一般般
推荐
强烈推荐
提交
最新文章
字节跳动一站式数据治理思考及实践
火山引擎 RTC 助力抖音百万并发“云侃球”
字节跳动数据中台的 Data Catalog 系统搜索实践
2022
12月
2篇
11月
5篇
10月
4篇
09月
8篇
08月
11篇
07月
14篇
06月
21篇
05月
17篇
04月
11篇
03月
6篇
02月
8篇
01月
8篇
2021年58篇
2020年47篇
2019年12篇
2017年6篇
目录
目录
最新文章
字节跳动一站式数据治理思考及实践
火山引擎 RTC 助力抖音百万并发“云侃球”
字节跳动数据中台的 Data Catalog 系统搜索实践
2022
12月
2篇
11月
5篇
10月
4篇
09月
8篇
08月
11篇
07月
14篇
06月
21篇
05月
17篇
04月
11篇
03月
6篇
02月
8篇
01月
8篇
2021年58篇
2020年47篇
2019年12篇
2017年6篇
目录
评论 2
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
查看更多评论
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额
抵扣说明：
1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。 2.余额无法直接购买下载，可以购买VIP、C币套餐、付费专栏及课程。
余额充值