# 合适的形状让难题变简单

关于 data structure 与 Big-O 的速成课。16 个概念——Data Structure、Big-O、Array、Hash Map、Set、Stack、Queue、Tree、Graph 等——每个都有英文名称、一幅图、一张带例子和代价的卡片，以及它与其他概念的关系。最后是一张速查表：什么操作用什么结构。

- **Author:** Fedor Chishchin
- **Level:** intro
- **Reading time:** 约 30 分钟阅读
- **Published:** 2026-06-13
- **Source:** https://fedorthinks.com/zh/learn/data-structures-express

---

## 1. 为什么结构很重要

在讲具体的结构之前，先说说它们背后共同的想法。data structure 并不学院派——它往往是决定你的代码是快是慢的那个唯一选择。

### 地图：六组里的 16 个概念

> 一张地铁图：先看到所有线路，再一站一站地乘过去。

最上面是三个基本想法：**Data Structure**、**Trade-off** 和 **Big-O**。下面是六组：Big-O 的增长形状、array、hash map 与 set、有顺序的结构（stack 和 queue）、有形状的结构（tree 和 graph），最后是实践中如何在它们之间做选择。

_Diagram: 上面是三个基本想法，下面是六组——第 2–7 章依次讲它们。_

### 如何阅读本课程

> 一本护照：每个人的栏目都一样，所以很容易比较。

每个概念都用同样的方式讲：它的**英文名称**（你在文档和面试中会遇到的术语）、一幅来自日常生活的画面、一幅**图**和一张**卡片**：它是什么、怎么运作、一个例子、代价，以及它与其他结构的关系。本课程只有一条规则：**没有最好的结构——只有最适合你最常做的那个操作的结构。**

### Data Structure — 为你最常做的操作组织数据

> 一个带标签格子的整洁工具箱，对比一袋乱堆的工具——同样的工具，但一个让你瞬间抓到要找的那件，另一个意味着每次都要翻找。

**data structure** 是一种在内存中安排数据的方式。不同的安排让不同的操作变快：有的擅长按名字查找，有的擅长保持顺序，有的擅长总能抓到最新的那一项。整个关键在于让结构匹配**你最常做的事**。

同一个任务，根据数据如何存放，可能轻而易举，也可能几乎不可能。在一本排好序的 dictionary 里找一个词只要几秒；在同样的词却被随机乱堆的情况下找它，可能要找一整天。所以「把这个弄快」当中有惊人的一部分，其实是「用对的形状把它存起来」。**结构就是那个决定。**

_Diagram: 同样的数据：在一堆里我们一个个查；在按 id 的 map 里直接跳过去。_

#### Data Structure (数据如何摆放)

- **是什么:** 为特定操作而在内存中安排数据的一种方式。
- **如何运作:** 这种安排事先就决定了哪些操作便宜、哪些操作昂贵。
- **例子:** 按 ID 查找一个用户：在一种结构里是瞬间的事，在另一种里却要把所有东西都翻一遍。
- **代价:** 选错了，日后靠「巧妙的优化」也补救不了。
- **关联:** 结构用 **Big-O** 来比较，并通过 **Trade-off** 来选择。

### Trade-off — 每种结构都要放弃一些东西

> 跑车和搬家货车都是车——你不会问哪个更好，你会问对什么更好。

没有哪种结构在所有事上都最好。一种给你瞬间查找，却没有顺序；另一种保持顺序，却查找很慢；还有一种添加很快，却在内部查找很慢。这就是 **trade-off**：一个操作上的强，要用另一个操作上的弱来换。天下没有免费的午餐——你的工作是选出适合你用途的那个取舍。

_Diagram: 每种结构都有自己的强项和自己的弱项。_

#### Trade-off (没有免费的午餐)

