深入理解 Go 语言的 map 实现原理

前言

一直很好奇 Go 语言的 map 底层是如何实现的。 Go map 的形式就是键值对，给定一个键，能尽快的找到对应的值。

• 任何可比较的类型都可以是键——所有简单的标量类型（布尔、整数、浮点、复数、字符串）、指针、通道、数组、接口。

• 不可比较的类型——切片、映射、函数。

因此，映射键和值应存储在为映射分配的内存中。这个过程我们使用的方法叫做哈希算法，哈希算法一般包括两步，伪代码如下：

• hash = hashfunc(key)
  

• index = hash % array_size
  

第一步，通过哈希算法计算键的哈希值，这个结果与桶的数量无关。而且这个计算出的哈希值一般是唯一的，避免出现两个不同的键得到相同的哈希值。 第二步，通过执行取模运算得到 0 到 array_size-1 之间的 index 序号。

哈希函数

为了处理内存地址，我们应该使用哈希函数。我们对哈希函数有以下要求：

• 确定性 - 应该为相同的键返回相同的值；

• 统一 — 值应该以某种方式与所有桶同等相关；

• 快速 - 应快速运行以多次使用；

map 的常见设计

map 的任务是设计一种数据结构用来维护一个集合的数据，同时需要对该集合进行增删查改的操作。最主要的数据结构有两种：哈希查找表（Hash table）、搜索树（Search tree）。哈希查找表用一个哈希函数将 key 分配到不同的桶（bucket，也就是数组的不同 index）。这样，开销主要在哈希函数的计算以及数组的常数访问时间。在很多场景下，哈希查找表的性能很高。 哈希查找表一般会存在“碰撞”的问题，就是说不同的 key 被哈希到了同一个 bucket。 一般有两种应对方法：链表法和开放地址法。

链表法将一个 bucket 实现成一个链表，落在同一个 bucket 中的 key 都会插入这个链表。开放地址法则是碰撞发生后，通过一定的规律，在数组的后面挑选“空位”，用来放置新的 key。

搜索树法一般采用自平衡搜索树，包括：AVL 树，红黑树。自平衡搜索树法的最差搜索效率是 O(logN)，而哈希查找表最差是 O(N)。当然，哈希查找表的平均查找效率是 O(1)，如果哈希函数设计的很好，最坏的情况基本不会出现。还有一点，遍历自平衡搜索树，返回的 key 序列，一般会按照从小到大的顺序；而哈希查找表则是乱序的。

Go map 的底层实现

Go 语言采用的是哈希查找表，并且使用链表法解决哈希冲突。

现在到 Go 源代码 map.go中看一看，源码中 Go map 的结构体如下：

hmap 是 hashmap 的缩写：

// A header for a Go map.type hmap struct {    // Make sure this stays in sync with the compiler's definition.    count     int       // 元素数量，调用 len(map) 时，直接返回这个值    flags     uint8     // 状态标志    B         uint8     // log_2 of # of buckets (can hold up to loadFactor * 2^B items)    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details    hash0     uint32 // 哈希 随机数种子
    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
    extra *mapextra // optional fields}

• count 代表 map 中元素的数量

• flags 代表当前 map 的状态（是否处于正在写入的状态等）

• 2 的 B 次幂表示当前 map 中桶的数量，2^B = Buckets size

• noverflow 为 map 中溢出桶的数量。当溢出的桶太多时，map 会进行 same-size map growth，其实质是避免桶过大导致内存泄露。

• hash0 代表生成 hash 的随机数种子

• buckets 是指向当前 map 对应的桶的指针。

• oldbuckets 是在 map 扩容时存储旧桶的，当所有旧桶中的数据都已经转移到了新桶中时，则清空。

• nevacuate 在扩容时使用，用于标记当前旧桶中小于 nevacuate 的数据都已经转移到了新桶中。

• extra 存储 map 中的溢出桶。

Go 中桶 buckets 是 bmap 结构。在运行时只列出了首个字段，即一个固定长度为 8 的数组。此字段顺序存储 key 的哈希值的前 8 位。

// A bucket for a Go map.type bmap struct {    tophash [bucketCnt]uint8}

tophash 通常包含此 buckets 中每个键的哈希值的最高字节。 如果 tophash[0] < minTopHash，则 tophash[0] 是一个桶疏散状态。

map 在编译时即确定了 map 中 key、value 及桶的大小，因此在运行时仅仅通过指针操作就可以找到特定位置的元素。编译期动态地创建一个新的结构：

type bmap struct {    topbits  [8]uint8    keys     [8]keytype    values   [8]valuetype    pad      uintptr    overflow uintptr}

bmap 就是我们常说的“桶”，桶里面会最多装 8 个 key，这些 key 之所以会落入同一个桶，是因为它们经过哈希计算后，哈希结果是“一类”的。在桶内，又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置（一个桶内最多有 8 个位置）。桶在存储的 tophash 字段后，会存储 key 数组和 value 数组。

如何从映射中获取数据（查）

我们需要找到键和值的内存地址。

首先找到桶。它是通过将密钥散列的前 8 位与桶结构中的相应数据存储进行比较来选择的。

接下来通过其地址查找键值。

k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))if t.indirectkey() {    k = *((*unsafe.Pointer)(k))}

接下来以同样的方式找到值。

if t.key.equal(key, k) {    e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))    if t.indirectelem() {        e = *((*unsafe.Pointer)(e))    }    return e}

映射扩增（增）

我们使用 oldbuckets 映射结构属性进行数据迁移。当存储桶中的数据过多时，迁移开始。我们将桶的当前值保存到旧桶中，然后在桶属性中创建双倍数量的桶。映射数据从旧桶复制到桶。 桶的数量总是 2 的幂。 这就是为什么有

B 属性——它是 2 的幂，显示当前的桶数。在迁移映射上是可访问的。这就是为什么在源代码的相同功能中使用存储桶和旧存储桶进行大量工作的原因。迁移后

oldbuckets 设置为 nil。数据的迁移地址可以更改，因此 GO 不允许获取映射值的指针：

mymap := map[string]string{"1": "1"}fmt.Println(&mymap["1"])
// cannot take the address of mymap["1"]

哈希碰撞的解决方式

哈希碰撞（HashCollision），即不同的键通过哈希函数可能产生相同的哈希值。解决哈希碰撞的两种主要的方法：

• 拉链法

• 开放定址法

Go 语言中的哈希表采用的是开放寻址法中的线性探测（LinearProbing）策略，线性探测策略是顺序（每次探测间隔为 1）的。由于良好的 CPU 高速缓存利用率和高性能，该算法是现代计算机体系中使用最广泛的结构。

线性探测，字面意思就是按照顺序来，从冲突的下标处开始往后探测，到达序列末尾时，从序列开始处探测，直到找到一个空位置储存这个 key，当序列都找不到的情况下回扩容（事实上当阵列容量快满的时候就会扩容了）；查询某一个 key 的时候，找到 key 对应的下标，比较 key 是否相等，如果相等直接取出来，否则按照顺寻探测直到碰到一个空位置，说明 key 不存在。

拉链法，简单理解为将元素连结成链表，当 key 的 hash 冲突时，我们在冲突位置的元素上形成一个链表，通过指针相互链接，当查询时，发现 key 冲突，顺着链表一直往下找，直到链表的尾节点，找不到则返回空。

推荐学习资料：

• Principles of map type in GO
  

• 大话图解golang map
  

• map 的实现原理
  

• 深度解密 Go 语言之map
  

• https://github.com/cch123/golang-notes/blob/master/map.md
  

• Go 语言底层原理剖析. 第 8 章 哈希表与 Go 语言实现机制