prinsip pelaksanaan peta golang

在学习 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。

Atas ialah kandungan terperinci prinsip pelaksanaan peta golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!