- **是什么:** 一种结构在某个操作上的强，总是要用另一个操作上的弱来换。
- **例子:** **Hash Map** 按 key 瞬间找到，但不保持顺序；**Array** 保持顺序，但按值查找很慢。
- **何时思考:** 每次你决定数据放在哪里的时候：我常做什么，又很少做什么？
- **关联:** 这种取舍用 **Big-O** 来衡量——每个操作都有自己的「形状」。

> **界定问题:** 「在这份数据上我最常做哪个操作——查找、保持顺序、添加和删除——哪种结构能让那一个变快，哪怕在别处要付出代价？」

> data structure 组织数据，让你的常见操作变快。合适的形状把难任务变简单——而每种结构都用某个操作上的速度，去换另一个操作上的弱。

## 2. Big-O：代价如何增长

要比较结构，你需要一种谈论速度、又不依赖具体机器的方式。Big-O 就是这种语言：它衡量当数据增长时工作量如何增长。

### Big-O notation — 看增长，而非秒数

> 问的不是一次配送要多久，而是当路线从十站变到一万站时总时间如何变化——是增长的形状，而非秒表上的读数。

**Big-O** 记号描述一个操作的代价如何随数据量（记作 **n**）的增长而增长。它忽略确切的毫秒数和具体的电脑，捕捉的是那个*形状*：把数据翻倍，工作量是翻倍、变四倍，还是几乎不变？正是这个形状决定了某样东西在规模变大时是否还快，所以 Big-O 是工程师不必真正运行就能比较各种方案的方式。

_Diagram: n 越大，各形状拉得越开：O(1) 和 O(log n) 几乎持平，O(n²) 直冲而上。_

#### Big-O notation (渐近复杂度)

- **是什么:** 对工作量如何随数据规模 **n** 增长的一种描述。
- **如何运作:** 舍去确切的秒数和硬件细节，只保留增长的形状。
- **例子:** 「在 array 中查找是 O(n)」：数据多十倍——工作量大约也多十倍。
- **注意:** 它不告诉你多少秒；它告诉你如何随规模变化。
- **关联:** 常见的形状就是 **Complexity classes**。

### Complexity classes — 从极好到糟糕的形状

> 一件家务随规模变化的四种方式：一种无论堆多大都是一步，一种随堆增长，一种随堆的平方爆炸式增长，还有一种即使堆变大也几乎不增长。

少数几种形状就覆盖了大多数代码：

- **O(1)** — 常数：无论规模多大，时间都一样（按 index 抓取某一项）。
- **O(log n)** — 对数：即使数据暴涨也几乎不增长（每一步把搜索范围减半）。
- **O(n)** — 线性：与数据同步增长（扫描一个 list）。
- **O(n²)** — 平方：爆炸式增长（把每一项和其他每一项比较）。经典的「测试时没事，上了生产就死」。

只有十项时，任何结构都感觉是瞬间的——差别显不出来。Big-O 关心的是 n 变大时会发生什么。这就是为什么东西在生产环境中会「突然」变慢：糟糕的形状一直都在，只是在数据增长之前被藏住了。

_Diagram: 十个测试数据时所有形状看起来都差不多；到了十亿，就是一道鸿沟。_

#### Complexity classes (O(1), O(log n), O(n), O(n²))

- **是什么:** 对典型增长形状的命名。
- **例子:** array 的 index——O(1)；平衡树查找——O(log n)；扫描一个 list——O(n)；循环里套循环——O(n²)。
- **注意:** O(n²) 在测试数据上跑得很好，面对一百万条记录却要卡上好几分钟。
- **规则:** O(1) 和 O(log n) 扛得住规模；O(n) 老实可靠；O(n²) 是警报。
- **关联:** **Map before loop** 是把 O(n²) 变成 O(n) 的主要办法。

> **Big-O 之问:** 「当这份数据变得很大时，这个操作是什么形状——工作量保持平稳、随数据增长，还是爆炸——它能扛住真实世界的规模吗？」

> Big-O 衡量工作量如何随数据增长，而不是原始的秒数。O(1) 和 O(log n) 扛得住规模；O(n) 老实可靠；O(n²) 测试时没事，上了生产就死。

