Golang map 的底层原理

前言

本文介绍 golang 中 map 的实现方式, 希望对读者和我有所帮助

结构

map是 go 语言中的基础的数据结构, 在寻找指定key时, 复杂度是O(1), 在某些场景能发挥很大的作用

golang 的 map 是 hashmap, 实现方式是数组+链表, 并且使用拉链法来取消 hash 的冲突

map 主要有两个核心的数据结构, hmap和bmap(bucket), 为什么说他核心呢? 因为 map 的实现就是依靠这两个结构体

hmap的结构有以下几个字段

• 元素个数: int
• flags: uint8
• 扩容字段: uint8
• 溢出的 bucket 数量: uint16
• 用于扩容的指针: *mapextra
• buckets 数组指针: unsafa.Pointer
• 搬迁进度: uintptr
• 扩容时用于复制的 buckets 数组: unsafe.Pointer
• hash seed: uint32

这里你需要重点了解的是buckets 数组指针, 也就是bmap, 那么bmap的结构如下

• 高位哈希: [8]uint8
• 字节数组(存储 key 和 value 的数组): []bytes
• 指向扩容 bucket 的指针: pointer

在bmap的字节数组中, 存储了我们真正的key和value

而高位哈希中存储了key的索引

指向扩容 bucket 的指针则存储了下一个bmap的位置, 所以说 bucket 是链表形式

对于bmap中的字节数组部分存储这个bmap里面的所有key和value, 他是一个数组, 里面存储的结构是这样的

key0, key1, key2, value0, value1, value2

是将所有的 key和key排在一起,value和value排在一起

这是为了内存对齐, 目的是减少空间浪费

也就是说, hmap的结构应该是

		       hmap
														
bmap0  bmap1  bmap2
|      |      |
bmap3  bmap4  bmap5
|      |      |

这种关系(我真是灵魂画手