golang中的map与线程安全

map介绍

​ Golang中Map存储的是kv键值对，采用哈希表作为底层实现，用拉链法解决hash冲突。

基本特性

1. 键值对存储：map 用于存储键值对，其中每个键都是唯一的，且映射到一个特定的值。
2. 动态类型：在 Go 中，map 的键和值可以是任意类型，但所有键必须是相同的类型，所有值也必须是相同的类型。
3. 动态大小：map 的大小是动态的，可以根据需要增长或缩减。这意味着你不需要事先知道 map 将存储多少元素。
4. 无序集合：map 是一个无序的数据结构，这意味着你不能指望键值对的存储或检索顺序。在理想情况下（即哈希函数分布均匀），键的访问（检索和更新）操作的时间复杂度是 O(1)。这意味着无论 map 中存储了多少元素，访问一个键所需的时间大致相同。
5. 高效的键访问：map 提供了高效的键访问。通过键，你可以快速检索或更新对应的值。
6. 哈希表实现：底层使用哈希表来实现，这使得 map 在大多数情况下能够提供快速的查找、添加和删除操作。
   1. 查找操作：通常是 O(1)。但在最坏的情况下（所有键都映射到同一个桶中），时间复杂度可能会退化到 O(n)。
   2. 添加操作：同样，理想情况下是 O(1)，但在需要扩容时（即当存储元素的数量超过当前容量的负载因子时），时间复杂度可能会暂时增加，因为需要重新哈希现有的元素到新的存储空间。
   3. 删除操作：理想情况下也是 O(1)。
7. 并发使用注意：Go 的 map 在没有额外同步机制的情况下并不是并发安全的。如果你需要在多个协程（goroutine）中并发访问 map，需要使用互斥锁（mutex）或者其他同步技术来避免并发冲突。
8. 内存效率：由于 map 使用动态扩容机制，因此在使用时相对内存高效，只有在需要更多空间时才会扩展。

对于map的实现，golang源码是这样介绍的

// A map is just a hash table. The data is arranged
// into an array of buckets. Each bucket contains up to
// 8 key/value pairs. The low-order bits of the hash are
// used to select a bucket. Each bucket contains a few
// high-order bits of each hash to distinguish the entries
// within a single bucket.
//
// If more than 8 keys hash to a bucket, we chain on
// extra buckets.

基础使用

插入方法

// 声明一个 map
var map1 map[keyType]valueType

// 使用 make 函数初始化
map1 = make(map[keyType]valueType)

//初始化时指定大小，超过时依然会自动扩容
m := make(map[keyType]valueType, initialCapacity)

// 简洁声明并初始化
map2 := make(map[keyType]valueType)

// 初始化时直接填充数据
map3 := map[keyType]valueType{
    key1: value1,
    key2: value2,
    // ...
}

读取方法

读取Map中的元素时，Go提供了一种独特的方式来检查元素是否存在。例如：

golang
value, ok := map1[key]

这里，value 是与键对应的值，而 ok 是一个布尔值，表示该键是否在Map中。如果键存在，ok 为 true，否则为 false。

遍历方法

遍历Map的常见方法是使用 for 循环：

for key, value := range map1 {
    fmt.Println("Key:", key, "Value:", value)
}

但是，Go中的Map是无序的。如果你需要按顺序遍历，可以使用两种方法：使用 orderedmap 包或先读取键，对它们排序，然后按顺序遍历。

使用 orderedmap

orderedmap 是一个第三方包，允许你按照插入顺序遍历Map。使用之前，需要先安装这个包。

import "github.com/wk8/go-ordered-map"

omap := orderedmap.New()
// 后续操作与普通map类似

读取键并排序

如果不想使用第三方库，可以先提取所有键，对它们排序，然后按顺序访问Map：

var keys []int
for k := range map1 {
    keys = append(keys, k)
}
sort.Ints(keys) // 对键进行排序

for _, k := range keys {
    fmt.Println("Key:", k, "Value:", map1[k])
}

桶

