> # map的底层 - 哈希表（hash table），又称散列表，它通过建立键`key`与值`value`之间的映射，实现高效的元素查询 - 查找元素，添加元素，删除元素 O(n)时间 - `hmap` 是 `map` 结构的头部，用于存储 `map` 的元数据 - `bmap` 是实际存储 `map` 键值对的结构。它表示一个存储桶（bucket） >### hmap ``` type hmap struct { count int // 活跃的键值对数量 == map 的大小。必须是第一个字段（由 len() 内置函数使用）。 flags uint8 // 标志位，用于存储与 map 状态相关的标志信息。 B uint8 // 存储桶的数量的对数（log_2），可以容纳最多 loadFactor * 2^B 个元素。 noverflow uint16 // 近似的溢出存储桶的数量；有关详细信息，请参见 incrnoverflow。 hash0 uint32 // 哈希种子，用于哈希函数的初始值。 buckets unsafe.Pointer // 指向存储桶数组的指针，数组大小为 2^B。如果 count == 0，则可能为 nil。 oldbuckets unsafe.Pointer // 指向先前存储桶数组的指针，其大小为当前的一半，仅在增长时为非 nil。 nevacuate uintptr // 迁移进度计数器（小于此值的存储桶已迁移到新的存储桶数组）。 extra *mapextra // 可选字段，包含一些额外的字段。 } ``` * **count**：记录 `map` 中当前存储的键值对的数量（活跃单元数），也是 `len()` 内置函数的依据。 * **flags**： 存储与 `map` 状态相关的标志信息。例如，用于记录 `map` 是否正在增长等状态。 * **B**：表示存储桶数量的对数（log\_2），存储桶数量为 `2^B`。它决定了 `map` 可以存储的最大键值对数量。 * **noverflow**： 记录溢出存储桶的数量（大致），在发生哈希冲突时，多个键值对可能会被分配到同一个存储桶，因此可能会产生溢出存储桶。 * **hash0**：哈希种子，用于哈希函数。通过引入种子，使得 `map` 的哈希分布更随机，以减少冲突。 * **buckets**： 指向当前存储桶数组的指针，数组的大小为 `2^B`。如果 `map` 为空（count == 0），该字段可能为 `nil`。 * **oldbuckets**： 在 `map` 进行扩容时，指向先前存储桶数组的指针，旧数组的大小是新数组的一半。在扩容过程中，这个指针会被用来迁移旧的键值对。 * **nevacuate**： 在扩容过程中，记录了迁移进度的计数器。小于此值的存储桶已经被迁移到新的存储桶数组。 * **extra**：可选字段，用于存储一些额外的数据，比如保存小 `map` 结构体的溢出数据或指向垃圾回收器的指针。 > bmap ``` type bmap struct { // tophash 通常包含此存储桶中每个键的哈希值的最高字节。 // 如果 tophash[0] < minTopHash，则 tophash[0] 是存储桶搬迁状态。 tophash [bucketCnt]uint8 // 接下来是 bucketCnt 个键和 bucketCnt 个元素。 // 注意：将所有键一起打包然后将所有元素一起打包使代码稍微复杂一些， // 比如交替存储 key/elem/key/elem/...，但是这样可以消除填充， // 填充可能需要，例如 map[int64]int8。 // 紧跟在这些之后的是溢出指针。 } ```  > # key的定位 - key 根据当前初始话的hash种子进行哈希计算得到哈希值， hash后几位确定桶的位置， 前几位作为tophash - 当两个不同的 key 落在同一个桶中，也就是发生了哈希冲突。冲突的解决手段是用链表法：在 bucket 中，从前往后找到第一个空位。这样，在查找某个 key 时，先找到对应的桶，再去遍历 bucket 中的 key。如果在 bucket 中没找到，并且 overflow 不为空，还要继续去 overflow bucket 中寻找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。 - 链式地址解决哈希冲突： 每个桶存储一个链表包含所有冲突的元素 > # 扩容 - 扩容的时候不是马上全部迁移， 而是会有标记状态， 每次迁移一部分 > # 相关阅读 - [go map底层实现](https://www.cnblogs.com/ybf-yyj/p/12763015.html) - [go map深度解析](https://www.jianshu.com/p/0a777dc7f7ae) - [golang map合并\_数据结构和算法(Golang实现)](https://blog.csdn.net/weixin_39688451/article/details/110236131) - [Hello算法](https://www.hello-algo.com/chapter_hashing/hash_map)