实现原理

Go 的 map 是一个指针，占用 8 个字节，指向 hmap 结构体，map 底层是基于哈希表+链地址法存储的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

type hmap struct {
    count     int    // 当前 map 中元素个数
    flags     uint8  // 写入状态标志
    B         uint8  // buckets 的数量（2^B 个）
    noverflow uint16 // 溢出 buckets 的数量
    hash0     uint32 // 生成 hash 的随机数种子

    buckets    unsafe.Pointer  // 指向 buckets 数组的指针
    oldbuckets unsafe.Pointer  // 扩容时，指向扩容前的 buckets 数组的指针
    nevacuate  uintptr  // 表示扩容进度，小于此地址的 buckets 已经迁移成功

    extra *mapextra  // 保存溢出桶的地址
}

type mapextra struct {
    overflow    *[]*bmap // overflow 包含的是 hmap.buckets 的 overflow 的 buckets
    oldoverflow *[]*bma  // oldoverflow 包含扩容时 hmap.oldbuckets 的 overflow 的 bucket
    nextOverflow *bmap   // 指向空闲的 overflow bucket 的指针
}

bmap 就是我们常说的 bucket，一个 bucket 里面会最多装 8 个key，这些 key 哈希结果的低 B 位是相同的。在 bucket 内，又会根据 key 计算出来的hash值的高8位（一个桶内最多有8个位置）来决定 key 到底落入哪个位置。

当 map 的 key 和 value 均不为指针类型时，bmap 将完全不包含指针，那么垃圾回收就不用扫描 bmap。bmap 指向溢出桶的字段 overflow 是 uintptr 类型，为了防止这些溢出桶被垃圾回收，所以需要 mapextra.overflow 将它保存起来。如果 bmap 的 overflow 是 *bmap 类型，那么垃圾回收需要扫描一个个拉链表，效率明显不如直接扫描一段内存（hmap.mapextra.overflow）效率高。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// bmap 静态结构
type bmap struct {
    tophash [bucketCnt]uint8 
}

// bmap 动态结构
type bmap struct{
    tophash [8]uint8   // 存储哈希值的高 8 位，用于快速比较和查找
    keys [8]keytype    // 存放 key，keytype 由编译器编译时候确定
    values [8]elemtype // 存放 value，elemtype 由编译器编译时候确定
    overflow uintptr   // 指向下一个 bmap，overflow 是 uintptr 而不是 *bmap 类型，保证 bmap 完全不含指针，是为了减少 GC，溢出桶存储到 extra 字段中
}

tophash 字段不仅存储 hash(key) 的高 8 位，还会存储一些状态值，用来表明当前 bucket 状态。/为了避免 hash(key) 高 8 位值和这些状态值相等，所以当 hash(key) < minTopHash 时，自动将其值加上 minTopHash 作为该 key 的 tophash。

1
2
3
4
5
6

emptyRest= 0 //表明此桶单元为空，且更高索引的单元也是空
emptyOne=1 //表明此桶单元为空
evacuatedX= 2 //用于表示扩容迁移到新桶前半段区间
evacuatedY= 3 //用于表示扩容迁移到新桶后半段区间
evacuatedEmpty = 4 //用于表示此单元已迁移
minTopHash= 5 // key的tophash值与桶状态值分割线值，小于此值的一定代表着桶单元的状态，大于此值的一定是key对应的tophash值

初始化 Map

1. 创建一个 hmap 结构体对象
2. 生成一个哈希因子 hash0 并赋值到 hmap 对象中（用于后续为key创建哈希值）
3. 根据 hint=10，并根据算法规则来创建B，此时的 B=1
4. 根据 B 去创建 bucket 并存放在数组中。当前的 Bmap 的数量为 2
   • B<4时，创建桶的个数为：$2^B$（标准桶）
   • B≥4时，创建桶的个数为：$2^B+2^{B-4}$（标准桶+溢出桶）

扩容 Map

Go map 扩容，数据迁移不是一次性迁移，而是等到访问到具体某个 bucket 时才将数据从旧 bucket 中迁移到新bucket 中。

• 一次性迁移会涉及到cpu资源和内存资源的占用，在数据量较大时，会有较大的延时，影响正常业务逻辑。因此 Go 采用渐进式的数据迁移，每次最多迁移两个bucket的数据到新的buckets中（一个是当前访问key所在的bucket，然后再多迁移一个bucket）

触发时机