​ Go map 的核心是由一系列称为“桶”的数据结构组成的。每个桶可以存储多个键值对（通常是 8 个）。这些桶的目的是通过哈希函数将键均匀地分散到各个桶中，从而减少哈希冲突。

bmap结构，即桶，是map中最重要的底层实现之一，其设计要点如下：

• 桶是map中最小的挂载粒度：map中不是每一个key都申请一个结构通过链表串联，而是每8个kv键值对存放在一个桶中，然后桶再通以链表的形式串联起来，这样做的原因就是减少对象的数量，减轻gc的负担。
• 桶串联实现拉链法：当某个桶数量满了，会申请一个新桶，挂在这个桶后面形成链表，新桶优先使用预分配的桶。
• 哈希高8位优化桶查找key : 将key哈希值的高8位存储在桶的tohash数组中，这样查找时不用比较完整的key就能过滤掉不符合要求的key，tohash中的值相等，再去比较key值
• 桶中key/value分开存放 ： 桶中所有的key存一起，所有的value存一起，目的是为了方便内存对齐
• 根据k/v大小存储不同值 ： 当k或v大于128字节时，其存储的字段为指针，指向k或v的实际内容，小于等于128字节，其存储的字段为原值
• 桶的搬迁状态 ： 可以根据tohash字段的值，是否小于minTopHash，来表示桶是否处于搬迁状态

负载因子（Load Factor）

传统负载因子

定义与基本概念

• 负载因子是用来衡量哈希表中空间占用率的一个核心指标。它定义为哈希表中已存储的元素数量与哈希表的总位置（槽数）数量的比例。数学上表示为：

  $$ \text{负载因子} = \frac{\text{已存储的元素数量}}{\text{哈希表的总位置数量}} $$

• 衡量指标：负载因子是衡量哈希表效率和空间利用的关键指标。它反映了表中有多少位置被占用，以及还有多少位置可用。

重要性

• 性能影响：负载因子的值直接影响哈希表的性能。一个较高的负载因子意味着哈希表的位置被大量占用，可能增加哈希冲突，降低查找效率。而一个较低的负载因子意味着哈希表有许多空闲位置，这可能导致内存的浪费。

• 扩容触发点：在哈希表的实现中，通常会设置一个负载因子的阈值。当表中的负载因子超过这个阈值时，哈希表将进行扩容，这通常包括分配更大的存储空间并重新分配（rehash）现有元素。

Go 语言中的负载因子

​ 在 Go 语言的 map 实现中，负载因子与桶（bucket）的平均填充元素数相关联。这里的负载因子并不是传统意义上的哈希表负载因子，而是与每个桶的平均键值对数量相关的一个特定实现细节。

\text{负载因子} = \frac{\text{已存储的元素数量}}{\text{哈希表中桶的数量}}

• 桶的平均元素数量：在 Go 语言中，当每个桶的平均填充元素数量达到特定值（如 6.5）时，map 将进行扩容。这意味着每个桶平均存储约 6.5 个键值对。

• 扩容策略：这种特定的扩容策略有助于保持 map 性能的平衡。它旨在优化内存使用和查找效率之间的关系，减少哈希冲突的同时避免过度占用内存空间。

哈希表（Hash Table）

​ 哈希表是一种用于存储键值对的数据结构，它通过一个哈希函数将键映射到表中的一个位置（称为“槽”或“桶”）来存储数据。哈希表的主要特点是它可以提供快速的数据查找，通常是常数时间复杂度 O(1)。哈希表的效率高度依赖于哈希函数的质量和处理冲突的方式。

哈希函数

​ 哈希函数是哈希表的核心，它将输入（键）转换为一个整数，这个整数通常用作数组的索引。理想的哈希函数应该满足以下条件：

• 快速计算
• 哈希值均匀分布
• 相同的输入总是产生相同的哈希值
• 不同的输入尽量产生不同的哈希值（尽管完全避免冲突是不可能的）

处理冲突

​ 当两个不同的键产生相同的哈希值时，就发生了冲突。处理哈希冲突的常见方法有两种：开放寻址法和拉链法。

