如果要评选「程序员使用频率最高的数据结构」，哈希表（Hash Table）以断层优势夺冠 🏆——Python 的 dict、C++ 的 unordered_map、Java 的 HashMap、Redis 的核心，全是它。本章讲透它的魔法与软肋。
🗺️ Map ADT：字典的抽象
Map 存「键值对（key, value）」：像字典一样，拿单词（key）查释义（value）。核心操作：
get(k)：查 k 对应的值；put(k, v)：插入/更新；erase(k)：删除。
用第 8 章的优先队列或平衡树实现？查找都要 O(log n)。能不能 O(1)？能——用空间换时间的终极表演 🎩。
🪄 魔法拆解：哈希函数
思路：开一个容量为 N 的桶数组（bucket array），用 key 直接算出下标：
index = hash(key) mod N 例：hash("cat") = 742 → 742 % 13 = 1
hash(key) 把任意 key 映射成整数，mod N 压进数组范围。查 "cat" 不用比较、不用遍历——算一下就到了，这就是 O(1) 的来源 ✨。
好哈希函数的两条职业操守：
- 均匀分布：把 key 洒得越均匀越好（书里推荐多项式哈希：
h = (31*h + c) mod N）； - 确定性：同一个 key 每次算出同一个下标。
💥 软肋：碰撞（Collision）
桶就 N 个，key 无限多——两个 key 挤进同一个桶是必然事件（生日悖论：23 个人里两人生日相同的概率超过 50% 🎂）。主流解法：
- 分离链表（separate chaining）：每个桶挂一条链表，撞了就往链上挂——简单、稳，STL unordered_map 用它；
- 开放寻址（open addressing）：撞了就往后找下一个空位（线性探测/二次探测）——省内存，但删除麻烦、容易「扎堆」。
性能守门员：负载因子 λ = n / N（元素数 / 桶数）。λ 越大越挤、链越长。业界经验值：λ 超过 0.9 就 rehash——申请约 2 倍大新桶数组，把所有元素重新散列一遍。虽然 rehash 那一下很贵 O(n)，但均摊到每次插入仍是 O(1)——第 6 章 doubling 策略的老朋友又来了 🤝。
⚠️ 安全提示：攻击者若摸清你的哈希规律，可以构造一批「全部撞进同一个桶」的 key，把 O(1) 恶意拖成 O(n)——哈希碰撞 DoS。所以现代实现都会加盐随机化（random seed）。
📏 想要有序怎么办？
哈希表查得快，但遍历出来是无序的。需要按 key 有序遍历时，两条路：
- 有序映射：用平衡搜索树实现（下一章主角），O(log n) 但有序；
- 跳表（Skip List）：本章最浪漫的结构——在有序链表上「掷硬币」随机建出多层高速通道，查找像坐地铁跳站，期望 O(log n)，实现却比红黑树简单一个数量级。用随机性对抗最坏情况，堪称概率数据结构的启蒙课 🎲。
🎯 本章通关清单
- [ ] 手算一个多项式哈希，解释为什么要 mod 素数
- [ ] 说出两种碰撞解决方案的优缺点
- [ ] 什么是负载因子？什么时候 rehash？
- [ ] 哈希表和有序映射，什么场景选谁？
哈希表快而不有序，平衡树慢一点但有序。下一章把「有序的树」玩到极致：AVL、伸展树、红黑树轮番登场 ⚖️