Golang中的map与线程安全

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中。如果键存在,oktrue,否则为 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 提供了 LoadStoreDelete 等基本操作方法,这些方法都是线程安全的。

适用场景

根据官方文档,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.RWMutexsync.Map 可能是更好的选择。顺便提一下,slice也不是线程安全的。

发表评论