开发者

Go语言针对Map的11问你知道几个?

目录
  • 1. Map 使用时需要注意哪些问题?
  • 2. Map 扩容是怎么实现的?
  • 3. Map 的 panic 能被 recover 吗?
  • 4. 并发使用 Map 除了加锁还有什么其他方案吗?
  • 5. sync.Map 和加锁的区别是什么?
  • 6. Map 的查询时间复杂度?
  • 7.Map Rehash 的策略是怎样的?什么时机会发生 Rehash?
  • 8. Map Rehash 具体会影响什么?哈希结果会受到什么影响?
  • 9. Map Rehash 过程中存放在旧桶的元素如何迁移?
  • 10. sync.Map 的 Load() 方法流程?
  • 11. sync.Map Store() 如何保持缓存层和底层 Map 数据是相同的?

1. Map 使用时需要注意哪些问题?

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

2. Map 扩容是怎么实现的?

在 Go 中,Map 的内部实现是基于哈希表(hash table)的,因此,当 Map 中的键值对数量增加时,Map 会自动扩容以提供更多的存储空间。下面是 Go Map 扩容的具体步骤:http://www.devze.com

  • 当 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 也是很容易遇到的问题。如下代码可以验证:

package main
import (
  "fmt"
)
func foo(){
  defer func(){
      if err := recover(); err != nil {
          fmt.Println(err)
      }
  }()
  var bar = make(map[int]int)
  go func(){
      defer func(){
          if err := recover(); err != nil {
              fmt.Println(err)
          }
      }()
      for{
          _ = bar[1]
      }
  }()
  for{
      bar[1]=1
  }
}
func main(){
  foo()
  fmt.Println("exit")
}

输出:

fatal error: concurrent map read and map write

goroutine 18 [running]:

runtime.throw({0x1021bdf62?, 0x0?})

        /opt/homebrew/Cellar/go@1.18/1.18.10/libexec/src/runtime/panic.go:992 +0x50 fp=0x14000046f70 sp=0x14000046f40 pc=0x10215f050

runtime.mapAccess1_fast64(0x0?, 0x0?, 0x1)

        /opt/homebrew/Cellar/go@1.18/1.18.10/libexec/src/runtime/map_fast64.go:22 +0x174 fp=0x14000046f90 sp=0x14000046f70 pc=0x10213eaa4

main.foo.func2()

        /Users/xxx/go/learn/main.go:43 +0x50 fp=0x14000046fd0 sp=0x14000046f90 pc=0x1021b8a00

runtime.goexiandroidt()

        /opt/homebrew/Cellar/go@1.18/1.18.10/libexec/src/runtime/asm_arm64.s:1270 +0x4 fp=0x14000046fd0 sp=0x14000046fd0 pc=0x10218aa64

created by main.foo

        /Users/xxx/go/learn/main.go:36 +0x84

goroutine 1 [runnable]:

main.foo()

        /Users/xxx/go/learn/main.go:47 +0x98

main.main()

        /Users/xxx/go/learn/main.go:52 +0x20

exit status 2

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

if h.flags&hashWriting != 0 {
  throw("concurrent map read and map write")
}

小结一下:

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

4. 并发使用 Map 除了加锁还有什么其他方案吗?

除了加锁之外,Go 并发使用 Map 的其他常见解决方案包括使用 sync.Map 和使用并发安全的第三方 Map 库。

1、使用 sync.Map sync.Map 是 Go 1.9 新增的一种并发安全的 Map,它的读写操作都是并发安全的,无需加锁。使用 sync.Map 的示例代码如下:

var m sync.Map
m.Store("name", "程序员祝融")
value, ok := m.Load("name")
if ok {
    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 中的www.devze.com Map 底层实现采用了哈希表,因此其查询时间复杂度为 O(1),最坏情况为 O(n)。

7.Map Rehash 的策略是怎样的?什么时机会发生 Rehash?

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

Go 标准库中的哈希表实现在以下情况下会触发 rehash 操作:

  • 当哈希表中的元素数量超过了哈希表容量的 2/3 时,会触发扩容操作。此时,哈希表的容量会翻倍,并且javascript哈希表中所有的元素都会重新哈希到新的槽位中。
  • 当哈希表中的元素数量过少,而哈希表的容量过大时,会触发收缩操作。此时,哈希表的容量会减半,并且哈希表中所有的元素都会重新哈希到新的槽位中。
  • 当哈希表的探测序列过长时,会触发重排操作。此时,哈希表中的元素不会重新哈希,但是它们的存储位置会发生变化,从而减少聚簇现象,提高哈希表的性能。

在进行 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 类型。因此,在并发性能要求较高的场景下,建议使用更android为轻量级的并发控制机制,例如互斥锁和读写锁,  来保护普通的 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 之间存在一定的延迟和不一致性,因此在一些特殊的场景下,可能会出现一些数据同步的问题,需要特别注意。

到此这篇关于Go语言针对Map的11问你知道几个?的文章就介绍到这了,更多相关Go语言Map内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新开发

开发排行榜