Olverae Assets

1 一句话定义

哈希表（hash table）就是用一个「哈希函数」把 key 算成数组下标，直接跳到那个格子存取——理想情况下，插入和查找都只要 O(1)，几乎一步到位。

把它想成带号码的储物柜：与其挨个柜子找你的包，不如有个规则（哈希函数）直接算出"你的包在 3 号柜"，一步取到。问题是可能两个人算到同一个柜子（冲突）——这时就在那个柜子后面挂一串（链地址法）。柜子够多、规则够散，冲突少、查找快；柜子太少或规则太烂，全挤进一个柜子，就退化成从头翻一条长链 O(n)。

8、15、22 都被哈希到桶 [1]（都 %7=1），于是在桶 [1] 后面挂成一条链（链地址法）。下一节你将逐个插入、看冲突怎么形成长链，再查找一个 key 体会"链越长查得越慢"。

2 模型 · 插入看冲突成链，查找看链有多长

7 个桶，哈希函数 hash(key) = key % 7。点 ▶ 看：每个 key 先算出桶号、跳进去；撞上别人就排到那条链的末尾（链地址法）。插完再查一个 key，看它要沿链比较几次。

哈希表（链地址法）怎么定义

一个「桶数组」，每个桶挂一条链表（装哈希到这里的所有 key）。

// 每个桶是一条链表（处理冲突）
struct node { int key; struct node *next; };
struct node *bucket[NBUCKETS];   // NBUCKETS 条链，初始全 NULL

int hash(int key) { return key % NBUCKETS; }   // 把 key 算成桶号

void insert(int key) {
    int h = hash(key);          // 算桶号
    listAppend(&bucket[h], key);  // 挂到该桶的链上（冲突就排队）
}

理想情况下，每个桶最多一两个元素，查找近似 O(1)。但若哈希函数烂（key 都映到同一桶）或负载因子（元素数 / 桶数）太高，链就会很长，查找退化成 O(n)——和直接在一条链表里找没两样。这正是 2521 24T2 Q7 考的"separate chaining 查找代价"。

哈希表演示 · 插入 8,15,22,5,3,17 再查找 22

代码（当前行高亮）

0

已插入元素

0

最长链长度

0.00

负载因子 n/桶数

提示

点 ▶ 演示：每个 key 经 hash=key%7 跳到桶里；撞上就挂到链尾。最后查找 22，看它沿链比较几次。

3 核心要点 · 4 句人话吃透哈希表

每张卡片先一句大白话。重点：哈希函数、冲突处理、负载因子、它为什么可能退化。

① 哈希函数 = key → 下标

一句话：哈希函数把任意 key 算成一个数组下标，于是不用遍历、直接跳过去存取，理想 O(1)。

常见做法 key % 桶数。好的哈希函数要把 key 尽量均匀地散到各个桶，避免扎堆。桶数常取质数，能让取模分布更均匀。

② 冲突在所难免 → 链地址法

一句话：两个 key 算到同一个桶就叫"冲突"。最常见的解决办法是在桶后面挂一条链表（separate chaining）。

冲突时把新 key 挂到那个桶的链上。查找时先定位桶，再沿链逐个比较。另一类做法是"开放定址"（冲突就找下一个空格），本页讲链地址法。

③ 负载因子决定快慢

一句话：负载因子 = 元素数 / 桶数，它衡量"平均每个桶挂多少"。越小越快，过大就该扩容（rehash）。

负载因子越低，链越短、查找越接近 O(1)。一般超过某阈值（如 0.75）就把桶数翻倍、重新哈希所有元素，把链重新打散。

④ 最坏会退化成 O(n)

一句话：哈希烂或太挤时，所有 key 挤进一个桶，哈希表就变成一条链表，查找 O(n)。

"平均 O(1)"是有前提的（哈希均匀、负载合理）。最坏情况（如 hash 永远返回同一个值）查找要走完整条链——这就是 24T2 Q7 让你分析的"最坏查找代价 = 最长链长度"。

理想: 每桶≈1 → 查找 O(1) 退化: 全挤一桶 → 查找 O(n)

4 错误实验室 · 点一下亲眼看 bug

下面 4 个是用哈希表最常翻车的坑——坏哈希退化、不取模越界、负 key 负下标、忽视负载因子。点击卡片看运行效果。

① 坏哈希函数

hash 总返回 0 → 全挤一桶，退化成链表

② 不取模直接当下标

bucket[key]，key 很大 → 数组越界

③ 负 key 算出负下标

key%n 可能为负 → bucket[负数] 越界

④ 负载过高不扩容

元素远多于桶 → 链普遍很长，查找变慢

// 点击上方任一卡片，查看错误代码与运行效果

$ ./a.out （等待运行...）

5 即时小测 · 5 题 + 动手例题

这 5 题正对哈希表套路：哈希函数、冲突处理、查找代价、负载因子、最坏退化。最后到练习系统亲手算桶分布、最长链。

去做例题：哈希表 · 各桶的链长

去做例题