提示：此文章为简略版
文章目录
前言
桶数组（可以理解为数组内存地址是连续的）
链表（内存地址是不连续的）
一、key 的类型要求
- map 中，key 的数据类型必须为可比较的类型，chan、map、func不可比较
二、读与写
2.1 读
- v := Map[key]
- v, ok := map[key]
第二种方式是读的同时添加一个 bool 类型的 flag 标识是否读取成功. 倘若 ok == false，说明读取失败， key 不存在，或者 map 未初始化.
第二种情况是为了区分，当一个未初始化的map，或者说map中没有对应的key，也是可以读取到对应val的类型零值的；
2.2 写
- 当对一个没有初始化的map进行写入的话，会panic
const plainError string
panic(plainError("assignment to entry in nil map"))
2.3 删除
delete(myMap,5)
如果删除的Map没有初始化或者没有对应的key，不会产生任何反应
2.4 遍历
- 遍历Map是无序的，所以遍历结果每次可能不一样
三、并发冲突
- 并发不安全的
- 并发读没问题
- 读的时候发现其他gorountine并发写，抛出fatal error；
- 并发写同上
fatal("concurrent map read and map write")
fatal("concurrent map writes")
这种报错是无法通过recover捕获的
四、核心逻辑
4.1 哈希存储
-
通过哈希值取余（hash%桶长度）
-
通过哈希方法取得 key 的 hash 值；
-
hash 值对桶数组长度取模，确定其所属的桶；
-
在桶中插入 key-value 对.
4.2 哈希冲突
首先会存在2种冲突
- 通过hash算法产生的hash值相同了（因为hash算法是具有离散性的，hash 译作散列，是一种将任意长度的输入压缩到某一固定长度的输出摘要的过程，由于这种转换属于压缩映射，输入空间远大于输出空间，因此不同输入可能会映射成相同的输出结果） 简略记：由于输入域（key）无穷大，输出域（hash 值）有限，因此必然存在不同 key 映射到相同 hash 值的情况，称之为 hash 冲突.
- hash值不同的时候，但是通过取模运算后，打到了同一个桶上面，这称为桶冲突
解决的方案：
- 通过计算某一个key，val的hash值&&取余操作是（时间复杂度是O(1)）
首先开始的解决方案为拉链法（当通过拉链法解决完冲突后，想要通过h1来获取对应的val时，先通过hash算法找到产生冲突的桶，然后再进行一次对链表得遍历即可）链表长度若是有限的，则时间复杂度是O(1)，但是当链表得长度无限放大（百万级别）那么对应线性级别的查询时间复杂度就会是O（N）；
- 基于上面链表得长度无法估量，则推出了map的扩容
- 扩容分为增量扩容和等量扩容；
- 当桶内 key-value 总数/桶数组长度 > 6.5 时发生增量扩容，桶数组长度增长为原值的两倍；
- 当桶内溢出桶数量大于等于 2^B 时( B 为桶数组长度的指数，B 最大取 15)，发生等量扩容，桶的长度保持为原值；
- 采用渐进扩容的方式，当桶被实际操作到时，由使用者负责完成数据迁移，避免因为一次性的全量数据迁移引发性能抖动.
当长度大于阈值时，在原本桶长度翻倍，开辟新的地址空间，然后进行数据迁移，这时候会产生问题：
-
时间复杂度O(N)
-
当旧桶数据量很大时，那么数据迁移会产生性能抖动，是不可取的；
解决办法：采用渐进式扩容，会有一段时间新老桶共存，让每次进行写操作的时候，优先将数据写入到新桶中，每次的读过程，优先去新桶中查询一遍，然后用老桶进行兜底，保证数据没有遗漏；后续每一次写操作，会进行对应一条数据进行迁移，将操作打散，化整为零，愚公移山；
4.3 go中拉链法解决 hash 冲突
（1）拉链法
拉链法中，将命中同一个桶的元素通过链表的形式进行链接，因此很便于动态扩展.
（2）开放寻址法
开放寻址法中，在插入新条目时，会基于一定的探测策略持续寻找，直到找到一个可用于存放数据的空位为止.
（1）桶数组中的每个桶，严格意义上是一个单向桶链表，以桶为节点进行串联；
（2）每个桶固定可以存放 8 个 key-value 对；
（3）当 key 命中一个桶时，首先根据开放寻址法，在桶的 8 个位置中寻找空位进行插入；
（4）倘若桶的 8 个位置都已被占满，则基于桶的溢出桶指针，找到下一个桶，重复第（3）步；
（5）倘若遍历到链表尾部，仍未找到空位，则基于拉链法，在桶链表尾部续接新桶，并插入 key-value 对.
map中数据不断变大，拉链法导致的链表数据会很长，这期间不断删操作除对应的key-val，会导致链表被拉的很长，数据填充率下降，这种情况下会逐渐演化成一个内存泄漏的问题（未被填充的部分内存得不到释放，链表长度得不到收敛），这时候就会触发一次等量扩容（桶节点数据，与桶数组骨干得长度的比值达到一个阈值，进行一次等量扩容，将间隙补上提高数据夯实度）
五、 数据结构
5.1 hmap
type hmap struct {
count int //总的k-v对个数为count个
flags uint8
B uint8 //桶长度为2^B个
noverflow uint16
hash0 uint32
buckets unsafe.Pointer //桶数组，因为数据地址是连续的，所以只给一个地址指针就可以找到整个桶
oldbuckets unsafe.Pointer //扩容过程中老的桶数组；
nevacuate uintptr
extra *mapextra //预分配的溢出桶
}
//溢出链表桶
type mapextra struct {
overflow *[]*bmap
oldoverflow *[]*bmap
nextOverflow *bmap
}
5.2 bmap
bmap即是map中的桶，可以存储8对k-v数据，以及一个溢出桶的指针
const bucketCnt = 8
type bmap struct {
tophash [bucketCnt]uint8
}
- 在代码层面只展示了 tophash 部分，但由于 tophash、key 和 val 的数据长度固定，因此可以通过内存地址偏移的方式寻找到后续的 key 数组、val 数组以及溢出桶指针；