第 04 章

哈希表——一个裁缝如何改变计算机寻找信息的方式

正在加载交互实验…

第一季 · 人类如何驯服数据

历史主线：1941—1963年，从 IBM 的信息检索研究到哈希冲突的数学分析

序幕：一百万份资料，只有一个问题

1953年，美国纽约。假设你正在一家大型研究机构工作。资料室里存放着一百万份科研记录。每份记录有一个唯一编号，管理人员每天都需要按照编号检索资料。如果使用普通无序数组，最坏情况下，需要比较一百万次。你可能会说：“那就把资料排好序，使用二分查找。”确实。对于一百万条记录，二分查找只需要大约20次比较就能确定位置。这已经非常了不起了。可是，资料每天都在新增、修改、删除。维持有序可能需要额外的更新成本。更重要的是，一个新的想法正在酝酿：我们为什么非得搜索？能不能直接根据编号，计算出这条记录应该存放的位置？这就是哈希技术背后极具突破性的思想。而根据 Donald Knuth 对早期文献的考证，提出这一思想的最早记录之一，来自一位经历相当特别的 IBM 研究人员。他不是传统意义上的数学家。他曾经是一名纺织行业的技术人员。他的名字叫：Hans Peter Luhn。

第一幕：1896年出生的德国少年，最初研究的竟然是纺织品

Hans Peter Luhn

1896—1964 · 德裔美国发明家、信息科学先驱Luhn 的研究横跨机械工程、信息检索、文献自动索引与商业情报。他的工作对于后来计算机处理文字和数据库记录具有深远影响。

Luhn 于1896年出生在德国巴门（Barmen），后来进入纺织行业，研究过纺织生产中的机械与技术问题。他拥有大量专利和发明。在今天看来，这似乎与哈希表毫无关系。但如果仔细观察，就会发现一种共同的思维方式。纺织工业要处理复杂而重复的生产流程：如何对材料进行分类，如何快速判断某种模式，以及如何通过机械装置减少人工操作。这些问题与信息检索有一个共同之处：如何将大量具体事物转化成可以自动识别、组织和处理的模式。当然，这只是我们对其研究方法的分析，不能据此断言他直接从某种纺织机械获得了哈希算法的灵感。1941年，Luhn 加入 IBM。与许多专注数值计算的工程师不同，他越来越关注一个问题：计算机能不能帮助人类处理文字和信息？当时，这个问题还远没有今天这样普遍。

为什么文字比数字难处理？

对于数字，计算机可以执行加减乘除。但对于一篇论文，它需要回答：论文在研究什么？哪些词语最重要？它与另一篇论文有什么关系？怎样在大量论文中找到某个研究主题？第二次世界大战之后，科学研究快速发展，研究论文、技术报告和商业信息大量增长。信息检索逐渐成为一个独立而重要的研究领域。Luhn 早年就在尝试利用穿孔卡片、机械装置与信息编码技术，让机器协助人们寻找资料。后来他开发的 KWIC（Keyword in Context，关键词上下文索引）技术，也在文献检索史上占据重要位置。1958年，他还发表了著名的论文 A Business Intelligence System，讨论利用机器辅助管理和传播企业信息。今天我们经常使用的 Business Intelligence（BI）一词，与这篇早期论文存在重要的历史联系。^{[IEEE Spectrum][数学 FTP 站点]}但在1953年，他面对的是一个更基础的难题：如何快速定位一条记录？

第二幕：1953年1月，一份没有公开发表的备忘录

这是本章最关键的历史节点。1953年1月，Luhn 在 IBM 的一份内部备忘录中，描述了通过记录的键值计算存储位置，再利用桶和链式结构处理记录的思想。这份备忘录没有作为普通学术论文正式发表。我们今天主要通过 Knuth 在《计算机程序设计艺术》第三卷，以及后来的数据结构史研究，了解到它的存在与重要性。^{[xlinux.nist.gov][opendatastructures.org][gwern.net]}这里必须承认一个历史局限：对于这份内部备忘录，我们能可靠确认的是其时间、基本技术思想和后来的文献评价，而不是发明当日发生的对话或 Luhn 的具体心理活动。但算法本身可以被我们重新推导出来。

一场思想实验：把搜索变成计算

假设我们需要管理七个客户编号：12、23、34、45、56、67、78我们准备了一个长度为10的数组。如果客户编号是 23，它应该被存放在哪里？我们规定：

h(k)=k\bmod10

也就是：编号除以10，取余数。那么：

h(23)=3

于是编号23放在3号位置。编号56呢？

h(56)=6

它放在6号位置。注意，这里出现了一次思维上的飞跃。过去的搜索方式是：“我不知道资料在哪里，所以必须找。”现在则变成：“只要知道资料的编号，就可以计算应该去哪里找。”

