元数据卡

• 前置知识：第1章（静态检查、测试优先、防御式编程）
• 预计时间：50 分钟
• 核心难度：进阶
• 完成标志：能设计带有完整不变式和等价性的 ADT

你的进度

铁匠师傅看了你锻造的第一个零件，点了点头：“构造没问题了。但你只会在锻造台上造单个零件。真正的好工匠，想的是零件之间的关系和接口。”

他把你带到工匠之都的材料仓库：每一类材料都有标准的接口定义——不管你是从哪个矿场采来的铁锭，只要符合工匠联盟的规格，就能互换。这就是 ADT 的核心思想。 你的任务

函数、基础类型、List、Map——这些是编程语言给你的预制零件。但当你的系统超过几万行代码时，这些预制零件不够用。你需要自己设计数据类型：规定它能做什么（接口）、隐藏它怎么实现（表示独立）、保证它永远不坏（不变量）、定义两个对象什么时候相等（等价性）。这四个问题，就是抽象数据类型（Abstract Data Type, ADT）的核心。

本章分层

• 必读：ADT 接口设计、表示独立、不变量、等价性
• 选读：表示泄露的检测工具
• 进阶：双重分发与等价的关系

本章不会要求你掌握

• 范型编程的高级用法
• 函数式 ADT 与代数数据类型

---

破局 · 溯源

你写了一个 Point 类表示二维坐标：

public class Point {
    public int x;
    public int y;
}

到处都能直接改 point.x = 10。非常好用的类是坏的类。当你把 x 和 y 变成 public 字段的那一瞬间，你就失去了对这两个值的控制——其他地方可以随意修改，让不变式失效。

抽象数据类型的第一条规则：隐藏实现，暴露行为。调用者不需要知道 Point 内部是用两个 int 还是用一个 long 或者极坐标存储的。调用者只问：你能给我哪些操作？

第一层：设计接口——只留操作，不留字段

好用的接口是窄的（只做一件事）、完整的（能做与这个类型相关的所有事）、抽象的（不暴露实现细节）。

在 Java 里，你通常把 ADT 声明为 interface：

// ch02/Point.java
/**
 * 二维空间中的一个点。不可变。
 * 
 * 抽象值：一对实数 (x, y)
 * 
 * 操作：
 *   - add(Point)   : 向量加法
 *   - distanceTo(Point) : 到另一点的距离
 *   - origin()     : 返回原点 (0,0)
 */
public interface Point {
    Point add(Point other);        // 返回新点，不修改自身
    double distanceTo(Point other); // 计算距离
    Point origin();                // 工厂方法
}

你注意两件事。第一，接口里没有 getX()、getY()——调用者要的是几何运算，不是坐标数值。第二，接口的方法签名只依赖接口类型，不依赖具体实现。

具体实现可以藏起来：

// ch02/CartesianPoint.java
package com.craft.internal;

class CartesianPoint implements Point {
    private final double x;
    private final double y;

    CartesianPoint(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public Point add(Point other) {
        if (other instanceof CartesianPoint cp) {
            return new CartesianPoint(this.x + cp.x, this.y + cp.y);
        }
        // 通用的做法：用 distanceTo 实现转换
        throw new UnsupportedOperationException("Not implemented for other types");
    }

    @Override
    public double distanceTo(Point other) {
        if (other instanceof CartesianPoint cp) {
            double dx = this.x - cp.x;
            double dy = this.y - cp.y;
            return Math.sqrt(dx * dx + dy * dy);
        }
        throw new UnsupportedOperationException("Not implemented for other types");
    }

    @Override
    public Point origin() {
        return new CartesianPoint(0, 0);
    }
}

你把 CartesianPoint 设为包私有（package-private），外部就看不到具体类了。调用者只和 Point 打交道：

Point p1 = PointFactory.create(3.0, 4.0);
Point p2 = PointFactory.create(1.0, 2.0);
Point p3 = p1.add(p2);  // 完全不知道内部是笛卡尔坐标还是极坐标

这正是你想要的：表示独立（representation independence）。换内部实现不影响调用方代码。

第二层：不变量——永远不变的承诺

上一章你学会了在运行时加断言。在 ADT 里，不变量是结构性的——你负责保证每个操作之后 ADT 内部仍满足条件。

// ch02/Fraction.java - 不可变有理数
package com.craft;

public final class Fraction {
    private final int numerator;   // 分子
    private final int denominator; // 分母

    // 不变量：denominator > 0
    // 不变量：Fraction 始终处于最简形式（gcd 归一）
    // 不变量：numerator 可以为 0，但 denominator 必须为正

