哈希表与 Map

哈希表是计算机科学中最伟大的发明之一——它把「查找」从 O(n) 直接降到 O(1) 平均，几乎所有的现代软件都离不开它。在 Go 中，map 是内置的关键字，使用极其方便，但它的底层实现却大有学问：hmap 结构、bucket、渐进式扩容、并发安全。本篇将从哈希表的原理讲起，深入 Go map 的实现细节，介绍 sync.Map 的适用场景，并覆盖两数之和、最长连续序列、快乐数等经典算法题。理解哈希表，是写出高效算法的关键一步。

一、哈希表原理

哈希表（Hash Table，也叫散列表）的核心思想是：通过一个哈希函数，把 key 映射到数组的某个下标，从而实现 O(1) 的存取。

1. 哈希函数

哈希函数 hash(key) -> index 需要满足：

确定性：相同的 key 每次哈希结果相同。
均匀性：不同的 key 尽量映射到不同下标，减少冲突。
高效性：计算速度快。

常见的哈希函数：除留余数法 hash(key) = key % m、乘法哈希、字符串哈希（如 FNV、MurmurHash）。Go runtime 内部对字符串和数值类型各有优化的哈希实现。

2. 冲突解决：链地址法、开放地址法

不同的 key 可能哈希到同一下标，这就是「冲突」。两种主流解决方法：

链地址法（Separate Chaining）：每个桶存一个链表，冲突的元素挂在链表上。Java 的 HashMap 用此法。优点是实现简单、装载因子可超 1；缺点是链表过长时查找退化为 O(n)，且链表节点内存不连续影响缓存。

开放地址法（Open Addressing）：冲突时按某种探测规则寻找下一个空位。包括线性探测、二次探测、双重哈希。Go map 采用的是开放地址法的一种变体。优点是所有数据都在数组里，缓存友好；缺点是删除复杂（需标记 tombstone）、装载因子不能太高。

3. 负载因子与扩容

负载因子（Load Factor） = 元素个数 / 桶个数。负载因子越高，冲突概率越大，查找越慢。当负载因子超过阈值时需要扩容：

分配更大的桶数组（通常是原来的 2 倍）。
把所有元素重新哈希到新桶中。

Go map 的负载因子阈值是 6.5（每个 bucket 容纳 8 个 KV），超过即触发扩容。

二、Go map 的底层实现

Go 的 map 不是简单的链地址法，它结合了开放地址法和溢出桶，设计相当精巧。

1. hmap 结构

runtime 中的核心结构（简化）：

type hmap struct {
	count     int             // 元素个数，len(map) 返回它
	flags     uint8           // 状态标志
	B         uint8           // 桶数量 = 2^B
	noverflow uint16          // 溢出桶数量近似值
	hash0     uint32          // 哈希种子，防止哈希攻击
	buckets   unsafe.Pointer  // 指向 2^B 个 bucket 数组
	oldbuckets unsafe.Pointer // 扩容时指向旧桶
	nevacuate uintptr         // 渐进式扩容进度
	extra     *mapextra       // 溢出桶相关
}

2. bucket 结构

每个 bucket 固定容纳 8 个 KV 对：

type bmap struct {
	tophash [8]uint8 // 每个槽位 key 哈希的高 8 位
	// 后面紧跟 8 个 key、8 个 value（编译时根据类型生成）
	// 最后一个字段是指向溢出桶的指针
}

查找过程：

计算 key 的完整哈希值。
用哈希值的低 B 位定位到 bucket。
用哈希值的高 8 位在 bucket 的 tophash 数组中快速比较。
tophash 匹配后再精确比较 key 是否相等。
当前 bucket 没找到，顺着溢出桶指针继续找。

这种「tophash 预筛 + 精确比较」的设计兼顾了速度和正确性。

3. 渐进式扩容

Go map 的扩容不是一次性完成的，而是渐进式的：

