golang map面试考点

golang map面试考点

1. Go语言中map的底层数据结构是什么样的？

Go 语言中的map底层是基于哈希表实现的。其核心数据结构为hmap，在这个结构里包含了一个由桶（bucket）组成的数组。每个桶实际上是一个bmap结构，它能够存储 8 个键值对。

就好比一个巨大的文件柜。这个文件柜被分成了许多小格子，每个小格子被称作 “桶”（bucket）。每个桶最多可以存放 8 个键值对，这就如同每个小格子最多能放 8 份文件一样。当你要存储一个键值对或者查找一个键对应的值时，Go 会先通过哈希函数计算出键的哈希值，然后依据这个哈希值来确定该键值对应该存放在哪个桶或者从哪个桶中查找。

hmap 结构体
├── count       // 键值对总数
├── B           // 桶数组长度为 2^B
├── buckets     // 桶数组（元素类型为 bucket）
│   ├── bucket[0]
│   │   ├── tophash[8]    // 存储哈希值的高8位（快速筛选）
│   │   ├── keys[8]       // 存储8个键
│   │   ├── values[8]     // 存储8个值
│   │   ├── overflow      // 溢出桶指针（如果超过8个键值对）
│   ├── bucket[1]
│   ├── ...
└── oldbuckets  // 扩容时的旧桶数组

计算 key 的哈希值 → hash 通过 hash 的低 B 位 → 确定桶索引 i 通过 hash 的高 8 位 → 快速筛选桶内可能匹配的键 遍历桶内 keys 数组，用 == 精确比较 key 找到匹配的键 → 返回对应 values 数组中的值 没找到 → 通过 overflow 指针继续遍历溢出桶

模拟案例

1. 假设我们有一个 map，它的结构如下：

• B = 2（这意味着桶数组的长度为 2² = 4，所以桶的索引范围是 0 到 3）
• buckets 数组：包含 4 个桶，分别是 bucket [0]、bucket [1]、bucket [2]、bucket [3]
• 每个桶：能够存储 8 个键值对，并且可能会有溢出桶。

2. 现在，我们要查询键值对key = "apple"，下面是具体的步骤：

步骤 1：计算 key 的哈希值 → hash

假设通过哈希函数计算得到 “apple” 的哈希值为：

hash = 0x123456789ABCDEF0

步骤 2：通过 hash 的低 B 位 → 确定桶索引 i

由于 B = 2，所以取 hash 的低 2 位：

低2位 = 0b10 → 对应十进制的2
因此，桶索引i = 2，也就是要查找bucket[2]

步骤 3：通过 hash 的高 8 位 → 快速筛选桶内可能匹配的键

取出 hash 的高 8 位：

高8位 = 0x12

接着查看 bucket [2] 的 tophash 数组：

bucket[2].tophash = [0x12, 0x34, 0x56, 0x78, 0x9A, 0xBC, 0xDE, 0xF0]

可以看到，tophash [0] 的值为 0x12，和我们计算得到的高 8 位相同，这表明对应的键可能是匹配的，所以需要进一步验证。

步骤 4：遍历桶内 keys 数组，用 == 精确比较 key

查看 bucket [2] 的 keys 数组：

bucket[2].keys = ["apple", "banana", "cherry", "date", "elderberry", "fig", "grape", "honeydew"]

从索引 0 开始遍历 keys 数组，将每个键与 “apple” 进行比较：

• keys [0] = “apple”，与查询的键完全相同，匹配成功！

步骤 5：找到匹配的键 → 返回对应 values 数组中的值

查看 bucket [2] 的 values 数组：

bucket[2].values = ["red", "yellow", "red", "brown", "purple", "purple", "green", "green"]

因为匹配的键索引是 0，所以对应的值为：

values[0] = "red"
最终返回结果："red"

步骤 6：没找到 → 通过 overflow 指针继续遍历溢出桶

如果在 bucket [2] 的 keys 数组中没有找到匹配的键，就会通过 overflow 指针去检查与之相连的溢出桶，然后重复步骤 3 到步骤 5 的操作，直到找到匹配的键或者遍历完所有相关桶。

2. 哈希冲突是怎么解决的？

哈希冲突指的是不同的键经过哈希函数计算后，得到了相同的哈希值。Go 语言采用链地址法来应对这种情况。你可以把每个桶想象成一个小格子，当这个小格子已经放满了 8 份文件（键值对），而此时又有新的文件要放进来，并且也要放在这个小格子时，Go 会给这个小格子再连接一个新的小格子（溢出桶），用来存放多出来的文件。这样，即使多个键的哈希值相同，它们也能被妥善地存放，只是可能会存放在不同的溢出桶中。