## 3. Array

最基本的结构是 array，也叫 list：一个有序的元素序列。确切知道它擅长什么、不擅长什么，是理解其他一切结构的基线。

### Array — 有序、带编号的序列

> 一排带编号的储物柜：东西按顺序放着，每个都有一个位置——0 号柜、1 号柜、2 号柜——所以你可以凭编号直接走到任何一个。

**array**（或 **list**）按顺序存放元素，每个元素在一个带编号的位置上，这个编号叫 **index**，从 0 开始。因为元素处在已知的、连续的布局里，按 index 跳到任何位置都是瞬间的——**O(1)**。array 是「一堆按顺序排好的东西」的默认选择，按位置直接访问就是它的超能力。

它有代价。在*末尾*添加或删除很便宜。但在*中间*插入或删除，会把后面的所有元素都挪一格，以保持顺序和编号不乱——**O(n)**。

_Diagram: 知道 index——直接打开对的那个柜子。_

_Diagram: 在中间插入会让后面的所有元素挪位；在末尾追加则很便宜。_

#### Array (list, index)

- **是什么:** 按顺序排列的元素，每个都有一个从零开始的 index。
- **快:** 按 index 访问——O(1)；在末尾追加——便宜。
- **慢:** 按值查找——O(n)；在中间插入或删除——O(n)。
- **例子:** 一个按顺序阅读、并在末尾追加的帖子 feed。
- **何时使用:** 你按位置读取，而且主要是追加。
- **关联:** 它的弱点——按值查找——由 **Hash Map** 来弥补；**Stack** 和 **Queue** 常常建立在它之上。

### Linear search — 按值查找

> 你能瞬间打开 500 号柜——但如果你只知道里面装了什么、不知道在哪个柜子，就只能一个个打开，直到找到为止。

问题在于：array 只有在你知道 _index_ 时才快。要按*内容*找一项——「这个 email 在列表里吗？」——你得逐个检查。这就是 **linear search**，**O(n)**：列表一大就慢。这个差距，正是下一种结构要解决的问题。

_Diagram: 没有 index，我们就一个个查——最坏情况下，查遍整个列表。_

#### Linear search (scan)

- **是什么:** 一个个检查元素，直到找到你要的那个。
- **代价:** O(n)：数据多十倍——耗时多十倍。
- **例子:** 在一百万个地址的列表上 `emails.includes(x)`。
- **注意:** 放进另一个循环里就变成 O(n²)——经典的「上了生产就慢」。
- **关联:** 被 **Hash Map** 或 **Set** 中 O(1) 的查找所取代。

> **Array 之问:** 「我是按位置访问这份数据、主要是追加——这正是 array 的强项——还是按值查找、在中间插入，那正是它慢的地方？」

> array 是有序、带 index 的序列：按位置访问是瞬间的，但按值查找或在中间插入是 O(n)。

## 4. Hash Map 与 Set

如果有一种结构配得上做你默认的主力，那就是 hash map。它解决了 array 最大的弱点——按值找东西——而且几乎是瞬间完成。

### Hash Map — 键值对

> 一本电话簿：你按名字找一个人，立刻拿到他的号码。你不用扫遍每一条记录——名字直接带你到答案。

**hash map**（也叫 dictionary、hash table，或者直接叫 map）把数据存成**键值对**：你给它一个 key，它给你对应的 value。按 ID 找用户、按名字找设置、按单词找计数——直接用 key。array 要求你知道位置，而 hash map 让你用一个有意义的名字去找。

_Diagram: key 直接通向 value——不用翻看其他条目。_

#### Hash Map (字典, hash table, map)

