1.map的基本使用

 map[K]V

注意点:

key类型必须是可比较的(comparable),也就是可以使用 ==和 !=操作符进行比较
可比较的类型有 bool,整数,浮点数,复数,字符串,指针,channel,接口,包括可比较元素的struct和数组都是可比较的
slice,map,函数值都是不可比较的
如果使用struct做为key时,需要注意,如果struct中的某个值修改了,在map中是无法获取到的,如下代码:

type mapKey struct {
	key int
}

func TestPool(t *testing.T) {
	var m = make(map[mapKey]string)
	var key = mapKey{10}
	m[key] = "hello"
	t.Log(m[key])
	key.key = 100 //重新给key赋值
	t.Log(m[key]) //这里无法获取到相关值
}

2.map的返回值

 v,ok :=map[key]

说明:

map[key]函数返回结果可以是一个值,也可以两个值
区分真正的零值和key不存在这两种情况,需要根据第二个返回值来区分,如果第二值返回true,说明值存在,为false,则说明key不存在
map是无序的,如里要对map排序,可以根据 map里的key先进行排序,再根据key,输出map的值,如下排序

func TestMapSort(t *testing.T) {
	var m = make(map[int]int)
	var s []int
	for i := 0; i < 10; i++ {
		m[i] = i
		s = append(s, i)
	}
	sort.Ints(s)
	t.Log(s)
	for i := range s {
		t.Logf("val:%d", m[i])
	}
}

3.使用map的常见错误

3.1 未初始化

使用map必须使用make初始化,否则赋值时报panic
从一个nil的map对象中获取数据时,不会panic,会得到零值

3.2 并发读写

go内建的map对象不是线程安全的,有并发问题,直接panic,如下代码,会报fatal error: concurrent map read and map write

 func TestGo(t *testing.T) {
     var m = make(map[int]int, 10)
     go func() {
         for {
             m[1] = 1
         }
     }()
     go func() {
         for {
             _ = m[2]
         }
     }()
     select {}
 }

4. 实现线程安全的map

自己实现的线程安全的map

 type RWMap struct {
     mu sync.RWMutex
     m  map[int]int
 }
 
 func NewRWMap(n int) *RWMap {
     return &RWMap{
         m: make(map[int]int, n),
     }
 }
 func (r *RWMap) Get(k int) (int, bool) {
     r.mu.RLock()
     defer r.mu.RUnlock()
     v, ok := r.m[k]
     return v, ok
 }
 func (r *RWMap) Set(k, v int) {
     r.mu.Lock()
     defer r.mu.Unlock()
     r.m[k] = v
 }
 func (r *RWMap) Delete(k int) {
     r.mu.Lock()
     defer r.mu.Unlock()
     delete(r.m, k)
 }
 func (r *RWMap) Len() int {
     r.mu.RLock()
     defer r.mu.RUnlock()
     return len(r.m)
 }
 func (r *RWMap) Each(f func(k, v int) bool) {
     r.mu.RLock()
     defer r.mu.RUnlock()
     for k, v := range r.m {
         f(k, v)
     }
 }
 //测试
 func TestSafeMap(t *testing.T) {
     m := NewRWMap(10)
     go func() {
         for {
             m.Set(1, 100)
             time.Sleep(time.Second)
         }
     }()
     go func() {
         for {
             v, _ := m.Get(1)
             fmt.Println(v)
             time.Sleep(time.Second)
         }
 
     }()
     select {}
 }

5.更高效的并发map: 分片加锁

原则: 尽量减少锁的粒度和锁的持有时间

常用的分片加锁map 第三方库 orcaman/concurrent-map

 //使用方法
 import (
     "github.com/orcaman/concurrent-map/v2"
 )
 //创建一个map
     m := cmap.New[string]()
 
     // 设置值
     m.Set("foo", "bar")
 
     // 获取值
     bar, ok := m.Get("foo")
 
     // 删除一个值
     m.Remove("foo")

6.Go内置的线程安全map

6.1 常用方法

Store(key, value any)
Load(key any)
Delete( key any)
LoadOrStore(key, value any)
LoadAndDelete(key any)
Range(f func(key, value any) bool)

