Java 集合 API 用例学习


第 16 讲 Java 集合 API 用例学习 如果没有完全理解 JAVA 库中的具有决定性的部分,你就不可能成为一个优秀的 JAVA 程序 员。基本类型都包含在 java.lang 中。java.util 包提供了集合(set)、列表(list)和映射 (map)等工具,你应该详细的了解它们。java.io 包也是很重要的,但是你只需要大概了解它 的内容就可以了。 在本章中,我们将探讨 java.util 的设计,而它常常被称为 java 集合 API(java ‘collections API’)。学习它是非常有价值的,这不仅是因为集合类非常的有用,而且因为 API 是一个设计非常好的代码例子。它们很容易理解,而且有很好的文档。API的代码是由 Joshua Bloch 所写,他同时还出版了我们在开始本门课程时所推荐的 Effective Java 这本书。 与此同时,几乎所有的面向对象编程的复杂问题都会在 API 的编写中出现,所以如果你认 真的学习 API,你将对自己以前编码时没有考虑过的编程问题有更广泛的理解。事实上可以毫 不夸张的讲,如果你能完全掌握一个类(例,ArrayList)是如何工作的,就可以说你已经完全 掌握 java 概念。我们没有时间探讨全部的问题,但我们将接触其中的绝大部分。他们中的一些, 例如串行化和同步,已经超过本课程的范围。 16.1 类型体系 简要的讲,API 提供三种方式的集合(collection):集合(set)、列表(list)和映射 (map)。set负责采集元素,但不包括元素的数量和顺序,每一个元素只可能在或不在一个 set 中。list 是一个元素序列,所以它包括元素的顺序和数量。map 是一个键和属性值的关联:它 有一组键,并将每个键映射到一个值上。 API 按照接口体系结构来组织它的类——各种类型的规格说明——以及一个单独的实现类 的体系。图表反映出一些选择类和接口的举例。Collection 接口抓取了 set 和 list 共有的性 质,但不包括 map,但我们将非正式地使用术语‘collections’来表示 map。SortedMap 和 SortedSet 用来为 map 和 set 提供以某种顺序取回元素的附加操作。 1 具体实现的类,例如 LinkedList,全部建立在实现框架的上部,例如他所继承的 AbstractList。这种接口和类的平行结构是一种非常重要的结构,这个非常值得学习。许多新 程序员往往在应该使用接口的时候却选择了抽象类。但通常来说,应该多使用接口而不是抽象 类。你很难通过扩展一个抽象类来更新一个存在的类(因为一个类最多只能有一个超类),但 为类实现一个新的接口就很容易。 Bloch 指出了将两种方式的优点结合在一起的方法(他的书的第 16 节:‘Prefer interfaces to abstract classes’),就是使用实现框架类,就像他在他的 API 中所做的那样。通过这种方 式,你可以得到使用基于规格说明解耦的接口的好处,同时还能得到使用抽象类来指出相关实 现中的共享代码的好处。 在 JAVA API 的文档中有每种 JAVA 接口的非正式规格说明。这点非常重要,因为他告诉每 一个实现类的某个接口的使用者通过该接口能够得到什么。例如你使用一个类,要使之符合List 的规格说明,你必须保证它还符合非正式的规格说明,否则它将无法按照程序员所期望的方式 运行。 这些规格说明基本上都不完整(如同大部分的规格说明)。具体类也有规格说明,它们中包 括若干接口规格说明的细节。例如,List 接口并没有说明 null 元素能否被储存,但 ArrayList 和 LinkedList 却明确说明 null 为非法。HashMap 允许 null 关键字和 null 属性值,而 HashTable 两者都不允许。 当你在编码的过程中用到集合类时,应该尽量通过通用接口或类来引用一个对象,例如, List p=new LinkedList(); 2 与下一种形式相比较好 LinkedList p=new LinkedList(); 如果你用前一种代码编译,你能很容易改变不同的队列实现: List p=new ArrayList(); 因为所有的代码都基于 p 是队列。而后一种你会发现很难做出改变,因为程序中的一些部 分执行只有 LinkedList 提供一些操作——事实上这些操作并不是必要的。这其中解释的详细细 节在 Bloch 的书 34 节(‘Refer to objects by their interfaces’)。 下周的 Tagger 案例学习中,我们将学习有关的更加复杂的例子,那时的代码需要访问 HashMap 的键。我们传递 Set 类型的 map 的一个视图,而不是整个 map: Set keys=map.keySet(); 现在使用键的代码并不知道这里的 set 是 map 的键的一个 set。 16.2 可供选择的方法 集合 API 允许一个类声明实现一个集合接口而不用实现它的所有方法。例如 List 的所有改 变者(mutator)s 都被指定为可选择的。这意味着你能实现一个类,它能满足 List 的规则说 明,但无论何时你调用 mutator 时它都会抛出一个 UnsupportedOperationException 异常,例 如 add 命令。 这种削弱 List 规格说明的企图是有问题的,因为这意味着如果你编写一些使用列表的代 码,在缺少有关列表的附加信息的情况下,你不知道它是否支持 add 命令。 但是没有这种可供选择操作的观念的话,你不得不声明一个单独的 ImmutableList 接口。 这将使接口数目成倍增加。有时,我们只需要某些 mutators,例如,HashMap 中的 keyset 方法 返回一个含有 map 中键的 set。这个 set 是一个视图:从 set 中删除一个键将导致从 map 中删 除一个键和与之相关的属性值。所以支持命令 remove,但不支持 add 命令,所以你不能在没有 属性值的情况下向 map 中加入一个键。 所以使用一个可供选择操作从工程角度来看是一个合理的选择。它意味着较少的编译时检 查,同时也减少了接口数量。 16.3 多态 set、list、map 这些容器都保存类型为 Object 的元素。它们被称为多态性,意为多种形 态,因为它们允许你使用不同类型的的容器:Integers 列表、URLs 列表等等。 这种方式的多态称为子类型多态,因为它依赖于类型体系。另一种不同多态称为参数多态, 它允许你定义容器时使用类型参数,所以客户端能够指示一个具体的容器能够包含什么类型的 元素: List[URL]bookmarks; //在 Java 中是不合法的 尽管已经有许多增加此种多态的提议,但 JAVA 中没有这种多态。参数多态的最大优点是程 序员可以告诉编译器元素的类型。编译器就可以发现那些插入了的类型错误的元素,或者提取 时被当作另一种类型的元素。 在子类型多态的情况下,必须显示指明取出的元素的类型,考虑下面代码: List bookmarks=new LinkedList(); URL u=.... 3 Bookmarks.add(u); ... URL x=bookmarks.get(0);//不能通过编译 因为 add 方法需要一个 Object 作为参数,而 URL 是 Object 的子类,所以 add u 是可以通 过的。而gets x 语句却不能通过,因为RHS 的表达式的类型是 Object,而你不能用一个 Object 给一个 URL 赋值,所以你不能靠这种变量来保存 URL。因此,在这里我们需要使用一个向下造 型(downcast),并用以下代码代替原代码: Url x=(URL)bookmarks.get; downcast 的效果就是在运行时进行检查。如果成功,调用这种方法将返回一个 URL 类型, 程序继续正常运行。如果失败,因为结果不是正确类型,将抛出一个 ClassCastException 异常, 任务将不被执行。一定要确保你明白这点,不要对 cast 如何修改返回的对象感到迷惑(学生常 常是这样的)。对象在运行时带动它的类型,如果一个对象由 URL 的构造器创建,它将含有这种 类型,所以在此不用强制改变而赋予它此种类型。 这种 downcast 比较让人讨厌,有时你必须写一个包装类从而将它们剔除。在浏览器中,你 常常想得到一个特殊的应用于书签列表的抽象数据类型。如果你要这么做,则需要在抽象类型 中使用 cast,而客户端将看到的方法如下: URL getURL(int i); 在它们的调用的上下文中不要求 cast,因此限制了 cast 错误可能发生的范围。 子类型多态给出许多参数多态中没有的灵活性。你可以建立一个异种的容器,这个容器可 以储存各种不同的元素。甚至可以使用该容器来保存它自己——尝试找出怎样表达这种多态类 型——即使这不是一个明智的做法。事实上,正如我们早先在‘相等’课程中提到的,如果你 这么做的话,JAVA API 类将崩溃。 写出一个元素、容器有什么类型常常是一个抽象类型的表示不变式种最重要的部分,你应该养 成在声明容器的同时写下注释的习惯,或者使用伪参数(pseudo-parametric)类型声明 List bookmarks;//List[URl] 或者作为表示不变式的一部分: RI:bookmarks.elems in URL 16.4 框架的实现 集合的具体实现构造于框架实现之上,通常使用模板方法(template method)设计模式(查 看 Gamma et al, 325-330 页)。一个抽象类没有自己的实例变量,但定义‘模板方法’它能够 调用其它声明为抽象而不包含任何代码的钩子方法(hook method)。在继承的子类中,钩子方 法被重载,而模板方法则被无改变的继承。 例如 AbstractList,将 iterator 作为一个模板方法,返回一个将 get 方法作为钩子来实 现的 iterator。equals 方法是 iterator 的另一个模板实现。一个子类,例如 ArrayList,它 为 get(比如取出数组中的第 i 个元素)提供一个表示(例如一个元素数组)和一个实现,并 且可以继承 iterator 和 equals。 一些具体的类替换了抽象实现。例如 LinkedList 取代了 iterator 的作用,因为可以直接 使用列表条目的表示,就可以写一个比使用钩子方法 get 更高效的遍历,它对每个调用执行一 次顺序搜索。 4 16.5 容量、空间分配和垃圾回收 一个使用数组作为它的表示的实现——例如 ArrayList 或 HashMap——当为它分配空间的 时候必须指定数组的大小。选择一个合适的大小对于性能的提升很重要。如果太小,原数组就 不得不被一个新队列取代, 从而导致生成新数组和回收旧数组的开销。如果太大,空间会被浪 费,当有许多集合类型实例时这将是一个大问题。 因此这种实现提供客户端可以设置初始容量的构造器,通过它可以决定分配空间的大小。 例如 ArrayList 有如下构造器: Public ArrayList(int initialCapacity) 按指定初始容量创建一个空列表 Parameters: initialCapacity-列表的初始容量 Throws: IllegalArgumentException-如果指定的初始容量不合法 还有可以自适应容量的方法:trimTosize,它有将容器的容量设置为恰好能够存储当前存 储的元素,ensureCapacity,它为给定的数量增加空间。 使用容量功能是有技巧的。如果你不知道特定的应用需要多大的容量,你可以使用一个 profiler 来得到它。 注意,这种容量的概念将一个行为问题转化为一个性能问题——这正是我们所需要的转换。 在许多旧的程序中,它们固定限制资源,如果资源用尽,程序也就无法运行。而使用这种基于 容量的方法,资源耗尽仅仅导致程序运行速度变慢。这对于设计程序是一个好的想法,因此它 通常能够有效的运行,即使有性能要求时也一样。 如果你学习 ArryList 中 remove 的实现,你将看到如下代码: Public Object remove(int index){ ... elementData[-size]=null;//让 gc 完成它的工作 ... 接下来是什么?不是无效资源自动回收吗?这是新手常犯的错误。如果在你的表示中有一 个数组,有一个单独的实例变量保存一个指示数组的那个元素被认为是抽象集合一部分的目录, 你常常会认为只需要去掉这个目录就可以移除所有的元素。一个抽象函数的的分析可以解决这 个疑惑:目录中的元素并不能认为是抽象集合的一部分,而且它们的值是不相关的。 但是还有一个障碍。如果没有将 null 赋给没有使用的槽(slot),就算程序中没有任何别 的地方引用那些元素,那些被 slot 引用的元素也不能被回收。垃圾回收器并不理解抽象函数, 因此它不知道实际上那些元素并不能通过集合访问,尽管可以通过表示访问它们。如果你忘记 了对这些 slot 置空,你的程序的性能必将大大下降。 16.6 复制、转化、包装等 所有具体集合类都提供以集合作为参数的构建器。这允许你赋值集合,或是将一个集合转 换为另一类型的集合,例如 LinkedList 有以下构造器: Public LinkedList(Collection c) 构建一个包含指定集合元素的列表,按照该集合迭代器返回的顺序保存这些元素。 Parameters: 5 c-将要保存在该列表中的集合。 可以用它来复制: List p=new LinkedList() ... List pCopy=new LinkedList(p) 由其它类型创建一个链表: Set s=new HashSet() ... List p=new Linked list(s) 构造器不能在接口中声明,List 的规格说明并没有说它所有的实现都应该有这样的构造器, 但是实际上是这样的。 Java.util.Collections 是一个特殊类,它包含一系列对集合操作或返回集合的静态方法。 其中的一些是一般的算法(比如排序算法),一些是包装。例如,unmodifiableList 方法以一 个列表为参数,并返回具有同样元素一个列表,但它是不可改变的。 Public static List unmodifiableList(List list) 返回一个指定列表的不可变的视图。这个方法允许为用户提供对内部列表的‘只读’访 问。尝试修改返回列表的操作都将导致抛出一个 UnsupportedOperationException 异常。 如果指定的列表是可串行化的,那么返回的列表也将是可串行化的。 Parameters: list-将返回它的一个不可改变的视图的列表。 Returns: 指定列表的一个不可改变的视图。 返回的列表并不是严格的不可变,它的属性值可能因为原列表值的改变而改变(参考下面 的 16.8 节),但它不能被直接修改。还有类似的以集合为参数并返回同步的包装的版本方法。 16.7 有序集合 一个有序集合必须有比较元素来决定它们顺序的方法。集合 API 对此提供两种方法。可以 使用‘自然排序’(natural ordering),它由 java.lang.Comparable 接口的 compareTo 方法对 不同类型元素的比较决定: Public int compareTo(Object 0) 它根据该对象小于、等于或大于给定对象 o 返回一个负整数、0 或正整数。当你给一个使 用自然排序的集合中添加元素时,元素必须构建在一个实现了 Comparable 接口的类中。Add 方 法将给定的元素向下 cast 成 Comparable 从而与集合中的元素进行比较,如果它不匹配,将抛 出一个 class cast 异常。 你还能使用一个与元素无关的排序,使用一个实现了具有下面方法的 java.util.Comparator 接口的对象: Public int compare(Object o1,Object o2) 上式与 compareTo 类似,但使用两个要进行比较的元素作为参数。这是一个策略(Strategy) 模式的例证,在它里面,算法从使用它的代码中解耦出来(参阅 Gamma,315-323 页)。 方法的选用取决于用来创建集合对象的构造器的选取。如果你使用以比较(Comparator) 为参数的构造器,将使用它来决定顺序。如果你使用不带参数的构造器,会使用自然排序。 6 比较面临与我们在第九课里面已经详细讨论过的相等的同样的问题。一个有序集合有一个 表示有序的表示不变式。如果通过一个公有方法调用改变一个元素将改变两个元素的属性,那 么将会发生表示暴露。 16.8 视图 我们在第九章介绍了视图的概念,视图是一种复杂的机制,现在和以后它将是非常有用的, 但却很危险。它们打破了许多我们有关于设计良好面向对象程序中应有的行为。 通过它们的使用目的,可以定义三种视图: z 功能扩展。一些视图提供对象功能的扩展而不用外加新的方法。迭代器属于这个范畴。 它可以代替采集类中的 next 和 hasNext 方法。但这使类的 API 更复杂。它同样难以支 持同一接口的多个迭代。我们能给类加入一个重置方法,这个方法用来重新启动迭代, 但这将导致一次只允许一个迭代。如果程序员忘记重置,这类方法将导致错误。 z 解耦。某些视图提供集合功能的一个子集。例如 Map 上的 KeySet 方法,返回一个由 map 的键组成的 set。因此允许代码中只与键相关的那部分从 Map 的规格说明中解耦出来。 z 坐标转换。List 的 subList 方法提供的视图给出了一种坐标转换。视图上的改变将导 致相应列表的改变,而允许通过一个目录访问这个列表,这目录是传递倒 subList 方 法的参数的一个偏移。 说视图危险有两个原因。首先,看不到的改变:在一个迭代器上调用 remove 将使它对应的 集合改变;对一个 map 调用 remove 则它的键 set 视图也会改变(反之亦然)。这会形成抽象别 名,从而使得一个对象的改变影响另一个对象。两个对象并不需要相同的字典范围。这意味着 我们在规格说明中的改变语句必须重新定义:如果你改变 c 而 c 有视图 v,这是否意味着 v 也 能被改变? 其次,返回视图的方法的规格说明常常限制允许的改变的类型。为了确保你的代码能够运 行,你必须理解这个规格说明。而这些规格说明常常是很难懂的。Liskov 的文章中的后置要求 是一个扩展我们的规格说明来处理这种复杂性的方法。 一些视图只允许相应的集合被改变。其它则只允许视图被改变——例如迭代器。而有些允 许视图和集合都改变,但这将导致改变的约束变复杂。例如集合 API,当列表有一个子列表视 图时,相应的列表不能有任何结构的改变:下面间接的对其进行解释: 结构改变就是那些改变列表大小或者类似方式的使得迭代器可能产生错误结果的改变。 它的意思并不十分准确清晰。我倾向于底层的列表不做任何改变。 同一底层集合的多个视图将使情况更复杂。例如你能对同一列表中使用多个迭代器。在这 种情况下,你必须考虑与视图间的交互。如果你通过某些迭代器改变了列表,则其它的迭代器 将变为无效,也就不能再使用了。 这里有一些有用的转移视图复杂度的方法,如果使用视图,你必须考虑清楚到底哪种对你 是有帮助的: z 你可以限制视图所能接受的范围。例如对迭代器使用 for-loop 循环而不是 while-loop 循环,你能限制迭代器对于循环的声明。这可以保证在迭代期间不发生一些意外的交 互。这种方法不一定总是可行的,我们下周将要讨论的 Tagger 程序中,我们将改变迭 代器的多个方法。 z 你能使用 Collections 类的一个方法来包装一个视图或者底层对象,从而阻止它们的 改变。例如,你为一个 map 建立了一个 KeySet 视图,并且不准备改变它,你可以使用 7 以下方式将之设置为不可变: Set s = map.keySey(); Set safe_s = Collections.unmodifiableSet(s); 8
还剩7页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 15 金币 [ 分享pdf获得金币 ] 2 人已下载

下载pdf

pdf贡献者

hacker_zxf

贡献于2012-01-18

下载需要 15 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf