速成课 · No. 23
data structure 不过是一种组织数据的方式，让你最常做的事情变快。选对了，一个操作瞬间完成；选错了，同样的任务慢如蜗牛。Big-O 就是描述这种差别的语言——当数据增长时，一个操作的代价如何增长。学会几种结构和这套记号，「为什么这么慢？」往往会自己给出答案。
只讲精髓 · 每个想法一个画面 · 掌握术语
在讲具体的结构之前，先说说它们背后共同的想法。data structure 并不学院派——它往往是决定你的代码是快是慢的那个唯一选择。
data structure 为你最常做的操作组织数据
一个带标签格子的整洁工具箱，对比一袋乱堆的工具——同样的工具，但一个让你瞬间抓到要找的那件，另一个意味着每次都要翻找。
data structure 是一种在内存中安排数据的方式。不同的安排让不同的操作变快：有的擅长按名字查找，有的擅长保持顺序，有的擅长总能抓到最新的那一项。整个关键在于让结构匹配你最常做的事——因为让一个操作瞬间完成的安排，往往会让另一个操作变慢。为你的常见情况而选。
合适的结构把难变成易
在一本排好序的 dictionary 里找一个词只要几秒；在同样的词却被随机乱堆的情况下找它，可能要找一整天。同样的数据，安排方式就是一切。
同一个任务，根据数据如何存放，可能轻而易举，也可能几乎不可能。按 ID 查找一个用户，在一种结构里是瞬间的事，在另一种里却要把所有东西都翻一遍。所以「把这个弄快」当中有惊人的一部分，其实是「用对的形状把它存起来」。一开始就选对，往往胜过日后任何巧妙的优化——结构就是那个决定。
每种结构都是一种取舍
跑车和搬家货车都是车——你不会问哪个更好，你会问对什么更好。一件事上的速度，要用另一件事上的代价来换。
没有哪种结构在所有事上都最好。一种给你瞬间查找，却没有顺序；另一种保持顺序，却查找很慢；还有一种添加很快，却在内部查找很慢。选择意味着知道你在为什么而优化，以及你愿意放弃什么。天下没有免费的午餐——每种结构都用某个操作上的强，去换另一个操作上的弱，而你的工作就是选出适合你用途的那个取舍。
data structure 组织数据，让你的常见操作变快。合适的形状把难任务变简单——而每种结构都用某个操作上的速度，去换另一个操作上的弱。
要比较结构，你需要一种谈论速度、又不依赖具体机器的方式。Big-O 就是这种语言：它衡量当数据增长时工作量如何增长。
Big-O 衡量增长，而非秒数
问的不是一次配送要多久，而是当路线从十站变到一万站时总时间如何变化——是增长的形状，而非秒表上的读数。
Big-O 记号描述一个操作的代价如何随数据量（记作 n）的增长而增长。它忽略确切的毫秒数和具体的电脑，捕捉的是那个形状：把数据翻倍，工作量是翻倍、变四倍，还是几乎不变？正是这个形状决定了某样东西在规模变大时是否还快，所以 Big-O 是工程师不必真正运行就能比较各种方案的方式。
常见的几种形状，从极好到糟糕
一件家务随规模变化的四种方式：一种无论堆多大都是一步，一种随堆增长，一种随堆的平方爆炸式增长，还有一种即使堆变大也几乎不增长。
少数几种形状就覆盖了大多数代码。O(1)——常数——无论规模多大都花同样的时间（按 index 抓取某一项）。O(n)——线性——与数据同步增长（扫描一个 list）。O(n²)——平方——随数据增长而爆炸（把每一项和其他每一项比较），是经典的「测试时没事，上了生产就死」。O(log n)——对数——即使数据暴涨也几乎不增长（每一步把搜索范围减半）。知道你的操作是哪种形状，就知道它能不能扛住规模。
形状只在规模变大时才要紧
两条短途完全相同的路线，在长途上却剧烈分叉——这个差别一直看不见，直到距离大到足以把它显露出来。
对十项数据，每种结构都感觉是瞬间的——差别显不出来。Big-O 关心的是当 n 变大时会发生什么：到一百万项时，一个在你测试里没事的 O(n²) 方案现在要磨上好几分钟，而一个 O(n) 的瞬间就完成了。这就是为什么东西会在生产里「突然」变慢：那个糟糕的形状一直都在，只是被藏着，直到数据长大才暴露。在规模把它揭穿之前就想想形状。
Big-O 衡量工作量如何随数据增长，而非原始的秒数。O(1) 和 O(log n) 扛得住规模；O(n) 诚实；O(n²) 测试时没事，上了生产就死。
最基础的结构是 array，也就是 list：一个有序的项目序列。弄清楚它在什么上面快、在什么上面慢，就为其他一切定下了基准。
array 是一个有序、带编号的序列
一排带编号的储物柜：项目按顺序摆放，每个都有一个位置——0 号柜、1 号柜、2 号柜——所以你可以按编号直奔任何一个。
array（或 list）按顺序存放项目，每一项位于一个带编号的位置，叫做 index，从 0 开始。因为项目排布在一个已知、连续的布局里，按 index 跳到任何位置都是瞬间的——O(1)。array 是「一堆按顺序排列的东西」的默认选择，而这种按位置直接访问就是它的超能力。当你知道某样东西在哪里，你立刻就能拿到它。
按位置快，按值查找慢
你能瞬间打开 500 号柜——但如果你只知道里面装了什么、却不知道是哪个柜，你就得一个个打开，直到找到它。
陷阱在于：array 只有在你知道 index 时才快。要按内容查找一项——「这个邮箱在 list 里吗？」——你得挨个检查，那是 O(n)，对大 list 来说很慢。所以 array 在你按位置访问时完美，在你按值搜索时很差。这个缺口，正是下一种结构要解决的问题。
在中间插入代价高昂
要把一本新书塞进一个塞满、带编号的书架中间，它后面的每一本书都得往下挪一格腾地方——一次小小的插入，一大堆挪动。
在 array 的末尾添加或删除很便宜，但在中间插入或删除意味着要把它后面的所有东西都挪动，以保持顺序和编号完好——O(n)。所以 array 在你大多按位置读取、在末尾追加时是理想的，在你不停地在中间插入和删除时则很不合适。把它们用在按 index 访问、追加为主的工作上。
array 是一个有序、带 index 的序列：按位置瞬间访问，但按值搜索或在中间插入是 O(n)。最适合按 index 读取、以追加为主的工作。
如果说有哪一种结构配当你的默认主力，那就是 hash map。它解决了 array 最大的弱点——按值查找东西——而且几乎是瞬间完成。
hash map 存放 key-value 对
一本电话簿：你按名字查一个人，立刻拿到他的号码。你不必扫遍每一条——名字直接把你带到答案。
hash map（也叫 dictionary、hash table，或干脆叫 map）把数据存为 key-value 对：你给它一个 key，它给你对应的 value。按 ID 查一个用户、按名字查一项设置、按词查一个计数——直接按 key 拿到。array 逼你必须知道位置，hash map 却让你按有意义的名字查找。它就是「按标识符查这个」的结构。
查找实际上是瞬间的
一个会变魔术的文件柜：给它一个标签，它直接打开正确的抽屉，不去检查其他抽屉——抽屉的数量并不会拖慢它。
hash map 的魔法在于按 key 查找实际上是 O(1)——常数时间，无论它装了多少项。它用 key 算出 value 究竟在哪里，于是直奔那里，而不是去搜索。一百万条还是十条，找一个都一样快。这就是为什么 hash map 是主力：它让「按名字查找」变成瞬间，而程序时时刻刻都在做这件事。
set：只问在不在，不存 value
门口的一张宾客名单——你不需要任何细节，只要一个是或否：这个名字在名单上吗？瞬间查到，无需扫描。
一个近亲是 set：一个只存 key、不存 value 的 hash map，用来快速回答一个问题——「这东西在不在？」检查成员资格和避免重复，都是 O(1)。每当你发现自己在扫描一个 list 去问「我以前见过这个吗？」，set 就把那个慢的 O(n) 检查变成瞬间。需要唯一性和快速的成员检测时，就用它。
hash map 实际上以 O(1) 按 key 找到一个 value——按标识符查找的主力。它的近亲 set 同样瞬间回答「这个在不在？」。
有时候你取出东西的顺序，和你存的是什么一样要紧。两种结构把两种自然的顺序形式化了——而它们之间的差别，只是一条简单直观的规则。
stack 是后进先出
一摞盘子：你从顶上加，也从顶上拿，所以你最后放下的那个盘子，是你最先拿起的那个。
stack 遵循 LIFO——后进先出。你从同一端添加（push）和移除（pop），所以最新的那一项最先出来。这匹配任何会嵌套或反向解开的东西：一段撤销历史、后退按钮、程序的 call stack。两个操作都是 O(1)。当自然的顺序是「最新优先」或「撤销最后一件事」时，你要用 stack。
queue 是先进先出
售票窗口前的一队人：人们按到达的顺序被服务，新来的排到队尾，队首的下一个被服务。
queue 遵循 FIFO——先进先出。你在队尾添加、从队首移除，所以项目按到达顺序被处理。这是讲究公平和顺序的结构：待处理的任务、等候的作业、按次序处理的请求——正是 queue 那门课里讲的消息队列的想法。和 stack 一样，它的操作是 O(1)。当到达的顺序应当就是处理的顺序时，你要用 queue。
规则决定行为
同一堆工作，两扇门：一扇交回最新的那一项，另一扇交回最旧的。仅仅是选哪一端这一个选择，就改变了下游的一切。
stack 和 queue 装的是同一种数据；唯一的差别是你从哪一端移除，而这一条规则塑造了整个行为。在它们之间选择，就是在选择你的工作以什么顺序回来：反向且嵌套（stack），还是公平且顺序（queue）。这是个小决定，却有大影响——把顺序选对，其余的逻辑就顺理成章了。
stack 是后进先出——撤销、嵌套、反转。queue 是先进先出——公平、按序的处理。同样的数据；你从哪一端移除，就是全部差别。
最后两种结构处理的数据不是一条扁平的线，而是有形状的——会分叉成层级，或连接成网络的东西。它们是你给关系建模的方式。
tree 是一个层级
一棵家谱或一张公司组织架构图：顶上有一个东西，向下分叉出子节点，每一个又能继续分叉——一种向外铺开、从不回环的结构。
tree 把数据组织成一个层级：顶上有一个根，向下分叉成带有子节点的 node，如此一路向下。它给任何嵌套的东西建模——文件夹套文件夹、评论及其回复、一份分类菜单。这种分叉的形状映照了现实世界里的嵌套，这让 tree 在你的数据是「东西里面套东西」时成为天然之选。你在软件里遇到的大多数层级，底下都是 tree。
balanced tree 以 O(log n) 搜索
在电话簿里找一个名字：翻开中间，再翻右半的中间，一次又一次——每一步都扔掉剩下的一半。
一棵组织良好的（balanced）tree 给你一个强大的性质：你可以通过反复把空间减半，以 O(log n) 搜索它，就像你在 dictionary 里找一个词、不必读完每一页那样。那种对数形状即使数据爆炸也几乎不增长——十亿项也只要大约三十步。数据库正是这样在巨大规模上保持查找之快：有序的数据以 tree 的形式存放，靠减半来搜索。
graph 是一张连接的网络
一张用道路相连的城市地图，或用友谊相连的人——以任意模式彼此相连的东西，没有顶也没有底。
graph 是最一般的形状：node 由 edge 相连，模式任意，包括回环。它给网络建模——社交关系、城市间的道路、页面之间的链接、任务之间的依赖。每当数据本质上是「东西与别的东西相关」、而非一个层级或一条线时，它就是 graph。许多困难而有趣的问题——最短路径、谁和谁相连——本质上都是 graph 问题。
tree 给层级建模，且在 balanced 时通过减半以 O(log n) 搜索。graph 给一张连接的网络建模。当数据有形状——嵌套或相连——时就用它们。
这些你很少从头去造——你的语言已经提供了它们。本事在于为眼前的活儿选对那一个，并懂得足够的 Big-O，在一个糟糕的选择咬人之前就感觉到它。
按你最常做的操作来选
你按你每晚要做的菜来配齐厨房，而不是按什么看上去气派——对的工具，是为你真实、反复的工作而备的那些。
实际的决定几乎总是：我最常做哪个操作，哪种结构能让那个变快？不停地按 key 查找？hash map。需要按到达顺序排列？queue。大多按位置读取？array。让那个占主导的操作来挑结构，并接受它在你很少做的事情上会更慢。优化常见情况；结构就是优化的手段。
在伸手去写循环之前，先伸手去拿一个 map
在一张张脸地搜寻人群里某个人之前，你先看看有没有一张宾客名单——名单瞬间回答的，正是搜索缓慢回答的。
一个极其常见、极其有效的招数：当你发现自己在扫描一个 list 去查找或匹配东西时——一个 O(n) 循环，或更糟，一个循环里套循环的 O(n²) 循环——问问能不能用一个 hash map 或 set 让它瞬间完成。把一个嵌套搜索换成一次 map 查找，是现实世界里最常见的提速手段之一。修复办法通常是结构，而不是一个更快的循环。
- 对这份数据，哪个操作占主导——查找、排序、添加/删除？ - 按 key 查找？ 一个 hash map（或一个 set，用于判断在不在）是 O(1)。 - 按位置访问、以追加为主？ array 合适。 - 移除的顺序要紧——最新（stack）还是最旧（queue）？ - 嵌套还是网络化的数据——一个 tree 还是一个 graph？ - 在规模上，Big-O 是什么——有没有什么悄悄是 O(n²)？
- data structure——一种组织数据、让常见操作变快的方式。 - Big-O / n——代价如何随数据规模增长。 - O(1) / O(n) / O(n²) / O(log n)——常数、线性、平方、对数增长。 - array / list / index——一个有序、带编号的序列；按位置 O(1)。 - hash map / dictionary / set——以 O(1) 做 key-value 查找和判断在不在。 - stack / queue / LIFO / FIFO——后进先出和先进先出。 - tree / graph / node / edge——层级和网络；balanced tree 以 O(log n) 搜索。
- 你按你最常做的操作来选结构，而非凭习惯。 - 你伸手去拿一个 hash map 或 set，而不是扫描一个 list 去查找或去重。 - 你能说出你热路径的 Big-O，并且没有隐藏的 O(n²)。 - 当移除顺序要紧时你用 stack 或 queue，当数据有形状时你用 tree 或 graph。 - 数据增长时东西依然快，因为你在规模把它暴露之前就选好了形状。
这些你不从头去造——你去选它们。让结构匹配你最常做的操作，在伸手写循环之前先拿一个 map，让 Big-O 在规模之前先警告你。