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数组大小为2^{B个元素，也就是有2}B个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回收