Go语言

Golang——hashmap

编程Cookbook

• 14 min read
Golang——hashmap
大家好，这里是编程Cookbook。本文详细介绍golang的哈希表的底层实现、扩容机制、插入查询过程以及并发安全性。

定义

字典（Map）类型其实是哈希表（Hash Table）的一个实现。字典用于存储键-值对的无序集合。

Key无序性

为什么 map 的 key 无序？扩容后键重新分布：键值对的存储位置随着扩容发生显著变化。随机化遍历起点：遍历时从随机 bucket 和随机 cell 开始，避免返回固定顺序。防止误解：杜绝程序员误以为 map 有固定的遍历顺序，避免潜在错误。语言特性：从 Go 1.0 起就设计为无序，以保持哈希表特性的一致性。

Key唯一性

注意： 同一个字典中的每个键都是唯一的。如果我们在向字典中放入一个键值对的时候其中已经有相同的键的话，那么与此键关联的那个值会被新值替换。

Key可比性

字典的 键类型必须是可比较的（支持 == 和 != 运算的类型），否则会引起错误。也就是说，map的键不能是切片、字典或函数类型，可以是布尔值、数字、字符串、指针、通道、接口类型、结构体、只包含上述类型的数组。
从语法上看，float 类型符合键的要求，但慎用。虽然 float 类型符合 Go 的 map 键要求（可比较），但由于浮点数的特性，如精度问题、NaN 的特殊性以及底层的哈希机制，使用 float 类型作为键可能导致一些诡异行为。

基本使用

  1. 使用字面量或者内置函数make进行声明。
  2. v,ok:=m[key] 查找key是否存在，返回v为key对应的value，如果不存在则为对应类型零值，ok为bool表示是否存在。

内置函数 delete 用于删除 map 中指定键的元素。如果 map 为 nil 或不存在该键，delete 是无操作的。

// The delete built-in function deletes the element with the specified key
// (m[key]) from the map. If m is nil or there is no     such element, delete
// is a no-op.
func delete(m map[Type]Type1, key Type)

底层实现

哈希表实现hmap

字典使用哈希表作为底层实现，一个哈希表里可以有多个哈希表节点（bucket），而每个 bucket 保存了 map 中的一个或一组键值对。

map 的数据结构由 runtime/map.go 中的 hmap 定义：

type hmap struct {
    count     int // 当前保存的元素个数
    ...
    B         uint8  // 指示 bucket 数组的大小
    ...
    buckets   unsafe.Pointer // bucket 数组指针，数组的大小为 2^B
    ...
}

示例：一个拥有 4 个 bucket 的 map：

g-3-1.png

​​​​​​​​

  • hmap.B = 2
  • hmap.buckets 长度为 2^B = 4。

元素经过哈希运算后会落到某个 bucket 中进行存储。查找过程类似。

bucket 数据结构bmap

bucket很多时候被翻译为桶，所谓的哈希桶实际上就是bucket。
bucket 的数据结构由 runtime/map.go 中的 bmap 定义：

type bmap struct {
    tophash [8]uint8 // 存储哈希值的高 8 位
    data    byte[1]  // key-value 数据: key/key/key/.../value/value/value...
    overflow *bmap   // 溢出 bucket 的地址
}
  • 每个 bucket 可以存储 8 个键值对。
  • tophash [8]uint8 是一个 包含 8 个元素的数组，每个元素是 8 位（1 字节）的无符号整数，存储的是 键的哈希值的高 8 位。低位用来选择桶，高位区分桶中不同的项。哈希值相同的键（准确的说是哈希值低位相同的键）存入当前bucket时会将哈希值的高位存储在该数组中，以方便后续匹配。
  • data 区存放的是 key-value 数据，顺序为 key/key/.../value/value/...，以节省字节对齐带来的空间浪费。
  • overflow 指针指向的是下一个 bucket，用类似链表的方式将 bucket 连接起来以解决冲突。
注意：上述中data和overflow并不是在结构体中显示定义的，而是直接通过指针运算进行访问的。

例子

假设一个 bmap 存储 3 个键值对（k1/v1, k2/v2, k3/v3）【最大8个】：

tophash = [0xA3, 0xB7, 0x12, ...]  // 每个元素是键哈希的高8位
data    = [k1][k2][k3][v1][v2][v3]       // 紧凑存储，无指针开销
overflow = nil                           // 无溢出 Bucket

查找流程：

  1. 计算目标键 k2 的哈希高 8 位（假设为 0xB7）。
  2. 扫描 tophash 找到 0xB7 在索引 1 的位置。
  3. 从 data 的偏移量读取 k2 和 v2。

下图展示bucket存放8个key-value对：

g-3-2.png

链地址法哈希冲突

