golang map 实现原理

type bmap struct {
    tophash [bucketCnt]uint8
    // data 的类型在 map 被分配空间的时候由 map 的 key 和 value 类型决定
    // 如果 key 类型和 value 类型都是未知类型，那么 data 的类型是 byte
    // 因为 byte 可以用于存储任何类型，也就是说 data 可以存储任何类型的 key 和 value
    // 在存储 key 和 value 的时候，需要将 key 和 value 转换成 uintptr，然后再转换成 byte 存储到 data 中
    // 读取 key 和 value 的时候反向操作即可
    // 因此，map 中的 key 和 value 一般都是需要转换成 uintptr 类型的
    // 这里我们可以简单地理解为 data 存储了键值对的二进制数据
    // 第一个 bucket 中如果存不下某个 key-value，还需要在第二个 bucket 中存储
    // 所以，data 的长度可以为 1 或 2
    // 当 data 的长度为 1 或 2 时，存储的键值对的个数分别为 1 或 2
    // 因此，bucket 中最多只能存储 8 个键值对
    // 否则，就需要将键值对存储在 overflow 中
    // overflow 是一个指向单链表头部的指针数组
    // 如果某个桶存储的键值对数量超过了 8，那么就将多余的键值对存储到 overflow 中
    // overflow 中的第一个 bucket 中也是能够存储 8 个键值对的，如果第一个 bucket 中存不下的话
    // 那么还需要在第二个 bucket 中继续存储
    // 所以，overflow 数组的长度也可以为 1 或 2
    // 当 overflow 数组长度为 1 或 2 时，最多存储 8 个键值对的 overflow
    // 当 overflow 数组长度为 3 时，最多存储 24 个键值对的 overflow
    // 也就是说，如果 map 中存储的键值对数量很多的话，那么可能会有很多个 overflow 桶
    // 而 overflow 数组是动态分配的，因此它的长度是不定的，只有在运行时才能确定
    data unsafe.Pointer
    // overflow 是一个指针数组，用于存储除当前桶以外的其它桶
    // 如果某个桶的键值对数量超过了 8，那么它会将多余的键值对存储到 overflow 中
    // overflow 数组中的每个元素都是一个 bucket 指针
    // 这些 bucket 指针构成了一个链表，也就是所谓的 overflow 链表
    overflow *[]*bmap
    // 这里存储的是这个 bucket 当前存储的键值对的个数
    count int16
    // flags 存储了 bucket 的标志
    // 一个 bucket 可能会有如下三种状态：
    // 1. empty，表示这个 bucket 没有存储任何键值对
    // 2. iterator，表示这个 bucket 正在被访问，不能再被其它操作使用
    // 3. deleted，表示这个 bucket 存储的键值对已经被删除了
    // 注意，该标志位只有在 GC 达到一定阈值后才会被置为 true，而且并不是立即删除键值对，而是在下一次 GC 的时候才会内存回收
    flags uint8
    // Bmap 的类型标记
    // Bmap 用来标识存储于上文中 data 指针中的数据类型
    // 如果 data 中存储的是 int，那么 Bmap 的值为 hmap.BmapInt
    // 如果 data 中存储的是 string，那么 Bmap 的值为 hmap.BmapString
    // 如果 data 中存储的是 interface{}，那么 Bmap 的值为 hmap.BmapInterface
    // 如果 data 中存储其他类型，那么 Bmap 的值为 hmap.BmapOther
    BmapType uint16
    // 与该 bucket 相关联的 key 的类型
    tophash0 uint8
}