前言

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

结构

mapkeyO(1)

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

hmapbmap(bucket)
hmap
  • 元素个数: int
  • flags: uint8
  • 扩容字段: uint8
  • 溢出的 bucket 数量: uint16
  • 用于扩容的指针: *mapextra
  • buckets 数组指针: unsafa.Pointer
  • 搬迁进度: uintptr
  • 扩容时用于复制的 buckets 数组: unsafe.Pointer
  • hash seed: uint32
buckets 数组指针bmapbmap
  • 高位哈希: [8]uint8
  • 字节数组(存储 key 和 value 的数组): []bytes
  • 指向扩容 bucket 的指针: pointer
bmapkeyvalue
key
bmap
bmapbmapkeyvalue
key0, key1, key2, value0, value1, value2

keykeyvaluevalue

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

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

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

hmapbmapbmapbmapkeyvaluebmap

新增 key 时

keyvaluekey高位低位低位keybmap高位keybmap

map 扩容

bmapbmap

然后把老的数据迁移到新的数组中

bmapbmap
bmapbmap

查找 key 时

key高位低位低位bmap高位bmap