go 的 map 与 sync.map

参考解析

题目来源: 字节跳动

答案：

Go语言中的Map是一种无序的键值对集合。Map可以通过key在O(1)的时间复杂度内进行查询、更改、删除操作，key到value间的映射由哈希函数实现。Go的Map相当于C++的Map，Java的HashMap，Python的Dict。

map

操作

  1. // 标准声明方法 cap可选
  2. var map_variable map[key_data_type]value_data_type
  3. map_variable = make(map[key_data_type]value_data_type, [cap])
  4. // 或者使用make函数 声明时直接初始化 cap可选
  5. map_variable := make(map[key_data_type]value_data_type [cap])
  6. // 访问 添加
  7. map_variable[key] = value
  8. // 删除
  9. delete(map_variable, key)

源码

  1. // A header for a Go map.
  2. type hmap struct {
  3.     // Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
  4.     // Make sure this stays in sync with the compiler's definition.
  5.     count     int // # live cells == size of map.  Must be first (used by len() builtin)
  6.     flags     uint8
  7.     B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
  8.     noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
  9.     hash0     uint32 // hash seed
  10.     buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
  11.     oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
  12.     nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
  13.     extra *mapextra // optional fields
  14. }
  16. // mapextra holds fields that are not present on all maps.
  17. type mapextra struct {
  18.     // If both key and elem do not contain pointers and are inline, then we mark bucket
  19.     // type as containing no pointers. This avoids scanning such maps.
  20.     // However, bmap.overflow is a pointer. In order to keep overflow buckets
  21.     // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
  22.     // overflow and oldoverflow are only used if key and elem do not contain pointers.
  23.     // overflow contains overflow buckets for hmap.buckets.
  24.     // oldoverflow contains overflow buckets for hmap.oldbuckets.
  25.     // The indirection allows to store a pointer to the slice in hiter.
  26.     overflow    *[]*bmap
  27.     oldoverflow *[]*bmap
  28.     // nextOverflow holds a pointer to a free overflow bucket.
  29.     nextOverflow *bmap
  30. }
  32. // A bucket for a Go map.
  33. type bmap struct {
  34.     // tophash generally contains the top byte of the hash value
  35.     // for each key in this bucket. If tophash[0] < minTopHash,
  36.     // tophash[0] is a bucket evacuation state instead.
  37.     tophash [bucketCnt]uint8
  38.     // Followed by bucketCnt keys and then bucketCnt elems.
  39.     // NOTE: packing all the keys together and then all the elems together makes the
  40.     // code a bit more complicated than alternating key/elem/key/elem/... but it allows
  41.     // us to eliminate padding which would be needed for, e.g., map[int64]int8.
  42.     // Followed by an overflow pointer.
  43. }
  44. // 基于go 1.17

map的一些关键点

  1. Map哈希冲突解决

当两个或者两个以上的元素被放在同一个bucket中，表示已经发生了哈希冲突。由于一个bucket最多储存8个键值对，bucket已满时会创建新的bucket，然后将旧的bucket和新的bucket使用链表连接起来，overflow存的即为新的bucket的地址。

  1. Map扩容机制

源码中有负载因子load factor，用途是评估哈希表当前的时间复杂度，其与哈希表当前包含的键值对数、桶数量等相关。如果负载因子越大，则说明空间使用率越高，但产生哈希冲突的可能性更高。而负载因子越小，说明空间使用率低，产生哈希冲突的可能性更低。

loadfactor = key_num / bucket_num (默认6.5)

除了负载因子，Go语言还有溢出桶的概念。结合源码我们发现，每个桶最多可以存储8个元素，如果超过8个，会使用定义相同的溢出桶来存储或者扩容。溢出桶overflow buckets过多的判定有一个固定值的阈值2^15 = 32768。

  1. Map的扩容原理
    1. 触发loadfactor的最大值，负载因子已达到当前界限。这种情况表示容量不足，直接扩容为原来大小的二倍
    2. 溢出桶overflow buckets过多，这种情况指的是桶分配了很多，但实际用到的桶的数量很少，即key过于分散，这时扩容指的是内存整理，把相近的key集中到一个桶，给另外的桶腾出空间。

扩容伴随着数据迁移，Go语言的map采用的是渐进式迁移的策略，不是一次性迁移所有的数据，每次最多移动两个桶，每次调用增删改都会查看是否迁移完毕，如果没有迁移完毕就尝试继续搬迁。渐进式迁移能使得数据迁移的均摊时间复杂度降低到O(1)。

  1. 切片作为map的值

特别注明，Go语言中可以使用切片作为map的值，这种情况下一个key对应多个value。

sync.Map

Go语言中的Map同样不是线程安全的。Go所提供的线程安全的版本是位于sync包下的Map。

如果并发地读写普通的Map，会报错误fatal error: concurrent map read and map write，map内部会对并发操作进行检查并提前发现。

你可以在Map上加锁，但这样性能不高。Go语言在1.9版本提供了效率较高的sync.Map

sync.Map有以下特性：

  1. 无需初始化，直接声明即可使用
  2. sync.Map不能像map那样读写，而是使用sync.Map提供的方法，Store(key, value)用于存储，Load(key)用于取值，Delete(key)表示删除。
  3. 遍历操作需要使用Range()函数配合一个回调函数，通过回调函数返回内部遍历出来的值。range参数中回调函数的返回值在需要继续迭代遍历时，返回true，终止迭代遍历时，返回false。如果成功读取Load()函数返回两个值，key对应的value以及ture表示成功读取；如果map中没有这个key，则返回nil表示失败的false。
  1. package main
  3. import (
  4.     "fmt"
  5.     "sync"
  6. )
  8. func main() {
  9.     var capId sync.Map
  11.     capId.Store("Beijing", 88)
  12.     capId.Store("London", 80)
  13.     capId.Store("Tokyo", "89") // 注意value是字符串
  15.     fmt.Println(capId.Load("Beijing"))
  16.     fmt.Println(capId.Load("Tokyo"))
  18.     fmt.Println()
  20.     value, _ := capId.Load("Beijing")
  21.     fmt.Println(value)
  23.     fmt.Println()
  25.     capId.Delete("Tokyo")
  26.     capId.Range(func(k, v interface{}) bool {
  27.         fmt.Printf("%s对应的id是%d\n", k, v)
  28.         return true
  29.     })
  30. }
  32. // output:
  34. // 88 true
  35. // 89 true
  36. // <nil> false
  37. // 
  38. // 88
  39. // 
  40. // Beijing对应的id是88
  41. // London对应的id是80

注意

  1. sync.Map因为没有初始化过程，无法指定key和value的数据类型，所以干脆就支持了所有的数据类型。它不限制一个map内所有的key和value都必须是相同的类型。
  2. sync.Map 没有提供获取 map 数量的方法，替代方法是在获取 sync.Map 时遍历自行计算数量，sync.Map 为了保证并发安全有一些性能损失，因此在非并发情况下，使用 map 相比使用 sync.Map 会有更好的性能。