当有两个或以上的键被哈希到同一个 bucket 时，就发生了冲突。Go 使用链地址法解决冲突。

  • 每个 bucket 可以存放 8 个键值对。
  • 超过 8 个键值对时会创建溢出（overflow） bucket，将其连接到原 bucket。

下图展示产生冲突后的map如下：

g-3-3.png

事实上哈希冲突并不是好事情，它降低了存取效率，好的哈希算法可以保证哈希值的随机性，但冲突过多也是要控制的，这就需要负载因子。

负载因子

负载因子衡量哈希表的冲突情况：

负载因子 = 键数量 / bucket 数量

例如，对于一个bucket数量为4，包含4个键值对的哈希表来说，这个哈希表的负载因子为1.

哈希表需要将负载因子控制在合适的大小，超过其阀值需要进行rehash，也即键值对重新组织：

  • 负载因子过小：空间利用率低。
  • 负载因子过大：冲突严重，存取效率低。

每个哈希表的实现对负载因子容忍程度不同，Go 中负载因子达到 6.5 时会触发扩容，而 Redis 负载因子大于 1 就触发扩容。

因为Redis的每个bucket只能存1个键值对，而Go的bucket可能存8个键值对，bucket满后会使用链地址法解决冲突，所以Go可以容忍更高的负载因子。

扩容

增量扩容

当负载因子过大时，Go 会新建一个 bucket，长度为原来的 2 倍，将旧 bucket 的数据搬迁到新 bucket。考虑到如果map存储了数以亿计的key-value，一次性搬迁将会造成比较大的延时，Go 使用逐步搬迁策略：

  • 每次访问 map 时都会触发搬迁，每次搬迁 2 个键值对。

下图展示了包含一个bucket满载的map(为了描述方便，图中bucket省略了value区域):

g-3-4.png

当前map存储了7个键值对，只有1个bucket。此地负载因子为7。再次插入数据时将会触发扩容操作，扩容之后再将新插入键写入新的bucket。

当第8个键值对插入时，将会触发扩容，扩容后示意图如下：

g-3-5.png

hmap数据结构中 oldbuckets成员指身原bucket，而buckets指向了新申请的bucket。

新的键值对被插入新的bucket中。 后续对map的访问操作会触发迁移，将oldbuckets中的键值对逐步的搬迁过来。当oldbuckets中的键值对全部搬迁完毕后，删除oldbuckets。

搬迁完成后的示意图如下：

g-3-6.png

数据搬迁过程中原bucket中的键值对将存在于新bucket的前面，新插入的键值对将存在于新bucket的后面。 实际搬迁过程中比较复杂，将在后续源码分析中详细介绍。

等量扩容

等量扩容并不会增加容量，而是把松散的键值对重新排列一次，提高 bucket 的使用率。适用于以下极端场景：

  • 大量增删操作导致键值对集中在少数 bucket，而负载因子不高，无法触发增量扩容。如下图所示：
g-3-7.png

上图可见，overflow的buckt中大部分是空的，访问效率会很差。此时进行一次等量扩容，即buckets数量不变，经过重新组织后overflow的bucket数量会减少，即节省了空间又会提高访问效率。

查找过程

查找过程如下：

  1. 计算哈希值：
    根据 key 值计算哈希值，确定键的哈希分布。
  2. 定位 bucket：
    取哈希值的低位与 hmap.B 取模，确定目标 bucket 的位置。
  3. 查找 tophash：
    在 bucket 的 tophash 数组中查找哈希值高位，用于快速定位可能的键。
  4. 比较键值对：
    如果 tophash 匹配，进一步比较 bucket 中的实际键（key）值，确认是否找到目标键。
  5. 处理溢出 bucket：
    如果当前 bucket 未找到目标键，则继续查找其溢出 bucket（overflow bucket）。
  6. 处理扩容中间态：
    如果 map 正在扩容，需同时检查新旧 bucket：
    • 先查找新 bucket。
    • 对未搬迁的旧 bucket，判断其 tophash[0] 是否在 (0,4) 区间内：
      • 已迁移：直接查找新 bucket。
      • 未迁移：从旧 bucket 中筛选符合当前 bucket 的键（基于 lowbits 判断键是否属于当前新 bucket）。
  7. 返回结果：
    • 如果找到目标键，返回其值。
    • 如果查找不到，返回对应类型的零值（0、""、nil 等）。

注：查找不到时，返回对应类型的零值。

Go 的 map 扩容期间先查新表，再按需查旧表；
Redis 的 dict 则先查旧表，再查新表。

插入过程

