Go 语言中的 map 即哈希表。哈希表把元素分到多个桶里，每个桶里最多放8个元素。在访问元素时，首先用哈希算法根据 key 和哈希表种子获得哈希值(暂将其命名为 h)，然后利用 h 的低 bbb 位得到桶的序号。其中桶的个数为 2b2^b2b 个，是 2 的幂。桶中存储了所有元素的 key、value 和 key 哈希值的高 8 位。所以在找到桶之后会遍历元素的高 8 位哈希值，判断与 h 的高 8 位哈希值是否相等，若相等则再对比 key。如果在当前桶中没有找到 key，还会与溢出桶的元素进行比较。

hmap
type hmap struct {
/**元数据**/count int // 哈希表元素数量B int // 2^B=桶的个数 hash0 uint32 // 哈希表种子，在创建哈希表时确定
/**存储**/buckets []bmap // 桶，一个桶中最多有8个元素mapextra struct { // 溢出桶overflow *[]*bmap // 非预分配的溢出桶nextOverflow *bmap // 指向预创建的溢出桶 }
}

bmap
type bmap struct {topbits [8]uint8 // 哈希值高 8 位keys [8]keytype // 存储keyvalues [8]valuetype // 存储valueoverflow *bmap
}

哈希表的逻辑结构是正常桶和溢出桶组成链表，但其内存结构是正常桶与预创建的溢出桶在连续的内存空间中，其它溢出桶在需要时才会创建，内存不连续。

map 的逻辑结构

make(map[keytype]valuetype, cap)

新增元素过程：如果新增的元素不存在于当前哈希表中，则把元素添加到正常桶中，如果正常桶满了，就尝试添加到溢出桶中，如果溢出桶也满了，则创建新的溢出桶。

扩容过程包含两步，首先创建一组新桶，然后迁移数据。新桶的大小由两个因素决定，如果装载因子超过 6.5，则容量翻倍，如果只是溢出桶太多，则容量不变。溢出桶多通常发生在向 map 中添加了很多元素后来又删掉的情况，容量不变的意义是将溢出桶中的数据“放回”正常桶中，不过不是放回原来的正常桶，而是放到新建的桶中。

hmap.oldbucketsdelete(map, key)