[TOC]
map
底层数据结构
// A header for a Go map.
type hmap struct {
// 元素个数，调用 len(map) 时，直接返回此值
count int
flags uint8
// buckets 的对数 log_2
B uint8
// overflow 的 bucket 近似数
noverflow uint16
// 计算 key 的哈希的时候会传入哈希函数
hash0 uint32
// 指向 buckets 数组，大小为 2^B
// 如果元素个数为0，就为 nil
buckets unsafe.Pointer
// 扩容的时候，buckets 长度会是 oldbuckets 的两倍
oldbuckets unsafe.Pointer
// 指示扩容进度，小于此地址的 buckets 迁移完成
nevacuate uintptr
extra *mapextra // optional fields
}
B：buckets数组的长度的对数，也就是说 buckets 数组的长度就是 2^B。bucket 里面存储了 key 和 value
-
buckets是一个指针，最终指向bmap这个数据结构
type bmap struct { tophash [bucketCnt]uint8 } // 但上述只是表面(src/runtime/hashmap.go)的结构，编译期间会给它加料，动态地创建一个新的结构： type bmap struct { topbits [8]uint8 keys [8]keytype values [8]valuetype pad uintptr overflow uintptr } -
bmap：即常说的桶。
- 桶里面最多装8个key，会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置
- 如若有第九个key进来，会再创建一个bucket，通过overflow指针连接
- bmap的内存模型，是key/key/.../value/value/...，这样可以减少额外的内存对齐所需要的空间
-
map的创建：
- map创建出来是一个指针，因此在作为函数参数传入时，内部的改动也会影响到map自身
- slice是一个结构体，因此作为函数参数传入时，不会影响到数据自身，但是由于数据是指针，因此可以改变指向的数据
-
map的遍历：是随机的
go中range遍历map，不是固定的从bucket0开始遍历，每次会随机一个bucket开始遍历，并且bucket内也是会随机一个cell遍历
map扩容
为避免大量key落在一个桶中，退化成链表，导致查询效率变为O(n)，装载因子被提出，用来衡量该情况。
loadFactor := count / (2^B)
count : map中元素个数
B：2^B表示buckets数目
-
触发扩容的时机：在向map中插入元素时，符合下面两个条件，会触发扩容
装载因子超出阈值6.5（元素塞满了bucket）
-
overflow的bucket过多：（元素没有塞满bucket了，bucket冗余空间过多）
当 B 小于 15，也就是 bucket 总数 2^B 小于 2^15 时，如果 overflow 的 bucket 数量超过 2^B；当 B >= 15，也就是 bucket 总数 2^B 大于等于 2^15，如果 overflow 的 bucket 数量超过 2^15
-
扩容的逻辑：“渐进式”扩容，原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个 bucket。
- 分配新的buckets
- 搬迁到新的buckets，发生在插入、修改和删除时，会先检查oldbuckets是否为nil（nil则搬迁完成，不需要再搬迁了）
-
扩容后的容量：针对扩容触发的条件1和2，有两种策略
-
buckets数目翻倍：
要重新计算 key 的哈希，才能决定它到底落在哪个 bucket。
-
buckets数目相等：
从老的 buckets 搬迁到新的 buckets，由于 bucktes 数量不变，因此可以按序号来搬，比如原来在 0 号 bucktes，到新的地方后，仍然放在 0 号 buckets。
-
context
context作用
- 在 一组 goroutine 之间传递共享的值
- 取消goroutine
- 防止goroutine泄露
- 不要将 Context 塞到结构体里。直接将 Context 类型作为函数的第一参数，而且一般都命名为 ctx。
- 不要向函数传入一个 nil 的 context，如果你实在不知道传什么，标准库给你准备好了一个 context：todo。
- 不要把本应该作为函数参数的类型塞到 context 中，context 存储的应该是一些共同的数据。例如：登陆的 session、cookie 等。
- 同一个 context 可能会被传递到多个 goroutine，别担心，context 是并发安全的。
context 主要用来在 goroutine 之间传递上下文信息，包括：取消信号、超时时间、截止时间、k-v 等。
随着 context 包的引入，context 几乎成为了并发控制和超时控制的标准做法。
context.Value
type valueCtx struct {
Context
key, val interface{}
}
key要求是可比较的
-
属于一个树结构
<img src="C:\Users\Supreme\AppData\Roaming\Typora\typora-user-images\image-20220220230609169.png" alt="image-20220220230609169" style="zoom:50%;" />
取值过程，是会向上查找的
允许存在相同的key，向上查找会找到最后一个key相等的节点，即层数高的节点
Goroutine
- M必须拥有P才可执行G中的代码，P含有一个包含多个G的队列，P可以调度G交由M执行
- 所有可执行go routine都放在队列中：
- 全局队列（GRQ）：存储全局可运行的goroutine（从系统调用中恢复的G）；
- 本地可运行队列（LRQ）：存储本地（分配到P的）可运行的goroutine
- workingschedule：各个P中维护的G队列很可能是不均衡的；空闲的P会查询全局队列，若全局队列也空，则会从其他P中窃取G（一般每次取一半）。
goroutine和线程的区别
- 内存占用：goroutine默认栈为2KB，线程至少需要1MB
- 创建和销毁：goroutine由go runtime管理，属于用户级别的，消耗小；线程是操作系统创建的，是内核级别的，消耗巨大
- 切换：goroutine切换只需要保存三个寄存器，线程切换需要寄存器
M:N模型（M个线程，N个goroutine）
- go runtime负责管理goroutine，Runtime会在程序启动的时候，创建M个线程（CPU执行调度的单位），之后创建的N个goroutine都会依附在这M个线程上执行。
- 同一时刻，一个线程只能跑一个goroutine，当goroutine发生阻塞时，runtime会把它调度走，让其他goroutine来执行，不让线程闲着
系统调用
同步调用
G1即将进入系统调用时，M1将释放P，让某个空闲的M2获取P并继续执行P队列中剩余的G（即M2接替M1的工作）；M2可能来源于M的缓存池，也可能是新建的。当G1系统调用完成后，根据M1能否获取到P，将对G1做不同的处理：
- 有空闲的P，则获取一个以继续执行G1；
- 无空闲P，将G1放入全局队列，等待被其他P调度；M1进入缓冲池睡眠
异步调用
- M 不会被阻塞，G 的异步请求会被“代理人” network poller 接手，G 也会被绑定到 network poller
- 等到系统调用结束，G 才会重新回到 P 上。
- M 由于没被阻塞，它因此可以继续执行 LRQ 里的其他 G。
