我正在参与「启航计划」

Go Map 的 11 连问，你顶得了嘛?准备了 Go 言语 Map 的 11 连问，相信大家看完必定会有帮助的。

  • 公众号：程序员回禄

1. Map 运用时需求留意哪些问题?

  • Map 的键有必要是可比较的类型，如整数、字符串和指针等，可是切片、函数和结构体等类型是不行比较的，因而不能用作键。
  • Map 中的元素是无序的，这意味着遍历 Map 时，元素的顺序可能会随机改动。
  • Map 的容量是动态变化的，它会主动调整容量以习惯新的元素。
  • 假如运用未初始化的 Map，会导致运行时错误。需求运用 make() 函数来初始化 Map。
  • Map 在并发环境下不是安全的。假如需求在并发环境下运用 Map，需求运用 sync 包中供给的锁机制来维护 Map。

2. Map 扩容是怎么完结的？

在 Go 中，Map 的内部完结是依据哈希表（hash table）的，因而，当 Map 中的键值对数量增加时，Map 会主动扩容以供给更多的存储空间。下面是 Go Map 扩容的详细步骤：

  • 当 Map 中的元素数量超过了负载因子（load factor）和哈希表容量的乘积时，map 就会触发扩容操作。在 Go 中，负载因子默以为 6.5。
  • Go Map 在扩容时会创立一个新的哈希表，并将本来的键值对从头散列到新的哈希表中。为了削减哈希冲突，新哈希表的容量是本来的两倍，而且容量必定是 2 的幂次方。
  • 在从头散列进程中，Go Map 会依据哈希值将本来的键值对分配到新哈希表中的对应方位上。假如两个键值对的哈希值相同，会运用链式哈希表（chained hash table）的办法进行处理，将它们放在同一个桶（bucket）中。
  • 一旦一切的键值对都现已从头散列到新的哈希表中，Go Map 就会将本来的哈希表开释掉，将新的哈希表作为 Map 的内部存储结构。

留意： 因为扩容操作可能会导致大量的从头散列操作，因而在扩容时可能会造成必定的功能影响。为了防止频频扩容，能够在创立 Map 时指定一个较大的容量，或许手动调用 runtime.GC() 来触发废物回收操作，以开释未运用的内存。

3. Map 的 panic 能被 recover 吗?

不能，并发读写 Map 也是很容易遇到的问题。如下代码能够验证：

packagemain
import(
"fmt"
)
funcfoo(){
deferfunc(){
iferr:=recover();err!=nil{
fmt.Println(err)
}
}()
varbar=make(map[int]int)
gofunc(){
deferfunc(){
iferr:=recover();err!=nil{
fmt.Println(err)
}
}()
for{
_=bar[1]
}
}()
for{
bar[1]=1
}
}
funcmain(){
foo()
fmt.Println("exit")
}

输出：

fatalerror:concurrentmapreadandmapwrite
goroutine18[running]:
runtime.throw({0x1021bdf62?,0x0?})
/opt/homebrew/Cellar/go@1.18/1.18.10/libexec/src/runtime/panic.go:992+0x50fp=0x14000046f70sp=0x14000046f40pc=0x10215f050
runtime.mapaccess1_fast64(0x0?,0x0?,0x1)
/opt/homebrew/Cellar/go@1.18/1.18.10/libexec/src/runtime/map_fast64.go:22+0x174fp=0x14000046f90sp=0x14000046f70pc=0x10213eaa4
main.foo.func2()
/Users/xxx/go/learn/main.go:43+0x50fp=0x14000046fd0sp=0x14000046f90pc=0x1021b8a00
runtime.goexit()
/opt/homebrew/Cellar/go@1.18/1.18.10/libexec/src/runtime/asm_arm64.s:1270+0x4fp=0x14000046fd0sp=0x14000046fd0pc=0x10218aa64
createdbymain.foo
/Users/xxx/go/learn/main.go:36+0x84
goroutine1[runnable]:
main.foo()
/Users/xxx/go/learn/main.go:47+0x98
main.main()
/Users/xxx/go/learn/main.go:52+0x20
exitstatus2

输出日志里没有呈现咱们在程序末尾打印的exit，而是直接将调用栈打印出来了。检查底层/opt/homebrew/Cellar/go@1.18/1.18.10/libexec/src/runtime/map_fast64.go:22中的代码不难发现这几行：

ifh.flags&hashWriting!=0{
throw("concurrentmapreadandmapwrite")
}