以下是整合了具体赋值过程的 Go 中 map 赋值流程：

  1. 计算哈希值：定位 bucket。
  2. 并发检查：检测写标志位，防止多协程冲突。
  3. 扩容检查与搬迁：
    • 判断是否正在扩容。
    • 若是，确保老 bucket 数据迁移完成。
  4. 定位插入点：
    • 遍历当前 bucket 和其 overflow bucket。
    • 找到空位或匹配键，记录插入点。
  5. 扩容触发与重新定位：
    • 判断是否需要扩容，必要时重新查找插入位置。
  6. 插入或更新键值：
    • 空闲位置插入新键。
    • 匹配位置直接更新值。
  7. 更新状态：
    • 扩容后更新键值分布。
    • 更新元素计数 count。
    • 清除写标志位。
  8. 返回值指针：返回键值对中 value 的指针，用于完成赋值操作。
如果写标志位 (hashWriting) 被置为 1，说明当前有其他协程在写入。程序此时会 panic，因为 Go 的 map 不支持并发写操作。

删除流程

  1. 写操作安全检查：检查写标志位，防止并发写冲突。
  2. 定位目标 bucket：通过哈希值找到目标 bucket。
  3. 检查扩容状态：如果正在扩容的过程中，直接触发一次搬迁操作。
  4. 查找目标键：在 bucket 和 overflow bucket 中查找 key 的位置。
  5. 清除键值对：
    • 使用 typedmemclr 或设置指针为 nil 清除 key 和 value。
  6. 更新状态：
    • 将 tophash 值置为空。
    • 减少 count 值，更新元素计数。

非并发安全

Go 的 map 不是线程安全的，在并发情况下，只读是线程安全的，同时读写是线程不安全的。

  • 多个协程中，如果多个协程同时对一个 map 执行只读操作（例如查找键值），是线程安全的。 map 的只读操作不会修改其内部结构，不会引发竞态条件。
  • 多个协程中，如果一个协程对 map 执行写操作（如插入或删除键值对），而另一个协程同时执行读操作，则会引发数据竞态问题。Go 会在运行时检测到并触发 panic，提示：concurrent map writes。
  • 在同一个协程内操作 map，包括遍历、删除、插入等，是安全的，但需要注意操作的顺序和可能的行为。
Go 的 map 本质是单协程（single goroutine）安全的，因此单线程内可以同时进行读和写操作，而不会引发 panic 或数据错误。但是不推荐这样做，插入/删除的键可能出现在遍历结果中，也可能不出现。

map 的线程安全机制

写标志机制

  • 每次写操作（如插入或删除键值对）都会设置一个写标志 hashWriting，来防止并发写引发的不一致问题。
  • 如果在写标志置位期间再次发生写操作，Go 会检测到并触发 panic。

写标志代码示例

设置写标志：

h.flags |= hashWriting

检测写标志：

if h.flags&hashWriting == 0 {
    throw("concurrent map writes")
}

解决方案

1. 使用读写锁

使用 sync.RWMutex 保护 map 的读写操作：

  • 读锁：
    • 调用 RLock() 进行读操作。
    • 读完后调用 RUnlock() 解锁。
  • 写锁：
    • 调用 Lock() 进行写操作。
    • 写完后调用 Unlock() 解锁。

示例：

package main

import (
	"fmt"
	"sync"
)

func main() {
	var mu sync.RWMutex
	m := make(map[int]string)

	// 写操作
	mu.Lock()
	m[1] = "one"
	mu.Unlock()

	// 读操作
	mu.RLock()
	fmt.Println(m[1])
	mu.RUnlock()
}

2. 使用 sync.Map

  • sync.Map 是 Go 提供的线程安全 map，适用于高并发场景。
  • 特性：
    • 支持并发读写。
    • 提供内置的遍历和删除方法。

示例：

package main

import (
    "fmt"
    "sync"
)

func main() {
    var sm sync.Map

    // 写入
    sm.Store(1, "one")
    sm.Store(2, "two")

    // 读取
    val, ok := sm.Load(1)
    if ok {
        fmt.Println(val)
    }

    // 删除
    sm.Delete(1)

    // 遍历
    sm.Range(func(k, v interface{}) bool {
        fmt.Printf("%v: %v\n", k, v)
        return true
    })
}

Q&A

key 和 value 为什么不能取地址？

  1. 不能取地址的原因：
    • 键和值可能因扩容或哈希冲突而重新分配内存。
    • 为避免内存安全问题，Go 禁止直接对 map 的键或值取地址。
  2. 解决方案：
    • 使用临时变量。
    • 将值存储为指针类型。
    • 用 struct 包装值。

比较两个 map 是否相等的方法

  1. 检查长度是否一致。
  2. 遍历其中一个 map，检查每个键值对是否存在于另一个 map 中。
  3. 对于复杂值类型，使用嵌套比较或 reflect.DeepEqual（内置函数，可以递归比较复杂数据结构）。

虽然 Go 不支持直接比较 map，但通过这些方法可以实现灵活且安全的比较逻辑。

Una comparación útil de camisetas de fútbol versión jugador comienza por la construcción del escudo y otros acabados. Antes de pagar, es útil verificar la guía de tallas específica para cada tipo de corte.