map

map 底层实现

1. map 创建时(makemap)会返回指向 map 的指针, 所以不需要取地址就可以传递
2. 底层由 buckets 数组组成, 数组中的元素称为 桶, 桶最多装 8 个 key
3. hash 结果 低B位(2^B 个桶, B为map中桶的数量)决定在哪个桶, 高8位决定在桶的那个位置
4. key, value 都不为指针且 size < 128 byte 时, 桶会被标记为不含指针, 避免 gc 扫描整个 hmap
5. 桶中的8个key,value是按照 key 放一起, value 放一起的结构. 目的是避免不同数据类型的内存空隙, 节省内存
6. 每个桶内有溢出部分,称为溢出桶,可以为多个,与主桶成链表形式,遍历时会遍历链表

线程是否安全

1. 非安全, 查找/赋值/遍历/删除过程都会检测写标志,一旦发现写标志=1,会直接 panic
2. 赋值和删除操作会将写标志设置为1

扩容过程

1. loadFactor := count / (2^B); 插入时检查
   • loadFactor > 6.5
   • overflow 中的 bucket 数量过多; B < 15 以 2^B 判断, B >= 15 以 2^15 判断
2. 渐进式扩容, 在每次 插入/修改/删除 key 的时候,会尝试进行搬迁操作

遍历过程

1. 非扩容中遍历: 遍历所有 bucket 以及 overflow bucket, 然后挨个遍历 bucket 中的 cell, 从所有的 cell 中取出 key, value 即可
2. 扩容中遍历: 新旧桶都要遍历

赋值过程

1. 计算 hash, 后 2^B 位定位到桶, 前8位定位到桶中的位置
2. 桶满了会创建 overflow bucket 存放

删除过程

1. hash 定位位置进行移除; 先定位 bucket, 然后定位 cell
2. 如果处于扩容中, 会触发一次搬迁操作

对 map 里的元素取地址

不行, 因为一旦扩容, key value 的位置就会改变, 保存的地址也就失效了

边遍历边删除

单个协程中理论是可行, 但是遍历结果可能会包含删除了的 key,也可能不包含.

比较 map 是否相等

需要遍历比较, 或者使用 reflect.DeepEquel() 进行比较

集合运算

1. key 在扩容时必定无序
2. 不扩容的情况下, Go 增加了随机数的 bucket index 开始遍历, 固定这一个无序的特性

哪些类型可以作为 key

可以比较的类型都可以作为 key