小结一下：

  • map会检测是否存在并发写
  • 假如检测到并发写会调用runtime.throw()函数抛出异常，这种异常是无法在业务代码中通过recover捕获的，直接error。这点最为致命。
  • 假如要并发写 map 有必要在业务层面上加锁（sync.Mutex或sync.RWMutext）或运用sync.Map

4. 并发运用 Map 除了加锁还有什么其他计划吗？

除了加锁之外，Go 并发运用 Map 的其他常见解决计划包含运用 sync.Map 和运用并发安全的第三方 Map 库。

  • 1、运用 sync.Map sync.Map 是 Go 1.9 新增的一种并发安全的 Map，它的读写操作都是并发安全的，无需加锁。运用 sync.Map 的示例代码如下：
varmsync.Map
m.Store("name","程序员回禄")
value,ok:=m.Load("name")
ifok{
fmt.Println(value)
}
//输出程序员回禄
  • 2、运用并发安全的第三方 Map 库 除了运用 sync.Map，还能够运用其他第三方的并发安全的 Map 库，如 concurrent-map、ccmap 等。这些库的运用办法与 Go 规范库的 Map 类似，但它们都供给了更高效、更牢靠的并发安全保证。

留意： 运用并发安全的第三方 Map 库可能会导致额定的依赖和复杂性，因而需求细心评价是否值得运用。

5. sync.Map 和加锁的区别是什么？

  • sync.Map 和运用锁的区别在于，sync.Map 不需求在并发拜访时进行加锁和解锁操作。相比之下，运用锁需求在并发拜访时显式地加锁和解锁，以防止竞赛条件和数据竞赛问题。
  • 在运用锁时，当多个 goroutine 一起拜访同一块数据时，有必要通过加锁来防止竞赛条件。这意味着只要一个 goroutine 能够拜访该数据，而且在该 goroutine 完结工作后，其他 goroutine 才能够拜访数据。这种办法能够保证数据的一致性，可是加锁会带来额定的开支，而且在高并发情况下可能会影响功能。
  • 相比之下，sync.Map 运用了更高档的算法来防止竞赛条件和数据竞赛问题，而不需求显式地进行加锁和解锁。当多个 goroutine 一起拜访 sync.Map 时，它会主动分配不同的段来存储数据，而且每个段都有自己的读写锁，以防止竞赛条件。这种办法能够进步并发功能，削减开支，而且防止死锁等问题。

因而，当需求在并发拜访时安全地共享数据时，能够考虑运用sync.Map来防止竞赛条件和数据竞赛问题，并进步功能。而当需求在运用锁时，需求显式地加锁和解锁来保证数据一致性和防止竞赛条件。

6. Map 的查询时刻复杂度？

Go 中的 Map 底层完结采用了哈希表，因而其查询时刻复杂度为 O(1)，最坏情况为O(n)。

  1. Map Rehash 的战略是怎样的？什么时机会产生 Rehash？

当哈希表中的元素数量到达必定阈值时，就会触发哈希表的扩容操作，也便是进行 rehash。

Go 规范库中的哈希表完结在以下情况下会触发 rehash 操作：

  • 当哈希表中的元素数量超过了哈希表容量的 2/3 时，会触发扩容操作。此刻，哈希表的容量会翻倍，而且哈希表中一切的元素都会从头哈希到新的槽位中。
  • 当哈希表中的元素数量过少，而哈希表的容量过大时，会触发缩短操作。此刻，哈希表的容量会减半，而且哈希表中一切的元素都会从头哈希到新的槽位中。
  • 当哈希表的勘探序列过长时，会触发重排操作。此刻，哈希表中的元素不会从头哈希，可是它们的存储方位会产生变化，从而削减聚簇现象，进步哈希表的功能。

在进行 rehash 操作时，哈希表会创立一个新的数组来存储从头哈希后的元素，然后将旧数组中的元素逐一仿制到新数组中。因为从头哈希的进程比较耗时，因而 Go 规范库中的哈希表完结采用了增量式 rehash 战略，在扩容和缩短时只会处理一部分元素，防止一次性处理过多元素导致功能下降。详细来说，增量式 rehash 的战略是：

  • 将新数组的容量设置为旧数组的两倍或一半，而且将哈希表的增量计数器加一。
  • 在对哈希表进行操作时，假如发现增量计数器的值到达了一个阈值，就会开端进行增量式 rehash 操作，将一部分元素从旧数组中仿制到新数组中，而且从头核算这些元素的哈希值。
  • 在完结一次增量式 rehash 操作后，会将哈希表的增量计数器清零。

通过增量式 rehash 的战略，Go 规范库中的哈希表完结能够在保证较短的 rehash 时刻的一起，防止一次性处理过多元素导致功能下降。

