3.3 抽象数据类型 (ADT)

1. 抽象和用户定义类型

用户定义类型
一种编程语言具有内置类型(如整数、布尔值、字符串等)和内置过程(如用于输入和输出)。
用户可以定义他们自己的数据类型和过程——用户定义的类型。
除了编程语言所提供的基本数据类型和对象数据类型，程序员可定义自己的数据类型

数据抽象
数据抽象：由一组操作所刻画的数据类型
传统的类型定义：关注数据的具体表示

抽象类型：强调“作用于数据上的操作”，程序员和client无需关心数据如何具体存储的，只需设计/使用操作即可。

抽象类型由其操作定义
T的操作和规约刻画了T的特征
当我们谈到列表类型时，我们指的不是链表或数组或表示列表的任何其他特定数据结构。
相反,我们的意思是一套不透明的价值观——可能的对象列表类型,满足所有的规格列表的操作:把get(),size(),等等。
ADT是由操作定义的，与其内部如何实现无关！

2. 分类类型和操作

可变和不可变数据类型
可变类型的对象：提供了可改变其内部数据的值的操作
不可变数据类型： 其操作不可改变内部值，而是构造新的对象
一些类型提供两种形式

对抽象类型的操作进行分类
构造器(从无到有) t* → T
生产器(从旧到新) T+, t* → T
观察器：获取抽象类型的对象并返回不同类型的对象。 T+, t* → t
变值器：改变对象属性的方法
T+, t* → void | t | T

▪每个T是抽象类型本身;
▪每个t是一些其他类型。
▪+标记表明该类型可能在签名的该部分出现一次或多次。
▪*标记表明它出现0次或更多次。
▪|指示or。

操作的签名
String.concat() 作为生产器
– concat: String × String → String

List.size()作为观察器
– size: List → int

String.regionMatches作为观察器
– regionMatches: String × boolean × int × String × int × int → boolean

构造器：可以像new一样作为构造函数实现
ArrayList()，或者只是一个静态方法，比如
Arrays.aslist (), List.of ()。

实现为静态方法的构造器通常称为工厂方法

Java中不同的String.valueOf(Object Obj)的方法是实现为工厂方法的其他创建者示例，与Object.toString()正好是相对的

变值器通常返回void，如果返回值为void，则必然意味着它改变了对象的某些内部状态

变值器也可能返回非空类型

3. 抽象数据类型示例

int和String
int是不可变的，所以它没有变值器。
构造器：数字文字0、1、2、…
生产器：算术运算符+，-，*，/
观察器：比较运算符==，!=，<，>
变值器:没有

String是Java的字符串类型。字符串是不可变的
构造器：字符串构造函数
生产器：concat , substring , toUpperCase
观察器：length , charAt
变值器:没有

List
List是Java的List类型，并且是可变的。

List也是一个接口，这意味着其他类提供数据类型的实际实现，比如ArrayList和LinkedList。

构造器：ArrayList,LinkedList构造函数，Collections.singletonList
生产器：Collections.unmodifiableList
观察器： size , get
变值器: add , remove , addAll，Collections.sort

4. 设计抽象类型

设计抽象类型
良好ADT的设计：靠“经验法则”，提供一组操作，设计其行为规约 spec

1.设计简洁、一致的操作
设计一组简单操作，通过简单操作的组合实现复杂的操作。操作的行为应该
是内聚的

2.要足以支持client对数据所做的所有操作需要，且用操作满足client需要的难度要低
判断方法：对象每个需要被访问到的属性是否都能够被访问到
没有get()操作就无法获取list的内部数据
用遍历方式获取list的size –太复杂 vs 提供
size()操作，方便client使用

3.要么抽象、要么具体，不要混合 — 要么针对抽象设计，要么针对具体应用的设计
面向具体应用的类型不应包含通用方法
面向通用的类型不应包含面向具体应用的方法

5.表示独立性

表示独立性
表示独立性：client使用ADT时无需考虑其内部如何实现，ADT内部表示的变化不应影响外部spec和客户端。

通过前提条件和后置条件充分刻画了ADT的操作，spec规定了client和implementer之间的契约，明确了client知道可以依赖哪些内容，implementer知道可以安全更改的内容

6.测试抽象数据类型

如何测试ADT
▪我们为ADT的每个操作创建测试，从而为它建立一个测试套件。
▪这些测试不可避免地相互作用。
▪测试创造者、生产者和突变者的唯一方法是对结果对象调用观察者，同样，测试观察者的唯一方法是为他们创建观察对象。

▪ 测试构造器, 生产器和变值器：调用观察器来观察这些操作的结果是否满足spec；
▪ 测试观察器：调用构造器, 生产器和变值器等方法产生或改变对象，来看结果是否正确。
▪ 风险：如果被依赖的其他方法有错误，可能导致被测试方法的测试结果失效。

