数据抽象

Posted on

数据类型指的是一组值和一组对这些值的操作的集合。原则上所有程序都只需要使用原始数据类型即可，但为了在更高层次的抽象上编写程序更加方便，重点学习定义和使用数据类型，这个过程也被称为数据抽象。

Java 编程的基础主要是使用 class 关键字构造被称为引用类型的数据类型。这种编程风格称为面向对象编程，因为它的核心概念是对象，即保存了某个数据类型的值的实体。

抽象数据类型（ADT）是一种能够对使用者隐藏数据表示的数据类型：

  • 在使用 ADT 时，我们的注意力集中在 API 描述的操作上，而不会去关心数据的表示；
  • 在实现 ADT 时，我们的注意力集中在数据本身，并将实现对该数据的各种操作；

在程序设计上，ADT 支持封装：

  • 以适用于各种用途的 API 形式，准确地定义问题；
  • 用 API 的实现描述算法和数据结构；

使用抽象数据类型

要使用一种数据类型并不一定非得知道它是如何实现的，所以我们首先来编写一个使用一种名为 Counter 的简单数据类型的程序。

要使用 Counter 对象，首先需要了解应该如何定义数据类型的操作，以及在 Java 语言中应该如何创建和使用某个数据类型的对象。

抽象数据类型的 API

我们使用 API 来说明抽象数据类型的行为，列出所有构造函数和实例方法（即操作），并简要描述它们的功用：

ADT 和静态方法库之间有许多共同之处：

  • 两者的实现均为 Java 类；
  • 实例方法也能接受 0 个或多个指定类型的参数；
  • 它们可能会返回一个指定类型的值，也可能不会；

当然，它们也有三个显著的不同：

  • ADT 中可能会出现若干个名称和类名相同且没有返回值的函数，这些特殊的函数被称为构造函数；
  • 实例方法不需要 static 关键字，它们不是静态方法；
  • 某些实例方法的存在是为了尊重 Java 的习惯——我们将此类方法称为继承的方法；

ADT 的 API 是和用例之间的一份契约，因此它是开发任何用例代码以及实现任意数据类型的起点。

继承的方法

根据 Java 的约定，任意数据类型都能通过在 API 中包含特定的方法从 Java 的内在机制中获益。

例如，Java 中的所有数据类型都会继承 toString() 方法来返回用 String 表示的该类型的值。但这种默认实现并不实用，我们常常会提供实现来重载默认实现，并在 API 中加上 toString() 方法。

用例代码

将程序组织为独立模块的机制可以应用于所有的 Java 类，因此它对基于抽象数据类型的模块化编程与静态函数库一样有效。

通过将实现某种数据类型的全部代码封装在一个 Java 类中，我们可以将用例代码推向更高的抽象层次。这种方式和原始数据的使用方式非常不同。

对象

可以声明一个变量 heads 并将它通过以下代码和 Counter 类型的数据关联起来：

1
Counter heads;

对象是能够承载数据类型的值的实体，所有对象都有三大重要特性：状态、标识和行为：

  • 对象的状态即数据类型中的值；
  • 对象的标识能够将一个对象区别于另一个对象，可以认为是在内存中的位置；
  • 对象的行为就是数据类型的操作；

Java 使用引用类型以示和原始数据类型的区别，可以认为引用就是内存地址。

创建对象

要实例化一个对象，我们用关键字 new 并紧跟类名以及 () 来触发它的构造函数，或在括号中指定一系列的参数，如果构造函数需要的话。

每当用例调用了 new()，系统就会：

  • 为新的对象分配内存空间；
  • 调用构造函数初始化对象中的值；
  • 返回该对象的一个引用；

我们一般都会在一条声明语句中创建一个对象并通过将它和一个变量关联起来初始化该变量。和原始数据类型不同的是，变量关联的是指向对象的引用，而并非数据类型的值本身：

调用实例方法

实例方法的意义在于操作数据类型中的值。我们调用一个实例方法的方式是先写出对象的变量名，紧接着是一个句点，然后是实例方法的名称，之后是 0 个或多个在括号中由逗号分隔的参数。

实例方法参数按值传递，方法名可以被重载，方法可以有返回值，它们也许还会产生一些副作用。

实例方法和静态方法的调用方式完全相同，可以通过语句（void 方法），也可以通过表达式（有返回值的方法）；静态方法的主要作用是实现函数，非静态方法的主要作用是实现数据类型的操作：

使用对象

要开发某种给定数据类型的用例，我们需要：

  • 声明该类型的变量，以用来引用对象；
  • 使用关键字 new 触发能够创建该类型的对象的构造函数；
  • 使用变量名在语句或表达式中调用实例方法；

