1.2 Data Abstraction：从API契约到表示不变量

来源、版次与独立重写边界

“1·2 · Data Abstraction”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“1·2 · Data Abstraction”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“1·2 · Data Abstraction”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：1.2 · Data Abstraction

• 1. 数据抽象：在本页通过“声明抽象值”连接解释、交互状态和练习验收。
• 2. 面向对象编程：在本页通过“写出 API 合同”连接解释、交互状态和练习验收。
• 3. 抽象数据类型：在本页通过“选择内部表示”连接解释、交互状态和练习验收。
• 4. 抽象数据类型实现：在本页通过“执行客户端调用”连接解释、交互状态和练习验收。
• 5. 抽象数据类型设计：在本页通过“检查表示不变量”连接解释、交互状态和练习验收。

从“调用者为什么不该知道private field”开始

数据抽象（data abstraction）不是给fields加上 private 就结束。真正目标是让client只依赖稳定behavior：它知道能构造什么、能调用什么、结果和错误是什么，却不需要知道count存在一个int里，date保存三个fields，还是statistics保存全部samples。

先预测：如果把 Counter 的 count 从 int 改成 long，所有clients是否必须修改？若API仍返回 int，语义与overflow contract可能已不一致；若API原本承诺可表示long range，则client signature也需变化。Representation可以隐藏，但public contract的value range、mutation和failure behavior不能靠“private”自动解决。

官方1.2按 Object-oriented programming、Using abstract data types、Examples of abstract data types、Implementing abstract data types、Designing abstract data types 推进，并以 Counter、Date、Accumulator 等完整types连接client与implementation。本页保留这五层，不把面向对象编程简化成“class里有methods”。

1.2.1 面向对象编程：object identity与method dispatch

面向对象编程（object-oriented programming）把program划分为objects之间的交互。new Counter("hits") 先分配object、运行constructor并返回reference；hits.increment() 以receiver选择object，再执行instance method。

Reference variable不是object本身。Assignment复制reference value，null 表示不引用任何object，调用null receiver会失败。两个references可以alias同一mutable object，因此“哪个variable被改了”常是错误问题；应问“哪个object的state被哪个operation改变”。

Counter a = new Counter("hits");
Counter b = a;
b.increment();
 
StdOut.println(a.tally());  // 1

Java仍是pass by value。把 a 作为argument传入method时复制的是reference value；callee可调用receiver methods改变共享object，却不能靠给parameter重新赋值让caller variable指向新object。Identity equality a == b 与value equality a.equals(b) 也必须分开。

1.2.2 使用抽象数据类型：先读API再写client

抽象数据类型（abstract data types）把“是什么”与“怎么存”分开。Client的第一份证据应是API：constructors、instance methods、argument types、return types、preconditions、postconditions与side effects。

Counter 的essential behavior可以写成：

public Counter(String id)        // initial tally is 0
public void increment()          // add exactly one
public int tally()               // observe current tally
public String toString()         // printable representation

Official Counter 还是 Comparable<Counter>，当前实现用 Integer.compare(this.count, that.count) 比较tallies。Comparison是否也应考虑name属于API语义选择，不是implementation detail；若排序只看count，两个不同name的counters可以compare equal却不一定是same value。Client不能从一个method的结果擅自推导未承诺的equality semantics。

Using abstract data types时，常见client pattern是创建objects、把它们放进arrays/collections、反复调用operations并输出results。测试应从API层验证：initial state、normal transitions、boundary values、multiple objects independence和invalid arguments，而不是直接读private fields。

1.2.3 三类示例：mutable、immutable与streaming

官方examples展示三种不同state strategy。

Counter：最小mutable ADT

Counter 保持stable identity，increment 原地修改 count，tally 查询state。name 是final reference，count 可变。Representation invariant至少包括count从0开始且只能按API单调增加；当前API没有decrement，因此negative state不应出现。

public class Counter {
    private final String name;
    private int count = 0;
 
    public Counter(String id) { name = id; }
    public void increment()   { count++; }
    public int tally()        { return count; }
}

int overflow是实现边界：足够多increments会wrap，破坏“单调增加”语义。Production API应限制operation count、改用long、检测overflow或明确modular behavior，而不能因为example短小就忽略value domain。

Date：constructor建立immutable value

