皮皮网

1.三万字带你认识 Go 底层 map 的实现
2.Go语言学习（2）--map的底层原理
3.Go实例讲解，并发编程-map并发读写的线程安全性问题
4.goland map底层原理
5.map在golang的底层实现和源码分析
6.go map and slice 2021-10-08

三万字带你认识 Go 底层 map 的实现

       map在Go语言中是一种基础数据结构，广泛应用于日常开发。其设计遵循“数组+链表”的通用思路，但Go语言在具体实现上有着独特的设计。本文将带你深入了解Go语言中map的c winform 源码底层实现，包括数据结构设计、性能优化策略以及关键操作的内部实现。

       在Go语言的map中，数据存储在数组形式的桶(bucket)中，每个桶最多容纳8对键值对。哈希值的低位用于选择桶，而高位则用于在独立的桶中区分键。这种设计有助于高效地处理冲突和实现快速访问。

       源码位于src/runtime/map.go，展示了map的内部结构和操作。在该文件中，定义了桶和map的内存模型，桶的内存结构示例如下。每个桶的前7-8位未被使用，用于存储键值对，避免了不必要的内存填充。在桶的末尾，还有一个overflow指针，用于连接超过桶容量的键值对，以构建额外的桶。

       初始化map有两种方式，根据是否指定初始化大小和hint值，调用不同的函数进行分配。对于不指定大小或hint值小于8的情况，使用make_small函数直接在堆上分配。当hint值大于8时，调用makemap函数进行初始化。

       插入操作的核心是找到目标键值对的内存地址，并通过该地址进行赋值。在实现中，没有直接将值写入内存，mfc源码分析而是返回值在内存中的对应地址，以便后续进行赋值操作。同时，当桶达到容量上限时，会创建新的溢出桶来容纳多余的数据。

       查询操作通过遍历桶来实现，找到对应的键值对。对于查询逻辑的优化，Go语言提供了不同的函数实现，如mapaccess1、mapaccess2和mapaccessK等，它们在不同场景下提供高效的关键字查找和值获取。

       当map需要扩容时，Go语言会根据装载因子进行决策，以保持性能和内存使用之间的平衡。扩容操作涉及到数据搬移，通过hashGrow()和growWork()函数实现。增量扩容增加桶的数量，而等量扩容则通过重新排列元素提高桶的利用率。

       删除操作在Go语言中同样高效，利用map的内部机制快速完成。迭代map时，可以使用特定的函数遍历键值对，实现对数据的访问和操作。

       通过深入分析Go语言中map的实现，我们可以看到Go开发者在设计时的巧妙和全面考虑，不仅关注内存效率，还考虑到数据结构在不同情况下的复用和性能优化。这种设计思想不仅体现在map自身，也对后续的缓存库等开发产生了深远的影响。

       综上所述，Go语言中map的底层实现展示了高效、灵活和强大的设计原则，为开发者提供了强大的工具，同时也启发了其他数据结构和库的设计。了解这些细节有助于我们更深入地掌握Go语言的点播 app 源码特性，并在实际开发中做出更优的选择。

Go语言学习（2）--map的底层原理

       Golang的Map底层是通过HashTable实现的，创建map时实际返回的是runtime/map.go中hmap对象的指针。hmap中buckets指向的是bucket数组的指针，bucket数组大小由B决定，通常为2^B个。单个bucket结构体内部不直接定义keys、values和overflow，而是通过指针运算访问。

       在查找、插入和删除过程中，通过哈希函数将键转换为哈希值，然后使用哈希值对bucket进行定位。查找时直接访问哈希表中对应的bucket，插入和删除操作涉及更新bucket中的键值对。

       Map的扩容机制基于负载因子，负载因子用于衡量冲突情况，定义为bucket数量与键值对数量的比值。当负载因子大于6.5，或者overflow数量超过时，Map会触发扩容。扩容时，新bucket长度为原bucket长度的2倍，旧bucket数据搬迁到新bucket。为了减少一次性搬迁带来的延迟，Go采用逐步搬迁策略，每次访问map时触发搬迁，每次搬迁2个键值对。

       扩容后，新bucket存储新插入的键值对，老bucket中的键值对逐步搬迁到新bucket。搬迁完成后，删除老bucket。搬迁过程中，老bucket中的键值对将位于新bucket的前部，新插入的文华 ccl 源码键值对位于新bucket的后部。

       等量扩容是重新组织bucket，提升bucket的使用率，而不是简单地增加容量。在某些极端场景下，如果键值对集中在少数bucket，可能导致overflow的bucket数量增多，但负载因子不高，无法执行增量搬迁。这时进行一次等量扩容，可以减少overflow的bucket数量，优化访问效率。

