📦 哈希表

在千万条记录里找一条数据，最快能有多快？哈希表说：平均只要一步！它靠一个「哈希函数」把数据直接换算成位置，像按门牌号找家一样。这一页学哈希函数、冲突是怎么来的、又怎么用链地址法和线性探测解决冲突。

考纲知识点：哈希表的概念与知识及其应用

📖

考纲 · 知识点详述

摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 七级

(4)掌握哈希表的概念与知识及其应用。

📚

先学一学

花 5 分钟读完下面 4 课，再去闯关就不慌啦

🔑 哈希表：一把钥匙开一个柜子

想象一个巨大的快递柜，柜子有编号 0、1、2……如果你记住「每一件快递该放几号柜」，取件时直接走到那个柜子开门就行，不用一个柜一个柜地找。哈希表（Hash Table）就是这个快递柜：它能存「键 → 值」，比如「用户名 → 头像」「学号 → 成绩」。

🧮 哈希函数：算柜门号的小公式

把「键」变成「柜门号」的函数叫哈希函数（散列函数）。比如存整数时常用取余：h(x) = x % 11。键 22 → 22 % 11 = 0，就放进 0 号柜；键 33 → 33 % 11 = 0，也想进 0 号柜……咦，撞车了！

💡 口诀：哈希函数像门牌号算法，把每个键「算」出一个柜门号。

🕊️ 为什么平均只要 O(1)？

数组要一个个比着找（O(n)），哈希表却直接拿键算位置、开门取货，不用和别人比来比去，所以平均查找时间是 O(1)。这是它最厉害的地方。

💥 哈希冲突：两个键抢一个柜子

柜子数量有限，不同的键完全可能算出同一个位置，这就叫哈希冲突（碰撞）。别慌，冲突一定会发生：想象有 11 个柜门却要塞 12 件快递，不管怎么分配，至少有一个柜门要塞两件——这是「抽屉原理」说的。

🪵 为什么选素数也躲不开冲突？

常用取余哈希 h(x) = x % p 会把 p 选成素数，这是为了让键分布更均匀，但并不代表就不会冲突：22 % 11 和 33 % 11 都等于 0，照样撞在一起。素数只能减少、不能消灭冲突。

💡 口诀：抽屉原理兜底——元素比柜子多，冲突躲不掉；素数取模只是让它们少撞点。

📈 装填因子：柜子满不满

装填因子 = 已存元素 ÷ 柜子总数。它越大，说明柜子越满，发生冲突的概率越高。所以哈希表装得太满时，一般会「扩容」换一张更大的表。

🧯 解决冲突：链地址法和线性探测

冲突了怎么办？好办法是把「多出来的元素」好好安置，而不是扔掉或覆盖。最常用的两招：

⛓️ 链地址法：一个柜门挂一条链子

每个哈希位置不直接放一个元素，而是放一条链表：撞到同一位置的元素，就一个个挂到同一条链子上，像串糖葫芦。C++ 里 unordered_map 就常用这种思路。最坏情况是「所有元素都挤进同一个槽」，那条链子长 n，查找就退化到 O(n)。

💡 口诀：链地址法＝一个柜门一条链，撞车元素排排挂；全挤一窝最坏 O(n)。

🚶 开放定址：往后找空位

冲突了不挂链子，而是在表里继续往后找第一个空位放进去，这叫线性探测（开放定址法的一种）。例如 h(x) = x % 11 先放 22 → 0 号，再放 33 时 0 号被占了，就放到 1 号空位。找元素时也从算出的位置往后找；走到头就绕回 0 号继续。开放定址法删元素时要小心（会打断探测链），所以实现相对复杂。

💡 口诀：线性探测像停车找车位——这个满了，往后挪一格；再不行，继续往后。

🚫 哪些不是好办法？

把新元素扔掉、或用新元素覆盖旧元素都不是合理解决冲突——数据丢了！另外「二分查找法」是搜索算法，不是哈希的冲突解决策略。真正常见策略是链地址法、开放定址法、二次哈希法等。

🌍 哈希表在哪儿：词典、缓存与密码

只要需要「给一个键，快速找到对应的值」，哈希表就大显身手：

📱 身边的哈希表

· 词典：查「单词 → 意思」。

· 缓存（Cache）：网站记住「用户 → 头像/购物车」，下次直接取。

· 编译器/数据库：快速查变量名、建立索引。

· 消息校验：把大文件「哈希」成一串短码，比对是否被改过（校验和、MD5 就是哈希思想的应用）。

💡 口诀：一键一值快速找，词典缓存都在用；哈希一算定位子，平均一步就找到。

🧪 读代码：C++ 的哈希表

看得懂就好，不用背：

#include <unordered_map>
unordered_map<string, int> score;
score["小明"] = 100; // 存：键"小明" → 值 100
cout << score["小明"]; // 取：直接报 100

🎯

闯关小锦囊 · 考点提醒

哈希表用哈希函数把键直接算成位置，平均查找 O(1)；不是每次都一定 O(1)。
哈希冲突：不同键算出同一位置。抽屉原理说明元素比槽位多时冲突不可避免。
取余哈希选素数能让分布更均匀，但不能保证不冲突。
链地址法：同一位置挂链表；所有元素挤同一个槽时最坏查找 O(n)。
线性探测（开放定址）：冲突后往后找第一个空位；删除元素实现相对复杂。
「丢弃新元素」「覆盖旧元素」不是合理解决冲突；二分查找也不是哈希冲突策略。
装填因子 = 元素数 ÷ 槽位数，越大越容易冲突，太满要扩容。

🎮

学完了？来闯关！

下面 16 个小挑战，点一点就能玩

Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。