不可变数据类型使alias安全：多个references共享同一Date不会产生后续state race。Official Date 把month/day/year设为final，constructor先验证calendar，next() 返回new Date。

public Date(int month, int day, int year) {
    if (!isValid(month, day, year))
        throw new IllegalArgumentException("Invalid date");
    this.month = month;
    this.day = day;
    this.year = year;
}
 
public Date next() {
    if (isValid(month, day + 1, year)) return new Date(month, day + 1, year);
    if (isValid(month + 1, 1, year))   return new Date(month + 1, 1, year);
    return new Date(1, 1, year + 1);
}

闰年规则是能被直接验收的representation invariant：能被400整除是leap year；能被100整除但不能被400整除不是；否则能被4整除才是。02/29/2100 必须被拒绝。Constructor应在invalid object逃逸前失败，不能先建立半合法state再等client发现。

Accumulator：不保存原始数据的stream ADT

Accumulator 每次 addDataValue 更新count、mean和deviation sum，constant memory计算mean、sample variance与standard deviation。当前官方实现使用Welford-style one-pass update，减少“两个巨大平方和相减”造成的floating-point cancellation。

public void addDataValue(double x) {
    n++;
    double delta = x - mu;
    mu  += delta / n;
    sum += ((double) (n - 1) / n) * delta * delta;
}
 
public double var() {
    if (n <= 1) return Double.NaN;
    return sum / (n - 1);
}

这里 n 必须等于已吸收values数量，mu 是当前mean，sum 对应sample variance乘以 n - 1。n <= 1 时sample variance未定义，返回NaN是API behavior。Streaming省内存，却不能支持任意删除旧sample或重算quantile；选择ADT时要同时承认它不支持什么。

1.2.4 实现抽象数据类型：representation invariant贯穿所有methods

表示不变量（representation invariant）是implementation correctness的中心。Constructor建立它，public methods保留它，queries依赖它。若method抛exception，也要说明object保持原state、进入可用的新state，还是不再可用。

Implementing abstract data types通常包含：

1. 选择private instance variables表示value；
2. 写constructor并验证arguments；
3. 实现instance methods，区分queries与commands；
4. 限制representation exposure；
5. 提供unit-test client，覆盖正常和错误路径。

Primitive final fields天然不会泄漏。若field是mutable array/list，仅返回其reference就会让client绕过API修改内部state。可使用defensive copy、immutable view或只暴露higher-level query；constructor接收mutable input时也要考虑caller之后继续修改它。

equals、hashCode、compareTo 与 toString 也是data-type contract。Equal objects必须有equal hash codes；comparison应与documented ordering一致；toString 用于display/debug，不应被当作未经承诺的serialization format。Official Date 按year/month/day比较并同时实现matching equality/hash。

1.2.5 设计抽象数据类型：从problem vocabulary反推API

设计抽象数据类型（designing abstract data types）不能从fields开始。先写典型clients和illegal operations，再决定identity、mutability与construction。

Mutable Counter适合累积事件；immutable Date适合value key与跨模块共享；stream Accumulator适合一次扫描与constant memory。把三者互换会产生不自然API：immutable Counter每次increment都分配object，mutable Date允许无效中间日期，保存全部samples的Accumulator失去stream advantage。

Good API尽量小而complete：每个operation有单一语义，names与arguments清晰，preconditions能验证，error policy一致。不要为“将来可能用”暴露fields或low-level mutations。Performance也是契约的一部分：Counter operations constant time，Date next constant time，Accumulator add/query constant time and memory；若implementation替换后失去关键bound，client即使编译也可能行为退化。

统一验收：从client use case追到representation

先预测，再操作三个本节实验

distance(p, q) = sqrt((px-qx)^2 + (py-qy)^2)

本节易错边界与可重放合同

练习与答案

本章回顾

1. Data abstraction用API定义values与operations，把representation和implementation隔离。
2. Object-oriented programming围绕receiver identity、references和instance methods组织计算。
3. Abstract data type correctness从client-visible contract开始，不从private field layout开始。
4. Counter展示mutable state，Date展示constructor-validated immutability，Accumulator展示constant-memory stream summary。
5. Representation invariant必须由constructor建立并被每个public method保留。
6. Reference aliases、mutable getter与不一致equality会绕过或破坏抽象边界。
7. Designing an ADT就是决定identity、mutation、errors、performance和明确不支持的operations。