除了这些直接用法外，我们可以和使用原始数据类型的变量一样使用和对象关联的变量：

  • 赋值语句；
  • 向方法传递对象或从方法中返回对象；
  • 创建并使用对象的数组；

你需要从引用而非值的角度去考虑问题才能理解这些用法的行为。

赋值语句

使用引用类型的赋值语句将会创建该引用的一个副本。赋值语句不会创建新的对象，而只是创建另一个指向某个已经存在的对象的引用。这种情况被称为别名：两个变量同时指向同一个对象。如下例所示：

1
2
3
4
Counter c1 = new Counter("ones");
c1.increment();
Counter c2 = c1;
c2.increment();

改变一个对象的状态将会影响到所有和该对象的别名有关的代码。

将对象作为参数

可以将对象作为参数传递给方法，这一般都能简化用例代码。

这将会传递引用的值，也就是传递对象的引用；方法虽然无法改变原始的引用，但它能够改变该对象的值。

将对象作为返回值

当然也能够将对象作为方法的返回值。这种能力非常重要，因为 Java 中的方法只能有一个返回值——有了对象我们的代码实际上就能返回多个值。

数组也是对象

在 Java 中，所有非原始数据类型的值都是对象，也就是说，数组也是对象。
当我们将数据传递给一个方法或是将一个数组变量放在赋值语句的右侧时，我们都是在创建该数组引用的一个副本，而非数组的副本。

对象的数组

创建一个对象的数组需要以下两个步骤：

  • 使用方括号语法调用数组的构造函数创建数组；
  • 对于每个数组元素调用它的构造函数创建相应的对象；

在 Java 中，对象数组即是一个由对象的引用组成的数组，而非所有对象本身组成的数组：

  • 如果对象非常大，那么在移动它们时由于只需要操作引用而非对象本身，这就会大大提高效率；
  • 如果对象很小，每次获取信息时都需要通过引用反而会降低效率；

运用数据抽象的思想编写代码（定义和使用数据类型，将数据类型的值封装在对象中）的方式称为面向对象编程。

一个数据类型的实现所支持的操作如下：

  • 创建对象：使用 new 关键字触发构造函数并创建对象，初始化对象中值并返回对它的引用；
  • 操作对象中的值：使用和对象关联的变量，调用实例方法，来对对象中的值进行操作；
  • 操作多个对象：创建对象的数组，像原始数据类型的值一样将它们传递给方法，或是从方法中返回；

这些能力是这种灵活且应用广泛的现代编程方式的基础，也是我们对算法研究的基础。

抽象数据类型举例

Java 语言内置了上千种抽象数据类型，我们也会为了辅助算法研究，创建许多其他抽象数据类型。

我们将会用到或开发的数据类型，可以被分为以下几类：

  • java.lang.* 中的标准系统抽象数据类型，可以被任意 Java 程序调用；
  • Java 标准库中的抽象数据类型，如 java.swt、java.net 和 java.io，它们也可以被任意 Java 程序调用，但需要 import 语句；
  • I/O 处理类抽象数据类型，和 StdIn 和 StdOut 类似，允许我们处理多个输入输出流；
  • 面向数据的抽象数据类型，它们的主要作用是通过封装数据的表示，简化数据的组织和处理；
  • 集合类抽象数据类型，它们的主要用途是简化对同一类型的一组数据的操作；
  • 面向操作的抽象数据类型，我们用它们分析各种算法；
  • 图算法相关的抽象数据类型；

从整体上来说，我们使用的抽象数据类型说明，组织并理解所使用的数据结构，是现代编程中的重要因素。

几何对象

面向对象编程的一个典型例子是为几何对象设计数据类型：

  • Point2D：平面上的点；
  • Interval1D：直线上的间隔；
  • Interval2D：平面上的二维间隔；

处理几何对象的程序在自然世界模型、科学计算、电子游戏、电影等许多应用的计算中有着广泛的应用。此类程序的研发已经发展成了计算机几何学，这门影响深远的研究学科。

信息处理

无数应用的核心都是组织和处理信息，抽象数据类型是组织信息的一种自然方式。

为了简化用例的代码，我们为每个类型都提供了两个构造函数，一个接受适当类型的数据，另一个则能够解析字符串中的数据。

每当遇到逻辑上相关的不同类型的数据时，都应该考虑定义一个抽象数据类型。这么做能够帮助我们组织数据，并在一般应用程序中极大地简化使用者的代码。

字符串