​ 开放寻址法（Open Addressing）是处理哈希表中冲突的另一种常用技术。与拉链法不同，开放寻址法不使用链表来存储冲突的元素，而是在哈希表数组本身中寻找空闲位置来存储这些元素。这种方法直接在哈希表的数组中存储所有元素，不需要额外的数据结构。

开放寻址法

工作原理

1. 插入操作：当一个新元素需要插入哈希表时，先使用哈希函数计算其索引。如果该索引对应的位置已被占用（发生冲突），则根据某种探测序列（probe sequence）在表中寻找下一个空闲位置。

2. 探测序列：探测序列定义了在发生冲突时如何在哈希表中搜索空闲位置。常见的探测方法包括线性探测、二次探测和双重哈希探测。

   • 线性探测（Linear Probing）：连续检查下一个槽位，直到找到空位。
   • 二次探测（Quadratic Probing）：探测间隔以二次方增加（例如，1, 4, 9, 16, …）。
   • 双重哈希（Double Hashing）：使用两个哈希函数，第二个哈希函数定义探测间隔。

3. 查找操作：查找元素时，也使用哈希函数计算索引，然后遵循相同的探测序列进行搜索，直到找到目标元素或遇到空槽位（表示元素不存在）。

4. 删除操作：删除元素时，不能简单地将槽位设置为空，因为这会中断探测序列。通常的做法是将删除的槽位标记为已删除（而非空闲），以便探测序列可以继续通过这个槽位。

优点和缺点

• 优点：

  • 内存利用率高，因为所有元素都存储在哈希表数组中，不需要额外的数据结构。
  • 可以避免链表可能带来的缓存不友好的问题。

• 缺点：

  • 当哈希表填满时，性能可能急剧下降，因此需要及时扩容。
  • 删除操作比较复杂，可能需要特殊的标记处理。
  • 集群（clustering）问题：特别是在使用线性探测时，连续的占用槽位可能导致新插入的元素需要经过更长的探测序列。

应用场景

​ 开放寻址法适用于元素数量较少或负载因子较低的情况。在这些情况下，开放寻址法的简单性和内存连续性可以带来性能上的优势。然而，随着元素数量的增加，特别是当负载因子接近或超过 0.7 时，拉链法通常会提供更好的性能。

开放寻址法是理解和实现哈希表的重要方面之一，对于需要高效空间利用和快速访问的场景特别有用。

拉链法（Chaining）

​ 拉链法是处理哈希表中冲突的一种常用技术。它的基本思想是在哈希表的每个槽（桶）中存储一个链表。当多个键映射到同一个槽时，这些键值对会被添加到对应槽的链表中。

拉链法的特点

• 添加操作：当插入一个新的键值对时，首先使用哈希函数确定其槽位置，然后将键值对添加到该槽的链表中。
• 查找操作：查找时，同样先计算哈希值以确定槽位置，然后在对应的链表中搜索具有相应键的元素。
• 删除操作：删除操作也是先定位到具体的槽，然后在链表中找到并删除相应的元素。

优点和缺点

• 优点：拉链法简单且在冲突较多的情况下仍然能保持较好的性能。它允许哈希表的负载因子超过 1，即存储的元素数量可以超过哈希表的槽数量。
• 缺点：在最坏的情况下（所有键都映射到同一个槽），查找性能会退化到 O(n)，其中 n* 是键值对的数量。

拉链法在golang中map的应用

​ 在 Go 语言中，map 的底层实现采用了一种结合桶（bucket）和链表的方法，这与传统拉链法有些相似，但也存在差异。

​ 在 Go 的 map 中，每个桶（由 bmap 结构体表示）可以存储固定数量的键值对，通常是 8 对。这意味着，不是每一个键值对都单独分配一个结构，而是多个键值对共享一个桶。这种设计减少了对象的数量，从而减轻了垃圾回收（GC）的负担。

​ 当一个桶填满时，Go map 会申请一个新的桶，并将其连接到原有的桶上，形成一种链表结构。这个新桶优先使用预分配的桶。当需要在 map 中插入新的键值对时，会根据哈希值定位到一个特定的桶。如果该桶已满，系统会沿着链表寻找或创建新的桶来存放这个键值对。

