Golang中，通过哈希查找实现hash，通过链表解决hash冲突
map的内存模型
map中更小的单元桶，每一个桶会装8个key，通过hash结果的高8位决定在桶里具体的位置，由hash结果的低B位决定落在哪个桶
bmap内存结构
bmap是存具体key-value的地方，进一步观察bmap底层， 将key，value分开存储可以避免在key、value不是同一种结构时出现的内存碎片，比如map[int64]int8,在每一个key-value后面都要padding7个字节，分开存储就只需要在最后加padding
当一个bmap满了以后，会通过overflow连接一个溢出桶，实际会将每一个bmap中的overflow统一迁移到hmap的extra中，主要是为了避免gc时扫描整个hmap，所以不在单独的桶里设置指针，而是直接让其指向hmap.extra.overflow数组
mapextra底层结构
map的初始化
hashTable := make(map[k]v, hint),当hint >= 4时后面会追加2^(hint-4)个桶，之后再内存页帧对齐又追加了若干个桶
分配hash数组
map的读写
value, ok := map[key] #可以通过ok判断map中是否存在这个key
valuePtr := map[key] #返回value对应类型的空值，对于key和value在map中存储的是否为指针，需要根据key，value的大小来判断，当大于128字节时，key和value存储的都为指针
将map作为函数参数时，会传递一个指针副本，对该副本操作，也同样会影响原始map对象中的值
对于访问key，通过key低B位确定哪个桶，通过桶高8位去与桶里每个tophash比较，只查找时，比较未找到就继续去overflow溢出桶里找，如果是插入没有找到，就插入第一个hashtop为empty的位置
map的key可以是除了slice，map，func 的任意类型，value可以是任意类型。
map并不是一个线程安全的数据结构，在边遍历边删除是一个同时读写的行为，被检测到会直接报panic
map的删除
通过delete(map, key)函数删除key，相应的hashtop被置为empty，并没有立即释放内存，在指针没有引用时会被系统gc
map扩容，扩容的两个临界点
1.由装载因子确定，默认6.5 、即元素个数 > = 桶个数 * 6.5，表示大部分桶已满 （B+1，将hmap的bucket数组扩容一倍）
2.由overflow的桶个数决定，当overflow溢出桶太多，代表可能是一边插入一边删除，导致大量桶出现空洞，此时值存储的非常稀疏，当bucket总数<2^15 时，overflow的bucket总数>=bucket总数;
bucket总数>=2^15,overflow的bucket >= 2^15，即认为溢出桶太多（移动bucket内容，使其更加紧密进而提高bucket利用率）缩容
当map中拥有大量hash冲突，也可能会导致overflow溢出桶数量过多，但这只是一种理论可能，golang中map中的hash随机种子几乎可以避免这种情况。
扩容过程：
由hmap内存结构知道了，buckets指向新的内存地址，oldbuckets仍然指向老的内存地址，golang中map的扩容是一种渐进式扩容，原有key/value不会一次性全部迁移完毕，每次只会迁移2个buckets，每一次搬迁以buckets作为单元，包括hash桶和这个桶的溢出链表。
对于2的缩容并不是真正的缩容，hash的容量没有发生变化，只是让数据更加紧凑，如果要做到真正的缩容就需要重新创建一个map，再复制。
参考：