map的底层数据结构为hmap
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/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
}
其中hmap的buckets数组大小为2B个元素，也就是有2B个buckets链表。count提供给len()函数使用，结构体中有一个buckets和一个oldbuckets是用来实现增量扩容的。正常使用的情况下oldbuckets为空，只有在扩容的时候才不为空。惰性扩容，不会一次性将所有数据拷贝到新的bucket中，而是在每次访问时放入新的buckets。每次扩容都是上次大小的两倍。
buckets
struct Bucket
{
uint8 tophash[BUCKETSIZE]; // hash值的高8位数组，它存在是为了快速试错，毕竟只有8位，比较起来会快一点
Bucket *overflow; // 溢出桶链表，如果有
byte data[1]; // BUCKETSIZE keys followed by BUCKETSIZE values
};
hash值的低8位标识一个Bucket，byte存放的是8个key/value对，存放顺序是key0key1key2...value0value1value2...
即
image.png
这样可以保证key0/value0/key1/value1因为内存对齐带来的内部内存碎片
hmap的大体结构
image.png
首先key经过hash函数生成hash值，通过哈希值的低8位来判断当前数据属于哪个桶(bucket)，找到bucket以后，通过哈希值的高八位与bucket存储的高位哈希值循环比对，如果相同就比较刚才找到的底层数组的key值，如果key相同，取出value。如果高八位hash值在此bucket没有，或者有，但是key不相同，就去链表中下一个溢出bucket中查找，直到查找到链表的末尾
hmap的查找
image.png
hmap的赋值
image.png
hmap的删除
image.png
并不真正的删除，而是将对应的tophash数组中对应的位置设为empty
hmap的扩容
当map长度/2^B达到装载因子后会进行扩容：将原来bucket数组数量扩充一倍，产生一个新的bucket数组，也就是bmap的buckets属性指向的数组。这样bmap中的oldbuckets属性指向的就是旧bucket数组。只有当访问原来就的bucket数组时，才会将就得bucket拷贝到新的bucket数组，进行渐进式的扩容。当然旧的数据不会删除，而是去掉引用，等待gc回收