- **是什么:** 按 key 查找的 key → value 键值对。
- **快:** 按 key 查找、插入和删除——实际上是 O(1)。
- **慢:** 没有顺序；按「值」而不是按 key 去找，又变回了扫描。
- **例子:** `users[id]`、`settings["theme"]`、单词计数 `counts[word] += 1`。
- **何时使用:** 你经常要按某个标识符查找东西。
- **关联:** 它的速度来自 **Hash function**；去掉 value 就成了 **Set**。

### Hash function — 为什么查找是瞬间的

> 一个神奇的文件柜：给它一个标签，它直接打开正确的那个抽屉，不用查看其他的——抽屉再多也不会让它变慢。

hash map 的神奇之处在于，按 key 查找实际上是 **O(1)**——常数时间，无论里面装了多少元素。key 会经过一个 **hash function**，由它*算出* value 存在哪里，所以 map 直接跳过去，而不是去搜索。一百万条还是十条，找到一个都一样快。这就是 hash map 作为主力的原因：「按名字查找」正是程序一直在做的事。

_Diagram: hash function 把 key 变成一个槽位编号——map 直接去那里。_

#### Hash function (hashing)

- **是什么:** 一个从 key 算出其 value 在表中位置的函数。
- **如何运作:** 同一个 key 总是得到同一个槽位——所以查找从不需要扫描条目。
- **例子:** `hash("eve")` → 3 号槽 → Eve 的号码就在那里。
- **关联:** **Hash Map** 和 **Set** 的核心。

### Set — 在或不在，没有 value

> 门口的宾客名单——你不需要任何细节，只要一个是或否：这个名字在名单上吗？瞬间核对，无需扫描。

近亲是 **set**：一个只存 key、不存 value 的 hash map，用来快速回答一个问题——「这个东西在吗？」。判断是否存在和避免重复，都是 **O(1)**。每当你发现自己在扫描一个 list 来问「这个我见过吗？」，set 就能把那个缓慢的 O(n) 检查变成瞬间完成。

_Diagram: set 以 O(1) 回答是或否，而且从不存放重复项。_

#### Set (membership)

- **是什么:** 一组不含 value 的唯一 key。
- **快:** 「在这里吗？」和添加——O(1)；重复项会被自动丢弃。
- **例子:** `seen = set()` —— 跳过已发过的 email；去掉列表中的重复项。
- **何时使用:** 需要唯一性和快速的成员检查。
- **关联:** 没有 value 的 **Hash Map**。

> **Map 之问:** 「我是在按一个有意义的 key 查找，还是在检查某样东西是否存在——这正是 hash map 和 set 能瞬间完成、而不必扫描 list 的事？」

> hash map 按 key 找 value，实际上是 O(1)——按标识符查找的主力。它的近亲 set 同样瞬间回答「这个在吗？」。

## 5. Stack 与 Queue

有时，你取东西的顺序和你存什么一样重要。两种结构把两种自然的顺序形式化了——它们之间的差别只是一条直观的规则。

### Stack — 后进先出（LIFO）

> 一摞盘子：你从顶上放，也从顶上拿，所以最后放下的那个盘子，是第一个被拿起的。

**stack** 遵循 **LIFO — last in, first out**（后进先出）。你在同一端添加（**push**）和移除（**pop**），所以最新的元素最先出来。这与一切嵌套或按相反顺序回退的东西相吻合：撤销历史、后退按钮、程序的 **call stack**。两种操作都是 **O(1)**。

_Diagram: push 放到顶上，pop 从顶上取：最新的最先出来。_

#### Stack (LIFO)

- **是什么:** 只在顶端添加和移除。
- **快:** `push` 和 `pop`——O(1)。
- **例子:** 编辑器里的撤销、浏览器的后退按钮、call stack。
- **何时使用:** 你需要「最新的优先」或「撤销上一步」。
- **关联:** **Queue** 的镜像：同样的数据，从另一端取出。

### Queue — 先进先出（FIFO）

> 售票窗口前的一队人：按到达的顺序被服务，新来的排到队尾，队首下一个被服务。