哈希地址实验室

实验一：把编号变成地址Hash Function

输入非负整数编号

计算公式

23 % 10 = 3

地址 0—

地址 1—

地址 2—

地址 3

地址 4—

地址 5—

地址 6—

地址 7—

地址 8—

地址 9—

尝试输入 23、56、12345 和 100001，观察计算机如何立即确定目标桶。

这就是哈希函数（Hash Function）的基本思想：

h:\text{Key}\rightarrow\text{Bucket Index}

把一个可能非常大的键值空间，映射到一个有限的地址空间。使用合适的哈希函数和数据结构，我们无需扫描全部数据，通常只需计算一次地址，然后检查那个位置附近的少量记录。这就是哈希表平均

O(1)

查找性能的来源。然而，一个致命的问题很快出现了。如果输入 23，结果是3。如果输入 43，结果还是3。如果输入 103，结果依然是3。三份不同的资料，竟然被分配到了同一个位置。我们发现了哈希表最著名的难题：哈希冲突（Hash Collision）。

第三幕：1954年，IBM 的另一群工程师给出了不同答案

IBM 701：IBM 早期重要的商业科学计算机，1952年发布。历史有趣的地方就在这里。当 Luhn 探索通过地址计算来检索资料时，IBM 内部的另一群工程师，也正在面对类似的难题。但他们需要解决的不是图书检索，而是汇编程序中的符号表（Symbol Table）。程序员写下一个符号：

LOOP

