抽象数据型(ADT)
抽象数据类型与表示独立性: 如何设计良好的抽象数据结构, 通过封 装来避免客户端获取数据的内部表示(即 "表示泄露"), 避免潜在 的 bug
ADT 的特性: 表示泄漏, 抽象函数 AF, 表示不变量 RI
基于数学的形式对 ADT 的这些核心特征进行描述并应用于设计中.
ADT 的四种操作
1)Creators(构造器):
创建某个类型的新对象,? 个创建者可能会接受? 个对象作为参数, 但是这个对象的类型不能是它创建对象对应的类型. 可能实现为构造函数或静态函数.(通常称为工厂方法)
t* -> T
例子: Integer.valueOf( )
2)Producers(生产器): 通过接受同类型的对象创建新的对象.
T+ , t* -> T
例子: String.concat( )
3)Observers(观察器): 获取抽象类型的对象然后返回一个不同类型的对象 / 值.
T+ , t* -> t
例子: List.size( ) ;
4)Mutators(变值器):
改变对象属性的方法 ,
变值器通常返回 void, 若为 void, 则必然意味着它改变了对象的某些内部状态; 当然, 也可能返回非空类型
T+ , t* -> t || T || void
例子: List.add( )
解释: T 是 ADT 本身; t 是其他类型;+ 表示这个类型可能出现一次或多次;* 表示可能出现 0 次或多次.
更多例子:
设计 ADT
设计好的 ADT, 靠 "经验法 则", 提供一组操作, 设计其行为规约 spec
原则 1: 设计简洁, 一致的操作
原则 2: 要足以支持 client 对数据所做的所有操作需要, 且 用操作满足 client 需要的难度要低
原则 3: 要么抽象, 要么具体, 不要混合 --- 要么针对抽象 设计, 要么针对具体应用的设计
表示独立性
client 使用 ADT 时无需考虑其内部如何实 现, ADT 内部表示的变化不应影响外部 spec 和客户端.
除非 ADT 的操作指明了具体的 pre 和 post-condition, 否则不能改变 ADT 的内部表示 --spec 规定了 client 和 implementer 之间的契约.
下面举例说明
首先看一个表示独立的例子,
- /** MyString represents an immutable sequence of characters. */
- public class MyString {
- //////////////////// Example of a creator operation ///////////////
- /** @param b a boolean value
- * @return string representation of b, either "true" or "false" */
- public static MyString valueOf(boolean b) { ... }
- //////////////////// Examples of observer operations ///////////////
- /** @return number of characters in this string */
- public int length() { ... }
- /** @param i character position (requires 0 <= i <string length)
- * @return character at position i */
- public char charAt(int i) { ... }
- //////////////////// Example of a producer operation ///////////////
- /** Get the substring between start (inclusive) and end (exclusive).
- * @param start starting index
- * @param end ending index. Requires 0 <= start <= end <= string length.
- * @return string consisting of charAt(start)...charAt(end-1) */
- public MyString substring(int start, int end) { ... }
- }
使用者只需要知道公共方法与规格说明, 下面是如何声明内部表示的方法, 作为一个实例变量
private char[] a;
一个可能的实现方法如下;
- public static MyString valueOf(boolean b) {
- MyString s = new MyString();
- s.a = b ? new char[] { 't', 'r', 'u', 'e' }
- : new char[] { 'f', 'a', 'l', 's', 'e' };
- return s;
- }
- public int length() {
- return a.length;
- }
- public char charAt(int i) {
- return a[i];
- }
- public MyString substring(int start, int end) {
- MyString that = new MyString();
- that.a = new char[end - start];
- System.arraycopy(this.a, start, that.a, 0, end - start);
- return that;
- }
执行以下操作后, 可以得到 snapshot diagram
因为这个数据类型是不可变的, 那么 substring 实际上没有必要真正去复制子字符串到? 个新的数组中. 它可以仅仅指向原来的 MyString 字符数组, 并且记录当前的起始位置和终? 位置.
那么另一种高效的实现如下:
此使执行相同的代码. snapshot diagram 如下:
不需要再拷贝一次 char.
不变量
不变量: 在任何时候总是 true
由 ADT 来负责其不变量, 与 client 端的任何行为无关
为什么需要不变量: 保持程序的 "正确 性", 容易发现错误
表示泄露
下面举例来说明:
- /**
- * This immutable data type represents a tweet from Twitter.
- */
- public class Tweet {
- public String author;
- public String text;
- public Date timestamp;
- /**
- * Make a Tweet.
- * @param author Twitter user who wrote the tweet
- * @param text text of the tweet
- * @param timestamp date/time when the tweet was sent
- */
- public Tweet(String author, String text, Date timestamp) {
- this.author = author;
- this.text = text;
- this.timestamp = timestamp;
- }
- }
因为变量都是 public, 所以下面的操作会直接访问到 Tweet 内部数据:
- Tweet t = new Tweet("justinbieber",
- "Thanks to all those beliebers out there inspiring me every day",
- new Date());
- t.author = "rbmllr";
这样的表示泄露不仅影响不变性, 也影响了表示独立性: 无法在不影响客户 端的情况下改变其内部表示
那么将变量都改为 private final 会怎么样呢
看下面的代码
- public class Tweet {
- private final String author;
- private final String text;
- private final Date timestamp;
- public Tweet(String author, String text, Date timestamp) {
- this.author = author;
- this.text = text;
- this.timestamp = timestamp;
- }
- /** @return Twitter user who wrote the tweet */
- public String getAuthor() {
- return author;
- }
- /** @return text of the tweet */
- public String getText() {
- return text;
- }
- /** @return date/time when the tweet was sent */
- public Date getTimestamp() {
- return timestamp;
- }
- }
在 private 和 public 关键字表明哪些字段和方法可访问时, 只在类内部还是可以从类外部访问. 所述 final 关键字还保证该变量的索引不会被更改, 对于不可变的类型来说, 就是确保了变量的值不可变.
但是上面的代码还是会有表示泄露产生, 如下面的操作:
我们画出 snap diagram 来说明
d 和 Tweet 中的 timestamp 指向相同的 Date, 但 Date 可变, d 对 Date 修改, 导致 Tweet 的 timestamp 也被修改. 这样, Tweet 的不变性就被破坏, Tweet 将自己内部对于可变对象的索引 "泄露" 了出来, 因此整个对象都变成可变的了, 使用者在使用时也容易造成隐藏的 bug.
我们可以通过防御性拷贝来解决该问题:
让 getTimestamp 返回一个新的对象实例.
即使这样, 下面的操作还会导致表示泄露
- /** @return a list of 24 inspiring tweets, one per hour today */
- public static List<Tweet> tweetEveryHourToday () {
- List<Tweet> list = new ArrayList<Tweet>();
- Date date = new Date();
- for (int i = 0; i <24; i++) {
- date.setHours(i);
- list.add(new Tweet("rbmllr", "keep it up! you can do it", date));
- }
- return list;
- }
该代码创建 24 个 Tweet 对象, 但构造时都是用相同的 date, 导致最后 24 个 Tweet 都同一时间结束, 如下图所示
所以我们对 creator 方法也做了防御性编程:
但这样的拷贝非常浪费, 但这没有办法
除非迫不得已, 否则不要把希望寄托于客户端上, ADT 有责任保证自 己的 invariants, 并避免 "表示泄露".
最好的办法就是使 用 immutable 的类型, 彻底避免表示泄露
总结:
简单来说, 一个主类有属性和方法两种成分, 这里的主类是指用户直接使用的类, 需要做到以下两点
1, 将类中所有的属性 (变量) 定义为 private 类型, 目的是不让用户得到你的内部属性
2, 方法或者返回 immutable data, 或者返回本应该返回的 mutable data 的副本, 或者返回一个不可修改的 mutable data
为了做到第二点的三个方面
1, 尽量使用 immutable 数据类型, 比如能使用 String 就不使用 StringBuilder, 能使用 Instance 就不使用 Data
2, 为了创造 mutable data 的副本, 可以进行 defensive copy. 可以在主类方法中构造然后返回, 但是推荐方法是使用 mutable 数据类型的 clone, 假如该 mutable 数据类型是自己写的类, 那么推荐在类中写一个 clone 的方法
3, 使用 Collections.unmodifiableSet 等方法这里需要注意的是第二个方面, 如果想要返回一个 Collection 类的数据, 有人说我创建了一个 Collection 类, 向里面添加数据后, 不管数据怎样, 都算 defensive copy 了, 但是如果数据是 mutable 类型, 那么就不算 defensive copy, 因为 Collection 类储存的是地址, 尽管 new 了一个 hashSet 或者 hashMap, 但是没有真正的对 mutable 数据进行 defensive copy.
抽象函数 AF 与表示不变量 RI
在研究抽象类型的时候, 先思考一下两个值域之间的关系:
表示域 (rep values) 里面包含的是值具体的实现实体. 一般情况下 ADT 的表示比较简单, 有些时候需要复杂表示.
抽象域 (A) 里面包含的则是类型设计时支持使用的值. 这些值是由表示域 "抽象 / 想象" 出来的, 也是使用者关注的.
ADT 实现者关注表示空间 R, 用户关注抽象空间 A .
R->A 的映射特点:
每一个抽象值都是由表示值映射而来 , 即满射: 每个抽象值被映射到一些 rep 值一
些抽象值是被多个表示值映射而来的, 即未必单射: 一些抽象值被映射到多个 rep 值
不是所有的表示值都能映射到抽象域中, 即未必双射: 并非所有的 rep 值都被映射.
抽象函数(AF):R 和 A 之间映射关系的函数
表示不变量(RI): 将 rep 值映射到布尔值
对于表示值 r, 当且仅当 r 被 AF 映射到了 A,RI(r)为真.
表示不变性 RI: 某个具体的 "表示" 是否是 "合法的"
也可将 RI 看作: 所有表示值的一个子集, 包含了所有合法的表示值
也可将 RI 看作: 一个条件, 描述了什么是 "合法" 的表示值
在下图中, 绿色表示的就是 RI(r)为真的部分, AF 只在这个子集上有定义.
来源: http://www.bubuko.com/infodetail-3098668.html