**queue** 遵循 **FIFO — first in, first out**（先进先出）。你在队尾添加（**enqueue**），从队首移除（**dequeue**），所以元素按到达顺序被处理。这是讲求公平和顺序的结构：待处理的任务、等待中的作业、要按顺序处理的请求——正是 queues 课程里消息队列的思想。和 stack 一样，它的操作也是 **O(1)**。

_Diagram: 新来的排到队尾，队首被服务——按到达顺序。_

#### Queue (FIFO)

- **是什么:** 在队尾添加，从队首取出。
- **快:** `enqueue` 和 `dequeue`——O(1)。
- **例子:** 交给后台 worker 的作业、按顺序处理的请求。
- **何时使用:** 到达的顺序就应该是处理的顺序。
- **关联:** **Stack** 的镜像；规模大了会长成消息队列。

### 规则决定行为

> 同一堆活儿，两扇门：一扇交还最新的，另一扇交还最旧的。仅仅选哪一端这一个选择，就改变了后面的一切。

stack 和 queue 存放的是同一类数据；唯一的差别是*从哪一端移除*。在两者之间选择，就是选择你的工作以什么顺序回来：相反而嵌套（stack），还是公平而有序（queue）。一个小决定，影响却很大——把顺序弄对，其余的逻辑自然就位。

_Diagram: 放进 1、2、3：stack 还给你 3、2、1，queue 还给你 1、2、3。_

> **顺序之问:** 「应该是最新的元素先出来（stack，用于撤销和嵌套），还是最旧的先出来（queue，用于公平、按序的处理）？」

> stack 是后进先出——撤销、嵌套、反转。queue 是先进先出——公平、按序的处理。同样的数据；从哪一端移除就是全部的差别。

## 6. Tree 与 Graph

最后这两种结构处理的数据不是一条平的线，而是有形状的——分叉成层级，或连成网络。它们是你为关系建模的方式。

### Tree — 层级

> 一棵家谱或一张公司组织架构图：顶上一个，向下分出子节点，每个子节点还能继续分叉——结构向外展开，从不绕回来。

**tree** 把数据组织成层级：顶上是一个**根**（root），分出带有子节点的**节点**，如此向下。它能为一切嵌套的东西建模——文件夹套文件夹、评论和它们的回复、一份分类菜单。分叉的形状反映了现实世界的嵌套，所以只要你的数据是「东西里面套东西」，tree 就是天然的选择。你在软件里遇到的大多数层级，底下都是 tree。

_Diagram: 文件系统就是一棵 tree：一个根，文件夹是节点，文件是叶子，没有环。_

#### Tree (root, node)

- **是什么:** 一种层级：每个节点都可以有子节点，但没有任何东西绕回来。
- **例子:** 文件夹和文件、一串评论、商店的分类树。
- **何时使用:** 你的数据是「东西里面套东西」。
- **注意:** 把层级硬塞进平面的 list，你就得再手动把它拼回去。
- **关联:** 有序而均匀的 tree 是 **Balanced tree**；tree 是 **Graph** 的一种特例。

### Balanced tree — O(log n) 的查找

> 在电话簿里找一个名字：先翻开中间，再翻右半边的中间，一次又一次——每一步都扔掉剩下的一半。

一棵组织良好的**平衡**（balanced）tree 带来一个强大的性质：你可以通过反复把空间减半，在 **O(log n)** 内查找它，就像你在 dictionary 里找一个词而不用读每一页。这种对数形状即使数据暴增也几乎不增长——**十亿项也只需要大约三十步**。数据库就是这样在巨大规模下保持查找迅速的：把有序数据放成 tree 的形式，用折半的方式去查。

_Diagram: 找 62：比 50 大——往右，比 75 小——往左。每一步都去掉一半。_

#### Balanced tree (balanced search tree)

