一、先看最简单的一版

五个水果当 key，桶只有 7 个。用 hash() 算出每个 key 的值，再对 7 取余，得到一个 0 到 6 的桶号。 演示里：苹果到 1 号桶、香蕉到 4 号、橙子到 2 号、西瓜到 6 号、葡萄到 0 号。 放的时候算一次，找的时候再算一次——同一个 key 算出来的桶号一定一样。这就是整个方法的支点。

所以找苹果只要两步：算桶号（1），去 1 号桶里翻。不用从头找。 这和线性搜索的「一个个看」、二分的「对半砍」都不一样：它根本不比大小。和第 5.2 的桶排序一样， 靠的是「算」。

二、哈希函数在做什么

哈希函数把任意 key 变成一个固定范围内的整数。它不需要「有意义」，只需要「稳定」。 稳定指：同一个 key 每次算出来必须一样。否则今天存进去、明天就找不到了。 另一个要求是「散」：不同的 key 尽量落到不同的桶里。散得越匀，链越短，找得越快。

所以哈希函数的质量直接决定哈希表的性能。 这跟排序算法不一样——排序的代码决定快慢，哈希表连函数都得挑。 顺带一句：Python 的 hash() 对字符串加了随机种子， 每次启动算出来的数都不一样。这是为了防止有人故意构造大量冲突来拖慢程序。

三、冲突躲不掉，只能处理

桶只有 7 个，key 有 23 个。按抽屉原理，一定有桶装了两个以上。 演示里统计了一遍：平均每桶 3.3 个，最长的那条链有 5 个。 这就是冲突。最常见的处理法叫链地址法：桶里不放单个值，放一条链表，撞了就挂在后面。

查找变成两步：先算桶号，再在链里找。所以链越短越快——这也是「桶要够多、函数要够散」的原因。 演示里那句提醒别忽略：Python 的 hash 有随机种子，桶里的具体分布每次都变， 但「平均每桶几个」这个量级不变。写结论要按量级写，不能按某次的具体数写。

四、三种查找放一起比

线性、二分、哈希，三种办法并排看最清楚：

哈希表的「1 次左右」是这么来的：算桶号一步，桶里通常只有一两个，翻一下就到。 跟数据总量无关，这是它最狠的地方。 注意「左右」两个字。 冲突多的时候它会退化成链上的线性搜索，所以它不是「永远 O(1)」，是「平均 O(1)」。 三种各有各的位置：线性最笨但零前提；二分要排序；哈希要额外内存和维护成本。 这就是第 3 章那条「没有最快，只有最配」的又一次出现。

五、哈希表的边界：只能按 key 找

哈希表有个容易被忽略的限制：它只认「等于」。 「找 key 是苹果的那条」——它一秒给你。 「找所有分数大于 80 的」——它帮不上忙，因为哈希函数只保证「相等算到同一个桶」。 范围查询、排序、前缀匹配，哈希表都不擅长。这些正是二分和树的强项。

所以真实系统里常常两者并存： 按主键查走哈希（或 B 树），按范围查走索引树。下一节 6.4 会看到数据库怎么选。 还有一条成本：插一个 key 就得跟着改桶结构，还要多占一片内存。 所以数据量很小的时候，用哈希表反而不如直接扫一遍。

六、动手 Demo：几个 key 算成桶号，撞了就挂在链上

先把五个水果算成桶号，看它们各自落到哪个桶。 再塞 23 个 key 进去，统计每个桶里装了几个、最长的那条链有多长。 最后把三种查找的代价列成一张表。

for k in ('苹果', '香蕉', '橙子', '西瓜', '葡萄'):
    print(k, hash(k) % 7)

buckets = [[] for _ in range(7)]
for i in range(23):
    k = 'key%d' % i
    buckets[hash(k) % 7].append(k)
for i, b in enumerate(buckets):
    print(i, len(b), b[:3])
print('最长的链', max(len(b) for b in buckets))

d = {}
for i in range(100000):
    d['key%d' % i] = i