Java 的 String 是一种重要而实用的 ADT。一个 String 值是一串可以由索引访问的 char 值，String 对象拥有许多实例方法：

split() 方法的参数可以是正则表达式，“\s+”表示“一个或多个制表符、空格、换行符或回车”。

为了使代码更加简洁清晰，不直接使用字符数组代替 String 值。

再谈输入输出

我们的标准库定义了数据类型 In、Out 和 Draw。当使用一个 String 类型的参数调用它们的构造函数时：

  1. 首先尝试在当前目录下查找指定的文件；
  2. 假设该参数是一个网站的名称，并尝试连接到那个网站；
  3. 抛出一个运行时异常；

指定的文件或网站都会成为，被创建的输入或输出流对象的来源或目标，所有 read*() 和 print*() 方法都会指向那个文件或网站。

抽象数据类型的实现

和静态方法库一样，我们也需要使用 class 实现 ADT，并将所有代码放入一个和类名相同并带有 .java 扩展名的文件中。

文件的第一部分语句会定义表示数据类型的值的实例变量。它们之后是实现对数据类型的值的操作的构造函数和实例方法：

单元测试用例 main()，通常在调试和测试中很实用。

实例变量

实例变量和局部变量的关键区别在于：

  • 每一时刻，每个局部变量只会有一个值；
  • 每一时刻，每个实例变量对应着无数值；

每个实例变量的声明都需要一个可见性修饰符，在 ADT 的实现中，我们会使用 private，也就是使用 Java 语言的机制来保证向使用者隐藏 ADT 中的数据表示。

如果我们使用 public 修饰这些实例变量，那么根据定义，这种数据类型就不再是抽象的了。

构造函数

每个 Java 类都至少含有一个构造函数，以创建一个对象的标识。

构造函数的作用是初始化实例变量，每个构造函数都将创建一个对象并向调用者返回一个该对象的引用。

如果没有定义构造函数，类将会隐式定义一个默认情况下不接受任何参数的构造函数，并将所有实例变量初始化为默认值。

重载构造函数一般用于将实例变量由默认值初始化为用例提供的值。

实例方法

每个实例方法都有一个返回值类型、一个签名和一个主体。

当调用者触发了一个方法时，它的效果就好像调用者代码中的函数调用，被替换为了这个返回值。

实例方法的所有行为都和静态方法相同，只有一点关键的不同：

  • 它们可以访问并操作实例变量；

面向对象编程为 Java 程序增加了另一种使用变量的重要方式：通过触发一个实例方法来操作该对象的值。

作用域

实现实例方法的 Java 代码中，使用了三种变量：

  • 参数变量：作用域是整个方法；
  • 局部变量：作用域是当前代码段中，它定义之后的所有语句；
  • 实例变量：作用域是整个类，如果出现二义性，可以使用 this 前缀区分；

API、用例与实现

每个 ADT 的实现都是一个含有若干私有实例变量、构造函数、实例方法和一个测试用例的 Java 类。

按照下面三步走的方式，用 ADT 满足用例的需求：

  • 定义一份 API：API 的作用是将使用和实现分离；
  • 用一个 Java 类实现 API 的定义：首先我们选择适当的实例变量，然后再编写构造函数和实例方法；
  • 实现多个测试用例，验证前两步做出的设计决定；

更多抽象数据类型的实现

理解抽象数据类型的威力和用法的最好方法，就是仔细研究更多的例子和实现。

日期

实现的性能往往是有区别的：实现中保存数据类型的值所需的空间较小，代价是在向用例按照约定的格式，提供这些值时花费的时间更多。

在实现中使用数据抽象的一个关键优势是：我们可以将一种实现替换为另一种而无需改变用例的任何代码。

维护多个实现

同一个 API 的多个实现可能会产生维护和命名问题。

在某些情况下，我们可能只是想将较老的实现替换为改进的实现；而在另一些情况下，我们可能需要维护两种实现，一种适用于某些用例，另一种适用于另一些用例：

  • 通过前缀的描述性修饰符，区别同一份 API 的不同实现；
  • 维护一个没有前缀的参考实现，它应该适用于大多数用例的需求；

累加器

累加器 API 定义了一种能够为用例计算一组数据的实时平均值的抽象数据类型：

它的实现很简单：维护一个 int 类型的实例变量，来记录已经处理过的数据值的数量；以及一个 double 类型的实例变量，来记录所有数据值之和，将和除以数据数量即可得到平均值：

请注意该实现并没有保存数据的值——它可以用于处理大规模的数据，甚至是在一个无法全部保存它们的设备上。

可视化的累加器