- **是什么:** 各侧深度相同的有序 tree。
- **如何运作:** 在每个节点比较，然后进入其中一半——另一半再也不会被看。
- **快:** 查找——O(log n)：十亿项 ≈ 30 步。
- **例子:** 数据库索引：以 tree 形式存放的有序 key。
- **关联:** 一种特殊的 **Tree**；与 **Hash Map** 不同，它保持顺序。

### Graph — 连接的网络

> 一张由道路连起城市、或由友谊连起人的地图——事物以任意的模式彼此相连，没有顶，也没有底。

**graph** 是最一般的形状：**节点**由**边**（edge）以任意模式相连，包括环。它为网络建模——社交关系、城市之间的道路、页面之间的链接、任务之间的依赖。只要数据本质上是「事物与其他事物相关」，而不是层级或一条线，它就是一个 graph。许多困难而有趣的问题——最短路线、谁和谁相连——本质上都是 graph 问题。

_Diagram: 节点和边以任意模式相连；允许有环——这一点不同于 tree。_

#### Graph (node, edge)

- **是什么:** 节点以及它们之间的边——没有层级，允许有环。
- **例子:** 社交网络里的朋友、城市之间的道路、页面之间的链接、任务依赖。
- **典型问题:** 最短路线；谁和谁相连。
- **何时使用:** 数据是一个网络，而不是一条线，也不是一个层级。
- **关联:** **Tree** 是只有一个根、没有环的 graph。

> **形状之问:** 「这份数据是嵌套成层级（tree），还是连成网络（graph）——我是在为这种形状建模，还是在把它硬塞进一个平面的 list？」

> tree 为层级建模，平衡时能以折半的方式在 O(log n) 内查找。graph 为连接的网络建模。当数据有形状——嵌套的或相连的——就用它们。

## 7. 如何选择

你很少需要从零构建这些——你的语言已经提供了。真正的功夫在于为这份工作选对结构，并且懂得足够的 Big-O，能在坏选择咬你之前就感觉到它。

### Dominant operation — 按你最常做的事来选

> 你按每晚要做的菜来备厨房，而不是按看起来唬人的菜。

实际的决定几乎总是：我最常做什么操作，哪种结构能让*那一个*变快？一直在按 key 查找？**Hash Map**。需要东西按到达顺序排列？**Queue**。主要是按位置读取？**Array**。让**主导操作**（dominant operation）来选结构，并接受它在你很少做的事情上会更慢。优化常见情况；结构就是办法。

_Diagram: 说出你最频繁的操作——它会指向那个结构。_

#### Dominant operation (优化常见情况)

- **思路:** 由最频繁的操作来选结构，而不是靠习惯。
- **例子:** 每秒成千上万次按 ID 查用户 → **Hash Map**，即使顺序丢了。
- **代价:** 罕见的操作会变慢——这是一次有意的取舍。
- **关联:** 在实践中运用的 **Trade-off**。

### Map before loop — 先想 map，再写循环

> 在一张张脸地从人群里找人之前，你会先看有没有宾客名单——名单瞬间回答的，正是搜索慢慢做的事。

一个极其常见、极其有效的做法：当你发现自己在扫描一个 list 来查找或匹配东西——一个 **O(n)** 的循环，更糟的是循环里再套一个 **O(n²)** 的循环——就问问自己，**hash map** 或 **set** 能不能让它瞬间完成。把嵌套的查找换成 map 查询，是现实中最常见的提速之一。解决办法通常是结构，而不是一个更快的循环。

_Diagram: 之前：循环里套循环，一百万次检查。之后：先建一次 map，之后每次查找 O(1)。_

#### Map before loop (用查找取代嵌套扫描)

- **问题:** 对每一项我们都要扫描另一个 list——O(n²)，上了生产就慢。
- **思路:** 先建一个 **Hash Map** 或 **Set**，然后以 O(1) 在里面查找。
- **例子:** 不要在遍历订单的循环里写 `users.find(u => u.id === order.userId)`——先建好 `byId`，再用 `byId[order.userId]`。
- **代价:** map 要占一点内存。
- **关联:** 把循环里的 **Linear search** 变成 O(1)。