7.不变量

ADT的不变量
ADT需要始终保持其不变量
不变量：程序在任何时候总是true的性质
例如：immutability就是一个典型的“不变量
由ADT来负责其不变量，与client端的任何行为无关

为什么需要不变量?
为什么需要不变量：保持程序的“正确性”，容易发现错误

如果没有这个不变量，那么在所有使用String的地方，都要检查其是否改变了

总是要假设client 有“恶意”破坏ADT不变量的
行为—defensive programming

不变性的第一个威胁来自客户机可以直接访问它的字段
表示泄露：不仅影响不变量，也影响了表示独立性：无法在不影响客户端的情况下改变其内部表示

private和public关键字表示哪些字段和方法只能在类中访问，哪些可以从类外部访问。
▪final关键字还有助于确保这个不可变类型的字段在对象构造之后不会被重新分配

防御性拷贝
防御性复制是一种防御性编程方法
-假设客户端会试图破坏不变量-可能是真的(恶意黑客)，但更有可能是无心之过
-确保类不变量不受任何输入的影响，以最小化可变性

复制和Clone()
可变类型通常有一个复制构造函数，允许您创建一个复制现有实例值的新实例。
-在本例中，Date的复制构造函数使用时间戳值，以1970年1月1日以来的毫秒为单位。
-作为另一个例子，StringBuilder的复制构造函数接受一个字符串。

复制可变对象的另一种方法是clone()，它受到一些类型的支持，但不是所有类型的支持。

▪一般来说，你应该仔细检查所有ADT操作的参数类型和返回类型。
▪如果任何类型是可变的，确保你的实现不会直接引用它的表示。
▪这样做会产生重复暴露。

把责任留给你的客户?

当复制代价很高时，不得不这么做,当复制代价很高时，不得不这么做

使用不可变类型而不是可变类型
除非迫不得已，否则不要把希望寄托于客户端上，ADT有责任保证自己的invariants，并避免“表示泄露”。

最好的办法就是使用immutable的类型，彻底避免表示泄露

总结
▪不要在对象中加入可变参数;创建防御副本
▪返回可变域的防御副本…
-返回新实例，而不是修改
▪或返回可变字段的不可修改视图
▪真实的教训-使用不可变的组件，以消除需要的防御性复制
保持不变性和避免表示泄漏，是ADT最重要的一个Invariant！

8. Rep不变量和抽象函数

两个值空间
R:表示值的空间(代表值),实现者看到和使用的值
一般情况下ADT的表示比较简单，有些时候需要复杂表示

A:抽象值的空间由类型要支持的值组成,client看到和使用的值

ADT开发者关注表示空间R，client关注抽象空间A

R和A之间的映射
每一个抽象值映射到一些代表值(满射)。

一些抽象的值映射到由多个代表值(未必单射)。

并不是所有的rep值映射(未必双射)。

抽象函数(AF)
抽象函数：R和A之间映射关系的函数，即如何将R中的每一个值解释为A中的每一个值。

AF : R → A

图中的弧表示抽象函数。

rep不变量(RI):另一个重要的ADT不变量
一个rep不变量，映射到布尔值代表:

RI : R → boolean

▪ 表示不变性RI：某个具体的“表示”是否是“合法的”
▪ 也可将RI看作：所有表示值的一个子集，包含了所有合法的表示值
▪ 也可将RI看作：一个条件，描述了什么是“合法”的表示值

记录RI和AF
rep不变量和抽象函数都应该记录在代码中，就在rep声明的旁边:

什么决定了AF和RI?
▪抽象值空间本身并不决定AF或RI:
-同一抽象类型可以有多个表示。
一组字符可以像上面一样表示为字符串，也可以表示为位向量，每个可能的字符表示一个位。
-显然，我们需要两个不同的抽象函数来映射这两个不同的代表值空间。
——不同的内部表示,需要设计不同的AF和RI

选择某种特定的表示方式R，进而指定某个子集是“合法”的(RI)，并为该子集中的每个值做出“解释”(AF)——即如何映射到抽象空间中的值。

同样的表示空间R，可以有不同的RI

即使是同样的R、同样的RI，也可能有不同的AF，即“解释不同”。

RI和AF如何影响ADT设计
设计ADT：
(1) 选择R和A；
(2) RI — 合法的表示值；
(3) 如何解释合法的表示值 —映射AF
做出具体的解释：每个rep value如何映射到abstract value,而且要把这种选择和解释明确写到代码当中

随时检查RI是否满足
rep不变量不仅仅是一个简单的数学概念。如果您的实现在运行时断言rep不变式，那么您可以尽早捕获bug

在所有可能改变rep的方法内都要检查

