彻底理解Golang Map

1. 彻底理解Golang Map

 本文目录如下，阅读本文后，将一网打尽下面Golang Map相关面试题
                                           Go中的map是一个指针，占用8个字节，指向hmap结构体;  源码 src/runtime/map.go 中可以看到map的底层结构
   每个map的底层结构是hmap，hmap包含若干个结构为bmap的bucket数组。每个bucket底层都采用链表结构。接下来，我们来详细看下map的结构
                                            bmap  就是我们常说的“桶”，一个桶里面会最多装 8 个 key，这些 key 之所以会落入同一个桶，是因为它们经过哈希计算后，哈希结果是“一类”的，关于key的定位我们在map的查询和插入中详细说明。在桶内，又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置（一个桶内最多有8个位置)。
   bucket内存数据结构可视化如下：
   注意到 key 和 value 是各自放在一起的，并不是  key/value/key/value/...  这样的形式。源码里说明这样的好处是在某些情况下可以省略掉 padding字段，节省内存空间。
                                           当 map 的 key 和 value 都不是指针，并且 size 都小于 128 字节的情况下，会把 bmap 标记为不含指针，这样可以避免 gc 时扫描整个 hmap。但是，我们看 bmap 其实有一个 overflow 的字段，是指针类型的，破坏了 bmap 不含指针的设想，这时会把 overflow 移动到 extra 字段来。
   map是个指针，底层指向hmap，所以是个引用类型
   golang 有三个常用的高级类型 slice 、map、channel,  它们都是 引用类型 ，当引用类型作为函数参数时，可能会修改原内容数据。
   golang 中没有引用传递，只有值和指针传递。所以 map 作为函数实参传递时本质上也是值传递，只不过因为 map 底层数据结构是通过指针指向实际的元素存储空间，在被调函数中修改 map，对调用者同样可见，所以 map 作为函数实参传递时表现出了引用传递的效果。
   因此，传递 map 时，如果想修改map的内容而不是map本身，函数形参无需使用指针
    map  底层数据结构是通过指针指向实际的元素 存储空间  ，这种情况下，对其中一个map的更改，会影响到其他map
   map 在没有被修改的情况下，使用 range 多次遍历 map 时输出的 key 和 value 的顺序可能不同。这是 Go 语言的设计者们有意为之，在每次 range 时的顺序被随机化，旨在提示开发者们，Go 底层实现并不保证 map 遍历顺序稳定，请大家不要依赖 range 遍历结果顺序。
   map 本身是无序的，且遍历时顺序还会被随机化，如果想顺序遍历 map，需要对 map key 先排序，再按照 key 的顺序遍历 map。
   map默认是并发不安全的，原因如下：
   Go 官方在经过了长时间的讨论后，认为 Go map 更应适配典型使用场景（不需要从多个 goroutine 中进行安全访问），而不是为了小部分情况（并发访问），导致大部分程序付出加锁代价（性能），决定了不支持。
   场景:  2个协程同时读和写，以下程序会出现致命错误：fatal error: concurrent map writes
   如果想实现map线程安全，有两种方式：
   方式一：使用读写锁   map  +   sync.RWMutex 
   方式二：使用golang提供的  sync.Map 
   sync.map是用读写分离实现的，其思想是空间换时间。和map+RWLock的实现方式相比，它做了一些优化：可以无锁访问read map，而且会优先操作read map，倘若只操作read map就可以满足要求(增删改查遍历)，那就不用去操作write map(它的读写都要加锁)，所以在某些特定场景中它发生锁竞争的频率会远远小于map+RWLock的实现方式。
   golang中map是一个kv对集合。底层使用hash table，用链表来解决冲突 ，出现冲突时，不是每一个key都申请一个结构通过链表串起来，而是以bmap为最小粒度挂载，一个bmap可以放8个kv。在哈希函数的选择上，会在程序启动时，检测 cpu 是否支持 aes，如果支持，则使用 aes hash，否则使用 memhash。
   map有3钟初始化方式，一般通过make方式创建
   map的创建通过生成汇编码可以知道，make创建map时调用的底层函数是 runtime.makemap 。如果你的map初始容量小于等于8会发现走的是 runtime.fastrand 是因为容量小于8时不需要生成多个桶，一个桶的容量就可以满足
                                           makemap函数会通过  fastrand  创建一个随机的哈希种子，然后根据传入的  hint  计算出需要的最小需要的桶的数量，最后再使用  makeBucketArray 创建用于保存桶的数组，这个方法其实就是根据传入的  B  计算出的需要创建的桶数量在内存中分配一片连续的空间用于存储数据，在创建桶的过程中还会额外创建一些用于保存溢出数据的桶，数量是  2^(B-4)  个。初始化完成返回hmap指针。
   找到一个 B，使得 map 的装载因子在正常范围内
   Go 语言中读取 map 有两种语法：带 comma 和 不带 comma。当要查询的 key 不在 map 里，带 comma 的用法会返回一个 bool 型变量提示 key 是否在 map 中；而不带 comma 的语句则会返回一个 value 类型的零值。如果 value 是 int 型就会返回 0，如果 value 是 string 类型，就会返回空字符串。
   map的查找通过生成汇编码可以知道，根据 key 的不同类型，编译器会将查找函数用更具体的函数替换，以优化效率：
                                           函数首先会检查 map 的标志位 flags。如果 flags 的写标志位此时被置 1 了，说明有其他协程在执行“写”操作，进而导致程序 panic。这也说明了 map 对协程是不安全的。
   key经过哈希函数计算后，得到的哈希值如下（主流64位机下共 64 个 bit 位）：
   m: 桶的个数
   从buckets 通过 hash & m 得到对应的bucket，如果bucket正在扩容，并且没有扩容完成，则从oldbuckets得到对应的bucket
   计算hash所在桶编号：
   用上一步哈希值最后的 5 个 bit 位，也就是  01010 ，值为 10，也就是 10 号桶（范围是0~31号桶）
   计算hash所在的槽位:
   用上一步哈希值哈希值的高8个bit 位，也就是 10010111 ，转化为十进制，也就是151，在 10 号 bucket 中寻找** tophash 值（HOB hash）为 151* 的 槽位**，即为key所在位置，找到了 2 号槽位，这样整个查找过程就结束了。
                                           如果在 bucket 中没找到，并且 overflow 不为空，还要继续去 overflow bucket 中寻找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。
   通过上面找到了对应的槽位，这里我们再详细分析下key/value值是如何获取的：
   bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset。第 i 个 key 的地址就要在此基础上跨过 i 个 key 的大小；而我们又知道，value 的地址是在所有 key 之后，因此第 i 个 value 的地址还需要加上所有 key 的偏移。
   通过汇编语言可以看到，向 map 中插入或者修改 key，最终调用的是  mapassign  函数。
   实际上插入或修改 key 的语法是一样的，只不过前者操作的 key 在 map 中不存在，而后者操作的 key 存在 map 中。
   mapassign 有一个系列的函数，根据 key 类型的不同，编译器会将其优化为相应的“快速函数”。
   我们只用研究最一般的赋值函数  mapassign 。
                                           map的赋值会附带着map的扩容和迁移，map的扩容只是将底层数组扩大了一倍，并没有进行数据的转移，数据的转移是在扩容后逐步进行的，在迁移的过程中每进行一次赋值（access或者delete）会至少做一次迁移工作。
   1.判断map是否为nil
   每一次进行赋值/删除操作时，只要oldbuckets != nil 则认为正在扩容，会做一次迁移工作，下面会详细说下迁移过程
   根据上面查找过程，查找key所在位置，如果找到则更新，没找到则找空位插入即可
   经过前面迭代寻找动作，若没有找到可插入的位置，意味着需要扩容进行插入，下面会详细说下扩容过程
   通过汇编语言可以看到，向 map 中删除 key，最终调用的是  mapdelete  函数
   删除的逻辑相对比较简单，大多函数在赋值操作中已经用到过，核心还是找到 key 的具体位置。寻找过程都是类似的，在 bucket 中挨个 cell 寻找。找到对应位置后，对 key 或者 value 进行“清零”操作，将 count 值减 1，将对应位置的 tophash 值置成  Empty 
   再来说触发 map 扩容的时机：在向 map 插入新 key 的时候，会进行条件检测，符合下面这 2 个条件，就会触发扩容：
   1、装载因子超过阈值
   源码里定义的阈值是 6.5 (loadFactorNum/loadFactorDen)，是经过测试后取出的一个比较合理的因子
   我们知道，每个 bucket 有 8 个空位，在没有溢出，且所有的桶都装满了的情况下，装载因子算出来的结果是 8。因此当装载因子超过 6.5 时，表明很多 bucket 都快要装满了，查找效率和插入效率都变低了。在这个时候进行扩容是有必要的。
   对于条件 1，元素太多，而 bucket 数量太少，很简单：将 B 加 1，bucket 最大数量( 2^B )直接变成原来 bucket 数量的 2 倍。于是，就有新老 bucket 了。注意，这时候元素都在老 bucket 里，还没迁移到新的 bucket 来。新 bucket 只是最大数量变为原来最大数量的 2 倍( 2^B * 2 ) 。
   2、overflow 的 bucket 数量过多
   在装载因子比较小的情况下，这时候 map 的查找和插入效率也很低，而第 1 点识别不出来这种情况。表面现象就是计算装载因子的分子比较小，即 map 里元素总数少，但是 bucket 数量多（真实分配的 bucket 数量多，包括大量的 overflow bucket）
   不难想像造成这种情况的原因：不停地插入、删除元素。先插入很多元素，导致创建了很多 bucket，但是装载因子达不到第 1 点的临界值，未触发扩容来缓解这种情况。之后，删除元素降低元素总数量，再插入很多元素，导致创建很多的 overflow bucket，但就是不会触发第 1 点的规定，你能拿我怎么办？overflow bucket 数量太多，导致 key 会很分散，查找插入效率低得吓人，因此出台第 2 点规定。这就像是一座空城，房子很多，但是住户很少，都分散了，找起人来很困难
   对于条件 2，其实元素没那么多，但是 overflow bucket 数特别多，说明很多 bucket 都没装满。解决办法就是开辟一个新 bucket 空间，将老 bucket 中的元素移动到新 bucket，使得同一个 bucket 中的 key 排列地更紧密。这样，原来，在 overflow bucket 中的 key 可以移动到 bucket 中来。结果是节省空间，提高 bucket 利用率，map 的查找和插入效率自然就会提升。
   由于 map 扩容需要将原有的 key/value 重新搬迁到新的内存地址，如果有大量的 key/value 需要搬迁，会非常影响性能。因此 Go map 的扩容采取了一种称为“渐进式”的方式，原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个 bucket。
   上面说的  hashGrow()  函数实际上并没有真正地“搬迁”，它只是分配好了新的 buckets，并将老的 buckets 挂到了 oldbuckets 字段上。真正搬迁 buckets 的动作在  growWork()  函数中，而调用  growWork()  函数的动作是在 mapassign 和 mapdelete 函数中。也就是插入或修改、删除 key 的时候，都会尝试进行搬迁 buckets 的工作。先检查 oldbuckets 是否搬迁完毕，具体来说就是检查 oldbuckets 是否为 nil。
   如果未迁移完毕，赋值/删除的时候，扩容完毕后（预分配内存），不会马上就进行迁移。而是采取 增量扩容 的方式，当有访问到具体 bukcet 时，才会逐渐的进行迁移（将 oldbucket 迁移到 bucket）
   nevacuate 标识的是当前的进度，如果都搬迁完，应该和2^B的长度是一样的
   在evacuate 方法实现是把这个位置对应的bucket，以及其冲突链上的数据都转移到新的buckets上。
   转移的判断直接通过tophash 就可以，判断tophash中第一个hash值即可
   遍历的过程，就是按顺序遍历 bucket，同时按顺序遍历 bucket 中的 key。
   map遍历是无序的，如果想实现有序遍历，可以先对key进行排序
   为什么遍历 map 是无序的？
   如果发生过迁移，key 的位置发生了重大的变化，有些 key 飞上高枝，有些 key 则原地不动。这样，遍历 map 的结果就不可能按原来的顺序了。
   如果就一个写死的 map，不会向 map 进行插入删除的操作，按理说每次遍历这样的 map 都会返回一个固定顺序的 key/value 序列吧。但是 Go 杜绝了这种做法，因为这样会给新手程序员带来误解，以为这是一定会发生的事情，在某些情况下，可能会酿成大错。
   Go 做得更绝，当我们在遍历 map 时，并不是固定地从 0 号 bucket 开始遍历，每次都是从一个**随机值序号的 bucket  开始遍历，并且是从这个 bucket 的一个 随机序号的 cell **开始遍历。这样，即使你是一个写死的 map，仅仅只是遍历它，也不太可能会返回一个固定序列的 key/value 对了。