    public Fraction(int numerator, int denominator) {
        if (denominator == 0) {
            throw new IllegalArgumentException("denominator cannot be zero");
        }
        // 符号归一化：负号永远在分子上
        if (denominator < 0) {
            numerator = -numerator;
            denominator = -denominator;
        }
        // 约分到最简形式
        int g = gcd(Math.abs(numerator), denominator);
        this.numerator = numerator / g;
        this.denominator = denominator / g;
    }

    // 加法
    public Fraction add(Fraction other) {
        int newNum = this.numerator * other.denominator
                   + other.numerator * this.denominator;
        int newDen = this.denominator * other.denominator;
        return new Fraction(newNum, newDen);
    }

    public double toDouble() {
        return (double) numerator / denominator;
    }

    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    // 检查不变量（用于调试）
    private void checkInvariant() {
        assert denominator > 0 : "denominator must be positive";
        assert gcd(Math.abs(numerator), denominator) == 1 : "fraction must be reduced";
    }
}

注意这个类的设计：构造器强制约分，add 方法返回新的 Fraction，所有字段用 final。不可变性本身就是最强的不变量——你不需要检查"值会不会变"。

每次你设计一个 ADT，坐下来先写这一小段文档：

抽象值：X 代表什么？
操作：创建、查询、变换各有哪些？
不变量：什么条件必须在任何操作前后成立？
表示：内部用什么字段实现？

这就像工匠铺的图纸——先设计，再锻造。

第三层：等价性——两个东西什么时候"一样"

你用 Map<Point, String> 存储点的标签。往里面放了坐标 (3, 4)，然后用 (3, 4) 去取——取不出来。你揉了眼睛，又试了一遍。还是不行。

原因：你忘了实现 equals 和 hashCode。

Java 默认的 equals（来自 Object）比较的是引用——两个不同的对象即使字段完全一样，也判为不等。所以 new Point(3, 4).equals(new Point(3, 4)) 在 Java 里返回 false。

对于 ADT，你需要基于抽象值定义等价性。两个 Fraction 相等，当且仅当它们表示同一个有理数——不管内部分子分母是否一样（其实构造函数已保证约分）。

// ch02/Fraction.java (续)
@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof Fraction)) return false;
    Fraction fraction = (Fraction) o;
    // 因为构造器保证了最简形态，可以直接比分子分母
    return numerator == fraction.numerator
        && denominator == fraction.denominator;
}

@Override
public int hashCode() {
    return Objects.hash(numerator, denominator);
}

hashCode 遵守的契约：如果两个对象 equals 返回 true，它们的 hashCode 必须相同。反向不成立——hashCode 相同不等于相等（哈希碰撞）。

违反这个契约的后果很直接：HashMap 存进去一个值，用逻辑相等的 key 取不出来。

在 Python 里等价性是这样实现的：

# ch02/fraction.py
from __future__ import annotations
import math

class Fraction:
    def __init__(self, numerator: int, denominator: int):
        if denominator == 0:
            raise ValueError("denominator cannot be zero")
        if denominator < 0:
            numerator = -numerator
            denominator = -denominator
        g = math.gcd(abs(numerator), denominator)
        self._num = numerator // g
        self._den = denominator // g

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Fraction):
            return NotImplemented
        return (self._num == other._num and self._den == other._den)

    def __hash__(self) -> int:
        return hash((self._num, self._den))

    def __add__(self, other: Fraction) -> Fraction:
        new_num = self._num * other._den + other._num * self._den
        new_den = self._den * other._den
        return Fraction(new_num, new_den)

__eq__ + __hash__ 一起实现，缺失一个就会导致集合类行为诡异。

第四层：表示泄露——你不想让别人看到的东西

表示泄露（representation exposure）是你最需要主动防御的问题。它发生在一个你不想暴露的内部数据结构通过 getter 暴露给了外部。

// ch02/Playlist.java (有表示泄露的例子)
public class Playlist {
    private final List<String> songs;

    public Playlist(List<String> songs) {
        this.songs = songs;
    }

    // 表示泄露！外部拿到引用后可以随意修改
    public List<String> getSongs() {
        return songs;
    }
}

调用方可以这样改：

Playlist pl = new Playlist(someList);
List<String> stolen = pl.getSongs();
stolen.add("偷偷加的歌");  // 修改了 Playlist 的内部

修复方法你已经见过了——保护性拷贝：

public List<String> getSongs() {
    return new ArrayList<>(songs);
}

或者返回不可变视图：

public List<String> getSongs() {
    return Collections.unmodifiableList(songs);
}

构造器同样需要保护性拷贝：

public Playlist(List<String> songs) {
    this.songs = new ArrayList<>(songs);  // 复制一份
}

表示泄露的后果：调用者可以破坏你的不变量。比如一个 ADT 要求 songs 元素不重复，调用者通过泄露的引用添加了重复项——不变量就破了。

检测表示泄露的方法：检查你的类里每个返回引用类型的方法和每个接受引用类型的构造器/setter。如果返回的是内部引用，或者直接把外部引用赋给内部字段，就是泄露。

