在学习 golang 的过程中，map 是我们经常使用的一种数据结构，可以用来存储 key-value 对。但是，你是否想过 map 的实现原理是什么呢？在本文中，我们将探究 golang 中 map 的实现原理。
map 实现原理简介
map 实际上是一个哈希表，它的实现原理就是哈希算法。哈希表是一种根据关键字直接访问内存存储位置的数据结构，也就是说，它提供了一种将关键字映射到内存地址的方法。在哈希表中，关键字被称为“键”，通过哈希函数计算得到的内存地址被称为“桶”，桶存储了键值对。
在 Golang 中，map 是通过在桶内存区域存储键值对实现的，每个桶都有一个头部结构体，用于描述桶的状态，这个头部结构体称为“bucket”。
bucket 数据结构
立即学习“go语言免费学习笔记（深入）”；
先来看一下 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 实现原理的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2393028.html