双倍扩容：元素太多（负载因子超 6.5），容量翻倍。
等量扩容：溢出桶太多但负载因子没超标，整理碎片（容量不变）。

扩容时，旧桶保留，每次访问 map 时顺便搬迁 1~2 个旧桶到新桶（evacuate）。这避免了单次扩容的卡顿，但意味着扩容期间存在新旧两套桶。

package main

import "fmt"

func main() {
	m := make(map[int]int, 8)
	// 观察扩容行为：不断写入
	for i := 0; i < 50; i++ {
		m[i] = i * 2
	}
	fmt.Println("元素个数:", len(m))
	fmt.Println("读取 m[25]:", m[25])
}

4. map 的并发安全问题

Go map 不是并发安全的：多个 goroutine 同时读写同一个 map 会触发 fatal error: concurrent map read and map write，且这是不可 recover 的致命错误。

package main

import (
	"fmt"
	"sync"
)

func main() {
	m := make(map[int]int)
	var wg sync.WaitGroup

	// 并发写会出问题（演示用，实际会 fatal error）
	// 这里用互斥锁保护
	var mu sync.Mutex
	wg.Add(2)
	go func() {
		defer wg.Done()
		for i := 0; i < 1000; i++ {
			mu.Lock()
			m[i] = i
			mu.Unlock()
		}
	}()
	go func() {
		defer wg.Done()
		for i := 0; i < 1000; i++ {
			mu.Lock()
			_ = m[i]
			mu.Unlock()
		}
	}()
	wg.Wait()
	fmt.Println("并发安全访问完成，元素个数:", len(m))
}

工程中保护 map 的两种方式：

sync.Mutex + map：读写都加锁，简单粗暴。
sync.RWMutex + map：读多写少时性能更好。
sync.Map：读多写极少场景下专用，下面详述。

三、sync.Map：并发安全 Map

sync.Map 是 Go 标准库提供的并发安全 map，它内部维护 read 和 dirty 两个 map：

read 是只读的（无锁），命中率高时性能极好。
dirty 包含新写入的 key，访问需要加锁。
当 dirty 命中次数累积到阈值，会提升为 read。

适用场景：读多写少、key 相对稳定。如果是写多读少，sync.Map 反而比 Mutex+map 慢。

package main

import (
	"fmt"
	"sync"
)

func main() {
	var m sync.Map

	// 存
	m.Store("name", "Alice")
	m.Store("age", 30)

	// 取
	if v, ok := m.Load("name"); ok {
		fmt.Println("name:", v)
	}

	// 取或存
	v, _ := m.LoadOrStore("city", "Beijing")
	fmt.Println("city:", v)

	// 遍历
	m.Range(func(key, value any) bool {
		fmt.Printf("%v -> %v\n", key, value)
		return true
	})

	// 删除
	m.Delete("age")
	_, ok := m.Load("age")
	fmt.Println("age 是否存在:", ok)
}

注意 sync.Map 没有提供 Len() 方法，因为并发环境下统计个数本身就有竞态问题。

四、常见算法

1. 两数之和（哈希表解法）

哈希表最经典的应用：用空间换时间。

package main

import "fmt"

func twoSum(nums []int, target int) []int {
	m := make(map[int]int) // 值 -> 下标
	for i, v := range nums {
		if j, ok := m[target-v]; ok {
			return []int{j, i}
		}
		m[v] = i
	}
	return nil
}

func main() {
	nums := []int{2, 7, 11, 15}
	fmt.Println("两数之和:", twoSum(nums, 9)) // [0 1]
}

2. 字符统计

package main

import "fmt"

func charCount(s string) map[rune]int {
	m := make(map[rune]int)
	for _, c := range s {
		m[c]++
	}
	return m
}

func main() {
	s := "hello world"
	counts := charCount(s)
	// 找出现最多的字符
	maxChar := ' '
	maxCount := 0
	for c, n := range counts {
		if n > maxCount {
			maxChar = c
			maxCount = n
		}
	}
	fmt.Printf("字符统计: %v\n", counts)
	fmt.Printf("最多字符: %c 出现 %d 次\n", maxChar, maxCount)
}

