第 3 章抽象数据类型 — 全书的方法论地基¶

这一章讲什么: 什么是抽象数据类型(ADT),为什么全书都围着它转; 以及同一个 ADT 用类、用函数(可变版)、用函数(不可变版)实现的三种写法有何异同。 它在全书链条里的位置: 方法论地基。第 4 章回答「多个实现之间怎么比」, 第 10 章起每一章都是「某 ADT 的若干实现候选 + 取舍分析」—— 没有本章的 ADT 视角,后面所有章节的结构都读不懂。

1. 顶层全景¶

  数据类型 = 可能的取值 + 能做的操作
      │
  抽象数据类型(ADT)= 只约定「操作和行为」,不约定「内部怎么存」
      │
      ├── 例:bag(多重集合)—— 能装重复值的容器
      │     操作:create / isEmpty / add / remove / find / greatest
      │
      └── 同一 ADT,三种实现(本章示范):
            ① 类:方法挂在对象上(this 就是 bag)
            ② 函数(可变):bag 当参数传,改完返回(bag 被引用传递)
            ③ 函数(不可变):不改动 bag,造一个新 bag 返回

  图说:ADT 是「需求合同」,实现是「施工方案」。
  全书每一章都在重复这个动作:同一个合同,多种施工方案,用第 4 章的尺子比出优劣。

2. 主线例子:bag 装下《Home, Sweet Home》的歌词¶

bag(多重集合) 先解释:像集合一样装东西,但允许重复—— 集合里同一个值只能出现一次,bag 里可以出现多次,还顺手记次数。书里给的定义:bag 是「像 set 的容器,但允许重复元素」¹。

bag ADT 有六个操作,先把「签名」这个列看懂。签名来自一个叫 Hindley-Milner 的类型标注体系(记不住名字没关系,认形状就行):参数类型按顺序写、用 × 隔开, 箭头后面是返回类型²:

操作	签名(读法)	干什么
Create	`→ bag`	造一个新 bag(无输入)
Empty?	`bag → boolean`	判断是否为空
Add	`bag × value → bag`	加一个值
Remove	`bag × value → bag`	移除一个值
Find	`bag × value → boolean`	查某值在不在
Greatest	`bag → value \\| undefined`	返回最大的值,空则 undefined

现在走主线例子(书里的 Listing 3-2,歌词来自 1823 年的原曲《Home, Sweet Home》)³:

第 ① 步:造 bag、验证为空。 const b = new Bag(); b.isEmpty() → true。内部状态:count = 0,data = {}。

第 ② 步:连加 9 个词。 HOME、HOME、SWEET、SWEET、HOME、 "THERE'S"、NO、PLACE、LIKE、HOME(原书共 10 次 add,HOME 出现 4 次)。走完内部状态:

  count = 10
  data = { HOME: 4, SWEET: 2, "THERE'S": 1, NO: 1, PLACE: 1, LIKE: 1 }

第 ③ 步:isEmpty() → false。 count 是 10,不再为空。

第 ④ 步:查找。 find("YES") → false("YES" in data 不成立); find("NO") → true。