​ 这种方式在某种程度上体现了拉链法的思想，即通过链表来解决哈希冲突。但与传统的拉链法（每个槽位对应一个链表）不同，Go 的实现是将多个键值对存储在同一个桶内，只有在这个桶填满时，才会通过链表的方式连接到新的桶。这样既保留了拉链法处理冲突的优势，又通过限制单个桶内键值对的数量，提高了内存的使用效率和查找效率。

​ 总的来说，Go map 的这种设计是对传统拉链法的一种改进和优化，它在维持良好的性能的同时，也考虑到了内存的有效使用。

hash值的使用

通过哈希函数，key可以得到一个唯一值，这个值根据操作系统位数，可能为32位或64位。map将这个唯一值，分成高位和低位，分别有不同的用途：

• 低位：用于寻找当前key属于哪个bucket
• 高位：用于寻找当前key在bucket中的位置，bucket有个tohash字段，便是存储的高位的值，用来声明当前bucket中有哪些key，这样搜索查找时就不用遍历bucket中的每个key，只要先看看tohash数组值即可，提高搜索查找效率

map其使用的hash算法会根据硬件选择，比如如果cpu是否支持aes，那么采用aes哈希（从硬件层面提高效率），并且将hash值映射到bucket时，会采用位运算来规避mod的开销

插入过程

插入新值时的过程

1. 调用哈希函数为给定键生成一个哈希码。
2. 基于哈希码的一部分确定存储键值对的桶。
3. 选定桶后，将新条目存储在该桶中。
4. 将传入键的完整哈希码与初始哈希码数组中的所有哈希码（如h1, h2…）进行比较。
5. 如果没有匹配的哈希码，意味着这是一个新条目。
6. 如果桶中有空位，则在键值对列表末尾存储新条目。
7. 否则，创建一个新桶，并将新条目存储在新桶中，旧桶的溢出指针指向这个新桶。

动态扩容

扩容过程

1. 触发扩容条件：
   • 当 map 的装载因子超过 6.5 时，即元素数量相对于桶数量太多，需要进行扩容。
   • 当使用的溢出桶（overflow buckets）数量过多时，即使桶的数量没有超过装载因子，也需要进行扩容。这种情况下，扩容的目的主要是内存整理，而不是增加桶的数量。
2. 扩容操作：
   • 扩容会新分配一个更大的数组（桶）。如果是因为装载因子过高，扩容会增加桶的数量（通常是翻倍）；如果是因为溢出桶过多，扩容后的桶数量和原来一样。
   • 在扩容过程中，map 结构体会做一些重新赋值操作，比如切换老的桶（oldbuckets）。

为什么负载因子是 6.5

​ 这个值是根据性能测试选择的。在这些测试中，考虑了如下因素：

• 溢出率：桶溢出的比例。溢出率过高意味着许多键被映射到了相同的桶，增加了冲突。
• 内存开销：每个键值对的平均内存占用。
• 查找性能：查找存在或不存在的键所需的平均步骤数。

​ 通过测试不同的负载因子，Go 团队发现，当负载因子为 6.5 时，这些因素之间达到了最佳平衡，即内存利用率和查找效率都处于理想状态。

​ 注意是平均6.5，前面说每个桶最多装8个元素。

渐进式搬迁

​ 为了避免一次性迁移大量数据带来的性能问题，Go map 采用了渐进式搬迁的方法。这意味着数据的迁移不是一次性完成的，而是在后续的 map 操作中逐渐进行。每次对 map 进行插入、删除或查找操作时，都会触发部分数据的搬迁。

​ 在扩容过程中，map 维护了一个指向旧桶数组的指针（oldbuckets），以及一个迁移进度指示器（nevacuate）。在每次 map 操作期间，会根据这个进度指示器将一部分数据从旧桶迁移到新桶中。这个过程会持续进行，直到所有数据都迁移到了新桶中。

​ 这种渐进式搬迁的方法可以在扩容期间分摊性能开销，避免了一次性重分配大量内存和数据迁移带来的性能下降。一旦所有数据都从旧桶迁移到新桶中后，oldbuckets 将被设置为 nil，这表示扩容和数据迁移已经完全完成。