可视化累加器的实现继承了 Accumulator 类并展示了一种实用的副作用。完成这项任务最简单的办法是添加一个构造函数，来指定需要绘出的点数和它们的最大值。

添加一个构造函数来取得某些功能，有时能通过测试用例，因为它对用例的影响和改变类名所产生的变化相同。

数据类型的设计

抽象数据类型是一种向用例隐藏内部表示的数据类型，这种思想强有力地影响了现代编程。

封装

面向对象编程的特征之一，就是使用数据类型的实现封装数据，以简化实现和隔离用例开发。封装实现了模块化编程，它允许我们：

  • 独立开发用例和实现的代码；
  • 切换至改进的实现而不会影响用例的代码；
  • 支持尚未编写的程序（对于后续用例，API 能够起到指南的作用）；

封装同时也隔离了数据类型的操作，这使我们可以：

  • 限制潜在的错误；
  • 在实现中添加一致性检查等调试工具；
  • 确保用例代码更明晰；

模块化编程成功的关键在于保持模块之间的独立性，我们坚持将 API 作为用例和之间的唯一的依赖点。

我们并不需要知道一个数据类型是如何实现的才能使用它，实现数据类型时也应该假设使用者除了 API 什么也不知道。封装是获得所有这些优势的关键。

设计 API

构建现代软件最重要也是最有挑战的一项任务就是设计 API，它需要经验、思考和反复的修改，但设计一份优秀的 API 所付出的所有时间，都能从调试和代码复用所节省的时间中获得回报。

为了验证我们的设计，我们会在 API 附近的正文中给出一些用例代码。但这些宏观概述之中也隐藏着每一份 API 设计都可能落入的无数陷阱：

  • API 可能会难以实现：实现的开发非常困难，甚至不可能；
  • API 可能会难以使用：用例代码甚至比没有 API 时更复杂；
  • API 的范围可能太窄：缺少用例所需的方法；
  • API 的范围可能太宽：包含许多不会被任何用例调用的方法。API 的大小一般会随着时间而增长，因为向已有的 API 中添加新方法很简单，但在不破坏已有用例程序的前提下，从中删除方法却很困难；
  • API 可能会太粗略：无法提供有效的抽象；
  • API 可能会太详细：抽象过于细致或是发散而无法使用；
  • API 可能会过于依赖某种特定的数据表示：用例代码可能会因此无法从数据表示的细节中解脱出来。要避免这种缺陷也是困难的，因为数据表示显然是 ADT 实现的核心；

只为用例提供它们所需要的，仅此而已。

算法与抽象数据类型

数据抽象天生适合算法研究，因为它能够为我们提供一个框架，在其中能够准确地说明一个算法的目的，以及其他程序应该如何使用该算法。

每个 Java 程序都是一组静态方法和（或）一种数据类型实现的集合。数据抽象使我们能够：

  • 准确定义算法能为用例提供什么；
  • 隔离算法的实现和用例的代码；
  • 实现多层抽象，用已知算法实现其他算法；

使用 Java 的类机制来支持数据的抽象，将使我们收获良多：我们编写的代码将能够测试算法，并比较各种用例程序的性能。

接口继承

Java 语言为定义对象之间的关系提供了支持，称为接口。

接口继承使得我们的程序能够通过调用接口中的方法，操作实现该接口的任意类型的对象（甚至是还未被创建的类型）。

在某些情况下 Java 的习惯用法鼓励我们使用接口：我们用它们进行比较和迭代。

实现继承

Java 还支持另一种继承机制，被称为子类。这种非常强大的技术使程序员不需要重写整个类，就能改变它的行为或者为它添加新的功能。

它的主要思想是定义一个新类（子类，或称为派生类），来继承另一个类（父类，或称为基类）的所有实例方法和实例变量。

每个类都是 Java 的 Object 类的子类：

字符串表示的习惯

当连接运算符的一个操作数是字符串时，Java 会自动将另一个操作数也转换为字符串。如果一个对象的数据类型没有实现 toString() 方法，那么转换会调用 Object 的默认实现。

默认实现一般都没有多大实用价值，因为它只会返回一个含有该对象内存地址的字符串。因此我们通常会为我们的每个类实现，并重写默认的 toString() 方法。

封装类型

Java 提供了一些内置的引用类型，称为封装类型。每种原始数据类型都有一个对应的封装类型：Boolean、Byte、Character、Double、Float、Integer、Long 和 Short 分别对应着 boolean、byte、char、double、float、int、long 和 short。

在需要的时候 Java 会自动将原始数据类型转换为封装类型。