8. Map Rehash 详细会影响什么？哈希结果会遭到什么影响？

rehash 操作会影响Map的功能。因为从头核算键的哈希值，rehash 操作会消耗必定的核算资源。此外，在 rehash 进程中，原始哈希表的一切键值对都需求仿制到新的哈希表中，因而 rehash 操作还会消耗必定的内存空间和时刻。

rehash 操作不会直接影响哈希结果。哈希结果是由哈希函数核算得出的，与Map中元素的数量和布局无关。rehash 操作只会影响哈希表的布局，即每个键在哈希表中的方位会产生变化，可是每个键的哈希值并不会改动。

9. Map Rehash 进程中存放在旧桶的元素怎么搬迁？

rehash 操作会创立一个新的哈希表，一起保存旧的哈希表不变。然后，它会顺次遍历旧哈希表中的每个桶，将桶中的一切键值对仿制到新哈希表中对应的桶中。在遍历每个桶时，假如桶中的元素现已被删去，则越过这些元素。

当遍历到一个桶时，Map完结会首要获取旧哈希表中该桶的互斥锁，以保证在仿制元素时不会有并发拜访的问题。然后，它会遍历桶中的一切键值对，关于每个键值对，它会核算键在新哈希表中的方位，并将键值对刺进到对应的桶中。刺进进程中，假如新哈希表中对应的桶现已存在元素，则会将新元素刺进到该桶的链表的尾部。

在整个 rehash 进程中，新哈希表会坚持为空，直到一切元素都被仿制结束。仿制完结后，Map完结会用新哈希表替换旧哈希表，并开释旧哈希表占用的内存空间。这样，Map中的一切元素都被搬迁到了新哈希表中。

需求留意的是，在 rehash 进程中，假如有并发拜访Map，则可能会产生竞赛条件。因而，Go 言语中的Map不是线程安全的。假如需求在多个 goroutine 中拜访Map，则需求运用互斥锁或其他并发安全的机制来维护拜访。

10. sync.Map 的 Load() 办法流程？

sync.Map中的Load()办法用于获取指定键对应的值，其流程如下：

  • Load()办法首要会获取sync.Map内部的读锁，以保证在拜访map中的数据时不会被其他 goroutine 搅扰。假如此刻有其他 goroutine 正在写入sync.Map，则Load()办法会阻塞，直到写入操作完结。
  • Load()办法接着会在sync.Map中查找指定的键，并回来其对应的值。假如指定键不存在，则Load()办法会回来一个零值和一个布尔值，表示该键不存在。
  • Load()办法完结后，会开释sync.Map的读锁，以便其他 goroutine 能够读取或写入map。

留意：虽然sync.Map能够在多个 goroutine 中安全地拜访和修正，但因为其内部仍然运用锁来保证并发安全，因而在高并发场景下，其功能可能不如非并发安全的map类型。因而，在并发功能要求较高的场景下，建议运用更为轻量级的并发控制机制，例如互斥锁和读写锁， 来维护一般的map。

11. sync.Map Store() 怎么坚持缓存层和底层 Map 数据是相同的?

在 Go 言语的sync.Map中，Store()办法用于向映射中存储一个键值对。为了坚持缓存层和底层map数据的一致性，sync.Map运用了一种特别的机制，详细流程如下：

  • 当运用Store()办法向sync.Map存储一个键值对时，首要会将键和值打包成一个interface{}类型的元素，并将该元素存储在一个map类型的缓存层中。
  • 当缓存层中的元素数量到达必定阈值（默以为256）时，sync.Map会将缓存层中的一切元素都仿制到一个新的底层map中，并将本来的底层map替换为新的底层map。
  • 在底层map替换进程中，sync.Map会先获取一个写锁，以保证没有其他 goroutine 在此期间对底层map进行读写操作。
  • sync.Map将缓存层中的一切元素仿制到新的底层map中，并在底层map上调用Store()办法来存储这些元素。这样，一切新的元素都被增加到新的底层map中，而本来的底层map中的元素则被保存下来。
  • 当新的底层map中的元素增加完结后，sync.Map会开释写锁，并将缓存层中的元素清空。这样，缓存层和底层map的数据就坚持了一致性。

留意： sync.Map运用缓存层和底层map之间的转换机制来防止锁的运用，从而进步了并发功能。但是，因为缓存层和底层map之间存在必定的延迟和不一致性，因而在一些特别的场景下，可能会呈现一些数据同步的问题，需求特别留意。

欢迎和我一起学习进步：能够在私信我

公众号搜：程序员回禄