Go `map` 底层实现与冲突处理

Sep 21, 2024 · 3 min read · Golang 中文 ·

Overview

Go语言中的map是一种哈希表（hash table）数据结构，支持键值对的高效存取。通过键（key）计算哈希值并将其映射到对应的存储桶（bucket）中，map可以在平均O(1)的时间复杂度下进行插入、查找和删除操作。Go的map底层实现非常精巧，结合了哈希表的基本思想，同时针对冲突和内存管理做了很多优化。

1. Go `map` 的基本结构

在Go中，map通过哈希表实现，其底层结构主要由以下几个部分组成：

1.1 Bucket（存储桶）

1Bucket
2+--------------------+---------------------+---------------------+
3| keys (k1, k2, ...) | values (v1, v2, ...) | overflow bucket ptr  |
4+--------------------+---------------------+---------------------+

存储桶: 是一个固定长度的数组，用于存储键值对。每个桶中包含了多个键（key）和值（value）对，以及一个指向溢出桶（overflow bucket）的指针。
存储桶：map中的数据被存储在 bucket（存储桶） 中，Go的map默认使用2^B个桶（B是map的大小参数），每个桶可以存储多个键值对。
每个 bucket 是一个存储单元，可以存放多个键值对。多个 bucket 组成了整个哈希表的存储空间。bucket 是哈希表的基本存储单位
每个桶包含若干个键值对和一个溢出链表（overflow bucket），用于解决哈希冲突。桶中的元素通过链表或线性探测等方式处理冲突。

1.2 哈希函数

map通过哈希函数将键映射到一个哈希值，然后通过哈希值找到对应的bucket。
哈希值的前几位决定了元素应该放入的桶。

1.3 扩容机制

当map中的桶负载因子超过一定阈值时，Go会触发扩容（rehash），扩展哈希表的大小。扩容过程中会将旧桶中的数据重新分配到新的桶中，以减少哈希冲突。

Go `map` 存储和查找的完整流程（结合 bucket 结构）

Go 中的 map 是通过哈希表实现的，使用 bucket（桶） 作为核心数据结构存储键值对。以下是 map 在存储和查找一个 key 时的完整流程，以及如何处理哈希冲突。

2. Go `map` 查找和存储流程

Go map 的核心结构包含：

bucket：存储键值对的单元。每个 bucket 能存储多个键值对（默认 8 个）。
tophash：存储每个键哈希值的高 8 位，用于快速定位键。
overflow 指针：当 bucket 满了时，指向一个额外的 overflow bucket。

1type bmap struct {
2    tophash   [8]uint8     // 哈希值的高 8 位
3    keys      [8]KeyType   // 键数组，最多 8 个键
4    values    [8]ValueType // 值数组，最多 8 个值
5    overflow  *bmap        // 指向溢出 bucket
6}

存储一个 key 的流程

步骤 1：计算哈希值

首先对要插入的 key 进行哈希计算，生成哈希值。

1hash := hashFunction(key)

步骤 2：找到 bucket

根据哈希值，通过 hash & (2^B - 1) 找到对应的 bucket 索引。B 是 map 当前的位宽，用来控制 bucket 的数量。

1bucketIndex := hash & (2^B - 1)
2bucket := buckets[bucketIndex]

步骤 3：在 bucket 中存储 key

空位存储：找到 bucket 后，首先会在 bucket 中检查是否有空位。如果有，存入键值对，同时将哈希值的高 8 位存入 tophash 数组中。
哈希冲突：如果 bucket 已满或存在冲突（多个键被哈希到同一 bucket），Go 会使用 overflow bucket。将溢出的键值对存储到下一个 overflow bucket。

 1if bucket has space {
 2    bucket.keys[i] = key
 3    bucket.values[i] = value
 4    bucket.tophash[i] = hashTop8
 5} else {
 6    if no overflow bucket {
 7        allocate new overflow bucket
 8    }
 9    store key-value in overflow bucket
10}

冲突处理：

同 bucket 存储：如果多个键被哈希到同一个 bucket，且 bucket 还有空间，直接存入该 bucket。
overflow bucket：如果 bucket 已满，分配一个新的 overflow bucket，并将新键值对存入 overflow bucket。

查找一个 key 的流程

步骤 1：计算哈希值

对要查找的 key 进行哈希计算，得到其哈希值。

1hash := hashFunction(key)

步骤 2：找到 bucket

通过 hash & (2^B - 1) 计算出 bucket 索引，找到目标 bucket。

1bucketIndex := hash & (2^B - 1)
2bucket := buckets[bucketIndex]

步骤 3：查找 key

检查 tophash：首先查看 tophash 数组，比较哈希值的高 8 位。如果匹配，继续比较 key 本身。
找到 key：如果找到相匹配的 key，返回对应的 value。
哈希冲突处理：如果 tophash 匹配但 key 不同，或 bucket 没有找到 key，Go 会查找 overflow bucket，继续寻找目标 key。

