map
- map的数据结构
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
// Make sure this stays in sync with the compiler's definition.
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}
- count:元素个数
- B buckets数量的对数
- hash0 哈希函数种子
- buckets buckets
- oldbuckets 扩容时的老buckets
- nevacuate 扩容进度
- extra 记录溢出桶的信息
- B 是 buckets 数组的长度的对数，即 buckets 数组的长度为 2^B，根据负载因子和初始化的map长度，能确认B的大小
- bmap数据结构
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr
overflow uintptr
}
- bmap 就是人们常说的“桶”，桶里面会最多装 8 个
- key 和 value 是各自放在一起的，并不是 key/value/key/value/... 这样的形式。这样做的好处是在某些情况下可以省略掉 padding 字段，节省内存空间。
- 每个 bucket 设计成最多只能放 8 个 key-value 对， 如果有第 9 个 key-value 落入当前的 bucket，则需要再构建一个 bucket ，并且通过 overflow 指针连接起来。这 就是所谓的“链表法”。
- 在程序启动时，Go 会检测 CPU 是否支持 aes，如果支持， 则使用aes hash，否则使用memhash。
- 计算hash之后，使用后B位定位，对长度取模定位具体的bucket，再取hash值的高8位，找到key在bmap中的位置。如果tophash位置重复，则继续向后查找，本个hmap没找到，则去overflow里找
- 扩容条件：1、装载因子超过阈值（源码里定义的阈值是 6.5）。 2、overflow 的 bucket 数量过多：当 B<15，也就是 bucket="" 总数="" 2^b="" 小于="" 2^15="" 时，overflow="" 的="" 数量超过="" 2^b；="" 当="" b="">= 15，也就是 bucket 总数 2^B 大于等于 2^15， overflow 的 bucket 数量超过 2^15
- 针对1进行翻倍扩容，B + 1，针对2，进行等量扩容，
- 渐进式扩容：原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个 bucket。
- 扩容中的遍历：扩容过程不是一个原子的操作， 它每次最多只搬运 2 个 bucket，所以如果触发了扩容操作，那么在很长时间里，map
的状态都是
处于一个中间态。map 遍历的核心在于理解 2 倍扩容时，老 bucket 会分裂到 2 个新 bucket 中去。而遍历操作，会按照新 bucket
的序号顺序进行，碰到老 bucket 未搬迁的情况时，要在老 bucket 中找到将来要搬迁到新 bucket 来的 key
map为什么是无序的？
1、触发2倍扩容后，元素的位置发生变化 2、每次遍历不是固定从0号bucket位置开始，而是每次随机获取一个bucket位置，这并且从这个bucket的一个随机需要cell开始。
map是线程安全么
在查找、赋值、遍历、删除的过程中都会检测写标志，一旦发现写标志置位（等于 1），则直接 panic
float类型可以做map的key么？
从语法上看，是可以的：Go 语言中只要是可比较的类型都可以作为 key，但是由于精度问题会导致一些诡异问题，最好不用。
如何比较两个map是否相等
1）都为 nil。 2）非空、长度相等，指向同一个 map 实体对象。 3）相应的 key 指向的 value “深度”相等。
可以对map元素取地址么
不能，扩容后地址会变
为什么选择渐进式扩容
避免性能抖动