面试题：Go语言中map的底层实现及冲突处理

Question

说明Go语言中map的底层数据结构，包括哈希表的组织形式，当发生哈希冲突时，Go语言是如何处理的，并且解释在高并发情况下map可能出现的问题及原因。

Answer 1

Go语言中map的底层数据结构

1. 哈希表组织形式：
   • Go语言的map底层是基于哈希表实现的。哈希表由数组（bucket数组）和链表（bucket内溢出桶链表）组成。
   • 每个bucket可以存放8个键值对。bucket结构体大致如下：

type bmap struct {
    tophash [8]uint8
    data    byte[1]
    overflow *bmap
}

• tophash数组用于存放每个键值对的哈希值的高8位，用于快速判断键是否在该bucket中。data部分存放实际的键值对数据，overflow指针指向溢出桶（如果当前bucket已满，新的键值对会存放在溢出桶中）。
• 数组（bucket数组）的大小是2的幂次方，会随着map中元素数量的增加而动态扩容。

2. 哈希冲突处理：
   • 当发生哈希冲突时，Go语言采用链地址法处理。即如果不同的键计算出相同的哈希值，它们会被放入同一个bucket中。
   • 当一个bucket已满（存放了8个键值对），后续再有键值对要放入该bucket时，会创建一个溢出桶（通过overflow指针链接），新的键值对会放入溢出桶中。

高并发情况下map可能出现的问题及原因

1. 问题：在高并发读写map时，会出现fatal error: concurrent map read and map write错误，程序会崩溃。
2. 原因：
   • Go语言的map不是线程安全的。在高并发场景下，多个goroutine同时读写map时，可能会出现竞争条件。
   • 例如，一个goroutine正在向map中写入数据，可能正在进行bucket的扩容操作等复杂逻辑，而另一个goroutine同时读取map，可能会读到不一致的数据，或者因为map内部结构正在改变而导致程序崩溃。

为了在高并发场景下安全使用map，可以使用sync.Map，它是Go语言标准库提供的线程安全的map实现。