写在前面

go面试中，map相关知识点问的比较多，本文总结了一些问题，希望对大家有帮助。

其他go相关知识收集在专栏：GO那些事儿，欢迎订阅。

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 也是很容易遇到的问题

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

runtime.throw() 函数抛出异常是无法recover的

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 时，它会自动分配不同的段来存储数据，并且每个段都有自己的读写锁，以避免竞争条件。这种方式可以提高并发性能，减少开销，并且避免死锁等问题。

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

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

7. 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() 方法流程？

func (m *Map) Load(key any) (value any, ok bool) {
   read, _ := m.read.Load().(readOnly)
   e, ok := read.m[key]
   if !ok && read.amended {
      m.mu.Lock()
      // Avoid reporting a spurious miss if m.dirty got promoted while we were
      // blocked on m.mu. (If further loads of the same key will not miss, it's
      // not worth copying the dirty map for this key.)
      read, _ = m.read.Load().(readOnly)
      e, ok = read.m[key]
      if !ok && read.amended {
         e, ok = 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 nil, false
   }
   return e.load()
}

可见Load函数直接从底层读取元素，如果存在则返回，不管此时是否有写入操作。因为e.load函数内是通过原子操作读取数据的。

因此当key存在的时候，Load函数不会加锁。Stone当元素存在的时候也不会加锁，而是通过atomic.CompareAndSwapPointer修改元素的值。

所以Load,Store只有当key不存在的时候才会加锁，其他情况不会加锁，因此它适合读多写少的场景，速度非常快。