6.2 源码分析

 type Map struct {
     mu Mutex
 //基本上你可以把它看成一个安全的只读的map
     //它包含的元素其实也是通过原子操作更新的，但是已删除的entry就需要加锁操作了
     read atomic.Value // readOnly
 //包含需要加锁才能访问的元素
 // 包括所有在read字段中但未被expunged（删除）的元素以及新加的元素
 
     dirty map[any]*entry
 
 //记录从read中读取miss的次数，一旦miss数和dirty长度一样了，就会把dirty提升为read
     misses int
 }
 type readOnly struct {
     m       map[any]*entry
     amended bool // 当dirty中包含read没有的数据时为true，比如新增一条数据.
 }
 //代表一个值
 type entry struct {
     
     p unsafe.Pointer // *interface{}
 }

说明:

为了减少锁对性能的影响,这里采用的空间换时间,通过冗余的两个数据结构 (只读的read 字段,可写的dirty),对只读字段操作不用加锁

优先从read字段读取,更新,删除,对read操作不用加锁
动态调整,如里miss次数多了之后,将dirty数据提升为read,避免总是对dirty加锁
double-checking操作,加锁之后还要再检查read字段,只有真的不存在后才操作dirty字段
延迟删除,删除一个键时,只是打标记,只有把dirty提升到read字段的时候,才会清理删除的数据

Store方法

 func (m *Map) Store(key, value any) {
     read, _ := m.read.Load().(readOnly)
     //如果read中有值,说明是更新,直接通过cas操作即可
     if e, ok := read.m[key]; ok && e.tryStore(&value) {
         return
     }
 
     m.mu.Lock()
     //如里read中不存在或cas时失败
     read, _ = m.read.Load().(readOnly)
     if e, ok := read.m[key]; ok { //双检查,看read是否已经存在
         if e.unexpungeLocked() {
     //此项目先前已经被删除了，通过将它的值设置为nil，标记为unexpunged
             m.dirty[key] = e
         }
         e.storeLocked(&value)
     } else if e, ok := m.dirty[key]; ok { // 如果dirty中有此项 直接更新
         e.storeLocked(&value)
     } else {
         //到这里说明是一个新key
         if !read.amended { //如里dirty为nil
         //需要创建dirty对象，并且标记read的amended为true,
         // 说明有元素它不包含而dirty包含
             m.dirtyLocked()
             m.read.Store(readOnly{m: read.m, amended: true})
         }
         m.dirty[key] = newEntry(value) //将新值增加到dirty对象中
     }
     m.mu.Unlock()
 }
 func (m *Map) dirtyLocked() {
     if m.dirty != nil { //如果dirty字段已经存在，不需要创建了
         return
     }
 
     read, _ := m.read.Load().(readOnly) // 获取read字段
     m.dirty = make(map[any]*entry, len(read.m))
     for k, e := range read.m { // 遍历read字段
         if !e.tryExpungeLocked() { // 把非punged的键值对复制到dirty中
             m.dirty[k] = e
         }
     }
 }

Load 方法

 func (m *Map) Load(key any) (value any, ok bool) {
     read, _ := m.read.Load().(readOnly) //首先从read处理
     e, ok := read.m[key]
     if !ok && read.amended { //如果不存在并且dirty不为nil(有新的元素)
         m.mu.Lock()
 // 双检查，看看read中现在是否存在此key
         read, _ = m.read.Load().(readOnly)
         e, ok = read.m[key]
         if !ok && read.amended { //依然不存在，并且dirty不为nil
             e, ok = m.dirty[key] // 从dirty中读取
             // 不管dirty中存不存在，miss数都加1
             m.missLocked()
         }
         m.mu.Unlock()
     }
     if !ok {
         return nil, false
     }
     return e.load() //返回读取的对象，e既可能是从read中获得的，也可能是从dirty中获得的
 }
 func (m *Map) missLocked() {
     m.misses++ // misses计数加一
     if m.misses < len(m.dirty) { // 如果没达到阈值(dirty字段的长度),返回
         return
     }
     m.read.Store(readOnly{m: m.dirty}) //把dirty字段的内存提升为read字段
     m.dirty = nil // 清空dirty
     m.misses = 0 // misses数重置为0
 }

Delete方法

 func (m *Map) Delete(key any) {
     m.LoadAndDelete(key)
 }
 func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
     read, _ := m.read.Load().(readOnly)
     e, ok := read.m[key]
     if !ok && read.amended {
         m.mu.Lock()
         //双检查
         read, _ = m.read.Load().(readOnly)
         e, ok = read.m[key]
         if !ok && read.amended {
             e, ok = m.dirty[key]
             delete(m.dirty, key)
         // miss数加1
             m.missLocked()
         }
         m.mu.Unlock()
     }
     if ok {
         return e.delete()
     }
     return nil, false
 }