1for i := 0; i < 8; i++ {
2    if bucket.tophash[i] == hashTop8 && bucket.keys[i] == key {
3        return bucket.values[i]
4    }
5}
6if overflow bucket exists {
7    search in overflow bucket
8}

冲突处理：

同 bucket 查找：在同一个 bucket 内，使用 tophash 和 key 进行比较，匹配后返回值。
overflow bucket 查找：如果未找到目标键且存在 overflow bucket，继续沿 overflow 链查找，直到找到键或确认键不存在。

3. `map` 的内存布局

3.1 `hmap` 数据结构

Go map的底层实现主要依赖于hmap结构，它定义了map的基本数据结构和管理逻辑。

简化后的hmap结构如下：

1type hmap struct {
2    count     int          // 当前map中的键值对数量
3    flags     uint8        // 记录map状态的标志
4    B         uint8        // 2^B 是当前桶的数量
5    buckets   unsafe.Pointer // 指向bucket数组
6    oldbuckets unsafe.Pointer // 扩容时，指向旧的bucket数组
7    nevacuate uintptr      // 扩容时记录已经移动的bucket数量
8    extra     *mapextra    // 存储一些额外信息（如溢出桶等）
9}

buckets：这是一个指向所有桶的指针，包含了所有存储键值对的桶。
oldbuckets：当map进行扩容时，oldbuckets存储指向旧桶的指针。
extra：用于存储溢出桶信息，避免主桶存储溢出数据。

3.2 扩容机制

当map的负载因子（load factor，即count/buckets）超过一定阈值时，map会自动扩容。扩容的方式是将桶的数量加倍，并重新计算每个键值对的哈希值，将它们放入新的桶中。

在 Go 中，map 采用**渐进式扩容（incremental resizing）**策略。当 map 需要扩容时，桶的数量通常会增加为原来的 2 倍，但扩容不会一次性完成。每次对 map 进行的插入、删除或查找操作时，Go 会逐步将旧桶中的数据迁移到新的桶中。这种方式避免了一次性扩容带来的性能开销，使扩容过程更加平滑，用户操作不会受到明显影响。

当 map 的桶数量小于 1024时，扩容按 2 倍的方式进行；但当桶数量达到或超过 1024时，扩容不再直接倍增，而是逐步增加桶的数量。这种方式既控制了内存使用，又保证了性能不会因为扩容而突然下降，从而保持了哈希表的高效性能。

4. `map` 实现的线程不安全性

Go的map并不是线程安全的。如果在多个goroutine中并发读写map，会出现数据竞争，导致未定义行为。因此，如果要在多个goroutine中安全地使用map，需要使用同步机制，如sync.Mutex或sync.Map。

 1package main
 2
 3import (
 4    "fmt"
 5    "sync"
 6)
 7
 8func main() {
 9    var mu sync.Mutex
10    m := make(map[int]int)
11
12    // 启动多个goroutine并发写map
13    for i := 0; i < 10; i++ {
14        go func(i int) {
15            mu.Lock()
16            m[i] = i
17            mu.Unlock()
18        }(i)
19    }
20
21    // 读取map时加锁
22    mu.Lock()
23    fmt.Println(m)
24    mu.Unlock()
25}

在上述代码中，通过sync.Mutex锁保证了对map的并发访问是安全的。

5. Go `sync.Map`

Go标准库提供了sync.Map来解决并发访问map时的线程安全问题。sync.Map是线程安全的，并且具有特殊的优化机制，使其适用于高并发的场景。

 1package main
 2
 3import (
 4    "fmt"
 5    "sync"
 6)
 7
 8func main() {
 9    var sm sync.Map
10
11    // 并发写入sync.Map
12    for i := 0; i < 10; i++ {
13        go func(i int) {
14            sm.Store(i, i*10)
15        }(i)
16    }
17
18    // 并发读取sync.Map
19    sm.Range(func(key, value interface{}) bool {
20        fmt.Printf("Key: %v, Value: %v\n", key, value)
21        return true
22    })
23}

sync.Map提供了Store、Load、Delete等线程安全的操作方法，并且内部通过某种分段锁机制优化了并发读写性能。

6. 总结

Go的map底层通过哈希表实现，通过哈希函数将键映射到不同的存储桶（bucket）中。
哈希冲突处理：当多个键哈希值相同时，Go使用开放地址法和溢出桶来处理冲突问题。每个桶可以存储多个键值对，且当一个桶满时会将数据存储在溢出桶中。
扩容机制：当map的负载因子过高时，会触发扩容机制，通过渐进式扩容来避免一次性重分配带来的性能问题。
线程不安全性：Go的map在并发读写时不是线程安全的，推荐使用sync.Mutex或者sync.Map来确保线程安全。

Go map 底层实现与冲突处理

Overview

1. Go map 的基本结构