天天看点
返回

【并发编程】map 基本用法和常见错误以及如何实现线程安全的map类型

博主介绍：

– 我是了 凡 微信公众号【了凡银河系】期待你的关注。未来大家一起加油啊~

前言

【并发编程】map 基本用法和常见错误以及如何实现线程安全的map类型

哈希表介绍

哈希表（Hash Table）这个数据结构，在Go语言基础的时候就已经涉及过了。实现的就是key-value直接的映射关系，主要提供的方法包括Add、Lookup、Delete等。因为这种数据结构是一个基础的数据结构，每个key都会有一个唯一的索引值，通过索引可以很快找到对应的值，所以使用哈希表进行数据的插入和读取都是很快的。Go语言本身就内建了这样一个数据结构，也就是map数据类型。

文章目录

  • 前言
    • 哈希表介绍
  • map的基本使用方法
    • 总结
  • 常见错误
    • 第一种：未初始化
    • 第二种：并发读写
  • 如何实现线程安全的map类型？
    • 加读写锁：扩展map，支持并发读写
    • 分片加锁：更高效的并发map

map的基本使用方法

Go内建的map类型如下：

map[k]v

其中，key类型的K必须是可比较的（comparable），也就是可以通过 == 和 !=操作符进行比较；value的值和类型无所谓，可以是任意的类型，或者为nil。

在Go语言中，bool、整数、浮点数、复数、字符串、指针、Channel、接口都是可比较的、包含可比较元素的struct和数组，这俩也是可比较的，而slice、map、函数值都是不可比较的。

上面这些可比较的数据类型都可以作为map的key吗？显然不是。通常情况下，我们会选择内建的基本类型，比如整数、字符串做key的类型、因为这样最方便。

这里有一点需要注意，如果使用struct类型做key其实是有坑的，以为你如果struct的某个字段值修改了，查询map时无法获取它add进去的值，如下例子：

type mapKey struct {
    key int
}

func main() {
    var m = make(mapKey]string)
    var key = mapKey{10}
    
    m[key] = "hello"
    fmt.Printf("m[key]=%s\n",m[key])
    
    // 修改key的字段的值后再次查询map，无法获取刚才add进去的值
    key.key = 100
    fmt.Printf("再次查询m[key]=%s\n",m[key])
}

那该怎么办呢？如果要使用struct作为key，我们要保证struct对象在逻辑上是不可变的，这样才会保证map的逻辑没有问题。

以上就是选取key类型的注意点了。看一下使用map[key]函数时需要注意的一个知识点。在Go中，map[key]函数返回结果可以是一个值，也可以是两个值，这是容易让人迷惑的地方。原因在于，如果获取一个不存在的key对应的值时，会返回零值。为了区分真正的零值和key不存在这两种情况，可以根据第二个返回值来区分，如下实例：

func main() {
    var m = make(map[string]int)
    m["a"] = 0
    fmt.Printf("a=%d; b=%d\n",m["a"],m["b"])
    
    av,aexisted := m["a"]
    bv,bexisted := m["b"]
    fmt.Printf("a=%d, existed: %t; b=%d, existed: %t\n", av, aexisted, bv, bexisted)
}

map是无序的，所以当遍历一个map对象的时候，迭代的元素的顺序是不确定的，无法保证两次遍历的顺序是一样的，也不能保证和插入的顺序一直。所以，如果想要按照key的顺序获取map的值，需要先取出所有的key进行排序，然后按照这个排序的key依次获取对应的值。而如果想要保证元素有序，比如按照元素插入的顺序进行遍历，可以使用辅助的数据结构，比如orderedmap，来记录插入顺序。

总结

map的类型是map[key]，key类型的ke必须是可比较的，通常情况，会选择内建的基本类型，比如整数、字符串做key的类型。如果要使用struct作为key，要保证struct对象在逻辑上是不可变的。在Go语言中，map[key]函数返回结果可以是一个值，也可以是两个值。map是无序的，如果我们想要保证遍历map时元素有序，可以使用辅助的数据结构，例如orderedmap。

常见错误

第一种：未初始化

和slice或者Mutex、RWmutex等struct类型不同，map对象必须在使用之前初始化。如果不初始化就直接赋值的话，会出现panic异常，例如以下情况，m实力还没有初始化就直接进行操作会导致panic：

func main() {
    var m map[int]int
    m[100] = 100
}

解决办法就是在第2行初始化这个实例 （m:=make(map[int]int)）。

从一个nil的map对象中获取值不会panci，而且会得到零值，所以下面的代码不会报错：

func main() {
    var m map[int]int
    fmt.Println(m[100])
}

这样应该可以意识到map的初始化问题。但有时候map作为一个struct字段的时候，就很容易忘记初始化了。

type Counter struct {
    Website string
    Start time.Time
    PageCounters map[string]int
}

func main() {
    var c Counter
    c.Website = "baidu.com"
    
    c.PageCounters["/"]++
}

所以，一定要记得“初始化不能忘”，目前还没有检测的工具。

第二种：并发读写

map类型是容易发生并发访问问题的。不注意就容易发生程序运行时并发读写导致的panic。

