地图：六组里的 16 个概念

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

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

如何阅读本课程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Array — 有序、带编号的序列

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

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

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

Linear search — 按值查找

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

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

Hash Map — 键值对

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

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

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

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

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

Set — 在或不在，没有 value

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

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

Stack — 后进先出（LIFO）

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

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

Queue — 先进先出（FIFO）

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

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

规则决定行为

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

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

Tree — 层级

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

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

Balanced tree — O(log n) 的查找

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

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

Graph — 连接的网络

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

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

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

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

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

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

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

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

一切如何连在一起

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

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