模拟案例

1. 假设我们有一个 map，它的结构如下：

• B = 2（这意味着桶数组的长度为 2² = 4，所以桶的索引范围是 0 到 3）
• buckets 数组：包含 4 个桶，分别是 bucket [0]、bucket [1]、bucket [2]、bucket [3]
• 每个桶：能够存储 8 个键值对，并且可能会有溢出桶。

2. 现在，我们要插入 3 个键值对，且它们都发生了哈希冲突：

m := make(map[string]string)
m["apple"] = "red"    // 哈希值假设为 0x12345678
m["banana"] = "yellow" // 哈希值假设为 0x12ABCDEF（与"apple"冲突）
m["cherry"] = "red"   // 哈希值假设为 0x12121212（与"apple"冲突）

步骤 1：插入 “apple”（哈希值 = 0x12345678）

• 低 2 位：0b10 → 桶索引 i=2
• 高 8 位：0x12
• 插入 bucket [2]：

bucket[2]
├── tophash: [0x12, 0, 0, 0, 0, 0, 0, 0]
├── keys: ["apple", nil, nil, nil, nil, nil, nil, nil]
├── values: ["red", nil, nil, nil, nil, nil, nil, nil]
└── overflow: nil

步骤 2：插入 “banana”（哈希值 = 0x12ABCDEF）

• 低 2 位：0b11 → 桶索引 i=3
• 高 8 位：0x12
• 插入 bucket [3]：

bucket[3]
├── tophash: [0x12, 0, 0, 0, 0, 0, 0, 0]
├── keys: ["banana", nil, nil, nil, nil, nil, nil, nil]
├── values: ["yellow", nil, nil, nil, nil, nil, nil, nil]
└── overflow: nil

步骤 3：插入 “cherry”（哈希值 = 0x12121212）

• 低 2 位：0b10 → 桶索引 i=2（与 “apple” 冲突）
• 高 8 位：0x12
• 插入 bucket [2]：

bucket[2]
├── tophash: [0x12, 0x12, 0, 0, 0, 0, 0, 0]
├── keys: ["apple", "cherry", nil, nil, nil, nil, nil, nil]
├── values: ["red", "red", nil, nil, nil, nil, nil, nil]
└── overflow: nil

3. 当桶已满时的溢出处理

假设我们继续插入更多键值对，导致 bucket [2] 已满（8 个键值对），此时再插入 “date”（哈希值 = 0x12567890）：

• 低 2 位：0b10 → 桶索引 i=2（冲突）
• 高 8 位：0x12
• 创建溢出桶：

bucket[2]
├── tophash: [0x12, 0x12, 0x12, 0x12, 0x12, 0x12, 0x12, 0x12]
├── keys: ["apple", "cherry", "date1", "date2", "date3", "date4", "date5", "date6"]
├── values: ["red", "red", "brown1", "brown2", "brown3", "brown4", "brown5", "brown6"]
└── overflow: bucket[2]_overflow

bucket[2]_overflow
├── tophash: [0x12, 0, 0, 0, 0, 0, 0, 0]
├── keys: ["date", nil, nil, nil, nil, nil, nil, nil]
├── values: ["brown", nil, nil, nil, nil, nil, nil, nil]
└── overflow: nil

4. 查询冲突键的过程

假设我们要查询 “cherry”：

1. 计算哈希值：0x12121212
2. 确定桶索引：低 2 位 0b10 → bucket [2]
3. 快速筛选：高 8 位 0x12 → 检查 bucket [2].tophash
4. 遍历 keys 数组：
   • 比较 keys [0]（“apple”）≠ “cherry”

• 比较 keys [1]（“cherry”）= “cherry” → 匹配成功

1. 返回对应值：values[1] → “red”

3. 两个不同的键哈希值相同，但值不同，get操作是如何进行的？

当你使用一个键去map中获取对应的值时，Go 会按照以下步骤操作：

1. 计算这个键的哈希值。
2. 用哈希值的一部分（高 8 位）来确定该键可能位于哪个溢出桶。
3. 用哈希值的另一部分（低几位）来确定该键位于哪个主桶。
4. 然后 Go 会遍历对应的桶（包括溢出桶），将桶中存储的键和你提供的键进行逐字节比较。
5. 如果找到了匹配的键，就返回对应的值；如果没找到，就返回零值。

