对于哈希表( hash table ), 实现了 key-value 之间的映射关系, 主要提供的方法包括Add, Lookup, Delelte 等. 因为哈希表是一种基础的数据结构, 每个 key 都会有一个唯一的索引值, 通过索引值可以很快地找到对应的值, 所以使用它进行数据的插入和读取是很快的. Go 语言本身就内建了这样数据结构, 就是 map 数据类型

Go 语言内建的 map 类型如下:

map[K]V

其中, key 类型的 K 必须是可比较的( comparable ), 也就是可以通过 == 和 ≠ 操作符进行比较; V的值和类型可以是任意类型, 或者为 nil. 在 Go 语言中, 布尔, 整数, 浮点数, 复数, 字符串, 指针, Channel, 接口都是可以比较的, 包含可比较类型元素的 struct 和数组也是可比较的, 而 slice, map, 函数值都是不能比较的.

通常情况下, 会选择内建的基本类型, 比如整数, 字符串作为 key 的类型, 因为这个最方便, 值不可变, 也不容易出错. 而使用 struct 作为 key 的类型, 如果 struct 的某个字段值被修改了, 那么在查询 map 时将无法获取它添加的值.

import "fmt"

// struct 作为 map 的 key
type mapKey struct {
	key int
}

func Run() {
	m := make(map[mapKey]string)
	key := mapKey{10}

	m[key] = "hello"
	fmt.Printf("m[key]=%s\\n", m[key])

	// 修改 key 的字段值后再次查询 map, 将无法获取刚才添加的值
	key.key = 100
	fmt.Printf("再次查询 m[key]=%s\\n", m[key])
}

如果使用 struct 作为 key 的类型, 则需要保证 struct 对象在逻辑上是不可变的.

在 Go 语言中, map[key] 函数返回结果可以是一个值, 也可以是两个值, 原因在于: 如果获取一个不存在的 key 对应的值, 则会返回零值, 为了区分真正的零值和 key 不存在的这两种情况, 可以根据第二个返回值来判断

即使同一个 map 没有发生改变, 每次遍历时顺序也可能不一样, 所以在遍历一个 map 对象时, 迭代的元素的顺序是不确定, 这就无法保证两次遍历的顺序是一样的, 也不能遍历的顺序和插入顺序一致.

因此如果想要按照 key 的顺序获取 map 的值, 则需要先取出所有的 key 进行排序, 然后按照排序后的key 依次获取对应的值. 而如果保证元素有序, 比如按照元素插入的顺序进行遍历, 则可以使用辅助的数据结构, 比如 orderedmap, 来记录插入顺序.

