0 前言
Go 语言中的 map 是一种内建的数据结构，用于存储键值对。它类似于其他编程语言中的哈希表或字典，提供了快速的插入、删除和查找操作。本文将深入浅出介绍map基本概念、使用方式、核心原理、性能以及最佳实践，帮助读者更好的理解和使用map。
如果您觉得有帮助，请关注我，另公众号【小张的编程世界】，如有任何错误或建议，欢迎指出。感谢您的阅读！
1 map基本概念
定义： map 是一种无序的键值对集合，键和值的类型可以是任何支持相等运算的类型。key 的数据类型必须为可比较的类型，chan、map、func不可比较。
语法：
var m map[string]int // 声明一个键为字符串，值为整数的 map
零值： map 的零值是 nil，一个 nil 的 map 不能存储键值对，必须进行初始化。
并发冲突： map 不是并发安全的数据结构，倘若存在并发读写行为，会抛出 fatal error，并且这是一种比较严重的错误，是无法使用recover操作捕获的，可能直接导致整个服务重启或者不可用。
2 map 使用
2.1 初始化
使用make创建：
// 创建一个空的 map，容量可省略
m := make(map[string]int,10)
直接赋值初始化：
// 创建并初始化一个 map
m := map[string]int{"a": 1, "b": 2, "c": 3}
2.2 插入或更新元素
m["key"] = value // 插入或更新键为 "key" 的值
2.3 获取元素
value := m["key"] // 获取键为 "key" 的值
如果键不存在，返回值类型的零值。要检查键是否存在，可以使用下面的语法：
value, ok := m["key"] // 如果键存在，ok 为 true，否则为 false
2.4 删除元素
delete(m, "key") // 删除键为 "key" 的键值对
2.5 遍历
map 的遍历是无序的
for key, value := range m {
fmt.Println(key, value) // 输出键和值
}
若不关心value值也可采取底下这种方式忽略
for key := range m {
fmt.Println(key)
}
3 核心原理
Go 语言中的 map 是通过哈希表 (hash table) 实现的。它提供了快速的键值对存储、查找、插入和删除功能。为了深入理解 map 的底层实现，我们需要探讨几个关键的概念：哈希函数、哈希桶、键冲突处理、扩容机制
哈希表的核心任务是通过哈希函数将键映射到哈希函桶中，然后在桶中存储键值对。
3.1 哈希函数
定义： 哈希函数是一种将输入数据（通常是任意长度）映射到定长输出数据（哈希值）的函数。
特性：
- 确定性： 即对于相同的输入，总是产生相同的输出。这一特性保证了哈希表等数据结构中的键值对能够准确地存储和检索。
- 高效性： 对于任意输入，哈希函数能够在短时间内生成哈希值。
- 均匀分布： 理想的哈希函数应将输入数据均匀地分布到所有可能的哈希值范围内，尽量避免哈希冲突（不同的输入映射到相同的哈希值）。
- 不可逆性： 给定一个哈希值，很难找到其对应的输入。
- 冲突性： 尽管均匀分布，但是由于输入域（key）无穷大，输出域（hash 值）有限，因此大数据量下必然存在不同 key 映射到相同 hash 值。
3.2 哈希桶
每个桶 (bucket) 是一个存储多个键值对的容器。一个桶通常可以存储 8 个键值对。当一个桶装满时，新的键值对将会被放入到一个新的桶中，形成链表。
3.3 键冲突处理
在 Go 语言的 map 实现中，哈希冲突是通过一种叫做链地址法（也称为拉链法）的技术来解决的。
链地址法的核心思想是将冲突的键值对存储在同一个桶中，并通过溢出桶 (overflow buckets) 来继续存储更多的键值对。
桶的基本结构：每个桶可以存储 8 个键值对。桶中不仅存储键和值，还存储一个 top hash，即键哈希值的高 8 位，用于快速比较和查找。
溢出桶：如果一个桶被填满（即包含了 8 个键值对），那么后续的键值对将被存储在该桶的溢出桶中。溢出桶通过指针链接形成一个链表，这样可以继续存储新的键值对。
3.4 查找操作
当在 map 中查找一个键时，Go 会根据键的哈希值定位到一个特定的桶，然后依次检查桶中的键，比较它们的 top hash 和实际键值。
匹配 top hash：首先比较 top hash，因为这是一个快速的初步检查。如果 top hash 不匹配，那么键肯定不在该桶中。
遍历溢出桶：如果在初始桶中找不到目标键，查找过程会继续在溢出桶中搜索，直到找到键或确定键不存在。
3.5 插入操作
- 计算哈希值：对键进行哈希运算，计算出哈希值，并确定目标桶的位置。
- 插入到桶中：检查目标桶是否有空闲槽位。如果有空位，则直接插入；否则，进入下一步。
- 使用溢出桶：如果目标桶已满（即所有 8 个槽位都被占用），Go 会创建或使用现有的溢出桶，将新键值对存储在溢出桶中。
3.6 扩容机制
当 map 中的键值对数量增多，导致哈希冲突频繁发生时，Go 的 map 会触发扩容机制：
- 渐进式扩容：扩容时，
map会重新分配一个更大的哈希桶数组（通常是当前大小的两倍）。原有的键值对会逐步搬移到新的桶中。每次插入、删除或查找操作时，都会触发一些键值对的迁移，直到整个迁移过程完成。 - 再哈希：在扩容过程中，
map会重新计算键的哈希值，并将它们分配到新的桶中。这一过程有助于减少冲突，优化查找效率。
4 源码走读
go版本为1.22
4.1 数据结构
hmap：
type hmap struct {
count int // 键值对总数，可以使用 len() 内置函数来获取
flags uint8 // 标识位，用于记录和管理map的状态，比如是否被并发读写
B uint8 // 计算哈希桶数值的，哈希桶数量为2的B次方
noverflow uint16 // 溢出桶数量
hash0 uint32 // 哈希种子
buckets unsafe.Pointer // 是一个指向 Bucket 数组的指针 实际存储数据的地方
oldbuckets unsafe.Pointer // 扩容时，保存旧的桶数组的指针
nevacuate uintptr // 扩容时的进度标识。小于这个值的桶已经完成了迁移
extra *mapextra // 指向 mapextra 结构体的指针
}
mapextra：
type mapextra struct {
overflow *[]*bmap // 包含了 hmap.buckets 的溢出桶
oldoverflow *[]*bmap //包含了 hmap.oldbuckets 的溢出桶
nextOverflow *bmap // 下一个可用的溢出桶
}
bmap：
const bucketCnt = 8
// bmap 就是 map 中的桶，可以存储 8 组 key-value 对的数据，以及一个指向下一个溢出桶的指针
type bmap struct {
tophash [bucketCnt]uint8
}
// 上面的 bmap 只是表面(runtime/map.go)的结构，编译期间会动态地创建一个新的结构
// 每组 key-value 对数据包含 key 高 8 位 hash 值 tophash，key 和 value
type bmap struct {
tophash [bucketCnt]uint8
keys [bucketCnt]keytype
values [bucketCnt]valuetype
pad uintptr
overflow uintptr
}
大概结构图如下：
4.2 图解流程
4.2.1 初始化
源码：
func makemap(t *maptype, hint int, h *hmap) *hmap {
mem, overflow := math.MulUintptr(uintptr(hint), t.Bucket.Size_)
// 超出内存可配置范围 置为0
if overflow || mem > maxAlloc {
hint = 0
}
// initialize Hmap
// 为nil 初始化
if h == nil {
h = new(hmap)
}
// 随机一个hash种子
h.hash0 = uint32(rand())
// Find the size parameter B which will hold the requested # of elements.
// For hint < 0 overLoadFactor returns false since hint < bucketCnt.
// 计算桶数组容量
B := uint8(0)
for overLoadFactor(hint, B) {
B++
}
h.B = B
// allocate initial hash table
// if B == 0, the buckets field is allocated lazily later (in mapassign)
// If hint is large zeroing this memory could take a while.
if h.B != 0 {
var nextOverflow *bmap
// 初始化桶数组
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
// 容量比较大，会提前申请一批溢出桶
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
初始化代码流程图如下：
4.2.2 插入数据
大概分为以下几步：
- 根据
key计算出hash值 - 根据
hash值找到对应的桶 - 判断当前是否正在扩容中，如果是则进行迁移工作，推进渐进式扩容
- 遍历该桶，先遍历本桶再遍历溢出桶，遍历过程中会对第一个空位进行标记，同时会判断插入的 key 是否存在桶中
- 如果key存在，则更新对应的 value 并退出遍历
- 否则桶遍历完之后，将元素插入标记的第一个空位
- 如果当前可扩容，则进行扩容，并重新返回第（2）步
源码：
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// 未初始化 直接panic
if h == nil {
panic(plainError("assignment to entry in nil map"))
}
if raceenabled {
callerpc := getcallerpc()
pc := abi.FuncPCABIInternal(mapassign)
racewritepc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.Key, key, callerpc, pc)
}
if msanenabled {
msanread(key, t.Key.Size_)
}
if asanenabled {
asanread(key, t.Key.Size_)
}
// 并发写 直接 fatal
if h.flags&hashWriting != 0 {
fatal("concurrent map writes")
}
// 通过hash种子计算key对应的hash值
hash := t.Hasher(key, uintptr(h.hash0))
// Set hashWriting after calling t.hasher, since t.hasher may panic,
// in which case we have not actually done a write.
// 设置写标记
h.flags ^= hashWriting
// 桶数组为空则进行初始化
if h.buckets == nil {
h.buckets = newobject(t.Bucket) // newarray(t.Bucket, 1)
}
again:
// 通过hash找到对应的桶索引
bucket := hash & bucketMask(h.B)
// 是否在正在扩容
if h.growing() {
// 进行迁移工作
growWork(t, h, bucket)
}
// 获取bucket的地址
b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))
// 获取hash的高8位
top := tophash(hash)
// 3个中间变量 标记 bucket 中出现的第一个空位
var inserti *uint8 // tophash位置
var insertk unsafe.Pointer // key位置
var elem unsafe.Pointer // value位置
bucketloop:
for {
// 外层循环遍历桶链表 先本桶在溢出桶
for i := uintptr(0); i < bucketCnt; i++ {
// 内层循环遍历桶内key-values
if b.tophash[i] != top {
//如果高8位不同，
//如果某个空位的 tophash 是空且 inserti 为 nil，则尝试将 inserti、insertk elem 指向第一个空位，方便后续插入
if isEmpty(b.tophash[i]) && inserti == nil {
inserti = &b.tophash[i]
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
}
// 如果整个桶没有数据（包括溢出桶）直接break
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
// 高8位相等
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
if t.IndirectKey() {
k = *((*unsafe.Pointer)(k))
}
// 对比key和所插入的key是否相同
if !t.Key.Equal(key, k) {
continue
}
// already have a mapping for key. Update it.
// 存在则更新
if t.NeedKeyUpdate() {
typedmemmove(t.Key, k, key)
}
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
goto done
}
// 继续遍历溢出桶
ovf := b.overflow(t)
if ovf == nil {
break
}
b = ovf
}
// Did not find mapping for key. Allocate new cell & add entry.
// If we hit the max load factor or we have too many overflow buckets,
// and we're not already in the middle of growing, start growing.
// 当前不处于扩容中，超过最大负载因子或者太多溢出桶的话，开始扩容
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
// 扩容
hashGrow(t, h)
// 重新开始，扩容会导致key的位置发生变化
goto again // Growing the table invalidates everything, so try again
}
//如果没空位的话，创建一个溢出桶，然后插入
if inserti == nil {
// The current bucket and all the overflow buckets connected to it are full, allocate a new one.
newb := h.newoverflow(t, b)
inserti = &newb.tophash[0]
insertk = add(unsafe.Pointer(newb), dataOffset)
elem = add(insertk, bucketCnt*uintptr(t.KeySize))
}
// store new key/elem at insert position
if t.IndirectKey() {
kmem := newobject(t.Key)
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
if t.IndirectElem() {
vmem := newobject(t.Elem)
*(*unsafe.Pointer)(elem) = vmem
}
typedmemmove(t.Key, insertk, key)
*inserti = top
h.count++
done:
if h.flags&hashWriting == 0 {
fatal("concurrent map writes")
}
h.flags &^= hashWriting
if t.IndirectElem() {
elem = *((*unsafe.Pointer)(elem))
}
return elem
}
插入数据代码流程图如下：
4.2.3 获取数据
大概分为以下几步：
- 根据
key计算出hash值 - 根据
hash值找到对应的桶 - 判断当前是否正在扩容中
- 如果是2倍扩容，将遍历起点往前移2的B次方
- 沿着桶链表依次遍历各个桶内的
key-value对 - 命中相同的
key，则返回value - 倘若
key不存在，则返回零值
源码：
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
if raceenabled && h != nil {
callerpc := getcallerpc()
pc := abi.FuncPCABIInternal(mapaccess1)
racereadpc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.Key, key, callerpc, pc)
}
if msanenabled && h != nil {
msanread(key, t.Key.Size_)
}
if asanenabled && h != nil {
asanread(key, t.Key.Size_)
}
// 未初始化或者数量为0 直接返回零值
if h == nil || h.count == 0 {
if err := mapKeyError(t, key); err != nil {
panic(err) // see issue 23734
}
return unsafe.Pointer(&zeroVal[0])
}
// 其他协程在并发写的话直接fatal
if h.flags&hashWriting != 0 {
fatal("concurrent map read and map write")
}
// 计算key对应的hash值
hash := t.Hasher(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize)))
// 判断oldbuckets是否为空，不为空则处于扩容中
if c := h.oldbuckets; c != nil {
// 如果是2倍扩容
if !h.sameSizeGrow() {
// There used to be half as many buckets; mask down one more power of two.
// 有一半的元素可能在靠前的旧桶位置，所以这里对 m 除以 2。为了确保能够遍历到所有可能存在的位置
m >>= 1
}
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))
// 若旧桶还没迁移完
if !evacuated(oldb) {
b = oldb
}
}
// 获得hash 高8位
top := tophash(hash)
bucketloop:
// 从b开始遍历桶 包括溢出桶
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
// 比较高8位
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
if t.IndirectKey() {
k = *((*unsafe.Pointer)(k))
}
// 找了key
if t.Key.Equal(key, k) {
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
if t.IndirectElem() {
e = *((*unsafe.Pointer)(e))
}
return e
}
}
}
// 没找到，返回类型对应的零值
return unsafe.Pointer(&zeroVal[0])
}
获取数据代码流程图如下：
4.2.4 删除数据
大概分为以下几步：
- 根据
key计算出hash值 - 根据
hash值找到对应的桶 - 判断当前是否正在扩容中，如果是则进行迁移工作，推进渐进式扩容
- 遍历该桶，先遍历本桶再遍历溢出桶
- 若
key存在，删除对应的key-value对,并将当前位置的tophash置为空
源码：
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
if raceenabled && h != nil {
callerpc := getcallerpc()
pc := abi.FuncPCABIInternal(mapdelete)
racewritepc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.Key, key, callerpc, pc)
}
if msanenabled && h != nil {
msanread(key, t.Key.Size_)
}
if asanenabled && h != nil {
asanread(key, t.Key.Size_)
}
// 未初始化或为空直接返回
if h == nil || h.count == 0 {
if err := mapKeyError(t, key); err != nil {
panic(err) // see issue 23734
}
return
}
// 其他协程在并发写直接fatal
if h.flags&hashWriting != 0 {
fatal("concurrent map writes")
}
// 根据key 获得hash值
hash := t.Hasher(key, uintptr(h.hash0))
// Set hashWriting after calling t.hasher, since t.hasher may panic,
// in which case we have not actually done a write (delete).
// 标记为正在写
h.flags ^= hashWriting
// 找到桶位置
bucket := hash & bucketMask(h.B)
// 是否在扩容
if h.growing() {
// 进行迁移工作
growWork(t, h, bucket)
}
b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))
bOrig := b
top := tophash(hash)
search:
for ; b != nil; b = b.overflow(t) {
// 遍历桶链表
for i := uintptr(0); i < bucketCnt; i++ {
// 遍历桶内key-value对
if b.tophash[i] != top {
// 桶内没数据直接break
if b.tophash[i] == emptyRest {
break search
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
k2 := k
if t.IndirectKey() {
k2 = *((*unsafe.Pointer)(k2))
}
// key不相等继续遍历
if !t.Key.Equal(key, k2) {
continue
}
// Only clear key if there are pointers in it.
if t.IndirectKey() {
*(*unsafe.Pointer)(k) = nil
} else if t.Key.PtrBytes != 0 {
memclrHasPointers(k, t.Key.Size_)
}
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
if t.IndirectElem() {
*(*unsafe.Pointer)(e) = nil
} else if t.Elem.PtrBytes != 0 {
memclrHasPointers(e, t.Elem.Size_)
} else {
memclrNoHeapPointers(e, t.Elem.Size_)
}
// 高8位置为空
b.tophash[i] = emptyOne
// If the bucket now ends in a bunch of emptyOne states,
// change those to emptyRest states.
// It would be nice to make this a separate function, but
// for loops are not currently inlineable.
if i == bucketCnt-1 {
if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
goto notLast
}
} else {
if b.tophash[i+1] != emptyRest {
goto notLast
}
}
// 向前遍历将tophash 为 emptyOne的更新为emptySet
for {
b.tophash[i] = emptyRest
if i == 0 {
if b == bOrig {
break // beginning of initial bucket, we're done.
}
// Find previous bucket, continue at its last entry.
c := b
for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
}
i = bucketCnt - 1
} else {
i--
}
if b.tophash[i] != emptyOne {
break
}
}
notLast:
// 删除成功 count-1
h.count--
// Reset the hash seed to make it more difficult for attackers to
// repeatedly trigger hash collisions. See issue 25237.
if h.count == 0 {
// 如果数量为0 更新hash种子
h.hash0 = uint32(rand())
}
break search
}
}
// 校验是否有并发写
if h.flags&hashWriting == 0 {
fatal("concurrent map writes")
}
// 清除标志
h.flags &^= hashWriting
}
删除数据代码流程大概如下：
4.2.5 遍历数据
我们都知道map遍历是无序的，今天就从源码角度来分析下
源码：
func mapiterinit(t *maptype, h *hmap, it *hiter) {
if raceenabled && h != nil {
callerpc := getcallerpc()
racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapiterinit))
}
it.t = t
// 未初始化或数量为0 直接返回
if h == nil || h.count == 0 {
return
}
if unsafe.Sizeof(hiter{})/goarch.PtrSize != 12 {
throw("hash_iter size incorrect") // see cmd/compile/internal/reflectdata/reflect.go
}
it.h = h
// grab snapshot of bucket state
it.B = h.B
it.buckets = h.buckets
if t.Bucket.PtrBytes == 0 {
// Allocate the current slice and remember pointers to both current and old.
// This preserves all relevant overflow buckets alive even if
// the table grows and/or overflow buckets are added to the table
// while we are iterating.
h.createOverflow()
it.overflow = h.extra.overflow
it.oldoverflow = h.extra.oldoverflow
}
// decide where to start
// 决定从哪里开始（随机的）
r := uintptr(rand())
// 选择从哪个bucket开始遍历
it.startBucket = r & bucketMask(h.B)
// 选择从bucket的哪个元素开始遍历
it.offset = uint8(r >> h.B & (bucketCnt - 1))
// iterator state
it.bucket = it.startBucket
// Remember we have an iterator.
// Can run concurrently with another mapiterinit().
if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
atomic.Or8(&h.flags, iterator|oldIterator)
}
mapiternext(it) // 真正遍历的函数
}