1.Golang并发map？

Golang并发map？

       Golang中sync.Map的实现原理

       前面，我们讲了map的源码用法以及原理Golang中map的实现原理，但我们知道，源码map在并发读写的源码情况下是不安全。需要并发读写时，源码一般的源码源码下载聊天做法是加锁，但这样性能并不高，源码Go语言在1.9版本中提供了一种效率较高的源码并发安全的sync.Map，今天，源码我们就来讲讲sync.Map的源码用法以及原理

       sync.Map与map不同，不是源码以语言原生形态提供，而是源码在sync包下的特殊结构：

       我们下来看下sync.Map结构体

       结构体之间的关系如下图所示：

       总结一下：

       Load方法比较简单，总结一下：

       总结如下：

       golandmap底层原理

       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(aheaderforagomap)，一个叫bmap(abucketforaGomap，通常叫其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中。注意：并不是java源码底层立刻把旧的数组中的元素转义到新的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置为空。

       下面先写一段测试程序，然后看下运行结果：

       运行结果：

       发生了错误，提示：fatalerror:concurrentmapreadandmapwrite，map发生了同时读和写了；但是这个错误并不是每次运行都会出现，就是有的时候会出现，有的时候并不会出现，根据笔者多次运行结果(其他例子，读者可以自己尝试下)来看还会有另外一种报错就是：fatalerror:concurrentmapwrites，就是map发生了同时写，但是只是读是不会有问题的。关于不同的运行结果小伙伴们可以自己写几个例子去测试下。下面就这两个错误的发生，笔者给出如下解释：

       （1）fatalerror:concurrentmapreadandmapwrite

       就是电脑dubbo源码当一个goroutine在写数据，而同时另外一个goroutine要读数据就会报错，不过这个报错也很好理解：还没写完就读，读的数据会有问题，或者反过来还没读完就开始写了，同样会导致读取的数据有问题；

       （2）fatalerror:concurrentmapwrites

       两个goroutine同时写一个内存地址，这种操作也是不允许的，会导致一些比较奇怪的问题；

       总体来看其实就是写map的操作和其他的读或者写同时发生了，导致的报错，做过几年开发的人可能会想到使用锁来解决，比如写map某个key的时候，通过锁来保证其他goroutine不能再对其写或者读了。

       实现思路：

       （1）当写map的某个key时，通过锁来保证其他goroutine不能再对其写或者读了。

       （2）当读map的某个key时，通过锁来保证其他的goroutine不能再对其写，但是可以读。

       于是我们马上想到golang的读写锁貌似符合需求，下面来实现下：

       再来看下运行结果：

       发现没有报错了，并且多次运行的结果都不会报错，说明这个方法是有用的，不过在go1.9版本后就有sync.Map了，不过这个适用场景是读多写少的场景，如果写很多的话效率比较差，具体的原因在这里笔者就不介绍了，后面会写篇文章详细介绍下。

       今天的文章就到这里了，如果有不对的地方欢迎小伙伴给我留言，看到会即时回复的。

       本文目录如下，阅读本文后，将一网打尽下面GolangMap相关面试题

       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/...这样的形式。源码里说明这样的kestrel源码解析好处是在某些情况下可以省略掉padding字段，节省内存空间。

       当map的key和value都不是指针，并且size都小于字节的情况下，会把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，需要对mapkey先排序，再按照key的顺序遍历map。

       map默认是并发不安全的，原因如下：

       Go官方在经过了长时间的讨论后，认为Gomap更应适配典型使用场景（不需要从多个goroutine中进行安全访问），而不是为了小部分情况（并发访问），导致大部分程序付出加锁代价（性能），决定了不支持。

       场景:2个协程同时读和写，以下程序会出现致命错误：fatalerror:concurrentmapwrites

       如果想实现map线程安全，有两种方式：

       方式一：使用读写锁map+sync.RWMutex

       方式二：使用golang提供的sync.Map

       sync.map是用读写分离实现的，其思想是空间换时间。和map+RWLock的实现方式相比，它做了一些优化：可以无锁访问readmap，而且会优先操作readmap，倘若只操作readmap就可以满足要求(增删改查遍历)，那就不用去操作writemap(它的读写都要加锁)，所以在某些特定场景中它发生锁竞争的频率会远远小于map+RWLock的实现方式。

       golang中map是一个kv对集合。底层使用hashtable，用链表来解决冲突，出现冲突时，不是每一个key都申请一个结构通过链表串起来，而是以bmap为最小粒度挂载，一个bmap可以放8个kv。在哈希函数的选择上，会在程序启动时，检测cpu是否支持aes，如果支持，则使用aeshash，否则使用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经过哈希函数计算后，得到的哈希值如下（主流位机下共个bit位）：

       m:桶的个数

       从buckets通过hashm得到对应的bucket，如果bucket正在扩容，并且没有扩容完成，则从oldbuckets得到对应的bucket

       计算hash所在桶编号：

       用上一步哈希值最后的5个bit位，也就是，值为，也就是号桶（范围是0~号桶）

       计算hash所在的槽位:

       用上一步哈希值哈希值的高8个bit位，也就是，转化为十进制，也就是，在号bucket中寻找**tophash值（HOBhash）为*的槽位**，即为key所在位置，找到了2号槽位，这样整个查找过程就结束了。

       如果在bucket中没找到，并且overflow不为空，还要继续去overflowbucket中寻找，直到找到或是所有的key槽位都找遍了，包括所有的overflowbucket。

       通过上面找到了对应的槽位，这里我们再详细分析下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数量多，包括大量的overflowbucket）

       不难想像造成这种情况的原因：不停地插入、删除元素。先插入很多元素，导致创建了很多bucket，但是装载因子达不到第1点的临界值，未触发扩容来缓解这种情况。之后，删除元素降低元素总数量，再插入很多元素，导致创建很多的overflowbucket，但就是不会触发第1点的规定，你能拿我怎么办？overflowbucket数量太多，导致key会很分散，查找插入效率低得吓人，因此出台第2点规定。这就像是一座空城，房子很多，但是住户很少，都分散了，找起人来很困难

       对于条件2，其实元素没那么多，但是overflowbucket数特别多，说明很多bucket都没装满。解决办法就是开辟一个新bucket空间，将老bucket中的元素移动到新bucket，使得同一个bucket中的key排列地更紧密。这样，原来，在overflowbucket中的key可以移动到bucket中来。结果是节省空间，提高bucket利用率，map的查找和插入效率自然就会提升。

       由于map扩容需要将原有的key/value重新搬迁到新的内存地址，如果有大量的key/value需要搬迁，会非常影响性能。因此Gomap的扩容采取了一种称为“渐进式”的方式，原有的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对了。