[TOC] ### Map Go语言中提供的映射关系容器为`map`，其内部使用`散列表（hash）`实现，所以它是一种`无序`的基于`key-value`的数据结构，同时也是一种引用类型，必须初始化才能使用。 ### 结构 map主要包含两个结构：`hmap`和`bmap`。 ~~~ type hmap struct { count int // 键值对的数目 flags uint8 //状态标识，比如是否在被写或者迁移等，因为map不是线程安全的所以操作时需要判断flags B uint8 // 桶的数目,是2的多少次幂 noverflow uint16 // 记录使用的溢出桶的数量 hash0 uint32 // hash 种子，做key 哈希的时候会用到 buckets unsafe.Pointer // 2^B个桶对应的地址指针 oldbuckets unsafe.Pointer // 扩容阶段记录旧桶的指针 nevacuate uintptr // 迁移的进度，小于此地址的bucket已经迁移完 extra *mapextra // 溢出桶相关 } type mapextra struct { overflow *[]*bmap //已经使用溢出桶的地址集合 oldoverflow *[]*bmap //迁移过程中老的溢出桶的地址 ​ nextOverflow *bmap //下一个空闲出的桶 } ​ type bmap struct { tophash [bucketCnt]uint8 } ​ //在编译期间会产生新的结构体 type bmap struct { tophash [8]uint8 //存储哈希值的高8位 data byte[1] //key value数据:key/key/key/.../value/value/value... overflow *bmap //溢出bucket的地址 } ~~~ #### hmap  >溢出桶的创建 在创建map的时候如果B>=4,那么认为会使用到溢出桶的概率比较大，就会创建2^(B-4)个溢出桶，在内存上和常规的hmap是连续的。 #### bmap  map使用的桶就是bmap，一个桶里可以放8个键值对，但是为了让内存排列更加紧凑，8个key放一起，8个value放一起，8个key的前面则是8个tophash，每个tophash都是对应哈希值的高8位。最后这里是一个bmap型指针，指向一个溢出桶overflow，溢出桶的内存布局与常规桶相同，是为了减少扩容次数而引入的，当一个桶存满了，还有空用的溢出桶时，就会在桶后面链一个溢出桶，继续往这里面存。 ### 扩容 #### 扩容的方式 扩容有两种，一种是等量扩容，另一种是双倍扩容 * **等量扩容** 负载因子没有超标，但是使用的溢出桶很多，就会触发等量扩容 >溢出桶多少的鉴定： 如果常规桶数目不大于2^15,那么使用溢出桶数目超过常规同就算是多了。 如果常规桶数目大于2 ^ 15,那么使用溢出桶数目一旦超过2^15就算是多了。 >原因 由于map中不断的put和delete key，桶中可能会出现很多断断续续的空位，这些空位会导致连接的bmap溢出桶很长，导致扫描时间边长。这种扩容实际上是一种整理，把后置位的数据整理到前面。**这种情况下，元素会发生重排，但不会换桶。**  * **双倍扩容(翻倍扩容)** 超过了6.5的负载因子，导致双倍扩容 >原因 由于当前桶数组确实不够用了，**发生这种扩容时，元素会重排，可能会发生桶迁移**。 如图中所示，扩容前B=2,扩容后B=3，假设一元素key的hash值后三位为101，那么由上文的介绍可知，在扩容前，由hash值的后两位来决定几号桶，即 01 所以元素在1号桶。 在扩容发生后，由hash值得后三位来决定几号桶，即101所以元素会迁移到5号桶。  #### 什么时候扩容 * 触发`load factor`的最大值，负载因子已达到当前界限 * 溢出桶`overflow buckets`过多 #### 扩容详情 首先我们了解下**装载因子(loadFactor)**的概念 loadFactor:=count / (2^B) 即 装载因子 = map中元素的个数 / map中当前桶的个数 通过计算公式我们可以得知，**装载因子是指当前map中，每个桶中的平均元素个数。** **扩容条件1**：**装载因子 > 6.5**(源码中定义的) 这个也非常容易理解，正常情况下，如果没有溢出桶，那么一个桶中最多有8个元素，当平均每个桶中的数据超过了6.5个，那就意味着当前容量要不足了，发生扩容。 **扩容条件2**:**溢出桶的数量过多** 当 B < 15 时，如果overflow的bucket数量超过 2^B。 当 B >= 15 时，overflow的bucket数量超过 2^15。 简单来讲，新加入key的hash值后B位都一样，使得个别桶一直在插入新数据，进而导致它的溢出桶链条越来越长。如此一来，当map在操作数据时，扫描速度就会变得很慢。及时的扩容，可以对这些元素进行重排，使元素在桶的位置更平均一些。 #### 扩容时的细节 1. 在我们的hmap结构中有一个oldbuckets吗，扩容刚发生时，会先将老数据存到这个里面。 2. 每次对map进行删改操作时，会触发从oldbucket中迁移到bucket的操作【非一次性，分多次】 3. 在扩容没有完全迁移完成之前，每次get或者put遍历数据时，都会先遍历oldbuckets，然后再遍历buckets。 ### map的增删查 #### 增  **map的赋值流程可总结位如下几步：** ①**通过key的hash值后“B”位确定是哪一个桶**，图中示例为4号桶。 ② 遍历当前桶，通过key的tophash和hash值，防止key重复，然后**找到第一个可以插入的位置**，即空位置处存储数据。 ③如果**当前桶元素已满，会通过overflow链接创建一个新的桶**，来存储数据。 **关于hash冲突**：当两个不同的 key 落在同一个桶中，就是发生了哈希冲突。冲突的解决手段是采用链表法：在 桶 中，从前往后找到第一个空位进行插入。如果8个kv满了，那么当前桶就会连接到下一个溢出桶（bmap）。 #### 删 找到了map中的数据之后，针对key和value分别做如下操作： ~~~ 1、如果``key``是一个指针类型的，则直接将其置为空，等待GC清除； 2、如果是值类型的，则清除相关内存。 3、同理，对``value``做相同的操作。 4、最后把key对应的高位值对应的数组index置为空。 ~~~ #### 查 **假设当前 B=4 即桶数量为2^B=16个**，要从map中获取k4对应的value  **参考上图，k4的get流程可以归纳为如下几步：** ①**计算k4的hash值**。\[由于当前主流机都是64位操作系统，所以计算结果有64个比特位\] ②**通过最后的“B”位来确定在哪号桶**，此时B为4，所以取k4对应哈希值的后4位，也就是0101，0101用十进制表示为5，所以在5号桶） ③**根据k4对应的hash值前8位快速确定是在这个桶的哪个位置**（额外说明一下，在bmap中存放了每个key对应的tophash，是key的哈希值前8位),一旦发现前8位一致，则会执行下一步 ④**对比key完整的hash是否匹配**，如果匹配则获取对应value ⑤**如果都没有找到，就去连接的下一个溢出桶中找** 为什么要多维护一个tophash，即hash前8位？ 这是因为tophash可以快速确定key是否正确，也可以把它理解成一种缓存措施，如果前8位都不对了，后面就没有必要比较了。 ### map的迁移 迁移的基础结构是`evacDst`数据结构如下：  #### 迁移过程   ### 总结 1. map的赋值难点在于数据的扩容和数据的迁移操作 2. bucket迁移是逐步进行的，在迁移的过程中每进行一次赋值，会做至少一次迁移工作。 3. 扩容不一定会增加空间，也可能只是做了内存整理 4. tophash的标志即可以判断是否为空也可以判断是否搬迁（用户key的tophash最小值为5,5以下为标识，用于标识此tophash对应的值的搬迁进度及状态），以及搬迁的位置。 5. 从map中删除key，有可能导致出现很多空的kv，这会导致迁移操作，如果可以避免，尽量避免。 ### 线程不安全 **map是线程不安全的** 在同一时间点，两个 goroutine 对同一个map进行读写操作是不安全的。举个栗子： 某map桶数量为4，即B=2。此时 goroutine1来插入key1， goroutine2来读取 key2. 可能会发生如下过程： ① goroutine2 计算key2的hash值,B=2，并确定桶号为1。 ② goroutine1添加key1，触发扩容条件。 ③ B=B+1=3, buckets数据迁移到oldbuckets。 ④ goroutine2从桶1中遍历，获取数据失败。 在工作中，当我们涉及到对一个map进行并发读写时，一般采用的做法是采用golang中自带的mutex锁 ~~~go type Resource struct { sync.RWMutex m map[string]int } ​ func main() { r := Resource{m: make(map[string]int)} ​ go func() { //开一个goroutine写map for j := 0; j < 100; j++ { r.Lock() r.m[fmt.Sprintf("resource_%d", j)] = j r.Unlock() } }() go func() { //开一个goroutine读map for j := 0; j < 100; j++ { r.RLock() fmt.Println(r.m[fmt.Sprintf("resource_%d", j)]) r.RUnlock() } }() } ~~~ * 对map数据进行操作时不可取地址 因为随着map元素的增长，map底层重新分配空间会导致之前的地址无效。 ### map的key值 **能作为map key 的类型包括：** |类型 |说明| | --- | --- | |boolean 布尔值 | | |numeric 数字 | 包括整型、浮点型，以及复数 | |string 字符串 | | |pointer 指针 | 两个指针类型相等，表示两指针指向同一个变量或者同为nil | |channel通道 | 两个通道类型相等，表示两个通道是被相同的make调用创建的或者同为nil | |interface 接口| 两个接口类型相等，表示两个接口类型 的动态类型 和 动态值都相等 或者 两接口类型 同为 nil | |structs、arrays |只包含以上类型元素 | | **不能作为map key 的类型包括：** * slices * maps * functions ### sync.map (并发安全) ~~~ type Map struct { mu Mutex //底层也是加锁了 read atomic.Value // readOnly dirty map[interface{}]*entry misses int } ~~~  ~~~go package main import ( "fmt" "strconv" "sync" ) // 并发安全的map var m = sync.Map{} func main() { wg := sync.WaitGroup{} // 对m执行20个并发的读写操作 for i := 0; i < 20; i++ { wg.Add(1) go func(n int) { key := strconv.Itoa(n) m.Store(key, n) // 存储key-value value, _ := m.Load(key) // 根据key取值 fmt.Printf("k=:%v,v:=%v\n", key, value) wg.Done() }(i) } wg.Wait() } ~~~ ### 链接 https://segmentfault.com/a/1190000040269520?sort=votes https://zhuanlan.zhihu.com/p/495998623