汇编器必须知道这个名字对应哪个内存地址。假如一个程序包含几千个符号，汇编器就需要反复查找这些名字。把所有符号逐个比较，显然不是理想的办法。根据后来 Donald Knuth 的历史考证及相关口述史，IBM 701 汇编器开发团队中的 Gene Amdahl、Elaine Boehme（后为 Elaine McGraw）和 Arthur Samuel 等人，在1954年前后使用了开放寻址与线性探测技术。Nathaniel Rochester 则是相关软件项目的重要组织者。^{[O'Reilly Media][维基百科][Gwern]}

Gene Amdahl（1922—2015）后来成为 IBM System/360 体系结构的重要设计者，并创办 Amdahl Corporation。在今天，他更经常因为著名的“Amdahl 定律”而被计算机工程师记住。

两条不同的技术路线

对于两个键映射到同一个位置的问题，工程师们发展出两种经典思路。第一种是 Luhn 早期备忘录中采用的链式处理思想：地址相同没关系，让这个桶里存放多个元素。第二种则是 IBM 汇编器团队采用的开放寻址思想：这个位置被占了？那就去检查其他位置。两者都解决冲突，却代表完全不同的工程取舍。我们先看看它们如何工作。

第四幕：链地址法——一个抽屉不够，就在里面放一串卡片

想象有一个档案柜，只设10个抽屉。编号为23、43、103的三份资料都应该进入3号抽屉。这时你有一个想法：为什么一个抽屉只能存放一份资料？完全可以在抽屉里放一个链表：23 → 43 → 103这样，哈希表就将前面几章学过的两种结构结合起来了：

使用数组，快速定位桶。
使用链表或其他容器，管理桶内部的元素。

我们亲自试试。

实验二：链地址法Separate Chaining

∅

23和43都进入3号桶，但两条记录得以同时保存。

你可以继续添加 13、33、53。它们全部进入3号桶。这时候你会发现：哈希表确实能够迅速找到桶，但如果大量元素集中在同一个桶里，桶内部的查找就会逐渐变慢。极端情况下，所有

n

个元素进入同一个桶，查找复杂度又会退化成

O(n)

。哈希表并没有消灭比较。它只是通过一个聪明的映射，让我们通常只需比较很少几个候选元素。

第五幕：开放寻址法——既然抽屉被占，就去隔壁找

这一次，我们使用另一种方法。还是一个拥有10个位置的数组。首先插入23。

23\bmod10=3

所以它放在3号位置。接着插入43。

43\bmod10=3

但3号位置已经有23。怎么办？检查4号位置。如果4号位置为空，就把43放进去。接着插入103，哈希地址仍是3。但3号、4号都被占用。继续检查5号。这就是线性探测（Linear Probing）。公式可以写成：

h_i(k)=(h(k)+i)\bmod m

其中

i=0,1,2,\ldots,m-1

。

亲自观察冲突是如何发生的

实验三：线性探测Linear Probing

位置 0

·

位置 1

·

位置 2

·

位置 3

23

位置 4

·

位置 5

·

位置 6

·

位置 7

·

位置 8

·

位置 9

·

已经插入 23，初始位置为3。

现在连续输入43、103、113、123。你会看到，一批本来都应该存放在3号位置的元素，开始占据连续的一段空间。这又带来一个新问题：聚集（Clustering）。越多元素聚集在一起，后来发生冲突时，需要连续探测的位置就可能越多。因此，线性探测虽然实现简单、局部性较好，却并不总是最优方案。更重要的是，删除也变复杂了。如果直接把中间一个位置清空，后续查找可能提前遇到空位而错误地认为某个元素不存在。所以开放寻址实现通常需要使用墓碑标记（Tombstone），或者专门的删除后重整策略。这与你之前学习过的开放寻址删除槽问题，正好连接起来。

第六幕：1956—1957年，一个工程技巧开始成为正式的计算机科学

早期哈希研究还有一个值得讲述的特点：并不是某一个人给出完整算法，然后其他人照着实现。相反，不同研究团队几乎同时遭遇类似问题，并独立发展出相近的方法。1956年，Arnold Dumey 在《Computers and Automation》发表了有关随机存储地址计算的文章，被认为是哈希技术早期公开文献之一。1957年4月，IBM 研究人员 W. Wesley Peterson 在 IBM Journal of Research and Development 上发表论文：Addressing for Random-Access Storage（随机存取存储的寻址）。这篇论文很有意思，因为它不是简单宣称某一种技术很快。Peterson 比较了不同检索方法所需要的搜索工作量，并讨论开放寻址系统的性能与实际应用。^{[Gwern][数学 FTP 站点][Gwern]}

1957年原始论文

W. W. Peterson, Addressing for Random-Access Storage, IBM Journal of Research and Development, Vol. 1, No. 2, pp. 130–146.阅读原始论文扫描版（PDF）

这篇论文的开头指出一个根本困难：有时无法仅凭记录的标识，直接确定其精确存储位置，因此还需要一定程度的搜索。论文提出了多个应用场景，包括人员档案、企业记录、翻译词典，以及汇编器和编译器的符号表。你会发现，哈希技术从一开始就不是一种脱离实际应用的数学游戏。它是工程师在解决真实的信息检索问题时，逐渐发展出来的算法家族。

1962—1963年：Donald Knuth 开始研究线性探测

Donald Knuth后来成为《计算机程序设计艺术》（The Art of Computer Programming）的作者。他的贡献不仅在于记录算法，更在于用严格的数学方法解释算法的运行成本。

1963年的一份技术笔记中，Knuth 明确提到，线性探测方法早在1954年就已经被用于 IBM 701 的汇编器。但即使它已经被实际使用多年，对探测过程所需操作次数的精确数学分析，仍然不是一件容易的事。^{[华盛顿大学课程][Gwern]}这就出现了算法发展史中反复发生的一幕：工程师已经知道一种方法很好用，数学家却仍在追问：为什么它快？究竟有多快？在哪些条件下会变慢？而这种追问，最终成为算法分析的重要组成部分。

第七幕：哈希表为什么能做到平均 O(1)？

现在我们已经知道，哈希表不是魔法。它可能出现冲突，而且冲突越多，通常就越慢。那么，为什么大家还说它的查找复杂度平均是

O(1)

呢？这里需要引入一个关键概念：装载因子（Load Factor）

\alpha=\frac{n}{m}

其中：

$n$ ：哈希表中保存的元素数量。
$m$ ：哈希桶或槽位的数量。

假设100个元素分布在1000个桶中。

\alpha=0.1

在哈希值分布均匀的情况下，很多桶都是空的，发生冲突的概率相对较低。如果1000个元素全部放入1000个桶：

\alpha=1

冲突压力就大得多了。特别要注意，链地址法与开放寻址法的装载因子含义略有不同：链地址法允许

\alpha>1

，而普通开放寻址法必须有足够的空槽才能插入新元素。

装载因子实验

装载率与碰撞压力概念演示

0.30

装载因子 α

稀疏 10%接近满载 95%

图中用填满的槽位数量示意开放寻址哈希表的占用情况，不表示真实哈希位置的分布。

目前空槽较多在良好的哈希函数下，探测通常较短。

这就是为什么许多哈希表会设置装载率阈值。当数据越来越多时，它会申请一张更大的表，然后把原来的元素重新分配到新的位置。这个过程叫作：Rehash（重新哈希）。Rehash 一次可能需要

O(n)

时间。但在合理的扩容策略下，把大量插入操作综合起来分析，单次插入的摊还时间复杂度仍然可以达到

O(1)

。这与你之前学过的动态数组扩容分析非常相似。

不同检索方式的复杂度比较

数据结构	典型查找	最坏情况
无序数组	$O(n)$	$O(n)$
有序数组 + 二分查找	$O(\log n)$	$O(\log n)$
普通链表	$O(n)$	$O(n)$
平衡二叉搜索树	$O(\log n)$	$O(\log n)$
哈希表	平均 $O(1)$	可能 $O(n)$

这里最关键的区别是：哈希表的

O(1)

通常建立在哈希计算足够高效、冲突控制合理、表容量适当等假设之上，并非对任意输入都无条件保证。如果哈希键是一个长度为

L

的字符串，第一次计算它的哈希值本身就可能需要

O(L)

时间。

第八幕：70多年后，Luhn 的思想仍藏在 Python 里

假如你写过这样一段代码：

student = {
    "Alice": 95,
    "Bob": 87,
    "Charlie": 92
}

print(student["Bob"])

你看不到哈希函数，也看不到底层数组。但在 CPython 中，dict 的底层就是经过高度优化的哈希表。当你查询：

student["Bob"]

Python 会利用键的哈希值定位候选位置，再通过键的相等性判断确认目标记录。它不会每次都从 Alice 开始，把所有学生逐个检查。这与1953年 Luhn 探索的核心思想有直接的技术传承关系。^{[Python 3.15.1 documentation][GitHub]}在 C++ 中，你也会看到类似的结构：

#include <unordered_map>
#include <string>

std::unordered_map<std::string, int> score;

score["Alice"] = 95;
score["Bob"] = 87;

int value = score["Bob"];

而 Python 的 set、C++ 的 unordered_set 也利用哈希技术实现高效的成员判断。不过，有一个容易被忽视的限制：哈希表擅长按精确键检索，却不天然擅长按顺序检索。如果你希望找到学生成绩在80到90之间的所有记录，或者需要按照姓名依次遍历，普通哈希表就未必是最合适的选择。这也为我们后面学习 B 树和数据库索引埋下了伏笔。

最后的挑战：你能像1954年的工程师一样解决冲突吗？

假设现在有一张长度为7的空哈希表。使用：

h(k)=k\bmod7

发生冲突时，采用线性探测。依次插入：10、17、24、5你认为最后编号24存放在哪个位置？

工程师的最后一道考题

位置 3位置 4位置 5位置 6

尾声：一位裁缝留给计算机世界的遗产

让我们重新回到1953年。当时没有 Python，也没有现代数据库。IBM 的研究人员还在探索，如何让机器更有效地处理越来越庞大的信息。Hans Peter Luhn 的经历尤其特别。他早年从事纺织技术工作，后来研究机械装置，再进入 IBM，探索文字检索与自动索引。而哈希思想，正是他众多研究成果中的一项。此后，Amdahl 等工程师在汇编器中实践不同的冲突处理方法，Dumey 和 Peterson 把技术经验写进公开文献，Knuth 等研究者进一步用数学分析它的效率。于是，一个原本只为解决存储与检索问题而发展的技术，逐步成为现代软件最重要的基础设施之一。今天，我们每次写下：

if user_id in users:
    ...

背后可能就有一套精密的哈希检索机制在工作。从早期 IBM 的穿孔卡片，到今天数据库、缓存和编程语言里的键值映射，设备早已天翻地覆。但那个最重要的想法没有改变：与其费力寻找某条信息，不如先建立一种规则，让它告诉我们应该从哪里开始寻找。

本章知识总结

概念	核心思想
Hash Function	将键映射到存储位置
Hash Collision	不同键可能映射到相同位置
Separate Chaining	用链式或其他桶内结构处理冲突
Open Addressing	冲突后在表中寻找其他槽位
Linear Probing	顺序检查后续槽位
Load Factor	衡量元素数与桶数之比
Rehash	扩容并重新分布记录
平均复杂度	在合理条件下查找、插入可达 $O(1)$

本章历史资料

想继续研究这段发明史，我推荐三份资料：

IEEE Spectrum：《Hans Peter Luhn and the Birth of the Hashing Algorithm》：详细介绍 Luhn 的经历和发明背景。
W. W. Peterson（1957）：《Addressing for Random-Access Storage》：哈希技术早期的重要原始论文。
Open Data Structures：Hash Tables：讨论现代哈希表实现与早期历史的开放教材。

下一章预告

第五章：树——为什么计算机开始模仿自然界的分支？

如果数组让数据排成一列，链表让数据连成一条线，哈希表让数据分散到不同位置……那么树，为什么能够成为数据库、文件系统和搜索算法的关键数据结构？下一章，我们将沿着一条更长的历史线索，从19世纪数学家研究的树形关系出发，走向20世纪的二叉搜索树、自平衡树，以及后来用于大型存储系统的 B 树。其中还有一个极富戏剧性的问题：1962年，两位苏联数学家如何想到让一棵树在插入和删除数据后，自己恢复平衡？这就是 AVL 树的故事。而它会带我们走进一场持续数十年的技术竞争：AVL 树、红黑树与 B 树，究竟各自解决了什么难题？