golang面经3——map模块和sync.Map模块

一、面试题相关

1、map的数据结构详解

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

        1）hmap结构（Map的头部）

type hmap struct { count int // 当前存储的键值对数量 flags uint8 // 状态标志（如是否正在写入） B uint8 // B=5的话，桶的数量就是32个。桶数量的对数（桶数量 = 2^B） noverflow uint16 // 溢出桶的大概数量 hash0 uint32 // 哈希种子（用于防御Hash-DoS攻击） buckets unsafe.Pointer // 指向桶数组的指针 oldbuckets unsafe.Pointer // 扩容时指向旧桶数组 nevacuate uintptr // 搬迁进度计数器 extra *mapextra // 可选字段，用于优化小对象存储 }

2）bmap结构（桶结构）

// 这是一个概念上的结构，并非源码中的实际定义 type bmap struct { // 1. 顶部哈希数组 (固定8个元素) tophash [bucketCnt]uint8 // bucketCnt 常量，值为 8 // 2. 接下来是 8 个键 (key) // keys [bucketCnt]keyType // keyType 在编译时确定 (例如 int, string 等) // 3. 再接下来是 8 个值 (value) // values [bucketCnt]valueType // valueType 在编译时确定 // 4. 最后是一个溢出桶指针 (可选，在特定条件下才存在) // overflow *bmap }

        每个桶可以存储最多8个键值对：

tophash的作用

        tophash [bucketCnt]uint8 // bucketCnt 常量，值为 8
        uint是一个字节8位（0~255），存储每个键哈希值的高8位
        用于快速比较，避免直接比较可能很大的key。利用tophash只是进行初步的过滤，将指定key高8位相同的key从bucket里找到，然后再从找到的key中进行完整的对比确认找的是哪个key。
        特殊值：

                0=空槽位（emptyRest）：该槽位为空，且后面所有槽位都为空

                1=已删除槽位（emptyOne）：仅该槽位为空，后面可能有非空槽位

溢出桶机制
        当单个桶存储超过8个元素时，会创建溢出桶：

                主桶 → 溢出桶1 → 溢出桶2 → ...

        每个溢出桶也是bmap结构，可以继续存储8个元素。

2.map中新加入一个新的成员得流程

（1）计算哈希值：根据 key 计算出一个哈希值。
（2）定位桶：利用哈希值的低位确定 key 应该存放在哪个桶中。
（3）遍历桶：依次检查桶内的每个槽位（也称为 cell）。
（4）查找或插入：
        情况一（Key 已存在）：如果找到相同的 key，则更新其对应的 value。
        情况二（Key 不存在）：如果 key 不存在，则寻找一个空槽位进行插入。
（5）处理溢出：如果当前桶已满，则需要链接一个新的溢出桶。
（6）扩容检查：在插入后，可能会触发 map 的扩容机制。

通过key hash值的低8位（当B为3的时候，如果B为4，就取低16位）确定使用哪个桶

通过key hash值的高8位存到桶内的tophash中

3.map 循环遍历是有序的还是无序的?

分析：

        考察对map遍历的底层实现是否了解，map在每次遍历的时候都会选定一个随机桶号，遍历从这个随机桶开始往后依次遍历完所有的桶，在每个桶内，则是按照之前选定随机槽位开始遍历，回答的时候要突出随机桶号和随机槽位。

回答：

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

4.go语言的map要这样设计，要随机选定桶号和槽位进行随机遍历?

分析：

        因为map是可以动态扩容的，map 在扩容后，会发生 key 的搬迁，这样 key 的位置就会发生改变，那么如果顺序谝历key，在扩容前后顺序肯定会不一样，这道题回答一定要突出扩容会带来key的位置发生变化回顾一下双倍扩容，key的变化过程，双倍扩容，目标桶扩容后的位置可能在原位置也可能在原位置+偏移量处。

回答：

        因为map 在扩容后，会发生 key 的搬迁，原来落在同一个 bucket 中的 key，搬迁后，有些 key 的位置就会发生改变。而遍历的过程，就是按顺序遍历 b