​ 渐进式搬迁策略使得 Go map 在处理大量数据时仍能保持较高的性能，特别是在动态扩容的情况下。这种策略的一个关键优点是，它允许 map 在扩容过程中继续进行高效的数据操作。

缩容机制

​ 在 Go 语言中，map 的缩容机制并不像其扩容机制那样明确和直接。Go 语言的 map 实现主要支持扩容操作，以应对元素数量的增长，但它不支持显式的缩容过程，即在元素被删除后释放内存。这意味着，一旦 map 扩容后，即使删除了一些元素，它所占用的内存空间不会自动减少。

关于 map 的扩缩容机制，有以下几点需要注意：

1. 伪缩容：目前 Go 语言中的 map 实现被认为是进行了“伪缩容”。这主要是指，虽然可以减少 map 中的元素数量，但 map 占用的内存空间实际上并不会减少。即使是在 map 中的元素被大量删除后，已经分配的内存也不会被释放。

2. 内存回收：如果需要减少 map 的内存占用，唯一的方法是创建一个新的 map 并将旧 map 中的元素复制到新的 map 中，然后丢弃旧的 map。这样，旧 map 占用的内存就可以被垃圾回收器回收。

3. 内存管理：因此，在使用 Go 语言的 map 时，应当注意内存管理。如果 map 用于存储大量元素并且会经常删除元素，那么可能需要定期创建新的 map 并复制元素，以避免内存使用无限增长。

​ 综上所述，Go 语言的 map 缩容机制并不像其他一些语言中那样自动或显式。这是一个需要开发者自己管理的方面，尤其是在涉及大型数据结构和内存管理时。

线程安全问题

​ 关于 Go 语言中 map 的线程安全问题，这是一个非常重要的话题。基本来说，Go 的 map 在原生状态下是不保证线程安全的。这意味着在没有适当同步机制的情况下，从多个协程（goroutine）并发访问同一个 map 可能会导致竞态条件（race condition）和其他并发错误。

实验

package main

import "testing"

func TestMap(t *testing.T) {
    var m = make(map[int]int)
    go func() {
        i := 0
        for {
            m[i]++
            i++
        }
    }()

    i := 0
    for {
        _ = m[i]
        i++
    }
}

上面代码会报错

fatal error: concurrent map read and map write

原因

1. 内部状态修改：当一个协程对 map 进行写入（添加、修改、删除元素）操作时，它可能会更改 map 的内部状态。例如，在插入新元素时可能会触发扩容操作。如果此时另一个协程尝试访问 map，可能会遇到 map 结构正在变化的情况，导致不可预测的行为。

2. 并发写入冲突：如果多个协程同时尝试写入 map，它们可能会尝试修改 map 的同一部分，这可以导致数据损坏或程序崩溃。

3. 读写冲突：即使是读操作，也可能与写操作冲突。例如，一个协程正在读取 map 的一个元素，而另一个协程同时删除该元素或修改该元素所在的桶的结构，这可能导致读取操作发生错误。

解决方案

sync.RWMutex

​ 如果 map 的读操作远多于写操作，可以使用读写互斥锁 sync.RWMutex。这允许多个协程同时读取 map，但写操作仍然需要独占访问。

var rwmu sync.RWMutex
rwmu.RLock()
// 对 map 进行读操作
rwmu.RUnlock()

rwmu.Lock()
// 对 map 进行写操作
rwmu.Unlock()

sync.Map

​ Go 标准库中的 sync.Map 是一个专门为并发场景设计的 map 类型。它优化了在特定使用情况下的性能，特别是在写入操作较少而读取操作频繁的场景中。sync.Map 提供了 Load、Store、Delete 等基本操作方法，这些方法都是线程安全的。

适用场景

根据官方文档，sync.Map 在以下两种场景下表现出优于普通 map 加读写互斥锁 (map+RWMutex) 的性能：

