06 - 哈希表：为什么查东西能「秒查」

哈希表是实际开发中用得最多、最重要的数据结构，没有之一。你天天在用的 Python 字典 dict、Java 的 HashMap、JavaScript 的对象，底层都是它。这一章讲清楚它凭什么能「秒查」。

先看它解决的痛点

假设你要存一堆「学号 → 姓名」，然后频繁地「给我学号 1007 的姓名」。

• 用数组/链表存：查一个得从头找，最坏要看完所有人，O(n)，人一多就慢。
• 有没有办法不管有多少数据，查一个都几乎一步到位？有，就是哈希表，O(1)。

这快得有点像变魔术，秘密在于一个巧妙的想法。

核心思想：让「值」自己算出「该存在哪」

普通查找慢，是因为你不知道数据在哪，只能挨个找。哈希表的天才之处是：不挨个找，而是根据数据本身，直接算出它该待的位置。

具体做法：

1. 准备一个大数组（叫「桶」）。
2. 存数据时，把「键」（比如学号）丢进一个特殊函数——哈希函数——它会算出一个数字，作为数组下标。
3. 把数据存到这个下标的位置。
4. 查数据时，再用同一个哈希函数算一遍，立刻算出它在哪个下标，直接跳过去取。

存 "学号1007→张三":
   "1007" ──哈希函数──▶ 算出下标 3 ──▶ 存到数组第 3 格

查 "学号1007":
   "1007" ──哈希函数──▶ 又算出下标 3 ──▶ 直接看第 3 格，拿到张三

因为「算下标」这步和数据总量无关（算一次就出结果），再「按下标取数组」又是 O(1)（数组的看家本领，第 03 章），所以整体查找是 O(1)——不管你存了 10 个还是 1000 万个，查一个都几乎一样快。

关键转变：从「挨个找」变成「算出来直接拿」。 这就是秒查的本质。

哈希函数：把任意键变成一个数字

哈希函数就是那个「把键变成数组下标」的转换器。它有两个要求：

• 同样的输入，永远得到同样的输出（不然存进去就找不着了）。
• 尽量把不同的键均匀地打散到不同下标（不然都挤到一个格子就慢了）。

你不用会自己设计哈希函数，只要理解它的作用：把五花八门的键（数字、字符串……）映射成一个数组下标。

绕不开的问题：哈希冲突

理想很美好，但有个躲不掉的麻烦：两个不同的键，可能算出同一个下标。这叫哈希冲突。

就像两个人算出来要坐同一个座位，怎么办？最常见的解法叫拉链法：

数组的每个格子不直接存数据，而是挂一个小链表。算到同一个下标的多个数据，就挂在这个格子的链表上。查找时先算下标定位到格子，再在这个小链表里找。

下标 3: ● ──▶ [学号1007→张三] ──▶ [学号2013→李四]
              （这两个键碰巧算到了同一个下标，就串成一串）

• 只要哈希函数设计得好、冲突少，每个格子的小链表都很短，查找依然接近 O(1)。
• 但如果冲突严重（大量键挤到少数格子），链表变长，就退化成慢慢找，接近 O(n)。所以「好的哈希函数 + 别太挤」很重要（数据太满时哈希表会自动扩容来缓解）。

哈希表的「软肋」

哈希表查得飞快，但天下没有免费的午餐，它也有代价：

• 数据是无序的：哈希函数把数据打得七零八落，所以哈希表里的数据没有顺序。你要「按大小排好序遍历」「找最小的几个」，哈希表帮不了你——那是树（下一部分）的强项。
• 费一点内存：为了减少冲突，数组通常留有余量，不会塞满。
• 最坏情况会退化：冲突严重时性能下降。

用在哪

• 任何「按键查值」的需求：缓存（key→value）、去重（判断某个东西见过没）、统计次数（词频统计）、数据库索引的一种……
• 一句直觉：「我想根据一个唯一标识，快速找到对应的东西」——第一反应就该是哈希表。

小结

• 哈希表能做到查找 O(1)「秒查」，是实际开发中最常用的结构（dict / HashMap 底层）。
• 核心思想：不挨个找，而用哈希函数根据键直接算出存储下标，一步定位。
• 哈希函数：把任意键映射成数组下标，要求「同输入同输出」且「打散均匀」。
• 躲不开哈希冲突（不同键算到同一下标），常用拉链法（每格挂个小链表）解决；冲突太多会退化变慢。
• 软肋：数据无序（要有序/找最值请用树）、略费内存。
• 直觉：「按唯一标识快速找对应值」就想到哈希表。

下一章 → 07 - 树：从家谱到文件夹 ｜ 回到 README 目录