print('字典里有', len(d), '条，取一条：', d['key99999'])

实跑输出：

--------------------------------------------------------------------
哈希表：算一下就知道在哪儿
--------------------------------------------------------------------


  ① 先看最简单的一版
  --------------------------------------------------------------------
  hash('苹果') % 7 = 1
  hash('香蕉') % 7 = 4
  hash('橙子') % 7 = 2
  hash('西瓜') % 7 = 6
  hash('葡萄') % 7 = 0
  桶里的样子：
    [0] ['葡萄']
    [1] ['苹果']
    [2] ['橙子']
    [3] （空）
    [4] ['香蕉']
    [5] （空）
    [6] ['西瓜']
  哈希函数把一个 key 算成一个桶号，之后就往那个桶里放。
  找的时候再算一次，直接到那个桶里翻——不用从头找。

  ② 冲突：两个 key 算到同一个桶
  --------------------------------------------------------------------

| 桶号 | 装了几个 | 算不算挤 |
|---:|---:|---|
| 0 | 2 | 正常 |
| 1 | 2 | 正常 |
| 2 | 4 | 正常 |
| 3 | 3 | 正常 |
| 4 | 5 | 偏挤 |
| 5 | 4 | 正常 |
| 6 | 3 | 正常 |

  23 个 key 塞进 7 个桶，平均每桶 3.3 个，最长的那条链有 5 个。
  冲突躲不掉，只能处理。最常见的处理法是「链地址法」：桶里放一条链表，撞了就挂在后面。
  查找时先算桶号，再在链里找。
  ! 这里用的是 Python 内置 hash，它的结果每次启动都不一样（有随机种子），所以桶里的具体分布会变；
  但「平均每桶几个」这个量级不变。

  ③ 三种查找放一起比
  --------------------------------------------------------------------

| 方法 | 1000 个里找 1 个 | 100 万里找 1 个 | 要不要有序 |
|---|---|---|---|
| 线性搜索 | 最多 1000 次 | 最多 100 万次 | 不用 |
| 二分搜索 | 10 次 | 20 次 | 要 |
| 哈希表 | 1 次左右 | 1 次左右 | 不用 |

  哈希表是三者里最快的，而且不要求有序。
  代价是要多占内存，还要维护那个「桶」的结构——插一个 key 就得跟着改。
  还有一条容易忽略：哈希表只能按 key 找。
  想「找所有分数大于 80 的」，哈希帮不上忙，还是得扫一遍或建索引。这就是它和数据库索引的分工。

①hash(k) % 7 就是全部：算一个哈希值，再对桶数取余，落到 0 到 6 之间。 ②第一个循环打印的桶号和演示里一样吗？ 不一定。Python 的字符串 hash 有随机种子，每次启动结果都不同。 ③第二个循环里 buckets[hash(k) % 7].append(k) 就是链地址法：撞进同一个桶的 key 排在一条链上。 ④最后那段是 Python 自带的字典。它内部就是哈希表，十万条里取一条不用遍历——这就是「算一下就到位」。

30 秒实验

1. 把桶数从 7 改成 3，再看最长的那条链，为什么会变长？
2. 把 % 7 改成 % 23（桶数和 key 一样多），看冲突还剩几个。
3. 想一个你工作里「反复按编号查一条记录」的场景，想想现在用的是什么办法。

常见误区

1. 「哈希表永远是一次查到。」冲突多的时候会退化成链上的线性搜索，是平均 O(1)。
2. 「哈希值算出来是固定的。」Python 对字符串加了随机种子，每次启动都不一样。
3. 「有了哈希表就不需要索引了。」范围查询、排序它都帮不上忙。

搜索数字有套路了，搜索文字呢？一串字符里找另一串，下一节有三代算法排队出场。

• ☐ （本篇完，下一篇 6.3 字符串搜索：朴素、KMP 与 BM）

相关笔记

• 线性搜索与二分搜索
• 桶排序与选择排序
• 17 编程原理 · 索引
• 🧮 写给大家看的算法书 · 索引