#### 选结构之前

- **哪个操作占主导**——查找、排序，还是添加/删除？
- **按 key 查找？** Hash Map（若只看是否存在，则用 Set）是 O(1)。
- **按位置访问、以追加为主？** Array 合适。
- **移除的顺序很重要**——最新的优先（Stack），还是最旧的优先（Queue）？
- **嵌套或网络状的数据**——Tree 还是 Graph？
- **在大规模下，Big-O 是多少**——有没有什么东西暗地里是 O(n²)？

#### 你选得好的迹象

- 你按**最常做的操作**来选结构，而不是靠习惯。
- 你会用 **Hash Map 或 Set**，而不是扫描 list 来查找或去重。
- 你能说出热点路径的 **Big-O**，而且没有隐藏的 **O(n²)**。
- 移除顺序重要时你用 **Stack 或 Queue**，数据有形状时你用 **Tree 或 Graph**。
- 数据增长时一切依然很快，因为你在规模暴露问题之前就选好了**形状**。

### 一切如何连在一起

> 一棵工具的家谱：每一个都补上前一个的弱点。

Big-O 是衡量每种结构的那把尺。Hash Map 弥补 Array 的弱点（按值查找）；Set 是没有 value 的 Hash Map。Stack 和 Queue 是附带「只从一端取」这条规则的序列。Tree 加上了层级，平衡的 tree 能在 O(log n) 内查找；Graph 去掉了最后一道限制，允许任意连接。

_Diagram: Big-O 衡量它们所有；每种结构都回应邻居的一个弱点或限制。_

## 速查表：全部 16 个概念

### 基础

- **Data Structure** (数据如何摆放): 一种组织数据的方式，让你的常见操作变快。
- **Trade-off** (没有免费的午餐): 一个操作上的强，要用另一个操作上的弱来换。

### Big-O

- **Big-O notation** (渐近复杂度): 工作量如何随数据规模 n 增长。
- **Complexity classes** (O(1), O(log n), O(n), O(n²)): 常数、对数、线性、平方。O(n²) 是警报。

### Array

- **Array** (list): 有序、带 index：按位置 O(1)，在中间插入 O(n)。
- **Linear search** (scan): 通过逐个检查来按值查找。O(n)。

### Hash map

- **Hash Map** (字典, map): Key → value，按 key 查找实际上是 O(1)。没有顺序。
- **Hash function** (hashing): 由 key 算出 value 的位置——所以不用扫描。
- **Set** (membership): 只有 key：「在这里吗？」O(1)，没有重复。

### 顺序

- **Stack** (LIFO): 后进先出。撤销、后退按钮、call stack。
- **Queue** (FIFO): 先进先出。按到达顺序处理。

### 形状

- **Tree** (层级): 根、节点、子节点，没有环。
- **Balanced tree** (balanced search tree): 折半查找——O(log n)。数据库索引的工作原理。
- **Graph** (网络): 节点和边以任意模式相连。网络、路线、依赖。

### 如何选择

- **Dominant operation** (常见情况): 最频繁的操作决定结构。
- **Map before loop** (用查找取代扫描): 在做嵌套扫描之前——先建一个 Hash Map 或 Set。

> 这些结构你不用从零构建——你只需要选择。让结构匹配你最常做的操作，先想 map 再写循环，让 Big-O 赶在规模之前向你示警。

速成课到此结束 · 7 章 · 16 个概念

接下来是练习：在你的代码里找一个为了查找或匹配而遍历 list 的地方，把它换成 hash map 或 set 的查找——然后留意在大数据上快了多少。再挑一个慢的操作，算出它的 Big-O，问问换一种结构能不能改变它的形状。但要把一个想法放在所有想法之上：合适的形状让难题变简单。大多数「为什么这么慢？」的答案，其实都是「它放在了错的结构里」——而选对结构，是你能买到的最便宜的速度。