等价性

我们检测的是标识是否相同，即引用是否相同。一般用例希望能够检测数据类型的值（对象的状态）是否相同，或者实现某种针对该类型的规则。

当我们定义自己的数据类型时，需要重载 equals() 方法，Java 约定 equals() 必须是一种等价性关系，它必须具有：

  • 自反性：x.equals(x) 为 true；
  • 对称性：当且仅当 y.equals(x) 为 true 时，x.equals(y) 返回 true；
  • 传递性：如果 x.equals(y) 和 y.equals(z) 均为 true，x.equals(z) 也将为 true；
  • 一致性：当两个对象均未被修改时，反复调用 x.equals(y) 总是会返回相同的值；
  • 非空性：x.equals(null) 总是返回 false；

确保这些性质成立并遵守 Java 的约定，同时又避免在实现时做无用功并不容易：

  • 如果该对象的引用和参数对象的引用相同，返回 true。这样测试在成立时，能够免去其他所有测试工作；
  • 如果参数为 null，根据约定返回 false。还可以避免在下面的代码中使用空引用；
  • 如果两个对象的类不同，返回 false。要得到一个对象的类，可以使用 getClass() 方法；
  • 将参数对象的类型从 Object 转换到 Date；
  • 如果任意实例变量的值不相同，返回 false。对于其他类，等价性测试方法的定义可能不同；

可以使用下面的实现，作为实现任意数据类型的 toString() 和 equals() 方法的模版：

内存管理

如下所示的三行赋值语句：

1
2
3
Date a = new Date(12, 31, 1999);
Date b = new Date(1, 1, 2011);
a = b;

本来该对象的唯一引用就是变量 a，但是该引用被赋值语句覆盖了，这样的对象被称为孤儿。

内存管理对于原始数据类型更容易，因为内存分配所需要的所有信息，在编译阶段就能够获取。

对象的内存管理更加复杂：系统会在创建一个对象时为它分配内存，但是程序在执行时的动态性，决定了一个对象何时才会变为孤儿，系统并不能准确地知道应该何时释放一个对象的内存。

Java 最重要的一个特性就是自动内存管理。它通过记录孤儿对象，并将它们的内存释放到内存池中，将程序员从管理内存的责任中解放出来。这种回收内存的方式叫做垃圾回收。

Java 的一个特点就是它不允许修改引用的策略，这种策略使 Java 能够高效自动地回收垃圾。

不可变性

Java 语言通过 final 修饰符来强制保证不可变性。当你将一个变量声明为 final 时，也就保证了只会对它赋值一次，可以用赋值语句，也可以用构造函数。试图改变 final 变量的值的代码，将会产生一个编译时错误。

一般来说，不可变的数据类型比可变的数据类型使用更容易，误用更困难，因为能够改变它们的值的方式要少得多。

不可变性的缺点：

  • 需要为每个值创建一个新对象。这种开销一般是可以接受的，因为 Java 的垃圾回收器通常都为此进行了优化；
  • final 非常不幸地只能用来保证原始数据类型的实例变量的不可变性，而无法用于引用类型的变量；

任何数据类型的设计都需要考虑到不可变性，而且数据类型是否是不可变的应该在 API 中说明，这样使用者才能知道该对象中的值，是无法改变的。

契约式设计

Java 语言中能够在程序运行时检验程序状态，为此我们将使用两种 Java 的语言特性：

  • 异常（Exception）：一般用于处理不受我们控制的不可预见的错误；
  • 断言（Assertion）：验证我们在代码中做出的一些假设；

大量使用异常和断言是很好的编程实践。

异常与错误

异常和错误都是在程序运行中出现的破坏性事件，Java 采取的行动称为抛出异常或是抛出错误。

一种叫做快速出错的常规编程实践提倡：一旦出错就立刻抛出异常，使定位出错位置更容易。

断言

断言是一条需要在程序的某处确认为 true 的布尔表达式。如果表达式的值为 false，程序将会终止并报告一条出错信息。我们使用断言来确定程序的正确性，并记录我们的意图。

默认设置没有启动断言，可以在命令行下使用 -ea 标志启用断言。断言的作用是调试：程序在正常操作中不应该依赖断言，因为它们可能会被禁用。

一种叫做契约式设计的编程模型采用的就是这种思想，数据类型的设计者需要说明：

  • 前提条件：用例在调用某个方法前必须满足的条件；
  • 后置条件：实现在方法返回时必须达到的要求；
  • 副作用：方法可能对对象状态产生的任何其他变更；

在开发过程中，这些条件可以用断言进行测试。