Map 面试题

1. Go 语言 Map 的底层实现原理是怎样的？

map 就是一个 hmap 的结构。Go Map 的底层实现是一个哈希表。它在运行时表现为一个指向 hmap 结构体的指针，hmap 中记录了桶数组指针 buckets、溢出桶指针以及元素个数等字段。每个桶是一个 bmap 结构体，能存储 8 个键值对和 8 个tophash，并有指向下一个溢出桶的指针 overflow。为了内存紧凑，bmap 中采用的是先存 8 个键再存 8 个值的存储方式。

hmap 结构体定义如下：

type hmap struct {
    count     int            // map 中元素的数量
    flags     uint8          // map 的状态标志
    B         uint8          // 桶的数量是 2^B
    noverflow uint16         // 溢出桶的数量
    hash0     uint32         // 随机数，防止哈希碰撞攻击
    
    buckets   unsafe.Pointer // 指向桶数组的指针
    oldbuckets unsafe.Pointer // 扩容时旧桶数组的指针
    nevacuate uintptr        // 扩容时已经迁移的桶数量

    extra *mapextra // 可选的额外信息
}

2. Go 语言 Map 的遍历是有序的还是无序的？

无序

map 每次遍历，都会从一个随机值序号的桶开始遍历，在每个桶中，再从按照
之前选定随机槽位开始遍历，所以是无序的

3. Go 语言 Map 的遍历为什么要设计成无序的？

Go 的 map 底层是哈希表（hash table），其结构特点决定了遍历顺序：

key 经过 hash 计算后分布到不同 bucket
bucket 内部存储 key/value
遍历时是按 bucket 顺序 + 随机起点

👉 Go runtime 在设计上还额外做了：

随机化遍历起点
避免开发者依赖顺序

4. Map 如何实现顺序读取？

将 Map 的键（key）取出来放到一个切片（slice）中，对切片进行排序，然后按照排序后的顺序访问 Map 中的值（value）。示例代码如下：

package main

import (
    "fmt"
    "sort"
)

func main() {
    keyList := make([]int, 0)
    m := map[int]int{
        3: 200,
        4: 200,
        1: 100,
        8: 800,
        5: 500,
        2: 200,
    }
    
    for key := range m {
        keyList = append(keylist, key)
    }
    sort.Ints(keylist)
    for _, key := range keylist {
        fmt.Println(key, m[key])
    }
}

5 Go 语言的 Map 是否是并发安全的？

不是

在查找、赋值、遍历、删除的过程中都会检测写标志，一旦发现写标志已经被置位（说明已经有 goroutine 在写），则直接 throw（runtime 触发 fatal error，不可被 recover 捕获）。赋值和删除函数在检测到写标志为复位状态后，会先将写标志位置位，再进行后续操作。

6. Map 的 Key 一定要是可比较的吗？为什么？

一定是

Go 语言的 Map 要求 Key 必须是可比较的（comparable），这是因为 Map 内部需要通过 Key 来计算哈希值并进行比较，以确定 Key 的位置和是否存在。不可比较的类型（如切片、函数、Map 本身等）无法进行哈希计算和比较，因此不能作为 Map 的 Key。

7. Go 语言 Map 的扩容时机是怎样的？

向 map 插入新 key 的时候，会进行条件检测，符合下面这2个条件，就会触发扩容：

装载因子超过阈值（源码里定义的阈值是 6.5），触发双倍扩容（B+1，buckets 数量翻倍）。
overflow 的 bucket 数量过多（触发等量扩容，B不变，仅重新整理键值对让分布更紧凑）:
1. 当 B < 15，也就是 bucket 总数 2^B < 2^15 时，如果 overflow 的 bucket 数量超过 2^B
2. 当 B >= 15 ，也就是 bucket 总数 2^B >= 2^15，如果 overflow 的 bucket 数量超过 2^15。