Observer方法可以不用，但建议也要检查，以防止你的“万一”

9.有益的可变性

有益的可变性
▪回想一下，一个类型是不可变的，当且仅当该类型的值在创建后没有变化。
▪随着我们对抽象空间A和R的新理解，我们可以完善这个定义:抽象的价值不应该改变。
▪但是只要rep值继续映射到相同的抽象值，就可以*地更改rep值，这样客户端就不会看到更改。
▪这种变化被称为有益的可变性

▪ 对immutable的ADT来说，它在A空间的abstract value应是不变的。
▪ 但其内部表示的R空间中的取值则可以是变化的。

为什么需要有有益的可变性?
这种实现者*通常允许性能改进
通过牺牲immutability的部分原则来换取“效率”和“性能”

10. 记录AF、RI和避免Rep暴露

记录AF和RI
在代码中用注释形式记录AF和RI
要精确的记录RI：rep中的所有fields何为有效
要精确记录AF：如何解释每一个R值

记录rep暴露安全声明
给出理由，证明代码并未对外泄露其内部表示

总结：ADT的Spec的内容
ADT的规约里只能使用client可见的内容来撰写，包括参数、返回值、异常等

如果规约里需要提及“值”，只能使用A空间
中的“值”。

ADT的规约里也不应谈及任何内部表示的细节，以及R空间中的任何值

ADT的内部表示(私有属性)对外部都应严格不可见

故在代码中以注释的形式写出AF和RI而不能在Javadoc文档中，防止被外部看到而破坏表示独立性/信息隐藏

如何建立不变量
不变量是一个适用于整个程序的属性——在对象不变量的情况下，它减少到对象的整个生存期。

要使保持不变，我们需要:
在对象的初始状态不变量为true，在对象发生变化时，不变量也要为true

将其转化为ADT操作的类型:
构造器和生产器在创建对象时要确保不变量为true
变值器和观察器在执行时必须保持不变性
在每个方法return之前，用checkRep()检查不变量是否得以保持。

表示泄漏的风险：一旦泄露，ADT内部表示可能会在程序的任何位置发生改变（而不是限制在ADT内部），从而无法确保ADT的不变量是否能够始终保持为true。

用这三个标准来检查你的ADT是否保持不变量
-由构造器和生产器建立;
-由变值器和观察器保存;
-无再现性暴露发生

11. ADT不变量代替前置条件

ADT不变量代替前置条件
用ADT不变量取代复杂的前置条件Precondition，相当于将复杂的前置条件precondition封装到了ADT内部

▪它更安全，因为所需的条件(排序没有重复)可以在一个地方执行，SortedSet类型，也因为Java静态检查起作用，防止在编译时出现错误，不满足这个条件的值被使用。
▪它更容易理解，因为它更简单，和名字
SortedSet传达了程序员需要知道的东西。
▪它更容易改变，因为代表
SortedSet现在可以在不更改排他性或其任何客户端的情况下进行更改。

12. 总结

▪抽象数据类型的特点是操作。
▪操作可以分为构造器、生产器、变值器和观察器;
▪ADT的规范是它的一套操作和规范。
▪一个好的ADT是简单的，连贯的，充分的，和代表独立的。
▪ADT的测试是通过生成测试的每一个操作，但使用构造器、生产器、变值器和观察器一起在相同的测试。

安全防范漏洞。好的ADT为数据类型提供定义良好的契约，这样客户端就知道从数据类型期望什么，实现者也有定义良好的*来改变。

容易理解。好的ADT将其实现隐藏在一组简单的操作之后，因此使用ADT的程序员只需要了解操作，而不需要了解实现的细节。

为变化做好准备。表示独立性允许抽象数据类型的实现在不需要从其客户端进行更改的情况下进行更改。

▪对于ADT对象实例来说，在对象的生命周期内，一个不变式是一个始终为真的属性。
▪一个好的ADT保持它自己的不变量。不变量必须由构造器和生产器创建，并由变值器和观察器保存。
▪rep不变量指定表示的合法值，应在运行时使用checkRep()进行检查。
▪抽象函数将一个具体的表示法映射到它所表示的抽象值。
▪再现暴露威胁着再现的独立性和不变保存。

▪安全防范漏洞。一个好的ADT保留它自己的不变量，这样那些不变量就不太容易受到ADT客户端的bug的影响，并且在ADT自身的实现中可以更容易地隔离对不变量的违反。显式地声明rep不变式，并在运行时使用checkRep()检查它，可以更早地捕获误解和错误，而不是继续使用损坏的数据结构。
▪容易理解。代表不变量和抽象函数解释了数据类型表示的含义，以及它与抽象的关系。
▪为变化做好准备。抽象数据类型将抽象与具体表示分离开来，这使得不必更改客户机代码就可以更改表示。