Go语言内建的map对象不是线程安全的，并发读写的时候运行时会有检查，遇到并发问题就会导致panic。

例如：

func main() {
    var m = make(map[int],10) // 初始化一个map
    go func() {
        for {
            m[1] = 1 // 设置key
        }
    }()
    
    go func() {
        for {
            _ = m[2] // 访问这个map 
        }
    }
}

运行后根据错误信息可以快速定位出来是哪一行出现了问题。

如何实现线程安全的map类型？

避免map并发读写panic的方式之一就是加锁，考虑读写性能，可以使用读写锁提供性能。

加读写锁：扩展map，支持并发读写

比较高兴的是，原本Go还没有正式发布泛型特性，所以不能实现一个通用的支持泛型的加锁map。但是Go语言在2021.09.27 Go 1.18加入了泛型特性，当然也可以使用interface{}来模拟泛型写，但是这样就会很复杂，不如泛型方案更直接、性能更好。

map类型为例，演示利用读写锁实现线程安全的map[int]int 类型：

// RWMap 一个读写锁保护的线程安全的map
type RWMap struct { // 读写锁保护下面的map字段
   sync.RWMutex
   m map[int]int
}

// NewRWMap 新建一个RWMap
func NewRWMap(n int) *RWMap  {
   return &RWMap{
      m: make(map[int]int, n),
   }
}

func (m *RWMap) Get(k int) (int, bool)  {
   m.RLock()
   defer m.RUnlock()
   v, existed := m.m[k]  // 设置一个键值对
   return v,existed
}

func (m *RWMap) Set(k int, v int) { // 设置一个键值对
   m.Lock()            // 锁保护
   defer m.Unlock()
   m.m[k] = v
}

func (m *RWMap) Delete(k int)  {  // 删除一个键
   m.Lock()                     // 锁保护
   defer m.Unlock()
   delete(m.m, k)
}

func (m *RWMap) Len() int  {  // map的长度
   m.RLock()           // 锁保护
   defer m.RUnlock()
   return len(m.m)
}

func (m *RWMap) Each(f func(k, v int) bool)  {  // 遍历map
   m.RLock()   // 遍历期间一直持有读锁
   defer m.RUnlock()

   for k, v := range m.m {
      if !f(k, v){
         return
      }
   }
}

分片加锁：更高效的并发map

虽然使用读写锁可以提供线程安全的map，但是在大量并发读写的情况下，锁的竞争会非常激烈。锁是性能下降的万恶之源之一。

在并发编程中，一条原则就是尽量减少锁的使用。一些单线程单进程的应用（比如redis等），基本上不需要使用锁去解决并发线程访问的问题，所以可以取得很高的性能。但是对于Go开发的应用程序，并发是常用的一个特性，这种情况下，能做的就是，尽量减少锁的粒度和锁的持有时间。

当然，可以优化业务处理的代码，以此来减少锁的持有时间，比如将串行的操作编程并行的子任务执行。这次的重点是对同步原语的优化，如何减少锁的粒度。

减少锁的粒度常用的方法就是分片（Shard），将一把锁分成几把锁，每个锁控制一个分片。Go知名的分片并发map的实现是orcaman/concurrent-map。

它默认采用32个分片，GetShard是一个关键的方法，能够根据key计算出分片索引。

var SHARD_COUNT = 32

// ConcurrentMap 分页SHARD_COUNT个分片的map
type ConcurrentMap []*ConcurrentMapShared

type ConcurrentMapShared struct {
   items map[string]interface{}
   sync.RWMutex // Read Write mutex, guards access to internal map.
}

// New 创建并发map
func New() ConcurrentMap {
   m := make(ConcurrentMap, SHARD_COUNT)
   for i := 0; i < SHARD_COUNT; i++ {
      m[i] = &ConcurrentMapShared{items: make(map[string]interface{})}
   }
   return m
}

func (m ConcurrentMap) GetShard(key string) *ConcurrentMapShared  {
   return m[uint(fnv32(key))%uint(SHARD_COUNT)]
}

增加或者查询的时候，首先根据分片索引得到分片对象，然后对分片对象加锁进行操作：

func (m ConcurrentMap) Set(key string, value interface{}) {
    // 根据key计算出对应的分片
    shard := m.GetShard(key)
    shard.Lock() // 对这个分片加锁，执行业务操作
    shard.items[key] = value
    shard.Unlaock()
}

func (m ConcurrentMap) Get(key string) (interface{}, bool) {
    // 根据key计算出对应的分片
    shard := m.GetShard(key)
    shard.Rlock()
    // 从这个分片读取key的值
    val, ok := shard.items[key]
    shard.RUnlock()
    return val, ok
}

除了GetShard方法，ConcurrentMap还提供了很多其他的方法。这些方法都是通过计算相应的分片实现的，目的是保证把锁的粒度限制在分片上。

golang 并发编程 操作系统 map 加锁
上一篇: 【并发编程】Once 基本用法和如何实现以及常见错误
下一篇: 【并发编程】Mutex （互斥锁）发展分析

继续阅读