举个例子，假设你有两个不同类型的键，比如KeyA和KeyB，它们经过哈希计算后得到了相同的哈希值。当你用KeyA去查找时，Go 会在对应的桶中找到存储的KeyA，并返回其对应的值，而不会把它和KeyB混淆，因为 Go 会精确比较键的类型和值。

模拟案例

1. 定义两个不同类型的键

type KeyA struct{ ID int }
type KeyB struct{ ID int }

2. 假设它们的哈希值完全相同

尽管 KeyA 和 KeyB 结构相同，但由于类型不同，Go 会将它们视为不同的键。 假设它们的哈希值均为：0x123456789ABCDEF0

3. 创建 map 并插入键值对

m := make(map[interface{}]string)

keyA := KeyA{ID: 1}  // 哈希值: 0x123456789ABCDEF0
keyB := KeyB{ID: 1}  // 哈希值: 0x123456789ABCDEF0

m[keyA] = "Value for KeyA"
m[keyB] = "Value for KeyB"

4. 底层存储结构（模拟）

假设 B = 2（桶数量为 4），则：

• 低 2 位：0b10 → 桶索引 i = 2
• 高 8 位：0x12

桶结构如下：

bucket[2]
├── tophash: [0x12, 0x12, 0, 0, 0, 0, 0, 0]
├── keys: [KeyA{1}, KeyB{1}, nil, nil, nil, nil, nil, nil]
├── values: ["Value for KeyA", "Value for KeyB", nil, nil, nil, nil, nil, nil]
└── overflow: nil

5. 执行 get 操作：m[keyA]

1. 计算哈希值：0x123456789ABCDEF0
2. 确定桶索引：低 2 位 0b10 → 定位到 bucket[2]
3. 筛选可能的键：高 8 位 0x12 → 匹配 tophash[0] 和 tophash[1]
4. 遍历并精确比较键：
   • 比较 keys[0]：
     • 类型：KeyA（与查询键类型相同）
     • 值：ID=1（与查询键值相同）
     • 匹配成功 → 返回 values[0]（“Value for KeyA”）
   • 跳过 keys[1]：类型为 KeyB，与查询键类型不同

6. 执行 get 操作：m[keyB]

类似地：

1. 定位到 bucket[2]
2. 筛选出 tophash[0] 和 tophash[1]
3. 遍历并精确比较键：
   • 比较 keys[0]：类型为 KeyA，不匹配
   • 比较 keys[1]：
     • 类型：KeyB（与查询键类型相同）
     • 值：ID=1（与查询键值相同）
     • 匹配成功 → 返回 values[1]（“Value for KeyB”）

以下是完善后的内容，修正了迁移次数的错误，并补充了关键细节：

4. map的扩容机制

触发条件

当出现以下两种情况时，map会触发扩容：

1. 负载因子过高： 当键值对数量超过桶数量的 6.5 倍（即负载因子 > 6.5）时，会创建 2 倍容量 的新桶数组，减少哈希冲突。
2. 溢出桶过多：
   • 当桶数量少于 2^15 时，若溢出桶数量 ≥ 桶数量；
   • 当桶数量 ≥ 2^15 时，若溢出桶数量 ≥ 2^15。 此时扩容会创建 相同容量 的新桶数组，主要目的是 整理碎片化内存（减少溢出桶）。

扩容过程

1. 创建新桶：
   • 负载过高触发：新桶数量 = 旧桶数量 × 2（如 8 → 16）。
   • 溢出桶过多触发：新桶数量 = 旧桶数量（容量不变，仅整理数据）。
2. 渐进式迁移：
   • 非一次性完成：扩容时仅创建新数组，旧数据保留。
   • 每次操作迁移 2 个旧桶：对 map 的增删改查操作会触发迁移，每次迁移 2 个旧桶（含主桶及溢出桶）到新数组。
   • 总迁移次数 = 旧桶数量 ÷ 2：例如从 8 个桶扩容到 16 个桶，需迁移 4 次（8 ÷ 2 = 4）。
3. 双哈希表共存：
   • 迁移期间同时维护 旧桶数组（oldbuckets） 和 新桶数组（buckets）。
   • 所有旧桶迁移完毕后，oldbuckets 被置为 nil，扩容完成。

5. 扩容期间的操作