• 超过负载：map 元素个数 > 6.5 * bucket 数量

  1 2 3 4 5 6 7 8 9

  if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { hashGrow(t, h) goto again // Growing the table invalidates everything, so try again } // 判断是否在扩容 func (h *hmap) growing() bool { return h.oldbuckets != nil }

  Copy

• 溢出桶太多：当 bucket 小于 $2^{15}$ 且溢出桶总大于等于桶总数，则认为溢出桶过多；当 bucket 大于等于 $2^{15}$时且溢出桶总数大于等于 $2^{15}$时，即认为溢出桶太多了。

扩容机制

• 双倍扩容：如果是因为超过负载扩容，新建一个 buckets 数组（大小为原先的 2 倍），然后旧的 buckets 数据搬到新的 buckets 中
• 等量扩容：如果是因为溢出桶太多，buckets 数量维持不变，重新做一遍类似双倍扩容的搬迁操作， 把松散的键值对重新排列一次，使得同一个bucket中的key排列地更紧密，提高buckets利用 率，进而保证更快的存取。

遍历 Map

使用 range 多次遍历 map 时输出的 key 和 value 的顺序可能不同。这是 Go 语言的设计者们有意为之，旨在提示开发者们，Go 底层实现并不保证 map 遍历顺序稳定，请大家不要依赖 range 遍历结果顺序。

主要原因有一下两点：

• map在遍历时，并不是从固定的0号bucket开始遍历的，每次遍历，都会从一个随机值序号的bucket，再从其中随机的cell开始遍历
• map遍历时，是按序遍历bucket，同时按需遍历bucket中和其overflow bucket中的cell。但是map在扩容后，会发生key的搬迁，这造成原来落在一个bucket中的key，搬迁后，有可能会落到其他bucket中了，从这个角度看，遍历map的结果就不可能是按照原来的顺序了

map 本身是无序的，且遍历时顺序还会被随机化，如果想顺序遍历 map，需要对 map key 先排序，再按照 key 的顺序遍历 map。

查找 Map

Go 语言中读取 map 有两种语法：带 comma 和 不带 comma。当要查询的 key 不在 map 里，带 comma 的用法会返回一个 bool 型变量提示 key 是否在 map 中；而不带 comma 的语句则会返回一个 value 类型的零值。如果 value 是 int 型就会返回 0，如果 value 是 string 类型，就会返回空字符串。

1
2
3
4
5
6
7
8
9

// 不带 comma 用法
value := m["name"]
fmt.Printf("value:%s", value)

// 带 comma 用法
value, ok := m["name"]
if ok {
    fmt.Printf("value:%s", value)
}

整个流程如下：

1. 写保护监测：函数首先会检查标志位 flags。如果 flags 的写标志位此时被置 1 了，说明有其他协程在执行写操作，进而导致程序 panic（这也说明了 map 不是线程安全的）；
2. 计算hash值：hash:=t.hasher(key,uintptr(h.hash0))， 不同类型的key会有不同的hash函数
3. 找到hash对应的bucket：hash 的低 B 个 bit 位，用来定位 key 所存放的bucket。如果当前正在扩容中，并且定位到的旧bucket数据还未完成迁移，则使用旧的bucket（扩容前的bucket）
4. 遍历bucket查找：利用哈希值的高 8 个 bit 位快速判断 key 是否已在当前 bucket 中（如果不在的话，需要去 bucket 的 overflow 中查找）
5. 返回key对应的指针：如果通过上面的步骤找到了key对应的槽位下标 i，根据此得到对应 value 的值

map 冲突解决方案

• 链地址法
• 开放寻址法
• 线性探测法

Go map采用链地址法解决冲突，具体就是插入key到map中时，当key定位的桶填满8个元素后（这里的单元就是桶，不是元素），将会创建一个溢出桶，并且将溢出桶插入当前桶所在链表尾部。

map 的负载因子

$负载因子=\frac{哈希表中存储元素}{桶数量}$，其是衡量当前哈希表中空间占用率的核心指标。

Go Map 的负载因子是 6.5，原因就是官方测试这个数值负载因子的性能较好，具体可看测试：

Map 和 sync.Map

Go 语言的 sync.Map 支持并发读写

1
2
3
4
5
6

type Map struct {
   mu Mutex
   read atomic.Value // readOnly
   dirty map[interface{}]*entry
   misses int
}

• map 在单个 goroutine 上的读写性能会很好，因为他在读写时没有额外的同步开销，但是他并不是并发安全的，如果多个 goroutine 同时读写一个 map 会导致数据竞争
• sync.Map 通常在并发读写时性能较好，在多 goroutine 场景下会更加安全，适合读多写少场景（写多场景下会导致 read map 缓存失效，性能下降）