第7篇 Go映射(Map)实现原理与并发安全摘要Go语言Map底层基于哈希表实现采用拉链法解决哈希冲突本文深入讲解Map的扩容机制、并发安全问题以及sync.Map的适用场景帮助你避免生产环境的Map踩坑。去年我们组做了一个高并发的计数服务用Map来缓存用户的访问次数。上线第一天就收到了告警服务直接panic退出了。日志里赫然写着fatal error: concurrent map writes。我当时还纳闷Map不就是存个key-value嘛怎么还能把进程搞崩。后来才知道Go的原生Map根本不支持并发写。这事让我花了一整个晚上排查最后把原生Map换成了sync.Map才解决。今天我就把Map的底层原理和并发安全问题从头到尾捋一遍让你少走弯路。一、Map的基本用法Map是Go里最常用的数据结构之一用来存储键值对。声明和初始化的姿势有好几种直接看代码。packagemainimportfmtfuncmain(){// 第一种写法用make创建空Map// 这里指定了初始容量为10能减少扩容次数scores:make(map[string]int,10)// 往Map里塞数据scores[张三]95scores[李四]87// 第二种写法字面量初始化适合已知数据的情况ages:map[string]int{张三:25,李四:30,}// 读取Map的值如果key不存在会返回零值// 这里王五不存在返回0score:scores[王五]fmt.Println(王五的分数,score)// 输出 0// 判断key是否存在用逗号ok模式value,ok:scores[张三]ifok{fmt.Println(张三的分数,value)// 输出 95}// 删除某个keydelete(scores,李四)// 遍历Map注意遍历顺序是随机的forname,age:rangeages{fmt.Printf(%s今年%d岁\n,name,age)}}这里有个细节经常被忽略。Map的遍历顺序是随机的Go故意这么设计的防止你依赖遍历顺序。如果你需要有序遍历得自己把key取出来排序再遍历。二、Map的底层实现原理Go的Map底层是一个哈希表用拉链法解决哈希冲突。说白了就是有一个桶数组每个桶里能装8个键值对。当发生哈希冲突时数据会被塞进同一个桶里。桶的结构大概是这样的。每个桶有一个头部信息记录桶里装了多少个key后面跟着8个key、8个value还有一个overflow指针指向溢出桶。当一个桶装满8个key之后新来的key会被放到溢出桶里用链表串起来。packagemainimportfmtfuncmain(){// 演示Map扩容对性能的影响// 预分配容量 vs 动态扩容// 不预分配Map会多次扩容m1:make(map[int]int)fori:0;i1000000;i{m1[i]i}// 预分配容量只做一次分配m2:make(map[int]int,1000000)fori:0;i1000000;i{m2[i]i}fmt.Println(两个Map大小,len(m1),len(m2))// 负载因子 元素数量 / 桶数量// Go的默认负载因子阈值是6.5// 当负载因子超过6.5或者溢出桶太多时触发扩容// 扩容有两种模式等量扩容和翻倍扩容}扩容机制是Map性能的关键。Go的Map在两种情况下会触发扩容。第一种是负载因子超过6.5这时会翻倍扩容桶数量乘以2。第二种是溢出桶太多这时做等量扩容桶数量不变但会把数据重新排列得更紧凑。扩容是渐进式的不是一次性搬完。每次操作Map的时候搬一点这样能把扩容的时间分摊到后续的读写操作中避免一次性卡顿太久。三、并发安全问题这就是我开头踩坑的地方。Go的原生Map不支持并发读写一旦多个goroutine同时写Map直接panic。packagemainimportsync// 这个程序会panic演示并发写Map的问题// 运行后能看到 fatal error: concurrent map writesfuncmain(){m:make(map[int]int)// 启动多个goroutine同时写Map// 这里用sync.WaitGroup等待所有goroutine完成varwg sync.WaitGroupfori:0;i100;i{wg.Add(1)gofunc(nint){deferwg.Done()m[n]n*2// 这一行在并发场景下会触发panic}(i)}wg.Wait()}解决并发写Map有两种主流方案。第一种是加互斥锁用sync.Mutex包一层。这种方式适合写多读少的场景。packagemainimport(fmtsync)// SafeMap 包装了一个带锁的MaptypeSafeMapstruct{mu sync.RWMutex// 读写锁读操作可以并发datamap[string]int// 内部存储用的原生Map}// NewSafeMap 创建一个线程安全的MapfuncNewSafeMap()*SafeMap{returnSafeMap{data:make(map[string]int),}}// Set 写入数据用写锁保护func(s*SafeMap)Set(keystring,valueint){s.mu.Lock()defers.mu.Unlock()s.data[key]value}// Get 读取数据用读锁保护允许多个goroutine同时读func(s*SafeMap)Get(keystring)(int,bool){s.mu.RLock()defers.mu.RUnlock()val,ok:s.data[key]returnval,ok}funcmain(){sm:NewSafeMap()varwg sync.WaitGroup// 并发写入这次不会panic了fori:0;i100;i{wg.Add(1)gofunc(nint){deferwg.Done()sm.Set(fmt.Sprintf(key%d,n),n)}(i)}wg.Wait()fmt.Println(写入完成Map大小,len(sm.data))}第二种是直接用sync.Map这是Go官方提供的并发安全Map。适合读多写少、key相对稳定的场景。packagemainimport(fmtsync)funcmain(){varm sync.Map// Store 写入数据m.Store(name,张三)m.Store(age,25)// Load 读取数据val,ok:m.Load(name)ifok{fmt.Println(name ,val)// 输出 name 张三}// LoadOrStore 原子地读取或写入// 如果key存在就返回现有值不存在就存入新值actual,loaded:m.LoadOrStore(name,李四)fmt.Println(actual ,actual,loaded ,loaded)// loaded为true说明key已存在返回的是旧值张三// Range 遍历m.Range(func(key,value any)bool{fmt.Printf(%v - %v\n,key,value)returntrue// 返回false可以提前终止遍历})// Delete 删除m.Delete(age)}sync.Map内部用了读写分离的设计读操作大部分情况不需要加锁所以读性能比加互斥锁的方案好。但写操作会涉及到dirty map的更新性能不如互斥锁方案。四、独家踩坑说个我踩过的坑。有一次我用sync.Map缓存用户session上线后发现内存一直涨GC了也降不下来。排查了好久才找到原因。sync.Map的Delete方法只是把entry标记为nil底层的dirty map里那个key还在。当大量的key被删除后sync.Map内部的dirty map会越来越大但这些key对应的value已经是nil了内存却没释放。解决办法是定期做一次全量重建。新建一个sync.Map把当前有效的数据搬过去旧的丢掉。另外如果你发现sync.Map的内存涨得快大概率是key的基数太大了这种场景sync.Map并不适合用普通的加锁Map反而更省内存。五、对比分析拿Go的Map跟Python的dict和Java的HashMap对比一下。Python的dict底层用开放寻址法Go用拉链法。Python的dict在CPython 3.6之后保证了插入顺序Go的Map遍历顺序是随机的。并发方面Python有GIL保护不会有并发panic的问题但性能也受限。Java的HashMap底层也是拉链法Java 8之后链表长度超过8会转红黑树Go没有这个优化溢出桶多了会触发等量扩容来整理。并发安全方面Java有ConcurrentHashMap分段锁设计并发性能很好。Go的sync.Map用的是读写分离加atomic设计思路完全不同。如果你需要极致的并发写性能Go里用分片加锁的方案比sync.Map更好就是把数据分到多个小Map里每个Map一把锁。六、总结Map的底层是哈希表加拉链法扩容是渐进式的。原生Map不支持并发写要么加锁要么用sync.Map。读多写少用sync.Map写多读多用分片加锁。下一篇我们聊Go结构体看看Go是怎么用组合代替继承来做面向对象的。