2. 怎么学习golang

除了Java、Python和JavaScript之外，如果要开始学习一门新语言的话，我想应该是Go!
Go语言正在被越来越多的公司使用。我们公司的后端服务已经全面采用Go语言实现了。
最开始接触Go语言是去年将一份Go代码“翻译”成Python并集成到测试平台上，说来也挺神奇，我从来没学过Go却完成了这个工作，这也侧面反应了Go的语法还是很平易近人的。
今年，在海翔飞调岗之后已经没有太多时间写代码了，但如果要开始学习一个新的语言或技术的话，我最想学的是Go！
目前来看，Go似乎还并没有太多测试人员使用的场景，不过，我之前介绍过的BDD行为驱动框架gauge是由Go开发的，当然，它也支持使用Go来编写BDD测试代码。
对于，已经有一定开发经验的同学，如何快速的开始学习Go语言呢？我这里给一些思路。
#### 第一步：下载和安装
在配置环境的时候你需要重点了解GOROOT、GOPATH的作用。
你还要准备一款称手的编辑器，如果你像我一样，一直都在使用VS Code的话，那么就它就可以了。
#### 第二步：从hello world开始
先运行一个hello world程序，认识Go语言的语法。
package main import (    "fmt") func main(){fmt.Println("helloworld!")}#### 第三步：熟悉Go的语法
接下来，你可能要花一周左右的时间熟悉Go语言的语法。比如，变量定义、if/for、函数、Map、跨文件的程序调用…等，当然，还有一些Go特有的知识。
当然，我更喜欢看视频教程，虽然质量参差不齐，但我仍然觉得看视频比我自己看书更有效率。
熟悉一段Go代码：
package main import"fmt"func myFunc() {i := 0Here:   //这行的第一个词，以冒号结束作为标签fmt.Println(i)i++    if i <10{        goto Here   //跳转到Here去}}func main() {    //调用函数myFunc()}#### 第四步：Go如何做单元测试
针对Go做测试也非常简单。比如，这是一个被测试文件：add.go。
package test_demofunc Add(a int, b int) int{    return a + b}
下面针对Add()函数编写测试用例，test_add.go
package test_demo import (    "testing") func TestAdd1(t *testing.T){r:= Add(1, 2)    if r !=3{t.Errorf("Add(1, 2)failed. Got %d, expected 3.", r)}} func TestAdd2(t *testing.T){r:= Add(2, 2)    if r !=4{t.Errorf("Add(2, 2)failed. Got %d, expected 4.", r)}}
你只需要执行 go test 命令就可以运行上面的测试了。
#### 第五步：从哪儿找第三方库
当然，你只学习go语言本身，基本是做不了什么事的，必须要使用第三方扩展库。
这里罗列了Go语言的第三方库，通过这些第三方库的介绍，我们也可以大概知道Go可以用来干什么。
如果你知道库的名字的话，也可以在这个网站上搜索。
据我了解，Go的第三方库大多都在GitHub上面。
#### 第六步：用Go做Web开发
Go是静态语言，而且支持并发编程，所以，他有天然的性能优势，大多公司主要使用Go也是开发后端服务（即API）。
终于到了实战阶段，如果我们真的要掌握一门语言，那么一定要用它来开发一个项目出来。这个过程大概需要一个月。
Beego是Go下在主流的Web开发框架，资料相对比较丰富，而且有完善的文档。你可为此制定一个目标，比如用它来开发一个Blog，为此，你需要详细阅读Beego文档，以及学习相关的Web开发技术。


等你完成这个项目的时候，我想你已经会使用Go语言了。

3. 为什么要学习Golang？

Go语言其实是Golanguage的简称，Go（又称 Golang）是 Google 的 Robert Griesemer，Rob Pike 及 Ken Thompson 开发的一种静态强类型、编译并发型语言。Go 语言语法与 C 相近，但功能上有：内存安全，GC（垃圾回收），结构形态及 CSP-style 并发计算。该语言的吉祥物为金花鼠（gordon），

金花鼠（gordon）
Go 语言特色——简洁、快速、安全、并行、有趣、开源、内存管理、数组安全、编译迅速
Go 语言用途：Go 语言被设计成一门应用于搭载 Web 服务器，存储集群或类似用途的巨型中央服务器的系统编程语言。对于高性能分布式系统领域而言，Go 语言无疑比大多数其它语言有着更高的开发效率。它提供了海量并行的支持，这对于游戏服务端的开发而言是再好不过了。
C/C++的问题：开发效率低，对开发者要求高；libc只向后兼容，运维难度偏大。
Lua/Python的问题：动态语言，缺少编译过程，低级错误频出；缺少有效的性能分析及调试工具。
链乔教育在线旗下学硕创新区块链技术工作站是中国教育部学校规划建设发展中心开展的“智慧学习工场2020-学硕创新工作站 ”唯一获准的“区块链技术专业”试点工作站。专业站立足为学生提供多样化成长路径，推进专业学位研究生产学研结合培养模式改革，构建应用型、复合型人才培养体系。

4. 为什么我全力推荐Golang

讨论哪个语言更好，就像在争论姚明和刘翔谁是更优秀的运动员。因为各自的坐标象限不同，常常会陷入一个难有结论怪圈。

所以本文绝不是在说Golang是比其他语言更好的语言。Golang只是最值得推荐的语言，尤其适合快速成长中的后端研发团队。

我推荐Golang的主要理由，并不是技术性的要素：不是他的高并发能力，编译的速度，跨平台能力，内存效率，也不是社区的活跃度等等。
事实上，创业之后，或者说成为一个技术管理者之后，技术优点就已经不再是我推荐任何一种语言的关键因素了。
因为，对于一个研发团队来说，项目成败的关键因素是：成本、质量和时间！


1、人力资源的成本
人力资源是研发团队最重要的资源，也是唯一的资源。其成本不仅仅是团队要支付的薪资代价。也包括获得资源的难易程度，例如招聘和培训的速度。以及维持资源，也就是保持员工满意度或者说士气的代价，也就是管理成本。（上述成本不仅指钱，时间也是非常昂贵的成本）
Golang有一系列特点，使它既容易上手，又易于维护。Golang可以让初阶和中阶工程师，经过少许培训，就写出相当不错的代码。直接点说，一票1-2年经验少许灵性的年轻工程师转Golang，只要少许指导，很快就可以写出高并发高负载能力生产级别的代码，而且质量相当有保证。而同样的工程，如果用C++或java等语言，则需要至少3-5年经验的工程师来完成，同时质量还是要让人担心。
那么，对于团队特别是成长型的或创业团队来说，现在有Golang这样一种语言，可以让大量初阶和中级工程师承担主要开发工作，还能保证相当优秀的结果，从资金成本和时间成本控制的角度，简直就是美梦成真。

2、项目研发的效率
说到高并发高负载，让我不能不想起nginx。nginx在2004年从web server领域横空出世，所向披靡。精巧严谨易于维护和扩展的代码结构，也是教科书级别的。
但是要知道，一个用C写出一个nginx，是需要世界上最优秀的工程师的。这样的工程师，不仅团队里面没有，连遇到一个都很难。
可现在，我再告诉你，一个使用Golang的中级工程师，就已经可以写出性能与nginx相近的高并发高负载应用。而且不仅性能相近，而且需要的代码行数和开发时间也短很多。这对于团队成员来说，这很可能是决定生死存亡还是走上人生巅峰的区别。
--

总之：
对于团队管理者来说，Golang可以让团队用更低的人力成本，更快的速度，更高的质量，完成项目研发。

对于工程师来说，Golang可以让人有更多的时间去思考和生活。
所以，我推荐Golang。

5. 如何评价Golang的设计

像 C# 和 Java 也可以使用 unsafe 来访问更底层,而高级封装,Go 语言只是抽象了一些用 C 实现起来特别繁重,坑特别多的东西.就像 slice 简化了对数组的操作和处理,而 channel 什么的,让实现并发逻辑简洁又高效,让程序员可以有更多精力聚焦业务逻辑的设计,而不是关心这个锁,那个锁.但要说到语言设计的优劣,Go语言确实没太多亮点.特别是处理数据库数据和 JSON类似的数据还是和其他强类型语言一样,麻烦又繁琐.
但在工程上,或者实际项目上,它有无可匹敌的几大优势:
1. 容易部署,比任何一种能胜任商业项目的语言都要简单,干练.
2. 由于语言设计的硬性规则,让执行一套辅助开发的工具,更好实现.比如代码格式化,代码分析.(虽然有点没人性,但很适合发挥团队效益)
3. 也因为硬性规则,编译时间特别快.
4. 也因为硬性规则,单元测试起来也很方便,基本可以实现边写边测.这种特性有时候很有用.
5. 因为编译时间快和部署的相对简单,它也能像动态语言一样,做一些类似脚本的工作.不需要像 Java 和 C# 一样,做点小事情,也要一个硕大的运行库,什么都要正规正矩的设计几个接口,不然重用起来很难.
再者很少有大项目,不需要或多或少的触碰一下底层来突破性能瓶颈,或者加速项目开发的.
比如说在 Go 语言里, 可以用 unsafe.Pointer(不需在内存上拷贝数据) 在 []byte 和 string 之间进行转换.
总而言之,Go 语言是一种进可攻退可守的语言.可以偏向效率的很快开发一个项目,可以为了性能,不断的优化数据结构,不断的开发硬件的性能.