Golang-map理解

注：以下内容是看小徐的公众号及B站学习源码做的笔记，个人理解，仅供参考

map的底层实现

hmap

hmap的结构体核心字段有：buckets 桶数组地址， B 定位值，桶的数目是2^B个， count 当前map的总kv对个数， 以及标记是否迁移的 oldbuckets地址，以及迁移进度指标。

bmap

bmap核心字段是8个kv对；一个tophash数组用来查找时候比对hash值高8位；溢出桶指针指向下一个桶位置，为了保证内存对齐 ，k放在一起，v放在一起。

go的map解决hash冲突实际是结合了开放地址法和开连法。 具体来说，存的时候首先击中桶数组的某个桶，在桶内采用开放寻址法找空位，找到了就直接存，找不到就开链。 所以go的map宏观上是开链法

map的插入：
首先key经过哈希函数生成64位值，低B位用来确定桶的位置，然后在桶中寻找空位（开放寻址+开链法法），找到空位时插入kv对，更新tophash值为64位的高8位。（插入可能触发扩容机制）

map的查找：
首先key经过哈希函数生成64位值，低B位用来确定桶的位置，然后在桶中用hash值的高8位与tophash数组比对，比对成功后再比对key是否相同（因为仅仅比对高8位可能有错误，所以再比对一次key）。 如果没有找到就去溢出桶中继续找。如果当前的map处于数据迁移状态，会优先到old桶数组中去找，找到的时候会协助迁移。

map是如何做到O(1)的复杂度的？

map扩容策略

当kv对不断的增多，就会造成挂载的mbuckets线性增长，那么map的查找肯定达不到O(1)，所以map是通过一个渐进式的扩容来保证每个桶内的kv对在常数级别，从而O（1）

增量式扩容： kv对/ 桶数组长度 > 6.5时发生，扩容，桶数组长度*2
等量式扩容：当map频繁的delete，造成kv对之间存在大量空洞，从而造成溢出桶数目在增加，然而桶内部8个kv对都没有用满，就需要等量扩容。 等量扩容的目的是进行迁移，从而把空洞去掉。 触发时机：溢出桶数 大于 桶数组长度时。 扩容时： 桶数组长度不变。
另外， map的扩容是渐进式扩容。 在查找或者使用的时候进行迁移。 因为一次迁移这个操作态重了，会造成性能抖动。 这也是为什么map的hmap结构体中有 oldbuckets 以及迁移进度变量。

师兄问题回答

1. 为何map 无序（每次遍历map顺序不一样）
   1. 每次遍历的起始桶位置不一样
   2. map可能处于渐进式扩容状态，导致桶内kv对的位置也在变化
2. 如何实现有序遍历map
   1. 先取出来key排序，再按照key的顺序遍历map