抽象数据类型
复习
- 数据为什么需要组织：同一批数据可以有多种组织方式，各有优劣
- 操作取舍：选择哪种，取决于你主要做哪些操作
- 组织成本：组织数据本身也有代价
TL;DR
- 抽象数据类型先规定“能做什么”，不规定“怎么做”
- 它把接口和实现分开，是“加一层”思想的又一次体现
- 同一个抽象可以有多种实现，各有取舍
- 使用者只依赖接口，不依赖实现
正文
上一章我们意识到，同一批数据可以有好几种摆放方式。可摆在面前的问题是：如果要写代码使用这些数据，难道每次换实现，都要把用到它的地方全部改一遍吗？
这就需要一个“约定”，把“能做什么”和“怎么做”分开。这个约定，叫作抽象数据类型（ADT，Abstract Data Type）。
先约好能做什么
抽象数据类型只描述一组操作，以及这些操作的语义，而不关心内部怎么实现。
以“集合”为例，它可能约定三件事：
- 加入一个元素
- 判断某个元素是否存在
- 删除一个元素
至于这些操作背后，是用数组、链表还是哈希表来做，使用者一概不必知道。它拿到的只是一份承诺：你按这个接口调用，我就给你这个结果。
这就像墙上的插座：你不需要知道电从哪来、怎么变压，只要插头对得上，就能取到电。接口就是那个插座标准。
同一份承诺，多种做法
接口一旦固定，实现就可以自由替换。
“集合”这个抽象，内部可以有完全不同的实现：用数组存，查找要一个个比；用有序数组，查找能二分；用哈希表，平均接近一步到位。它们对外都叫“集合”，都支持那三个操作，但性能取舍各不相同。
于是，我们得到了一种非常舒适的开发方式：写代码时只对着抽象编程，等到真正关心性能时，再挑一个合适的实现换上。 上层代码几乎不用改。
抽象，是为了隔离变化
你也许已经发现，这和整部教程反复出现的主题一脉相承：在计算机科学里，没有什么问题是加一层解决不了的。
抽象数据类型加的这一层，隔离的是“接口”与“实现”的变化。实现改了，接口不动，使用者就不受影响；就如同底层的晶体管换了一代，逻辑门的用法依然照旧。
接下来，我们分别谈“数据怎么摆”（数据结构）和“步骤怎么走”（算法）。先解决后者，因为它有一个绕不开的前提：怎样才算一个合格的算法？
思考题 1
为什么“规定能做什么”比“规定怎么做”更有利于替换实现？
思考题 2
举一个你熟悉的“接口与实现分离”的例子，并说说这样做的好处。
小结
知识点
- 抽象数据类型规定操作及其语义，不规定实现
- 接口与实现分离，便于替换实现
- 同一个抽象可以有多种性能取舍不同的实现
- 抽象的核心作用是隔离变化
参考资料
- Wikipedia(zh)：抽象数据类型：只定义操作、不定义实现的数据类型
- Wikipedia(zh)：接口 (计算机科学)：规定组件如何交互的约定
思考题答案（仅供参考）
思考题 1
因为“怎么做”是经常变化的细节，而“能做什么”是稳定的契约。只要契约不变，内部实现怎么改，使用者都不用跟着改。这样就把变化限制在局部，降低了耦合。
思考题 2
比如电源插座、USB 接口、或者编程中的函数库：调用者只需知道函数名、参数和返回值，不必知道它内部怎么实现。好处是内部可以自由优化或替换，而调用方代码保持稳定。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