3. 最长连续序列（LC 128）

题目：给定未排序数组，找出最长连续元素序列长度（要求 O(n)）。

思路：用哈希表存所有数，对每个序列起点（即 num-1 不在集合中）向后数长度。

package main

import "fmt"

func longestConsecutive(nums []int) int {
	set := make(map[int]bool)
	for _, n := range nums {
		set[n] = true
	}
	maxLen := 0
	for n := range set {
		// 只从序列起点开始数
		if !set[n-1] {
			cur := n
			length := 1
			for set[cur+1] {
				cur++
				length++
			}
			if length > maxLen {
				maxLen = length
			}
		}
	}
	return maxLen
}

func main() {
	nums := []int{100, 4, 200, 1, 3, 2}
	fmt.Println("最长连续序列:", longestConsecutive(nums)) // 4 (1,2,3,4)
}

4. 快乐数（LC 202）

题目：对正整数，反复把每位平方求和，最终能到 1 是快乐数，否则会陷入循环。

思路：用哈希表记录出现过的数，遇到重复即说明有循环。

package main

import "fmt"

func isHappy(n int) bool {
	seen := make(map[int]bool)
	for n != 1 {
		if seen[n] {
			return false
		}
		seen[n] = true
		n = squareSum(n)
	}
	return true
}

func squareSum(n int) int {
	sum := 0
	for n > 0 {
		d := n % 10
		sum += d * d
		n /= 10
	}
	return sum
}

func main() {
	fmt.Println("19 是快乐数?", isHappy(19)) // true
	fmt.Println("2 是快乐数?", isHappy(2))   // false
}

五、自定义哈希类型

Go 中 map 的 key 必须是可比较类型（comparable）：所有基本类型、指针、channel、数组、结构体（字段都可比）、接口都行。但切片、map、函数不可比较，不能作为 key。

package main

import "fmt"

type Point struct {
	X, Y int
}

func main() {
	// 结构体作为 key
	m := make(map[Point]string)
	m[Point{1, 2}] = "A"
	m[Point{3, 4}] = "B"
	fmt.Println("Point{1,2}:", m[Point{1, 2}])

	// 数组作为 key（注意不是切片）
	arr := make(map[[3]int]string)
	arr[[3]int{1, 2, 3}] = "abc"
	fmt.Println("[1,2,3]:", arr[[3]int{1, 2, 3}])

	// 字符串作为 key
	wordCount := make(map[string]int)
	for _, w := range []string{"go", "rust", "go", "c", "go"} {
		wordCount[w]++
	}
	fmt.Println("词频:", wordCount)

	// 以下会编译错误：切片不能作 key
	// bad := make(map[[]int]int)
}

当用结构体作 key 时，若包含不可比较字段（如切片、map），整个结构体就不可比较，编译会报错。

六、Go map 使用注意事项

遍历顺序随机：Go 故意把 map 遍历顺序随机化，避免开发者依赖顺序。需要有序时把 key 取出排序。

package main

import (
	"fmt"
	"sort"
)

func main() {
	m := map[int]string{3: "c", 1: "a", 2: "b"}
	keys := make([]int, 0, len(m))
	for k := range m {
		keys = append(keys, k)
	}
	sort.Ints(keys)
	for _, k := range keys {
		fmt.Printf("%d:%s ", k, m[k])
	}
	fmt.Println()
}

删除元素：delete(m, key) 是 O(1) 操作，且 key 不存在时不会报错。
零值问题：从 map 取不存在的 key，返回值类型的零值。要区分「不存在」和「值为零」，需用逗号 ok 模式。

package main

import "fmt"

