关于ADT的一些思考

ADT基本概念

1.什么是ADT？

抽象数据类型（Abstract Data Type,ADT）是将数据对象，数据对象之间的关系和数据对象的基本操作封装在一起的一种表达方式，是用于简化描述抽象算法，分类与评价数据结构，形式描述程序设计语言的类型系统。

在ADT设计时，首先要考虑对不可变类型的满足，虽然不可变类型在程序运行时会产生大量的重复信息复制，但能确保已经定义的变量不会被其他地方修改，在保障代码安全性的同时，也保障的线程安全性。其次，还需要ADT还需要具备表示独立性，因为要设计良好的数据结构，就需要考虑如何通过封装来避免用户端获取数据的内部表示，避免潜在的bug，即在client和implementer之间建立“防火墙”。

2.ADT的三个特性

① 表示泄露：保障了ADT内部表示不会被客户端其他代码任意篡改。

② 抽象函数AF：通过映射得到用户端希望的内容。

③ 表示不变量RI：对ADT内部表示进行限制，获取到希望表示的信息。

2.1 Abstraction and User-Defined Types（抽象和用户定义类型）

①除了编程语言所提供的基本数据类型和对象数据类型，用户可以定义自己的数据类型。

②数据抽象：由一组操作所刻画的数据类型。

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

 eg: An abstract data type Bool has the following operations:

2.2 Classifying Types and Operations(对类型和操作进行分类)

①可变数据类型和不可变数据类型

可变数据类型：当该数据类型的对应变量的值发生了改变，那么它对应的内存地址不发生改变，对于这种数据类型，就称可变数据类型，当可变数据类型改变时它实际上是更改了内存中的内容。

不可变数据类型：当该数据类型的对应变量的值发生了改变，那么它对应的内存地址也会发生改变，对于这种数据类型，就称不可变数据类型。其中基本数据类型都是不可变数据类型，例如int，如果一个int类型的数据发生改变，那么它指向了内存中的另一个地址，但是需要注意的是java缓存了所有-128-127的值。

String & StringBuilder

String： 不可变数据类型

StringBuilder：可变数据类型

注：对于可变数据类型在非必要的情况下尽量不要重写两个函数，对于不可变数据类型，在重写equals时一定要重写hashCode，否则若hashCode不相同不会继续比较equals.

②对抽象类型的操作进行分类

creator（构造器）: t* → T

producer（生产器）: T+, t* → T

observer（观察器）: T+, t* → t

mutator（变值器）: T+, t* → void | t | T

（T：抽象形本身；t: 其他类型）

例子：

构造器：String.valueOf(Object Obj)

生产器：String.concat() is a producer (concat: String * String -> String)

观察器：List.size() is an observer (size: List ->int)

变值器：Set.add() returns a boolean indicates whether the set was actually changed.

            Component.add()  returns the object itself

说明：

构造器：可能实现为构造函数或静态函数，作为静态方法实现的构造这通常被称为工厂方法。

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

2.3 Abstract Data Type Examples

①List： List 是Java的列表类型并且是可变的；

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

-------creator: ArrayList and ListedList constructors, Collections, singletonList

-------- productor: Collections.unmodifiabledList

-------- observer: size, get

-------- multator: add, remove, addAll, Collections.sort

2.4 Designing an Abstract Type

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

经验法则1：设计简洁.一致的操作

经验法则2：要足以支持client对数据所做的所有操作需要，且要用满足client需要的难度要低。

2.5 Representation Independence（表示独立性）

表示独立性：client使用ADT时无需考虑其内部如何实现，ADT内部表示的变化不应影响外部SPEC和客户端。例如，List提供的操作与list是否表示为数组的linked list无关。

3.总结

ADT就是定义了一些操作的集合，其中对每个操作都有明确的spec，来确保用户能够正确使用这个ADT，比如RI,AF，不变量等概念都是在实现时程序员去思考的，然后以注释的形式写进去的，不会被client看到，正是这些特征才能保证ADT是真正作为一个中介在客户端和程序员之间作为桥梁，客户通过文档了解ADT的功能去使用它，程序员通过ADT的特征去用具体的实现去表示，同时遵循这些特征才能保证ADT的对于用于用户来说是完全独立于实现的，因此这些特性是必要的。