---

第二个例子：图形 ADT 设计

把这个思路走完一遍。设计一个接口 Shape：

// ch02/Shape.java
/**
 * 平面几何图形。不可变。
 * 
 * 抽象值：封闭区域
 * 操作：
 *   - area() : double
 *   - perimeter() : double
 *   - contains(Point) : boolean
 */
public interface Shape {
    double area();
    double perimeter();
    boolean contains(Point p);
}

实现圆形：

// ch02/Circle.java
public final class Circle implements Shape {
    private final Point center;
    private final double radius;

    // 不变量：radius > 0

    public Circle(Point center, double radius) {
        if (radius <= 0) {
            throw new IllegalArgumentException("radius must be positive");
        }
        this.center = center;  // 假设 Point 是不可变的
        this.radius = radius;
    }

    @Override
    public double area() {
        return Math.PI * radius * radius;
    }

    @Override
    public double perimeter() {
        return 2 * Math.PI * radius;
    }

    @Override
    public boolean contains(Point p) {
        return center.distanceTo(p) <= radius;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Circle)) return false;
        Circle circle = (Circle) o;
        return Double.compare(radius, circle.radius) == 0
            && center.equals(circle.center);
    }

    @Override
    public int hashCode() {
        return Objects.hash(center, radius);
    }
}

你添加一个矩形和一个复合图形 UnionShape：

// ch02/UnionShape.java
/**
 * 两个形状的并集。
 */
public final class UnionShape implements Shape {
    private final Shape a;
    private final Shape b;

    public UnionShape(Shape a, Shape b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public double area() {
        // 简单实现（不考虑重叠）：a + b
        return a.area() + b.area();
    }

    @Override
    public double perimeter() {
        // 这个实现忽略重叠交叉，近似值
        return a.perimeter() + b.perimeter();
    }

    @Override
    public boolean contains(Point p) {
        return a.contains(p) || b.contains(p);
    }
}

这就是 ADT 组合的威力：调用方不知道也不在乎某个 Shape 是 Circle、Rectangle 还是 UnionShape——它只知道调用 area() 会得到一个面积。你可以在不改变调用方任何代码的前提下任意增加新的形状类型。

等价性在这个例子里变得微妙：两个 UnionShape 什么时候相等？即使内部的两个 Shape 顺序不同，它们的集合运算结果一样。有人选择基于抽象值相等（"覆盖的区域完全一致"），有人选择基于结构相等（"包含相同的一组子形状"）。没有一个绝对正确的答案——等价性的定义是你在设计 ADT 时做出的设计决策，把它写清楚。

---

常见陷阱

陷阱一：用 instanceof 判断等价性而不做类型检查。 if (o instanceof Fraction) 是对的，因为 Fraction 是 final 的。如果类可能被继承，需要用 getClass() 检查：

if (o == null || getClass() != o.getClass()) return false;

陷阱二：把 equals 实现放到子类中却破坏了对称性。 一个父类 Point 和一个子类 ColorPoint，colorPoint.equals(point) 可能返回 false（因为 ColorPoint 检查颜色），但 point.equals(colorPoint) 可能会 true（因为 Point 不检查颜色）——违反了对称性。

陷阱三：用可变对象做 Map 的 key。 一个对象存进 HashMap 后，如果修改了它的 equals 相关字段，这个对象就"丢失"了——它在桶里，但 hashCode 变了，get 时找不到。

// 坏例子
Map<List<Integer>, String> map = new HashMap<>();
List<Integer> key = new ArrayList<>(List.of(1, 2, 3));
map.put(key, "value");
key.add(4);  // key 变了！再也拿不出来了

陷阱四：过度设计接口。 不是所有类都需要一个接口加多个实现。如果你的 Point 只会有一种实现（笛卡尔坐标），可以直接写 final class，不必抽接口。接口是用于需要替换实现的场景。

---

通关挑战

• 热身：给 Fraction 加上减法、乘法和除法。每次操作后检查不变量。
• 挑战：设计一个 Deck（牌组）的 ADT。接口只暴露洗牌、抽牌、剩余张数。内部可以用 List<Card> 或 Stack<Card>——但不要暴露实现。实现 equals 和 hashCode，写测试验证。
• 观察：找到你项目里一个类，检查它的 getter 和构造器有没有表示泄露。如果有，修掉它。

---

旅人笔记

抽象数据类型把"怎么实现"和"怎么用"分开，通过隐藏表示细节、维护不变量、定义等价性，让代码在逻辑层面变得精确——你不再是在改内存里的字段，是在操作一个数学概念。

---

下一站预告

拿到了 ADT 这把尺子，你开始思考更大的问题：整个系统应该长什么样子？不止是单个数据类型，而是整个软件工厂的蓝图。下一章，从需求分析到架构设计。