golang map 实现原理

在学习 Golang 的过程中，map 是我们经常使用的一种数据结构，可以用来存储 key-value 对。但是，你是否想过 map 的实现原理是什么呢？在本文中，我们将探究 Golang 中 map 的实现原理。

map 实现原理简介

map 实际上是一个哈希表，它的实现原理就是哈希算法。哈希表是一种根据关键字直接访问内存存储位置的数据结构，也就是说，它提供了一种将关键字映射到内存地址的方法。在哈希表中，关键字被称为“键”，通过哈希函数计算得到的内存地址被称为“桶”，桶存储了键值对。

在 Golang 中，map 是通过在桶内存区域存储键值对实现的，每个桶都有一个头部结构体，用于描述桶的状态，这个头部结构体称为“bucket”。

bucket 数据结构

先来看一下 bucket 的数据结构：

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
}

从上面的定义中，我们可以看到，bucket 存储了以下信息：

• tophash：用于快速筛选出不匹配的 key；
• data：存储键值对的数据；
• overflow：存储 overflow 链表的指针数组；
• count：存储了当前 bucket 中存储的键值对的个数，最多为 8；
• flags：存储了 bucket 的一些状态信息；
• BmapType：存储了 data 中存储数据的类型；
• tophash0：与该 bucket 相关联的 key 的类型。

实现原理

由于 map 存储的数据是键值对，而且键值对的 key 值是不可重复的并且能够进行比较大小操作，我们可以采用哈希函数将 key 值转换为一个唯一的哈希值，然后将哈希值作为 key 值对应的索引，将 value 值存储在该索引上。

在 Golang 中，每一个 map 都有一个哈希表，这个哈希表实际上就是一段连续的存储空间，可以存储若干个桶（bucket），每个桶都是一个 bucket 类型的结构体。

那么哈希表的大小是如何确定的呢？它是在 map 创建时动态分配内存而来的，首次分配空间时候使用的默认大小为 8 个桶。如果第一次增加元素的时候，桶的数量不够，则哈希表的大小会扩容，并重新计算每个元素在哈希表中的索引位置。

在 Golang 中，哈希函数的作用主要是将 key 值散列化，使其更方便的定位到哈希表中的一个桶，从而加速查找 key 值对应的 value 值。在 Golang 中，哈希函数的实现采用了 MurmurHash3 算法。

由于哈希函数是将 key 映射到一个整数，因此不同的 key 值可能映射到相同的索引。这种情况被称为哈希冲突。当出现哈希冲突时，Golang 采用链表法来进行解决，将相同索引上的键值对存储在该索引的链表中，这些键值对就称为 overflow。

总结

Golang 的 map 实现原理主要依赖哈希表和哈希函数。哈希函数用于散列化 key 值，将其映射到哈希表中的一个桶，从而加速查找 value 值的操作。哈希表由若干个桶组成，每个桶由一个 bucket 类型的结构体表示，存储了键值对的信息。当哈希表中的同一索引位置上存在多个键值对时，采用链表法存储 overflow。Golang 中的 map 实际上就是一个动态哈希表，可以动态地调整哈希表的大小。在使用 map 时，需要注意避免哈希冲突和包含无法比较大小的类型作为 key。

以上是golang map 实现原理的详细内容。更多信息请关注PHP中文网其他相关文章！