java集合框架.doc

翻译：陈磊参考：官方文档Java集合框架1集合介绍11.1 什么是集合框架11.2 Java集合框架的优点22接口22.1 Collection接口32.1.1 遍历集合42.1.2 集合接口容量操作52.1.3 集合接口数组操作62.2 Set接口62.2.1 Set接口基础操作72.2.2 Set接口容量操作82.2.3 Set接口数组操作92.3 List接口92.3.1 比较vector102.3.2 集合操作112.3.3 位置访问和搜索112.3.4 迭代器122.3.5 范围视图操作142.3.6 List算法162.4 Queue接口163实现171 集合介绍一个集合-也叫容器-是将多个元素组装成一个单元的简单对象。集合被用来存储、检索、操纵、传送多个数据。尤其是，它用自然组表示数据集合，像一副扑克牌、一个邮件夹、一个电话薄。1.1 什么是集合框架集合框架是表示集合和操纵集合的统一结构。所有的集合框架包含：接口：代表集合的抽象数据类型。接口允许集合有统一的操作，而不用考虑细节。在面向对象语言中，通常用接口形成层次结构。实现：接口的具体实现。本质上，也是可重用的数据结构。算法：实现了集合接口的对象的、例如，搜索和排序等执行有效计算的方法。算法是多态的：同养的方法能在很多集合接口的实现中使用。本质上，算法是可重用功能。除了java集合框架，还有C+ Standard Template Library (STL)和Smalltalk的集合层级。以前，集合框架相当复杂，以至于被认为是难以学习的。我们相信，java集合框架打破了这个传说，你可以通过本文自学。1.2 Java集合框架的优点Java集合框架有以下优点：减少编程工作：通过提供数据结构和算法，集合框架让你专注于程序的重要部分，而不是专注于建设低级结构（plumbing）。通过促进无关API之间影响，java集合框架使你免于编写适配对象或者转码去联接API。增加程序的速度和质量：集合框架提供高性能、高质质量的数据结构和算法的实现。每个接口有各种实现供选择，程序可以被简单的调优通过选择集合实现。因为你从写自己的数据结构的苦力中解放，你有很多时间致力于改善程序质量和性能。允许无关API之间的交互：集合接口通过本地API来回传递集合。如果我的网络管理API提供一个节点名集合，同时如果你的GUI工具期望一个列头集合，我们的API将无缝交互，甚至它们是独立开发的。减少学习使用新API的工作：很多API自然地提供输入集合和提供集合输出。过去，每个API有一个子API，用来操作它的集合，这些子APi没有什么一致性，需要从头学，很容易犯错。集合框架的出现，解决了这个问题。减少设计新API的工作：这个是 以前优势的另一面。设计值和实现者不必每次都为自己的集合设计方法，而是使用标准集合接口。软件重用：符合标准集合接口的新数据结构被自然重用。新的算法也同样。2 接口“核心集合接口”包含了不同类型的集合，如下图。这些接口允许独立实现细节之外操作这些集合。核心集合接口java集合框架的基础。Set是集合的一种类型，SortedSet是Set的一种类型，以此类推。注意，集合是两个树组成的，-Map不是真正地集合。注意，所有的核心集合接口是泛型的，例如，看Collection接口的声明。public interface Collection语法告诉你接口是泛型的。当你声明一个集合实例，你可以也应该指定集合中的对象类型。指定类型允许编译器核实（编译时）放进集合的对象类型是对的。在运行时能减少错误。关于泛型请看Generics (Updated)当你了解怎么使用这些接口，你同时也了解了java集合框架。这章讨论有效使用接口的一般指南，包括什么时候使用哪个接口。你还将学到每个接口的程序设计，帮助你了解它。为了保持核心集合框架可管理，java平台不为每个接口类型的每个变体提供分离的接口。（变体可能包括不可变、固定大小(fixed-size)、只添加(append-only)），这样，每个接口的修改操作是指定的选项-具体实现可以不支持所有操作。如果一个不支持操作被调用，集合抛出一个UnsupportedOperationException。实现对于支持的操作时可靠的。java平台的所有general-purpose实现支持所有可选操作。下面列出核心集合接口的描述：Collection 集合结构的root接口。一个集合代表一些元素对象的组合。Collection接口是所有集合的最小共同标准，是用来传递集合同时使用集合的共性操作。有些类型的集合允许重复元素，有些不允许，有些是有序的，有些不是有序的。java平台不提供这个接口的直接实现，而是提供了它的一些特殊的子接口，像Set和List。Set 一个不包含重复元素的的集合。这个借口模型是精确的set抽象，用来代表sets，例如扑克牌卡片，学生的课程，或者机器上运行的程序。List 一个有序集合，List可以有重复元素。可以精确控制每个元素的插入位置，通过序号访问元素。如果你使用过vector，你已经了解了List的使用方式。Queue 一个用来在处理之前持有一些对象的集合。除了基本的Collection的操作职位，还提供了额外的添加、抽取、查看操作。Queue很特殊，但不是必要的。FIFO方式管理元素。异常使用优先队列，通过提供的比较器排序或者自然顺序。无论怎么排序，队列的第一个元素首先被移除，通过remove或者poll。在FIFO队列中，所有实现必须执行排序属性。Map 从key到value的映射对象。Map不能包含重复key；每个key只能对应一个value。如果你使用过Hashtable，你已经熟悉了Map的基本使用方式。下面两个核心接口仅仅是Set和Map的有序版本SortedSet 保持它的元素升序排序的Set。提供了几个体现排序优势的附加操作。Sorted 集合通常用于自然顺序集合，像单词列表和会员清单SortedMap 保证key升序的map。Sortedmap被用作自然顺序key value集合，像字典和电话本。要了解排序接口如何保持元素顺序，看Objet Ordering一章。2.1 Collection接口Collection表示一组叫做元素的对象。Collection接口被用来传递对象集合。例如，按照惯例，所有一般目的(general-purpose)集合有一个接收Collection类型参数的构造方法。这个构造方法被叫做“转换构造”，它初始化当前集合，并包含这个参数的元素，无论这个参数给定collection的子接口或者实现。即，允许你转换集合类型。假设，例如，你有一个Collection c，它可能是List 、Set、或者其他。下面的实例创建一个ArrayList（List接口的一个实现），初始化包含c的所有元素。List list = new ArrayList(c);下面是Collection接口：public interface Collection extends Iterable / Basic operations int size(); boolean isEmpty(); boolean contains(Object element); / optional boolean add(E element); / optional boolean remove(Object element); Iterator iterator(); / Bulk operations boolean containsAll(Collection c); / optional boolean addAll(Collection c); / optional boolean removeAll(Collection c); / optional boolean retainAll(Collection c); / optional void clear(); / Array operations Object toArray(); T toArray(T a);这个接口处理你给定的集合，这个接口有告诉你元素个数的方法（size，isEmpty），检查给定对象是否在集合里（contains），添加和移除元素（add，remove），提供迭代（iterator）。add方法是通过的，对于可重复集合和不可重复集合是一样适用的。它保证调用完成之后集合包含制定元素，如果集合改变返回true。相似的，remove用来删除一个元素，假设集合包含要删除的元素，集合被改变返回true。2.1.1 遍历集合有两个方法：（1）使用for-each结构，（2）使用Iterators2.1.1.1 for-each结构for-each简明的遍历集合或者数组。下面的代码使用for-each，打印集合每个元素。2.1.1.2 IteratorsIterator是遍历集合的对象，若需要，可以简单地从集合移除元素。调用集合的iterator方法获得Iterator。下面是Iterator接口。public interface Iterator boolean hasNext(); E next(); void remove(); /optionalhasNext方法返回true，如果还有元素没有迭代，nexe方法返回迭代的下一个元素。remove方法移除当前集合的next方法返回的最后一个元素。remove方法每次只能调用一次，不然抛出异常。使用Iterator当你需要：l 移除当前元素，for-each不能调用remove。因此，for-each接口不能过滤。l 并行的迭代多个集合下面的方法展示如何使用Iterator过滤任意集合-遍历集合移除制定元素。static void filter(Collection c) for (Iterator it = c.iterator(); it.hasNext(); ) if (!cond(it.next() it.remove();这个简单代码多态的，它处理任意集合类型。这个例子证明使用java集合框架写一个多态 算法是多么简单。2.1.2 集合接口容量操作“容量操作”在整个集合上操作。你可以使用这些基础操作实现快速的操作，虽然大多数情况这些实现是低效的。下面是容量操作：l containsAll 如果集合包含指定集合的所有元素，返回truel addAll 把指定集合的元素全部加到集合里l removeAll 移除集合中的、同时在指定集合中的元素。l retainAll 移除不包含在指定集合中的元素。即，只保留和制定集合中的元素一致的元素。l clear 移除所有元素。addAll、 removeAll、 retainAll方法如果集合被修改返回true。看下面的例子，从集合c删除所有指定元素。c.removeAll(Collections.singleton(e);假设你想移除所有nullc.removeAll(Collections.singleton(null);这个例子用户Collections.singleton，这个静态工厂方法立即返回包含制定元素的不可变Set。2.1.3 集合接口数组操作toArray方法在旧API和集合之间建立了桥接，输出一个数组。数组操作允许集合内存转换成数组。无参数地简单创建一个数组对象。更复杂的形式允许调用者提供一个数组，或者选择输出数组的运行时类型。例如，假设c是集合，下面的片段表示c的内容转储到长度和c一致的新数组对象。Object a = c.toArray();假设c只包含String(或者因为c是Collection类型)，接下来片段将c转储到新分配的String数组String a = c.toArray(new String(0)2.2 Set接口一个Set是一个不含有重复元素的Collection。它模拟精确set抽象。Set接口只含有Collection遗传方法和对重复元素添加的限制方法。Set对equals和hashCode操作行为有很大联系，允许Set实例被有意义的比较，即使他们的实现类型不同。如果两个Set含有同样的元素，那么他们相等。下面是Set接口：public interface Set extends Collection / Basic operations int size(); boolean isEmpty(); boolean contains(Object element); / optional boolean add(E element); / optional boolean remove(Object element); Iterator iterator(); / Bulk operations boolean containsAll(Collection c); / optional boolean addAll(Collection c); / optional boolean removeAll(Collection c); / optional boolean retainAll(Collection c); / optional void clear(); / Array Operations Object toArray(); T toArray(T a);java平台包含三个一般目的Set实现：HashSet, TreeSet,和LinkedHashSet。HashSet将它的元素存储到哈希表，是最佳性能实现；但是它不保证迭代顺序。TreeSet将它的元素存储到红黑树，基于值排序；它本质上被HashSet慢。LinkedHashSet被实现成贯穿了链表的哈希表，基于插入顺序排列值。（LinkedHashSet spares its clients from the unspecified, generally chaotic ordering provided by HashSet at a cost that is only slightly higher）。这是一个简单有用的Set例子，假设你有一个Collection c，你想创建一个集合包含c的元素，但是不重复。Collection noDups = new HashSet(c);它依靠Set工作（按照定义，不包含重复），初始包含c所有元素。它使用了Collection接口一章中提到的“标准转换构造器”。这是一个稍稍不同的例子，它保存集合原始顺序而移除重复元素。Collection noDups = new LinkedHashSet(c);下面的泛型方法，封装了前面的例子，返回与传递参数类型一样的Set。public static Set removeDups(Collection c) return new LinkedHashSet(c);2.2.1 Set接口基础操作size方法返回它的元素个数（它的基数）。isEmpty方法按照字面意思就是空判断。add方法添加一个指定元素当这个元素不存在，返回布尔值表示是否添加。相似地，remove方法移除一个指定元素如果这个元素存在，返回布尔值表示是否移除。iteraator方法返回Set的Iterator对象。下面的程序拿到参数中的单词，打印重复单词，去掉重复之后单词和个数。import java.util.*;public class FindDups public static void main(String args) Set s = new HashSet(); for (String a : args) if (!s.add(a) System.out.println(Duplicate detected: + a); System.out.println(s.size() + distinct words: + s); 运行：java FindDups i came i saw i left输出：Duplicate detected: iDuplicate detected: i4 distinct words: i, left, saw, came注意集合类型是Set，强烈建议保持这个编码习惯，因为这样可以灵活的改变实现。如果存储集合的变量或者传递集合的参数是实现类型，那么实现类型改变这个参数或者变量就要被改变。此外，接口类型可以统一调用方法，而避免使用实现的特殊方法。如果上面的例子想要打印结果按照字母顺序打印，那么就要使用TreeSet。下面是输出结果：java FindDups i came i saw i leftDuplicate detected: iDuplicate detected: i4 distinct words: came, i, left, saw2.2.2 Set接口容量操作容量操作很适用于Set；当使用时，执行标准集合算法（set-algebraic）操作。假设s1和s2是集合。容量操作:l s1.containsAll(s2)如果s2是s1子集合返回true。l s1.addAll(s2)s1转换成s1和s2的合集。l s1.retainAll(s2)s1转换成s1和s2的交集。l s1.removeAll(s2)s1转换成s1中有但是s2中没有的（非对称）要计算合集，交集，或者差集而不改变两个集合，那么调用容量操作之前必须复制一个集合。看下面的例子：Set union = new HashSet(s1);union.addAll(s2);Set intersection = new HashSet(s1);intersection.retainAll(s2);Set difference = new HashSet(s1);difference.removeAll(s2);上面的例子的类型是HashSet，前面提到，它是java平台最好的全面的Set实现。也可以用其他一般目的实现Set代替。让我们回顾FindDups程序。假设你想要知道参数中哪些单词是唯一的，哪些不是，而且你不想任何重复被打印。通过两个集合实现，一个存储所有参数，一个存储重复的参数，两个集合差就是出现一次的单词。import java.util.*;public class FindDups2 public static void main(String args) Set uniques = new HashSet(); Set dups = new HashSet(); for (String a : args) if (!uniques.add(a) dups.add(a); / 差集 uniques.removeAll(dups); System.out.println(Unique words: + uniques); System.out.println(Duplicate words: + dups); 输入：I came I saw I left输出：Unique words: left, saw, cameDuplicate words: i一个特殊的集合算法是：集合对称差（包含两个集合的元素，但不同时在两个集合里）。下面代码实现了集合对称差：Set symmetricDiff = new HashSet(s1);symmetricDiff.addAll(s2);Set tmp = new HashSet(s1);tmp.retainAll(s2);symmetricDiff.removeAll(tmp);2.2.3 Set接口数组操作Set接口的数组集合和其他集合一样，见集合接口一章。2.3 List接口List是一个有序集合（也叫序列）。Lists可以包含重复元素。除了遗传方法，List包含：位置访问(Positional access) 基于元素在list中的数字位置操作它。搜索(Search) 搜索指定对象，返回它的数字位置。迭代(Iteration) 利用list的顺序特点扩展迭代。范围查看(Range-view ) 对list进行任意范围操作。List接口：public interface List extends Collection / Positional access E get(int index); / optional E set(int index, E element); / optional boolean add(E element); / optional void add(int index, E element); / optional E remove(int index); / optional boolean addAll(int index, Collection c); / Search int indexOf(Object o); int lastIndexOf(Object o); / Iteration ListIterator listIterator(); ListIterator listIterator(int index); / Range-view List subList(int from, int to);java平台包含两个List一般实现。ArrayList，最佳执行实现，和LinkedList，在某些情况下最佳性能。当然Vector已经被翻新实现List2.3.1 比较vector如果你已经使用过vector，你已经熟悉了List的基础知识。（当然，List是接口，vector是具体实现。）List修复了Vector中的一些次要API缺陷。通常使用Vector，像elementAt和setElementAt，已经给出了更短的名字。当你用这两个操作模拟数组，更短的名字才好。看下面的语句：ai = aj.times(ak);Vector等价操作是：v.setElementAt(v.elementAt(j).times(v.elementAt(k), i);List等价操作是：v.set(i, v.get(j).times(v.get(k);你可能注意到set方法代替Vector的SetElement，调换了参数顺序来匹配数组操作：gift5 = golden rings;Vector等价操作：gift.setElementAt(golden rings, 5);List等价操作：gift.set(5, golden rings);为了一致性的目的，方法add代替insertElementAt(Object, int)，同时调换了参数顺序。vector的三个范围操作（indexOf， lastIndexOf， setSize）已经被一个单独的范围访问操作（subList）替换，这个方法更强大和一致。2.3.2 集合操作继承全部自Collection的方法。remove操作总是删除指定的第一次出现的元素（从左到右）add和addAll操作总是添加到list的尾部。下面的例子是list联接。list1.addAll(list2);上面例子的无破坏性例子，两个list组成第三个list。List list3 = new ArrayList(list1);list3.addAll(list2);注意这个例子，是非破坏性形式，利用ArrayList的标准转换构造器。类似Set接口，List加强对equals和hashCode方法的要求，因此两个List对象可以逻辑比较，而不用关心他们的实现。当两个List元素相同，顺序相同，则相等。2.3.3 位置访问和搜索基本位置访问操作（get，set，add，remove）相对于vector（elementAt，setElement，insertElement）的一个值得注意的地方是：set和remove操作返回值被重写或者删除；Vector对应没有返回。搜索操作indexOf和lastIndexOf和vector同名方法一样。addAll操作将指定集合的指定位置的所有元素插入。顺序是指定集合的迭代顺序。下面是模拟addAll的位置访问：public static void swap(List a, int i, int j) E tmp = a.get(i); a.set(i, a.get(j); a.set(j, tmp);当然，有一个大不同。这是一个多态算法：它交换任意List的两个元素，不管实现类型。下面是另一个使用swap的多态算法。public static void shuffle(List list, Random rnd) for (int i = list.size(); i 1; i-) swap(list, i - 1, rnd.nextInt(i);这是java平台的Collecions类中的算法，随机交换指定list指定随机源。这优点微妙：从list的尾部开始，重复交换一个随机选择元素导当前位置。不像大多数纯粹为了混排，它是公平（所有排列可能性是平等的，如果随机源是公正的）、快速（恰好需要list.size()-1次交换）的。下面的程序使用这个算法随机打印参数。import java.util.*;public class Shuffle public static void main(String args) List list = new ArrayList(); for (String a : args) list.add(a); Collections.shuffle(list, new Random(); System.out.println(list); 事实上，这个程序可以更短更快，Arrays类有个assList方法，允许array转成List。这个方法不复制数组。List变化成数组，或者相反。结果不是一个一般实现目的List，因为它没有实现add和remove操作：数组是不可变的。利用Arrays.asList，调用shuffle的库版本，使用默认随机源，得到和上面一样行为的程序：import java.util.*;public class Shuffle public static void main(String args) List list = Arrays.asList(args); Collections.shuffle(list); System.out.println(list); 2.3.4 迭代器正如你预料的，List的iterator返回迭代器，它按照一定顺序返回元素。List也提供了一个强大的迭代器，叫ListIterator，允许从两个方向遍历list，遍历的同时可以修改，还可以获取当前的迭代位置。ListIterator接口如下：public interface ListIterator extends Iterator boolean hasNext(); E next(); boolean hasPrevious(); E previous(); int nextIndex(); int previousIndex(); void remove(); /optional void set(E e); /optional void add(E e); /optionalhasNext, next remove方法继承自Iterator。hasPrevious和previous对应hasNext next。前面两个方法涉及当前元素的前一个，后面的两个方法涉及游标的后面元素。previous将游标向上一个移动，next将游标向下一个移动。下面是逆序迭代的标准程序：for (ListIterator it = list.listIterator(list.size(); it.hasPrevious(); ) Type t = it.previous(); .注意上面迭代器的参数。List接口有两个形式的listIterator方法。一个是无参的返回list开头的迭代器；一个是有参的返回参数指定位置的迭代器。next返回的是当前这个元素，previous返回的是index-1的元素。长度n的list，有n+1个索引值，从0到n。直观的说，索引总是在两个元素中间，一个元素调用previous返回，一个元素调用next返回。n+1个索引对应元素的n+1个空挡，从首个元素的前面到最后一个元素的后面。下面展示了4个元素的5个索引位置。可以混合调用next和previous，但是你不得不小心。第一次调用previous和最后一次调用next是返回同一个元素。相似地，第一次调用next和顺序调用previous的最后一次返回同一个元素。所以不用奇怪，nextIndex返回的索引是下一次调用next返回元素的下标，而previousIndex返回的索引时下一次调用previous返回元素的下标。这两个方法可以报告要找到元素的位置或者利用这个位置从新创建ListIterator迭代器。也不用奇怪，nextIndex返回值总是比previousIndex大。这意味着，两个分界行为：（1），访问第一个元素时，previusIndex返回-1，（2），访问最后一个元素时nextIndex返回list.size()。结合上面所述，List.indexOf的实现可能是：public int indexOf(E e) for (ListIterator it = listIterator(); it.hasNext(); ) if (e = null ? it.next() = null : e.equals(it.next() return it.previousIndex(); / Element not found return -1;注意indexOf返回it.previousIndex(),即使是正向遍历。原因是it.nextIndex()返回的是将要遍历的元素索引，而我们想要返回我们正在遍历的元素。Iterator集合提供remove操作来删除next的最新一个元素。而ListIterator删除next和previous的最新一个元素。ListIterator提供两个修改list的附加操作set和add。set方法覆盖next或者previous的最新一个元素。下面的多态算法替换所有指定元素到新元素：public static void replace(List list, E val, E newVal) for (ListIterator it = list.listIterator(); it.hasNext(); ) if (val = null ? it.next() = null : val.equals(it.next() it.set(newVal);add方法在当前位置之前立即插入一个新元素。下面的算法用一个集合替换一个元素。public static void replace(List list, E val, List newVals) for (ListIterator it = list.listIterator(); it.hasNext(); ) if (val = null ? it.next() = null : val.equals(it.next() it.remove(); for (E e : newVals) it.add(e); 2.3.5 范围视图操作范围操作，subList(int fromIndex, int toIndex),返回索引范围是fromIndex（包括）到toIndex（不包括）的list。这种半开区间（half-open range）和循环体类似：for (int i = fromIndex; i toIndex; i+) .视图（view）这个术语意思是，List调用subList返回的list就是视图，就是说后者映射到前者上。这个方法消除了直接的范围操作（译者：这里是说返回的list不是一个新的list，是一个特殊的list类型-subList，可以看jdk源码）。任何想要对list的一部分进行操作都可以调用subList。例如下面的例子，删除范围的元素：list.subList(fromIndex, toIndex).clear();类似地例子在一个范围内搜索：int i = list.subList(fromIndex, toIndex).indexOf(o);int j = list.subList(fromIndex, toIndex).lastIndexOf(o);注意上面的例子，返回subList的位置，而不是List的位置。任何list的多态算法都可以在subList上执行。下面是一个多态算法，实现使用subList（deal a hand from a deck？）。返回一个新的List（hand）包含list（deck）的指定数量的元素。返回的元素被删除。public static List dealHand(List deck, int n) int deckSize = deck.size(); List handView = deck.subList(deckSize - n, deckSize); List hand = new ArrayList(handView); handView.clear(); return hand;注意，这个算法从deck的末尾返回。以为很多一般List实现，例如ArrayList，从尾部删除要比从开始删除性能好很多。接下来的程序使用dealHand方法结合Collecions.shuffle方法形成52张牌中的一手。程序接收两个命令行参数：（1）牌的个数（2）每手牌的个数。import java.util.*;public class Deal public static void main(String args) if (args.length 2) System.out.println(Usage: Deal hands cards); return; int numHands = Integer.parseInt(args0); int cardsPerHand = Integer.parseInt(args1); / Make a normal 52-card deck. String suit = new String spades, hearts, diamonds, clubs ; String rank = new String ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, jack, queen, king ; List deck = new ArrayList(); for (int i = 0; i suit.length; i+) for (int j = 0; j deck.size() System.out.println(Not enough cards.); return; for (int i = 0; i numHands; i+) System.out.println(dealHand(deck, cardsPerHand); public static List dealHand(List deck, int n) int deckSize = deck.size(); List handView = deck.subList(deckSize - n, deckSize); List hand = new ArrayList(handView); handView.clear(); return hand; 执行，输出：% java Deal 4 58 of hearts, jack of spades, 3 of spades, 4 of spades, king of diamonds4 of diamonds, ace of clubs, 6 of clubs, jack of hearts, queen of hearts7 of spades, 5 of spades, 2 of diamonds, queen of diamonds, 9 of clubs8 of spades, 6 of diamonds, ace of spades, 3 of hearts, ace of hearts虽然subList相当强大，但是必须小心使用它。如果对调用subList的list做add和remove操作，那么返回的subList将变的不明确。因此，强烈建议“短暂的使用”subList做范围操作。你使用返回su