第 ⑤ 步:最大的词。 greatest() → "THERE'S"。实现原理:取出 data 的全部键、sort() 排序、pop() 弹出最后一个—— 字符串按字典序排序,T 开头最大(HOME、LIKE、NO、PLACE、SWEET、THERE'S 中排最后)。 THERE'S 里有撇号,注意它在字典序里排得靠前(撇号的编码小于字母), 但这里首字母 T 已经决定胜负,撇号没机会出场。

第 ⑥ 步:移除再查。 remove("THERE'S"):count 减 1 变 9, data 里 "THERE'S" 的计数是 1,直接 delete 整个键。再 greatest() → SWEET(现在 SWEET 是字典序最大的键)。再 remove("SWEET") 的话:计数是 2,大于 1,只减计数不变结构—— data.SWEET 从 2 变 1,count 变 8;键还留着,这就是 bag 和 set 的分界。

移除里有个容易漏的细节:要删的值不在 bag 里时,remove 什么都不做—— 不报错、不改动,先 find 确认存在再动手⁴。

3. 核心原理¶

3.1 抽象:三个容易混的软工概念¶

抽象(abstraction) 的意思是「刻意忽略细节,只留高层意图」: 你要存取字符串,答案是「字典 ADT」,至于字典内部用树还是哈希表,此刻不管⁵。

作者接着区分了三个相关但不同的概念⁶:

封装(encapsulation):像给模块套一层壳,数据和操作数据的方法收在同一处, 只有模块自己负责处理自己的数据;
数据隐藏(data hiding):把模块的内部实现藏住,外部谁也碰不到, 于是内部可以随便改、不影响别人——「封装把东西聚起来,数据隐藏保证没人能从外面乱动」;
模块化(modularity):把系统拆成可以独立设计、独立开发的模块; 模块用得对,封装和数据隐藏自动都有。

三者的关系一句话:模块化是拆法,封装是收拢,数据隐藏是封死。第 1 章模块的「公开清单」就是数据隐藏的具体机制;本章 ADT 的「操作表」在数据层面的同款。

3.2 可变与不可变:设计 ADT 时第一个岔路口¶

数据类型按「改起来怎么办」分两类⁷:

可变(mutable):创建之后能直接改。JavaScript 里对象和数组都是;
不可变(immutable):任何「修改」都产出一个全新的值,原值不动。 JavaScript 里数字和字符串都是——s.toUpperCase() 不会改 s,只返回新串。

设计 ADT 时这个岔路是真实存在的:给「日期」提供 setMonth()(原地改)就是可变设计; 提供 addMonths(n)(返回新日期对象)就是不可变设计。书里提醒: 用 React Redux 的开发者对这个选择不陌生——Redux 要求状态不可变, 想改状态必须生成一个新状态对象⁸。不可变设计的代价预告在第 18 章:复杂结构复制起来不便宜,需要专门技巧(路径复制)。

3.3 操作的四种分类¶

给 ADT 的操作分类,书里用了四个词⁹:

类别	干什么	bag 里的例子
Creator(创建者)	造一个新对象	`newBag()`
Observer(观察器)	读对象,产出别的类型	`isEmpty`、`find`、`greatest`
Producer(生产者)	用旧对象造一个同类型新对象	不可变版 `add`(返回新 bag)
Mutator(修改器)	直接改对象	可变版 `add`、`remove`

判据一句话:不可变类型只有前三种操作;Mutator 是可变类型的专属。这个分类在第 18 章会原样回来:判断一个结构「函数式不函数式」, 就是看它的写操作全是 Producer 还是允许 Mutator。

3.4 实现一:类版 bag¶

第 2 节主线例子的内部实现(Listing 3-1)核心就这几行¹⁰:

class Bag {
  count = 0;
  data = {};

  find(value) { return value in this.data; }

  greatest() {
    return this.isEmpty() ? undefined : Object.keys(this.data).sort().pop();
  }

  add(value) {
    this.count++;
    if (this.find(value)) { this.data[value]++; }
    else { this.data[value] = 1; }
  }

  remove(value) {
    if (this.find(value)) {
      this.count--;
      if (this.data[value] > 1) { this.data[value]--; }
      else { delete this.data[value]; }
    }
  }
}

内部的表示选择交代一下:用「键 → 出现次数」的普通对象当存储 (HOME 加两次只存 {HOME: 2},不存两个 HOME),外加 count 记总数。书里明说:这不是高性能实现(那是第 11 章的事),只是类写法的示范¹¹。

greatest() 偷懒地用语言自带能力:取键、排序、弹尾——O(k log k),k 是不同值的个数, 不是「真正的」快速取最大。这个偷懒是全书的常态:先用语言自带的武器写出能跑的版本, 性能问题留给后面章节用对的结构解决。

3.5 实现二:可变函数版¶

类换成函数,变化比想象小(Listing 3-3)¹²:

const newBag = () => ({ count: 0, data: {} });
const isEmpty = (bag) => bag.count === 0;
const find = (bag, value) => value in bag.data;

const add = (bag, value) => {
  bag.count++;
  if (find(bag, value)) { bag.data[value]++; } else { bag.data[value] = 1; }
  return bag;
};
// remove 同构:先 find,在则改,return bag;

两个真正的差别。第一,对象不再藏在 this 里,而是明晃晃当第一个参数传—— 调用从 b.add(x) 变成 add(b, x)。第二,add/remove 末尾多了 return bag。

return bag 初看多余:对象是引用传递,add(b, x) 不改名字也已经改了 b 的内容。书里的解释要抄下来:既然不希望外部依赖实现的内部形态,最简最稳的规矩是「改动类操作永远返回更新后的对象」——这样哪天内部不用对象表示了 (比如换成数组),调用处的写法 b = add(b, x) 一个字不用改¹³。

这正是第 2 章「状态当参数传、新状态当返回值交出去」的落地。

3.6 实现三:不可变函数版¶

不可变版只改 add/remove 两个函数,其余原样。改法只有一招: 动手改之前,先复制一个新对象¹⁴:

const add = (bag, value) => {
  bag = { count: bag.count + 1, data: { ...bag.data } };  // 复制!
  if (find(bag, value)) { bag.data[value]++; } else { bag.data[value] = 1; }
  return bag;                                              // 旧 bag 原封未动
};

const remove = (bag, value) => {
  if (find(bag, value)) {
    bag = { count: bag.count - 1, data: { ...bag.data } };
    if (bag.data[value] > 1) { bag.data[value]--; } else { delete bag.data[value]; }
  }
  return bag;
};

{ ...bag.data } 是第 1 章的展开复制:新对象拿到旧 data 的全部键值对, 此后随便改都不碰旧对象。remove 里还有个小讲究:值不存在时原样返回旧 bag, 不为了统一而白造一个新对象。

代价书里预先点了:bag 的内部只是个扁平对象,复制便宜; 等到树、堆这类嵌套结构,整体复制会贵到不能接受——第 18 章专门解决这件事 (路径复制:只复制改动路径上的节点)。本章的三个实现就是把「实现选择」这张地图的三个角先各插一面旗¹⁵。

4. 作者的判断与证据¶

「ADT 先行」是立场鲜明的组织原则:原书原话——这本书「不会为数据结构而研究数据结构」, 永远放在 ADT 及其所需操作的语境里看¹⁶。这是全书结构的直接原因。
三种实现没有谁被宣布为赢家:类版、可变函数版、不可变函数版并列展示, 取舍标准被刻意推迟到第 4 章(性能分析)。作者只给了两条即时判断: return bag 的纪律(最简最稳)¹³,和不可变复制的成本预告¹⁵。
「键→次数」对象表示的局限是明说的:不是高性能实现,greatest 依赖排序—— 诚实的范围声明,避免了读者把示范代码搬进生产¹¹。

判断(我们的,不是书里的): 本章最值钱的不是 bag 本身,而是那张「操作签名表」的工作方式——把需求压成一张小表,实现的自由度全部留在表外, 比较实现时只认表上的行为。这是软件工程里「接口先于实现」的最小教学样本, 也是为什么这本书敢在同一章并列三种范式(类/可变/不可变)而不乱。 如果错,会错在: bag 太简单,复制成本低,三种实现的差别看着都不疼; 换成大结构,不可变版的真实开销会改变「哪种值得教」的答案——作者其实也知道, 所以把账留给了第 18 章,但没有在本章给出量化。

5. 边界与局限¶

只教方法,不教选择:三种实现并列,却没给「什么时候选哪种」的决策表; 唯一的线索是「性能问题第 4 章谈、不可变成本第 18 章谈」。
签名体系点到为止:Hindley-Milner 只给了够用的子集(参数 × 参数 → 返回), 泛型、类型约束、变长参数都一句话带过²。
错误处理在正文中缺席,只在习题 3.4 里补:失败时返回特殊值(如 undefined) 或抛异常,二者都是合法的 ADT 契约表达²⁰。
「代数数据类型(ADT 的另一种展开)」只在注释里出现一句,本书不展开。

5.1 习题答案的三处增量(「Chapter 3」)¶

链式调用(3.1): 想让 b.add(x).add(y) 连写,改法只有一处—— add/remove 末尾 return this¹⁷。this 就是对象自己,把自己交回去, 下一个调用接着在自己身上发生。这是全书唯一一处需要 this 的场景, 也从侧面说明为什么后面章节不依赖类。

数组版实现(3.2): 用数组替代对象:greatest 变成取末元素(数组保持有序), add 变成 push 后 sort(),find 直接用 .includes()¹⁸。同一 ADT,表示换了,操作全数照旧——这就是「抽象」的实际收益。顺带:这个版本暗埋了性能对比的种子——每次 add 都全排序,比对象版的计数慢得多, 第 4 章的尺子正是为此准备的。

额外操作(3.3)与集合预告(3.5): 答案列了可选的扩展操作表 (数总数、数某值次数、批量加、全删、找「下一个更大值」),口径是「只有真的需要才加」¹⁹;3.5 则把 set ADT 直接预告到第 13 章²¹。

6. 可带走的¶

数据类型 = 取值 + 操作;ADT = 只定操作和行为的类型,内部表示留给实现。
三个软工词分清楚:模块化是拆法,封装是收拢,数据隐藏是封死。
可变 vs 不可变是设计岔路:不可变 = 每次修改产新值;JS 中对象/数组可变,数字/字符串不可变。
操作四分类:Creator / Observer / Producer / Mutator;不可变类型没有 Mutator。
签名读法:bag × value → bag,参数 × 分隔,箭头后是返回。
函数式实现的纪律:改动类操作永远返回更新后的对象(b = add(b, x)), 内部表示换了,调用处不改。
不可变实现 = 改前复制({...bag.data});嵌套结构的复制成本是第 18 章的题。
先写能跑的,再换对的结构:greatest 用排序偷懒,是全书「先正确后性能」的第一次亮相。

7. 原文地图¶

主题	原书章	原文位置
抽象的定义	The Theory	`text/12-fm-the-theory.txt:64`(搜「hiding or omitting」)
封装/数据隐藏/模块化	The Theory	`text/12-fm-the-theory.txt:71`(搜「Encapsulation」)
可变与不可变	The Theory	`text/12-fm-the-theory.txt:92`(搜「mutable」)
Redux 注	The Theory	`text/12-fm-the-theory.txt:103`(搜「Redux」)
操作四分类	The Theory	`text/12-fm-the-theory.txt:109`(搜「Creators」)
bag ADT 与签名	The Theory	`text/12-fm-the-theory.txt:133`(搜「multiset」) · `text/12-fm-the-theory.txt:239`(搜「Hindley-Milner」)
类版实现 Listing 3-1	The Theory	`text/12-fm-the-theory.txt:273`(搜「class Bag」)
测试 Listing 3-2(greatest=THERE'S)	The Theory	`text/12-fm-the-theory.txt:325`(搜「new Bag」) · `text/12-fm-the-theory.txt:345`(搜「THERE」)
可变函数版 Listing 3-3 与 return bag 纪律	The Theory	`text/12-fm-the-theory.txt:365`(搜「newBag」) · `text/12-fm-the-theory.txt:400`(搜「mandatory」)
不可变版 add/remove	The Theory	`text/12-fm-the-theory.txt:450`(搜「{...bag.data}」) · `text/12-fm-the-theory.txt:478`(搜「not be so easy」)
ADT 立场(不为结构而结构)	The Theory	`text/12-fm-the-theory.txt:18`(搜「just for the sake」)
答案 3.1(return this)	Chapter 3	`text/66-ch03-chapter-3.txt:7`(搜「return this」)
答案 3.2(数组版)	Chapter 3	`text/66-ch03-chapter-3.txt:16`(搜「newBag」)
答案 3.3(扩展操作表)	Chapter 3	`text/66-ch03-chapter-3.txt:63`(搜「Count all」)
答案 3.4(错误处理两法)	Chapter 3	`text/66-ch03-chapter-3.txt:127`(搜「exception」)

出处:「The Theory」第 133 段(text/12-fm-the-theory.txt:133,搜「multiset」)。原文:a bag「is a container like a set, but it allows for repeated elements」;集合作定义就不能有重复元素。 ↩
出处:「The Theory」第 236–239 段(text/12-fm-the-theory.txt:236,搜「Signature」)。原文:JavaScript 不给函数标类型,但把参数与返回写清有助理解;「指定函数的参数和返回结果称为签名,它基于一个叫 Hindley-Milner 的类型系统」——参数类型按序、以 × 分隔,箭头后为结果类型。泛型与约束见第 245 段(搜「generic types」)。 ↩↩
出处:「The Theory」第 325–347 段(text/12-fm-the-theory.txt:325,搜「new Bag」)。原文:新 bag 为空;加入若干键后 isEmpty() 为 false;find("YES") 为 false 而 find("NO") 为 true;greatest() 先返回 THERE'S,移除后返回 SWEET。歌词条数与键计数依 Listing 3-2 的 10 次 add 逐次推演。 ↩
出处:「The Theory」第 318 段(text/12-fm-the-theory.txt:318,搜「anything at all」)。原文:移除时先确认键在 bag 里;「如果不在,就什么都不做」;计数大于 1 减 1,恰好为 1 则删除整个键。 ↩
出处:「The Theory」第 64 段(text/12-fm-the-theory.txt:64,搜「hiding or omitting」)。原文:抽象「意味着隐藏或略去细节,转而把握一个 overarching 的高层概念」;例子:需要存取字符串,答案就是字典 ADT。 ↩
出处:「The Theory」第 71–77 段(text/12-fm-the-theory.txt:71,搜「Encapsulation」)。原文:封装=模块像套了壳,数据与操作数据的方法收在一处;数据隐藏=内部细节对外不可见、可自由更改;模块化=系统拆成可独立设计的模块,「正确使用模块同时提供封装与数据隐藏」。 ↩
出处:「The Theory」第 92 段(text/12-fm-the-theory.txt:92,搜「mutable」)。原文:JavaScript 中对象和数组可变(创建后可改值),数字和字符串不可变(操作产生全新值)。 ↩
出处:「The Theory」第 103 段(text/12-fm-the-theory.txt:103,搜「Redux」)。原文注释:Redux 开发者熟悉不可变性——不能直接改状态,必须生成带改动的新状态;「Redux 假定你以不可变方式管理状态数据」。 ↩
出处:「The Theory」第 109–121 段(text/12-fm-the-theory.txt:109,搜「Creators」)。原文四类:Creators 造新对象;Observers 产出不同类型的值;Producers 用旧对象造同类型新对象;Mutators 直接修改对象;「不可变数据类型只适用前三种」。 ↩
出处:「The Theory」第 273–308 段(text/12-fm-the-theory.txt:273,搜「class Bag」)。原文 Listing 3-1 完整给出 count/data 字段与五个方法;greatest 用 Object.keys(this.data).sort().pop()。 ↩
出处:「The Theory」第 253 段(text/12-fm-the-theory.txt:253,搜「performant」)。原文:「我们找的不是特别高性能的实现 bag 的方式(第 11 章会讲到),眼下只是类用法的一个例子」。 ↩↩
出处:「The Theory」第 365–396 段(text/12-fm-the-theory.txt:365,搜「newBag」)。原文 Listing 3-3:newBag 返回 {count: 0, data: {}};与类版相比仅两处差别——用 bag 参数代替 this,add/remove 末尾显式 return bag。 ↩
出处:「The Theory」第 400 段(text/12-fm-the-theory.txt:400,搜「mandatory」)。原文:由于对象是引用传递,不改名字也已改了内容,return bag 看似不必;「但如果你用别的方式实现这个 ADT、不用对象,返回新的具体数据类型就是必须的。既然不想让外部依赖实现的内部细节,最简(且最安全)的工作方式是永远返回更新后的新对象,无论其类型。」 ↩↩
出处:「The Theory」第 449–474 段(text/12-fm-the-theory.txt:450,搜「{...bag.data}」)。原文不可变版:add 里 bag = {count: bag.count - 1, data: {...bag.data}}(注意原书代码此处 count 写为 bag.count - 1,正文解说与上下文均指「+1」——原书疑似笔误,我们按逻辑讲);remove 先 find 再复制改新对象,值不存在时原样返回旧 bag。 ↩
出处:「The Theory」第 478 段(text/12-fm-the-theory.txt:478,搜「not be so easy」)。原文:「但对于更复杂的数据结构(本书后面会看到),创建现有结构的新副本可能不那么容易或快速,你需要做额外的处理或结构安排。」 ↩↩
出处:「The Theory」第 18 段(text/12-fm-the-theory.txt:18,搜「just for the sake」)。原文:「这本书不会为数据结构而研究数据结构;我们总是在 ADT 及所需操作的语境中考察它们。」 ↩
出处:「Chapter 3」第 7 段(text/66-ch03-chapter-3.txt:7,搜「return this」)。答案原文:「add() 和 remove() 方法只需以 return this 结尾即可允许链式调用,就这样。」 ↩
出处:「Chapter 3」第 16–36 段(text/66-ch03-chapter-3.txt:16,搜「newBag」)。答案原文数组版:greatest 取 bag[bag.length - 1](数组保持有序),add 为 push 后 sort(),find 用 .includes()。 ↩
出处:「Chapter 3」第 63 段(text/66-ch03-chapter-3.txt:63,搜「Count all」)。答案原文:「只有真的为某个具体问题需要这些操作时,才该要求它们」;列出的扩展含 Count all、Count value、Add many、Remove all、Find next。 ↩
出处:「Chapter 3」第 127 段(text/66-ch03-chapter-3.txt:127,搜「exception」)。答案原文:失败可返回特殊值(如 greatest 对空 bag 返回 undefined),也可抛异常作为「另一种返回值」,用 try/catch 接收。 ↩
出处:「Chapter 3」第 133 段(text/66-ch03-chapter-3.txt:133,搜「Chapter 13」)。答案原文:「我们将在第 13 章考虑这个,请往前翻!」 ↩

第 3 章 抽象数据类型 — 全书的方法论地基¶