Go实例讲解，并发编程-map并发读写的线程安全性问题

       先上实例代码，后面再来详细讲解。

       /** * 并发编程，map的线程安全性问题，使用互斥锁的方式 */ package main import ( "sync" "time" "fmt" ) var data map[int]int = make(map[int]int) var wgMap sync.WaitGroup = sync.WaitGroup{ } var muMap sync.Mutex = sync.Mutex{ } func main() { // 并发启动的协程数量 max := wgMap.Add(max) time1 := time.Now().UnixNano() for i := 0; i < max; i++ { go modifySafe(i) } wgMap.Wait() time2 := time.Now().UnixNano() fmt.Printf("data len=%d, time=%d", len(data), (time2-time1)/) } // 线程安全的方法，增加了互斥锁 func modifySafe(i int) { muMap.Lock() data[i] = i muMap.Unlock() wgMap.Done() }

       上面的代码中 var data map[int]int 是一个key和value都是int类型的map，启动的协程并发执行时，也只是非常简单的对 data[i]=i 这样的一个赋值操作。

       主程序发起1w个并发，不断对map中不同的key进行赋值操作。

       在不安全的情况下，我们直接就看到一个panic异常信息，程序是无法正常执行完成的，如下：

       fatal error: concurrent map writes goroutine [running]: runtime.throw(0x4d6e, 0x) C:/Go/src/runtime/panic.go: +0x9c fp=0xcbf sp=0xcbf pc=0xac runtime.mapassign_fast(0x4ba4c0, 0xce, 0xc, 0x0) C:/Go/src/runtime/hashmap_fast.go: +0x3d9 fp=0xcbfa8 sp=0xcbf pc=0xbed9 main.modifyNotSafe(0xc) mainMap.go: +0x4a fp=0xcbfd8 sp=0xcbfa8 pc=0x4a1f1a runtime.goexit() C:/Go/src/runtime/asm_amd.s: +0x1 fp=0xcbfe0 sp=0xcbfd8 pc=0xcc1 created by main.main mainMap.go: +0x

       对比之前《 Go实例讲解，并发编程-slice并发读写的线程安全性问题》，slice的数据结构在不安全的并发执行中是不会报错的，只是数据可能会出现丢失。

       而这里的map的数据结构，是直接报错，所以在使用中就必须认真对待，否则整个程序是无法继续执行的。

       所以也看出来，Go在对待线程安全性问题方面，对slice还是班级社区源码更加宽容的，对map则更加严格，这也是在并发编程时对我们提出了基本的要求。

       将上面的代码稍微做些修改，对 data[i]=i 的前后增加上 muMap.Lock() 和 muMap.Unlock() ，也就保证了多线程并行的情况下，遇到冲突时有互斥锁的保证，避免出现线程安全性问题。

       关于为什么会出现线程安全性问题，这里就不再详细讲解了，大家可以参考之前的两篇文章《 Go实例讲解，并发编程-slice并发读写的线程安全性问题》和《 Go实例讲解，并发编程-数字递增的线程安全性问题》。

       这里，我们再来探讨一个问题，如何保证map的线程安全性？

       上面我们是通过 muMap 这个互斥锁来保证的。

       而Go语言有一个概念：“不要通过共享内存来进行通信，而应该通过通信来共享内存”，也就是利用channel来保证线程安全性。

       那么，这又要怎么来做呢？下面是实例代码：

       /** * 并发编程，map的线程安全性问题，使用channel的方式 */ package main import ( "time" "fmt" ) var dataCh map[int]int = make(map[int]int) var chMap chan int = make(chan int) func main() { // 并发启动的协程数量 max := time1 := time.Now().UnixNano() for i := 0; i < max; i++ { go modifyByChan(i) } // 处理channel的服务 chanServ(max) time2 := time.Now().UnixNano() fmt.Printf("data len=%d, time=%d", len(dataCh), (time2-time1)/) } func modifyByChan(i int) { chMap <- i } // 专门处理chMap的服务程序 func chanServ(max int) { for { i := <- chMap dataCh[i] = i if len(dataCh) == max { return } } }

       数据填充的方式我们还是用1w个协程来做，只不过使用了chMap这个channel来做队列。

       然后在 chanServ 函数中启动一个服务，专门来消费chMap这个队列，然后把数据给map赋值 dataCh[i]=i 。

       从上面简单的对比中，我们还看不出太多的区别，我们还是可以得出下面一些

       1 通过channel的方式，其实就是通过队列把并发执行的数据读写改成了串行化，以避免线程安全性问题；

       2 多个协程交互的时候，可以通过依赖同一个 channel对象来进行数据的读写和传递，而不需要共享变量，可以参考之前的文章《 Go实例讲解，利用channel实现协程的互动-会聊天的Tom&Jerry》；

       我们再来对比一下程序的执行效率。

       使用互斥锁的方式，执行返回数据如下：

       data len=, time=4

       使用channel的方式，执行返回数据如下：

       data len=, time=

       可以看出，这种很简单的针对map并发读写的场景，通过互斥锁的方式比channel的方式要快很多，毕竟channel的方式增加了channel的读写操作，而且channel的串行化处理，效率上也会低一些。

       所以，根据具体的情况，我们可以考虑优先用什么方式来实现。

       优先使用互斥锁的场景：

       1 复杂且频繁的数据读写操作，如：缓存数据；

       2 应用中全局的共享数据，如：全局变量；

       优先使用channel的场景：

       1 协程之间局部传递共享数据，如：订阅发布模式；

       2 统一的数据处理服务，如：库存更新+订单处理；

       至此，我们已经通过3个Go实例讲解，知道在并发读写的情况下，如何搞定线程安全性问题，简单的数据结构就是int类型的安全读写，复杂的数据结构分别详细讲解了slice和map。在这次map的讲解中，还对比了互斥锁和channel的方式，希望大家能够对并发编程有更深入的理解。

goland map底层原理

       map 是Go语言中基础的数据结构，在日常的使用中经常被用到。但是它底层是如何实现的呢？

        总体来说golang的map是hashmap，是使用数组+链表的形式实现的，使用拉链法消除hash冲突。

        golang的map由两种重要的结构，hmap和bmap(下文中都有解释)，主要就是hmap中包含一个指向bmap数组的指针，key经过hash函数之后得到一个数，这个数低位用于选择bmap(当作bmap数组指针的下表)，高位用于放在bmap的[8]uint8数组中，用于快速试错。然后一个bmap可以指向下一个bmap(拉链)。

        Golang中map的底层实现是一个散列表，因此实现map的过程实际上就是实现散表的过程。在这个散列表中，主要出现的结构体有两个，一个叫 hmap (a header for a go map)，一个叫 bmap (a bucket for a Go map，通常叫其bucket)。这两种结构的样子分别如下所示：

        hmap :

        图中有很多字段，但是便于理解map的架构，你只需要关心的只有一个，就是标红的字段： buckets数组 。Golang的map中用于存储的结构是bucket数组。而bucket(即bmap)的结构是怎样的呢？

        bucket ：

       ç›¸æ¯”于hmap，bucket的结构显得简单一些，标红的字段依然是“核心”，我们使用的map中的key和value就存储在这里。“高位哈希值”数组记录的是当前bucket中key相关的“索引”，稍后会详细叙述。还有一个字段是一个指向扩容后的bucket的指针，使得bucket会形成一个链表结构。例如下图：

       ç”±æ­¤çœ‹å‡ºhmap和bucket的关系是这样的：

       è€Œbucket又是一个链表，所以，整体的结构应该是这样的：

       å“ˆå¸Œè¡¨çš„特点是会有一个哈希函数，对你传来的key进行哈希运算，得到唯一的值，一般情况下都是一个数值。Golang的map中也有这么一个哈希函数，也会算出唯一的值，对于这个值的使用，Golang也是很有意思。

        Golang把求得的值按照用途一分为二：高位和低位。

        如图所示，蓝色为高位，红色为低位。 然后低位用于寻找当前key属于hmap中的哪个bucket，而高位用于寻找bucket中的哪个key。上文中提到：bucket中有个属性字段是“高位哈希值”数组，这里存的就是蓝色的高位值，用来声明当前bucket中有哪些“key”，便于搜索查找。 需要特别指出的一点是：我们map中的key/value值都是存到同一个数组中的。数组中的顺序是这样的:

        并不是key0/value0/key1/value1的形式，这样做的好处是：在key和value的长度不同的时候，可 以消除padding(内存对齐)带来的空间浪费 。

        现在，我们可以得到Go语言map的整个的结构图了：(hash结果的低位用于选择把KV放在bmap数组中的哪一个bmap中，高位用于key的快速预览，用于快速试错)

        map的扩容

        当以上的哈希表增长的时候，Go语言会将bucket数组的数量扩充一倍，产生一个新的bucket数组，并将旧数组的数据迁移至新数组。

        加载因子

        判断扩充的条件，就是哈希表中的加载因子(即loadFactor)。

        加载因子是一个阈值，一般表示为：散列包含的元素数 除以 位置总数。是一种“产生冲突机会”和“空间使用”的平衡与折中：加载因子越小，说明空间空置率高，空间使用率小，但是加载因子越大，说明空间利用率上去了，但是“产生冲突机会”高了。

        每种哈希表的都会有一个加载因子，数值超过加载因子就会为哈希表扩容。

        Golang的map的加载因子的公式是：map长度 / 2^B(这是代表bmap数组的长度，B是取的低位的位数)阈值是6.5。其中B可以理解为已扩容的次数。

        当Go的map长度增长到大于加载因子所需的map长度时，Go语言就会将产生一个新的bucket数组，然后把旧的bucket数组移到一个属性字段oldbucket中。注意：并不是立刻把旧的数组中的元素转义到新的bucket当中，而是，只有当访问到具体的某个bucket的时候，会把bucket中的数据转移到新的bucket中。

        如下图所示：当扩容的时候，Go的map结构体中，会保存旧的数据，和新生成的数组

       ä¸Šé¢éƒ¨åˆ†ä»£è¡¨æ—§çš„有数据的bucket，下面部分代表新生成的新的bucket。蓝色代表存有数据的bucket，橘黄色代表空的bucket。

        扩容时map并不会立即把新数据做迁移，而是当访问原来旧bucket的数据的时候，才把旧数据做迁移，如下图：

       æ³¨æ„ï¼šè¿™é‡Œå¹¶ä¸ä¼šç›´æŽ¥åˆ é™¤æ—§çš„bucket，而是把原来的引用去掉，利用GC清除内存。

        map中数据的删除

        如果理解了map的整体结构，那么查找、更新、删除的基本步骤应该都很清楚了。这里不再赘述。

        值得注意的是，找到了map中的数据之后，针对key和value分别做如下操作：

        1

        2

        3

        4

        1、如果``key``是一个指针类型的，则直接将其置为空，等待GC清除；

        2、如果是值类型的，则清除相关内存。

        3、同理，对``value``做相同的操作。

        4、最后把key对应的高位值对应的数组index置为空。

map在golang的底层实现和源码分析

       在Golang 1..2版本中，map的底层实现由两个核心结构体——hmap和bmap（此处用桶来描述）——构建。初始化map，如`make(map[k]v, hint)`，会创建一个hmap实例，包含map的所有信息。makemap函数负责创建hmap、计算B值和初始化桶数组。

       Golang map的高效得益于其巧妙的设计：首先，key的hash值的后B位作为桶索引；其次，key的hash值的前8位决定桶内结构体的数组索引，包括tophash、key和value；tophash数组还用于存储标志位，当桶内元素为空时，标志位能快速识别。读写删除操作充分利用了这些设计，包括更新、新增和删除key-value对。

       删除操作涉及到定位key，移除地址空间，更新桶内tophash的标志位。而写操作，虽然mapassign函数返回value地址但不直接写值，实际由编译器生成的汇编指令提高效率。扩容和迁移机制如sameSizeGrow和biggerSizeGrow，针对桶利用率低或桶数组满的情况，通过调整桶结构和数组长度，优化查找效率。

       evacuate函数负责迁移数据到新的桶区域，并清理旧空间。最后，虽然本文未详述，但订阅"后端云"公众号可获取更多关于Golang map底层实现的深入内容。

go map and slice --

        golang是值传递，什么情况下都是值传递

        那么，如果结构中不含指针，则直接赋值就是深度拷贝；

        如果结构中含有指针（包括自定义指针，以及slice，map等使用了指针的内置类型），则数据源和拷贝之间对应指针会共同指向同一块内存，这时深度拷贝需要特别处理。因为值传递只是把指针拷贝了

        map源码:

        /golang/go/blob/a7acf9afbdcfabfdf4/src/runtime/map.go

        map最重要的两个结构体：hmap 和 bmap

        其中 hmap 充当了哈希表中数组的角色， bmap充当了链表的角色。

        其中，单个bucket是一个叫bmap的结构体.

        Each bucket contains up to 8 key/elem pairs.

        And the low-order bits of the hash are used to select a bucket. Each bucket contains a few high-order bits of each hash to distinguish the entries within a single bucket.

        hash值的低位用来定位bucket，高位用来定位bucket内部的key

        根据上面bmap的注释和 /golang/go/blob/go1..8/src/cmd/compile/internal/gc/reflect.go ，

        我们可以推出bmap的结构实际是

        注意：在哈希桶中，键值之间并不是相邻排列的，而是键放在一起，值放在一起，来减少因为键值类型不同而产生的不必要的内存对齐

        例如map[int]int8，如果 key/elem/key/elem这样存放，那么int8类型的值就要padding 7个字节共bits

        更多可参考

        /p/

        /articles/

        因此，slice、map作为参数传递给函数形参，在函数内部的改动会影响到原slice、map

Go 语言入门 2-集合(map)的特性及实现原理

       在 Go 语言的世界里，map 是一种独特的数据结构，它以键值对的形式存储数据，以其高效性和独特的哈希管理机制著称。Go 语言的 map 实现由 hmap 结构管理哈希桶数组，而桶的内部结构由 bmap 定义，保证了键的唯一性并提供了近乎瞬时的 O(1) 查找性能。

       map 的创建方式有两种：一是通过字面量初始化，二是通过 make 函数，这为灵活性提供了保障。其基本操作包括：通过计算键的哈希值获取索引，对桶进行查找、添加、更新或删除元素。在处理哈希冲突时，Go 采用了一种名为拉链法的策略，当桶满时，会创建新的溢出桶，并通过 next 指针将它们串联起来。然而，随着元素的增长，查询效率会逐渐降低，因此，Go 通过负载因子这一指标来监控冲突，当达到预设阈值（例如，Go 6.5 版本的 0.，Redis 1 和 Java 0. 不同）时，会触发 rehash 过程。当溢出桶数量达到 \(2^{ }\) 时，也会自动进行调整。

       rehash 是一个细致的分步操作，它逐步地将旧桶的数据迁移到新桶，确保数据的一致性。这个过程结束后，旧的哈希桶会被释放，以保持内存的高效利用。深入理解 map 的这些核心原理，将有助于你在 Go 的开发旅程中游刃有余。

       如果你在实际应用中遇到 map 相关的挑战，别犹豫，我们欢迎你在评论区分享你的问题，让我们共同探索和学习。如果你想了解更多关于 Go 语言的实用技巧，别忘了关注我们的公众号「Python 学习爱好者」，那里有丰富的编程资源和成长社区，期待你的加入。

golang map 源码解读（8问）

       map底层数据结构为hmap，包含以下几个关键部分：

       1. buckets - 指向桶数组的指针，存储键值对。

       2. count - 记录key的数量。

       3. B - 桶的数量的对数值，用于计算增量扩容。

       4. noverflow - 溢出桶的数量，用于等量扩容。

       5. hash0 - hash随机值，增加hash值的随机性，减少碰撞。

       6. oldbuckets - 扩容过程中的旧桶指针，判断桶是否在扩容中。

       7. nevacuate - 扩容进度值，小于此值的已经完成扩容。

       8. flags - 标记位，用于迭代或写操作时检测并发场景。

       每个桶数据结构bmap包含8个key和8个value，以及8个tophash值，用于第一次比对。

       overflow指向下一个桶，桶与桶形成链表存储key-value。

       结构示意图在此。

       map的初始化分为3种，具体调用的函数根据map的初始长度确定：

       1. makemap_small - 当长度不大于8时，只创建hmap，不初始化buckets。

       2. makemap - 当长度参数为int时，底层调用makemap。

       3. makemap - 初始化hash0，计算对数B，并初始化buckets。

       map查询底层调用mapaccess1或mapaccess2，前者无key是否存在的bool值，后者有。

       查询过程：计算key的hash值，与低B位取&确定桶位置，获取tophash值，比对tophash，相同则比对key，获得value，否则继续寻找，直至返回0值。

       map新增调用mapassign，步骤包括计算hash值，确定桶位置，比对tophash和key值，插入元素。

       map的扩容有两种情况：当count/B大于6.5时进行增量扩容，容量翻倍，渐进式完成，每次最多2个bucket；当count/B小于6.5且noverflow大于时进行等量扩容，容量不变，但分配新bucket数组。

       map删除元素通过mapdelete实现，查找key，计算hash，找到桶，遍历元素比对tophash和key，找到后置key,value为nil，修改tophash为1。

       map遍历是无序的，依赖mapiterinit和mapiternext，选择一个bucket和offset进行随机遍历。

       在迭代过程中，可以通过修改元素的key,value为nil，设置tophash为1来删除元素，不会影响遍历的顺序。