func Run() {
	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 的两种常见错误

1. 未初始化 与 slice 或者 Mutex, RWMutex 等 struct 类型不同, map 对象必须在使用之前初始化. 如果不初始化就直接赋值的话, 则会出现 panic 异常.

   func main() {
   	var m map[int]int // m 没有被初始化
   	m[100] = 100
   }
   

2. 并发读/写

   Go 内建的 map 对象不是 线程(goroutine)安全的, 并发读/写的时候运行时会有检测, 遇到并发问题就会导致 panic

   // fatal error: concurrent map read and map write
   func Run() {
   	m := make(map[int]int, 10)
   	go func() {
   		for {
   			m[1] = 1
   		}
   	}()
   
   	go func() {
   		for {
   			_ = m[2]
   		}
   	}()
   
   	select {}
   }
   

   对 map 的并发迭代访问和写也会导致 panic

   // fatal error: concuttent map iteration and map write
   func Run() {
   	var m = make(map[int]int, 10)
   	go func() {
   		for {
   			m[1] = 1
   		}
   	}()
   
   	go func() {
   		for {
   			for k, v := range m {
   				_, _ = k, v
   			}
   		}
   	}()
   
   	select {}
   }
   

   加读写锁: 扩展 map, 支持并发读/写

   避免 map 并发读/写 panic 的方法之一就是加锁. 考虑读/写性能, 可以使用读写锁以提高性能

   import "sync"
   
   type RWMap[K comparable, V any] struct {
   	m map[K]V
   	sync.RWMutex
   }
   
   func NewRWMap[K comparable, V any]() *RWMap[K, V] {
   	return &RWMap[K, V]{m: make(map[K]V)}
   }
   
   func (m *RWMap[K, V]) Get(k K) (V, bool) {
   	m.RLock()
   	defer m.RUnlock()
   	v, existed := m.m[k]
   	return v, existed
   }
   
   func (m *RWMap[K, V]) Set(k K, v V) {
   	m.Lock()
   	defer m.Unlock()
   	m.m[k] = v
   }
   
   func (m *RWMap[K, V]) Delete(k K) {
   	m.Lock()
   	defer m.Unlock()
   	delete(m.m, k)
   }
   
   func (m *RWMap[K, V]) Len() int {
   	m.RLock()
   	defer m.RUnlock()
   	return len(m.m)
   }
   
   func (m *RWMap[K, V]) Each(f func(k K, v V) bool) {
   	m.RLock()
   	defer m.RUnlock()
   
   	for k, v := range m.m {
   		if !f(k, v) {
   			return
   		}
   	}
   }
   

   对于 map 对象的操作可分为两类, 其中查询和遍历可以被看作读操作, 增加,修改和删除可以看作写操作. 唯一麻烦在于不能使用 for-range 进行遍历, 提供了 Each 方法进行安全的遍历

   Go 官方在 Go 1.9 中增加了一个线程安全的 map, 也就是 sync.map, 在一些场景使用它可以提高性能.

   sync.Map 的使用方法

   sync.Map 并不是用来替换内建的 map 类型的, 它只能被应用在一些特殊场景.

   • 在只会增长的缓存系统中, 一个 key 只被写入一次而被读很多次
   • 多个 goroutine 为不相交(disjoint) 的键集读, 写和重写键值对.

   这两个场景说的比较笼统, 而且其中还包含了一些特殊的情况. 因此建议针对自己的场景做性能评测, 如果确实能够显著提高性能, 则再使用 sync.Map

   sync.Map 提供了 9 个方法, 可以把它们归为三类

   • 读操作
   1. Load(key any) (value any, ok bool): 读取一个键对应的值 1. Range(f func(key, value any) bool): 遍历 map
   • 写操作
   1. Store(key, value any): 存储或者更新一个键 1. Delete(key any): 删除一个键 2. Swap(key, value any) (previous any, loaded bool) : 替换一个键, 并把以前的结果返回. 如果这个键不存在, 则 loaded 返回 false, 但新值还是设置成功了

   • 读/写操作

     1. ComareAndDelete(key, old any) (deleted bool): 如果所提供的值和旧值相等, 则删除这个键
     2. CompareAndSwap(key, old, new any) bool : CAS操作, 如果所提供的值和旧值相等, 则设置新值
     3. LoadAndDelete(key any) (value any, loaded bool): 返回并删除一个键, 如果这个建不存在, 则 loaded 返回 false
     4. LoadOrStore(key, value any) (actual any, loaded bool): 返回一个键, 如果这个键不存在, 则 loaded 返回 false, 并返回所提供的值, 否则返回以前的值

     import (
     	"fmt"
     	"sync"
     )
     
     func Run4() {
     	var wg sync.WaitGroup
     	var m sync.Map
     
     	// 并发写
     	wg.Add(5)
     	for i := 0; i < 5; i++ {
     		i := i
     		go func() {
     			m.Store(i, fmt.Sprintf("test #%d", i))
     			wg.Done()
     		}()
     	}
     	wg.Wait()
     	fmt.Println("stroe done")
     
     	// 并发读
     	wg.Add(5)
     	for i := 0; i < 5; i++ {
     		i := i
     		go func() {
     			t, _ := m.Load(i)
     			fmt.Println("for loop: ", t)
     			wg.Done()
     		}()
     	}
     	wg.Wait()
     
     	// 遍历, 也是线程安全
     	m.Range(func(k, v any) bool {
     		fmt.Println("range: ", v)
     		return true
     	})
     }
     

   sync.Map 的实现

   • 以空间换时间, 通过冗余的两个数据结构( 只读的 read 字段, 可写的 dirty 字段) , 来减少加锁对性能的影响
   • 对只读字段(read) 的操作不需要加锁. 优先从 read 字段读取, 更新, 删除.
   • 动态调整. 未命中的次数多了之后, 将 dirty 数据提升为 read 数据, 避免总是从 dirty 中加锁读取
   • 双重检查. 加锁之后, 还要再检查 read 字段, 确定所查询的键值真的不存在, 才操作 dirty 字段
   • 延迟删除. 删除一个键值只是打上标记, 只有在创建 dirty 字段的时候才释放这个键, 然后, 只有在 dirty 数据被提升 read 数据的时候, read 字段才会释放这个键

   type Map struct {
   	mu Mutex // 万不得已才使用的锁
   	
   	// 实际上是一个"只读" 的 map, 访问它的元素不需要加锁, 所以很快
   	read atomic.Pointer[readOnly]
   
   	// 包含 map 中所有的元素, 包括新增的元素
   	// 访问 dirty 字段必须加锁, 当未命中达到一定的次数后会把它转为 read 字段
   	dirty map[any]*entry
   }
   
   type readOnly struct {
   	m  map[any]*entry
   	amended bool // 如果有 dirty 数据, 则返回 true(有些数据只在 dirty 字段中, 不在这个 m)
   }
   
   // expunged 标记一个键值对已经从 dirty 字段中删除了, 将它的值暂时设置为 expunged 这个值
   // 标识出来
   var expunged = new(any)
   
   // entry 代表一个键值
   type entry struct { p unsafe.Pointer }
   

   对 “只读”是加了引号, 其实更新或者删除 readOnly 元素也是可以的, 都不涉及锁. 如果 dirty 字段非 nil 的话, map 的 read 字段和 dirty 字段将会包含相同的非 expunged 的项. 所以, 如果通过 read 字段更改这个项的值, 从 dirty 字段也会读取到这个项的新值, 因为本来它们指向的就是同一个地址.

   dirty 字段包含重复项的好处就是, 一旦未命中次数达到阈值, 需要将 dirty 数据提升为 read 数据的话, 只需要简单地把 dirty 对象设置为 read 对象即可. 不好的则是创建新的 dirty 对象需要逐条遍历 read 数据, 把非 expunged 的项复制到 dirty 对象中

   重点关注 Swap, Load 和 Delete 这三个核心方法, 这些方法都是从 read 字段开始处理的, 因为读取 read 字段不用加锁.

   func (m *Map) Swap(key, value any) (previous any, loaded any) {
   	read := m.loadReadOnly() // 1
   	if e, ok := read.m[key]; ok { // 2
   		if v, ok := e.trySwap(&value); ok { // 3
   			if v == nil {
   				return nil, false
   			}
   			return *v, true
   		}
   	}
   	m.mu.Lock() // 4
   	read = m.loadReadOnly() // 5
   	if e, ok := read.m[key]; ok { // 6
   		if e.unexpungeLocked() {
   			m.dirty[key] = e
   		}
   		if v := e.swapLocked(&value); v != nil {
   			loaded = true
   			previous = *v
   		}
   	} else if e, ok := m.dirty[key]; ok { // 7
   		if v := e.swapLocked(&value); v != nil {
   			loaded = true
   			previous = *v
   		}
   	} else { // 8
   		if !read.amended { // 9
   			// We're adding the first new key to the dirty map.
   			// Make sure it is allocated and mark the read-only map as incomplete.
   			m.dirtyLocked() // 10
   			m.read.Store(&readOnly{m: read.m, amended: true})
   		}
   		m.dirty[key] = newEntry(value)
   	}
   	m.mu.Unlock()
   	return previous, loaded
   }
   

   1行读取 read 字段, 原子操作, 没有使用到锁 mu. 2 行检查 read 字段是否包含这个 key, 如果包含, 则直接尝试交换(3 行; 如果键不存在, 那就是新增). 注意, 这里还是对 read 字段的操作, 虽然是写操作, 但是不需要加锁

   如果 read 字段不存在, 那么还要检查 dirty 字段. 这个时候就需要在 4 行加锁了, 一旦进入这里, 性能可能就会受到影响; 5 行再次读取 read 字段, 要进行双重检查. 6行进行双重检查, 如果此时 read 字段已经包含整个 key, 则进行更新或者交换.

   7 行处理只存在于 dirty 字段中的键, 这个时候交换就好.

   8 行是 read 字段和 dirty 字段都不存在的1场景, 这是新的键, 直接加到 dirty 字段中就好. 但这个时候 dirty 字段可能是空的, 需要把 dirty 字段建立起来, 也就是从 read 字段中读取现有的数据, 包括删除的 key 要被标记成 expunged. dirty 字段建立好后, 把 read.amended 设置为 true. 之后, 在 dirty 字段中加入这个键值对.

   Load 方法用来读取一个 key 对应的值. 它也是从 read 字段开始处理的 一开始并不需要加锁

   func (m *Map) Load(key any) (value any, ok bool) {
   	read := m.loadReadOnly()
   	e, ok := read.m[key]
   	if !ok && read.amended { // 1
   		m.mu.Lock()
   		read = m.loadReadOnly()
   		e, ok = read.m[key]
   		if !ok && read.amended { // 2
   			e, ok = m.dirty[key]
   			m.missLocked() // 3
   		}
   		m.mu.Unlock()
   	}
   	if !ok {
   		return nil, false
   	}
   	return e.load()
   }
   
   func (m *Map) missLocked() {
   	m.misses++
   	if m.misses < len(m.dirty) { // 4
   		return
   	}
   	m.read.Store(&readOnly{m: m.dirty}) // 5
   	m.dirty = nil
   	m.misses = 0
   }
   

   1 行是键不在 read 字段的场景, 否则直接读取出来返回

   如果键不在 read 字段中, 则需要检查 dirty 字段, 这个时候就要加锁. 这时还要进行双重检查. 再次检查 read 字段, 如果其中存在键的话, 则直接读取出来返回; 否则, 在 2行进行检查.

   如果 dirty 字段中存在键, 那么也是读取出来返回, 否则就的确不存在了. 只要进入 dirty 字段中, misses 就会加 1

   misses 增加后, 需要看它是否达到了阈值, 如果达到了 dirty 字段的数量, 则认为未命中次数太多了, 会影响性能, 就在 5 行把 dirty 数据提升为 read 数据, 然后将 dirty 字段置为 nil, 将 misses 置为0, 重新开始

   func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
   	read := m.loadReadOnly()
   	e, ok := read.m[key]
   	if !ok && read.amended {
   		m.mu.Lock()
   		read = m.loadReadOnly()
   		e, ok = read.m[key]
   		if !ok && read.amended {
   			e, ok = m.dirty[key]
   			delete(m.dirty, key)
   			// Regardless of whether the entry was present, record a miss: this key
   			// will take the slow path until the dirty map is promoted to the read
   			// map.
   			m.missLocked()
   		}
   		m.mu.Unlock()
   	}
   	if ok {
   		return e.delete()
   	}
   	return nil, false
   }
   
   // Delete deletes the value for a key.
   func (m *Map) Delete(key any) {
   	m.LoadAndDelete(key)
   }
   
   

   这个 Delete 方法实现几乎和 Load 方法一样, 处理流程完全一致, 只不过它把先前的读取数据改成删除数据.

   sync.Map 没有 Len 这样查询 sync.Map 包含的项目数量的方法, 因此你想要得到 sync.Map 的项目数量的话, 则可能不得不通过 Range 逐个计数.

   https://github.com/golang/go/blob/master/src/sync/map.go

   高效的并发 map

   在并发编程中 ,在大量的并发读/写的情况下, 使用读写锁的 map , 对锁竞争会非常激烈, 影响其性能, 因此尽量减少锁的使用避免影响其性能.. 但是在 Go 语言开发的应用程序中, 并发是常用的一个特性, 因此尽量减小锁的粒度和减少对锁的持有时间.

   减小锁的粒度常用的方法就是分片(shard), 将一个锁分为多个锁, 每个锁都控制一个分片. 如 orcaman/concurrent-map

   但也有一些 lock-free( 无锁并发 )线程安全的 map, 提高性能, 如: cornelk/hashmap 或 alphadose/haxmap