1. 缓存系统：在一个只会增长的缓存系统中，一个键值对被写入后将被频繁读取或更新，但写入次数相对较少。
2. 分离的键集：多个 goroutine 分别读写不相交的键集，进行键值对的读、写和重写操作。

var m sync.Map
m.Store(key, value) // 写入
value, ok := m.Load(key) // 读取
m.Delete(key) // 删除

实现原理

sync.Map 的高性能线程安全实现依赖于以下几个关键设计：

1. 两个内部存储结构：sync.Map 维护一个主存储和一个只读存储。主存储用于最新的写入操作，而只读存储包含了先前版本的数据，形成一种数据快照。这使得在大多数情况下，读操作可以在无锁的情况下进行，因为它们主要针对稳定且不变的只读存储。

2. 延迟删除和原子操作：当从 sync.Map 中删除一个键值对时，它并不会立即从内存中移除，而是被标记为删除。这降低了写操作的频率。所有写入和删除操作都是通过原子操作完成的，保证了线程安全。

3. 读写分离：sync.Map 的设计将读写操作分离。由于读操作主要针对不经常变化的只读存储，因此可以在无锁的情况下安全进行，极大地提高了并发读的性能。

4. 动态调整：sync.Map 能够根据使用情况动态调整内部结构，例如，将数据从主存储迁移到只读存储，以优化性能。

性能优化

​ 在写入少，读取多的场景中，如缓存系统，或者当多个 goroutine 同时操作不同的键时，sync.Map 的这种设计可以显著提高性能。在这些场景下，由于读取操作的高效率和写入操作的原子性，sync.Map 能够提供比传统的带锁 map 更好的性能。

​ 总的来说，sync.Map 是一个针对特定并发场景优化的数据结构，它通过内部的复杂机制，实现了在高并发环境下的高效线程安全操作。然而，它并非适用于所有情况，特别是在写入操作频繁的场景中，传统的 map 加锁可能会更加高效。因此，选择 sync.Map 还是普通 map 应该基于具体的应用场景和性能需求。

其他并发安全map的实现库

1. orcaman/concurrent-map

GitHub: orcaman/concurrent-map

• 特点：
  • orcaman/concurrent-map 是一个简单易用的并发安全的哈希表实现。
  • 它通过将 map 分割成多个小的 map 段（shards）来减少锁的粒度，从而提高并发性能。每个段有自己的读写锁，这减少了锁争用，提高了并发读写的效率。
  • 提供基本的 map 操作如 Set, Get, Remove, Items 等。

2. cornelk/hashmap

GitHub: cornelk/hashmap

• 特点：
  • cornelk/hashmap 是另一个高性能的并发安全的哈希表实现。
  • 它特别为高并发场景优化，比如在多核处理器上运行时，能够提供非常好的性能。
  • 支持扩展和收缩，可以根据存储的元素数量自动调整大小。
  • 提供了丰富的 API，包括迭代器、大小估计、自定义等值比较等功能。

3. alphadose/haxmap

GitHub: alphadose/haxmap

• 特点：
  • alphadose/haxmap 是一个较新的高性能并发安全的哈希表实现。
  • 这个库的特色在于其使用了一种叫做 "hopscotch hashing" 的技术，这种技术旨在提高缓存利用率和降低冲突概率。
  • 旨在提供高速的并发读写操作，同时保持较低的内存占用。
  • API 上提供了类似的基本操作，如添加、删除、查找等。

总结

​ 这些库各有其特点和优势，选择合适的库取决于具体的应用场景和性能需求。例如，在需要处理大量并发读写操作的情况下，可能会选择 cornelk/hashmap；而如果希望降低内存占用并提高缓存效率，则 alphadose/haxmap 可能是一个好的选择。重要的是要根据实际需求和性能测试来选择最适合项目的并发安全 map 实现。

结论

​ 在多协程环境下，对 map 的安全访问需要采用合适的同步机制。选择哪种机制取决于具体的使用场景和性能要求。简单地使用互斥锁可以提供安全保证，但可能会影响性能。在读多写少的场景中，sync.RWMutex 或 sync.Map 可能是更好的选择。顺便提一下，slice也不是线程安全的。