func main() {
	m := map[string]int{"a": 0}
	// 直接取：无法区分「不存在」和「值为 0」
	fmt.Println("a:", m["a"]) // 0
	fmt.Println("b:", m["b"]) // 0

	// 逗号 ok 模式
	if v, ok := m["a"]; ok {
		fmt.Println("a 存在，值:", v)
	}
	if _, ok := m["b"]; !ok {
		fmt.Println("b 不存在")
	}
}

预分配容量：知道大小时用 make(map[K]V, n) 预分配，减少扩容。
map 不能取地址：&m["key"] 会编译错误，因为 map 内部可能扩容，地址会失效。

七、复杂度分析

操作	平均	最坏（哈希冲突严重）
插入	O(1)	O(n)
查找	O(1)	O(n)
删除	O(1)	O(n)
遍历	O(n)	O(n)
扩容	单次均摊 O(1)	-

Go map 的最坏情况非常罕见，因为扩容机制会主动控制负载因子。工程上可以认为 map 操作是 O(1)。

八、小结

哈希表是算法优化的「瑞士军刀」，本篇要点：

原理：哈希函数把 key 映射到数组下标，实现 O(1) 存取；冲突用链地址法或开放地址法解决；负载因子过高触发扩容。
Go map 底层：hmap + bmap（bucket）结构，每个 bucket 容 8 个 KV，用 tophash 高 8 位预筛。采用渐进式扩容，扩容期间新旧桶并存。
并发安全：原生 map 不是并发安全的，并发读写会致命错误。读多写少用 sync.Map，写多用 Mutex/RWMutex + map。
算法应用：两数之和（空间换时间）、字符统计、最长连续序列（只从起点数）、快乐数（检测循环）。
key 要求：必须是 comparable 类型，切片/map/函数不能作 key。结构体作 key 时所有字段都必须可比较。
工程注意：遍历顺序随机、用逗号 ok 区分零值和不存在、预分配容量、不能对 map 元素取地址。

哈希表是后续学习很多数据结构（如哈希集合、LRU 缓存）的基础。下一篇我们将进入树的世界，从二叉树遍历到二叉搜索树、平衡树，再到 Go 标准库的 container/heap，层层递进。

入门篇

进阶篇

资深篇

哈希表与 Map

一、哈希表原理

1. 哈希函数

2. 冲突解决：链地址法、开放地址法

3. 负载因子与扩容

二、Go map 的底层实现

1. hmap 结构

2. bucket 结构

3. 渐进式扩容

4. map 的并发安全问题

三、sync.Map：并发安全 Map

四、常见算法

1. 两数之和（哈希表解法）

2. 字符统计

3. 最长连续序列（LC 128）

4. 快乐数（LC 202）

五、自定义哈希类型

六、Go map 使用注意事项

七、复杂度分析

八、小结

哈希表与 Map ​

一、哈希表原理 ​

1. 哈希函数 ​

2. 冲突解决：链地址法、开放地址法 ​

3. 负载因子与扩容 ​

二、Go map 的底层实现 ​

1. hmap 结构 ​

2. bucket 结构 ​

3. 渐进式扩容 ​

4. map 的并发安全问题 ​

三、sync.Map：并发安全 Map ​

四、常见算法 ​

1. 两数之和（哈希表解法） ​

2. 字符统计 ​

3. 最长连续序列（LC 128） ​

4. 快乐数（LC 202） ​

五、自定义哈希类型 ​

六、Go map 使用注意事项 ​

七、复杂度分析 ​

八、小结 ​

哈希表与 Map

一、哈希表原理

1. 哈希函数

2. 冲突解决：链地址法、开放地址法

3. 负载因子与扩容

二、Go map 的底层实现

1. hmap 结构

2. bucket 结构

3. 渐进式扩容

4. map 的并发安全问题

三、sync.Map：并发安全 Map

四、常见算法

1. 两数之和（哈希表解法）

2. 字符统计

3. 最长连续序列（LC 128）

4. 快乐数（LC 202）

五、自定义哈希类型

六、Go map 使用注意事项

七、复杂度分析

八、小结