参考：

  • 解剖Go语言map底层实现
  • Go语言核心手册-3.字典

一、Go Map底层结构：

Go map的底层实现是一个哈希表（数组 + 链表），使用拉链法消除哈希冲突，因此实现map的过程实际上就是实现哈希表的过程。

先来看下go map底层的具体结构：

type hmap struct {count      int            // 元素个数，调用len(map)返回这个值B          uint8          // bucket数量是2^B, 最多可以放 loadFactor * 2^B 个元素，再多就要扩容了hash0      uint32         // hash seedbuckets    unsafe.Pointer // 指向bucket数组的指针（存储key val）；大小：2^B oldbuckets unsafe.Pointer // 扩容时，buckets 长度是 oldbuckets 的两倍// ...
}
type bmap struct {topbits  [8]uint8     // 高位哈希值数组keys     [8]keytype   // 存储key的数组values   [8]valuetype // 存储val的数组overflow uintptr      // 指向当前bucket的溢出桶// 为缓解当存在多个key计算后的哈希值低8位相同的个数大于一个bucket所能存放的数目8个时，且这个map还没达到扩容条件时，做的一种存储设计。
}

hmapbmap
hmapbucketsbmapbmaptopbitsoverflowkeysvalues

二、key-value是如何存放的：

keysvalues

三、根据key 查找/新增 数据：

对传来的key进行哈希运算得到唯一哈希值，并将该哈希值分为高位和低位，如图所示：
在这里插入图片描述
蓝色为高位，红色为低位。 低位用于寻找当前key属于哪个bucket，而高位用于寻找对应bucket中的具体key。

bmaptopbits

新增的过程与查找过程类似，也是填充桶的过程。

四、删除map中的数据

针对map中的key-value数据：

  • 如果是指针类型数据，则将其原有引用去除，利用go GC来清理内存
  • 如果是值类型数据，则直接清理对应内存空间
bmaptopbits

五、map的扩容

loadFactor = 6.5oldbuckets

加载因子越小↓，说明空间利用率低，因此 “产生冲突的机会” 低；
加载因子越大↑，说明空间利用率高，但是 “产生冲突的机会” 也高了。

不过需要注意的是：

oldbucketsoldbuckets

六、map的等量扩容（缩容）

overflow

其实就是重新整理一下数据，使溢出桶中的数据重新紧凑的放在普通bucket桶中，避免不必要的空间浪费。