第22章Introduction to Java Programming,EJava集合框架学习目标·描述Java集合框架的层次体系结构（22.1~22.2节）。·使用Co11ection接口中定义的通用方法来操作规则集和线性表（22.3节）。?使用Iterator接口来遍历一个集合（22.4节）。·使用for-each循环简化对集合的遍历（22.4节）。·探究如何使用以及何时使用HashSet（22.4.1节）LinkedHashSet（22.4.2节）或者TreeSet（22.4.3节）来存储元素。·使用Comparable接口和Comparator接口来比较元素（22.5节）。·探究如何使用以及何时使用ArrayList或LinkedList来存储元素（22.6节）。·使用co1lections类中的静态工具方法来排序、查找和打乱线性表，以及找出集合中的最大元素和最小元素（22.7节）。·比较规则集和线性表的性能（22.8节）。·区分Vector与ArrayList然后使用Stack类创建栈（22.9节）。·探究collection，Queue、LinkedList以及PriorityQueue之间的关系，然后使用PriorityQueue类创建优先队列（22.10节）。·区分Collection与Map，并描述何时及如何使用HashMap、LinkedHashMap和TreeMap来存储带键值的值（22.11节）。·使用collections类中的静态方法来获得单元素规则集、单元素线性表和单元素图，以及不可变的规则集，不可变的线性表和不可变的图（22.12节）。22.1引言数据结构（datastructure）是以某种形式将数据组织在一起的集合。数据结构不仅存储数据，还支持那些访问和处理数据的操作。前面已经学习了ArrayList，它是一种将数据存储在线性表中的数据结构。Java还提供了几个能更有效地组织和操作数据的数据结构。这些数据结构通常称为Java集合框架(Java Collections Framework)。在面向对象思想里，一种数据结构也被认为是一个客器（container），它是一个能存储其他对象的对象，这里的其他对象是指数据或者元素。有些人将数据结构称为容器对象（containerobject）。定义一种数据结构从本质上讲就是定义一个类。数据结构类应该使用数据域存储数据，并提供方法支持查找、插入和删除等操作。因此，创建一个数据结构就是创建这个类的一个实例。然后，可以使用这个实例上的方法来操作这个数据结构，例如，向该数据结构中插入一个元素，或者从这个数据结构中删除一个元素。Java集合框架支持以下两种类型的容器：·一种是为了存储一个元素集合，简称为集合（collection）。PDG·另一种是为了存储键/值对，称为图（map）。22.2集合Java集合框架支持三种主要类型的集合：规则集（Set）、线性表（List）和队列（Queue）。Set的
18·第22章Java集合框架实例用于存储一组不重复的元素，List的实例用于存储一个由元素构成的有序集合，Queue的实例用于存储用先进先出方式处理的对象。这些集合的通用特性都被定义在接口中，而它的实现是在具体类中提供的，如图22-1所示。NavfoableSePTreeSetrtedSetSetlHashSetK-LinkedHashSetCollectionAbstractCoTlectionkvector-Stack-ListN-ArrayListtiallistK-LinkedList]4bbstractQueueKPriorityQueue]接口抽象类具体类图22-1集合是存储对象的容器注意在Java集合框架中定义的所有接口和类都存储在java.util包中，设计指南Java集合框架的设计是使用接口、抽象类和具体类的一个很好的例子用接口定义框架。为方便起见，用抽象类提供这个接口的部分实现，具体类用具体的数据结构实现这个接口注意Java集合框架中的所有具体类都实现了java.lang.cloneable和java，io，Serializable接口。所以，它们的实例都是可复制且可序列化的。22.3Collection接口和AbstractCollection类Collection接口是处理对象集合的根接口。它的公共方法在图22-2中列出。AbstractCollection类是提供collection接口部分实现的便利类。除了size方法和iterator方法之外，它实现了Collection接口中的所有方法。方法size和iterator在合适的子类中实现。Co1lection接口提供了在集合中添加与删除元素的基本操作。add方法给集合添加一个元素。addA11方法会把指定集合中的所有元素添加到这个集合中。remove方法从集合中删除一个元素。removeAl1方法会从这个集合中删除指定集合中的所有元素。retainAl1方法保留既出现在这个集合中也出现在指定集合中的元素。所有这些方法都返回boolean值。如果执行方法会改变这个集合，那么返回值为true。clear（）方法只是删除集合中的所有元素。注意方法addAll、removeAll、retainA1l类似于规则集上的并、差，交运算。Collection接口提供了多种查询操作。方法size返回集合中元素的个数。方法contains检测集合中是否包含指定的元素。方法containsA11检测这个集合是否包含指定集合中的所有元素。如果集合为空，方法isEmpty返回true。Collection接口提供的toArray（）方法返回一个表示集合的数组。集合可以是一个规则集，也可以是一个线性表。Iterator接口提供了对不同类型集合中的元素进行遍历的统一方法。Co1lection接口中的iterator方法返回Iterator接口的一个实例，如图22-2所示，它使用next（）方法顺序访间集合中的元素。也可以使用hasNext（）方法来检测选代器中是否还有更多的元素，而remove(）方法删除从选代器返回的最后一个元素
第22章Java集合框架·19-interface-Java.uriLCollection<E>向集合中添加新元素0+add(o:E):boolean将集合c中的所有元素添加给这个集合+addA71(c:Co1lection<? extends E>):boolean删除集合中的所有元素+clearO:void+contains(o:Object):boolean如果该集合包含元素o则返回true+containsA71(c:Co)lection<?>):boolean如果该集合包含c中的所有元素则返回true+equals(o:Object):boolean如果该集合等于另一个集合o则返国true+hashCodeO:int返回该集合的散列码+isEmptyO:boolean如果该集合不包含任何元素则返回true+iteratorO:IteratorcE返回该集合中元素所用的选代器+remove(o:Object):boolean从集合中删除元素0+removeA71(c:Co1lection<?>):boolean从集合中删除c中的所有元素+retainA71(c:Co1lection<7>):boolean保留c和该集合都有的元素+sizeO:int返回集合的元素个数+toArrayO:ObjectD返回该集合的元素构成的数组objectdnterfacexJava.util.teratorcE>+hasNextO:boo7ean如果选代器有更多的元素要遍历则返回true+nextO:E返回来自选代器的下一个元素+removeO:void删除使用next方法获取的最后一个元素图22-2Co11ection接口包含了处理集合中元素的方法，并且你可以获取一个遍历集合中元素的选代器对象设计注意Co1lection接口中的有些方法是不能在具体子类中实现的。在这种情况下，这些方法会拖出异常java.lang.UnsupportedoperationException，它是RuntimeException算常类的一个子类，这样设计很好，可以在自己的项目中使用。如果一个方法在子类中没有意义，可以按如下方式实现它：publicvoidsomeMethodO{throw new UnsupportedOperationException("Method not supported");122.4规则集Set接口扩展了Co1lection接口。它没有引人新的方法或常量，只是规定Set的实例不包含重复的元素。实现Set的具体类必须确保没有向这个规则集添加重复的元素。也就是说，在一个规则集中，定不存在元素e1、e2使得e1.equals（e2）的返回值为trueAbstractSet类是一个便利类，它扩展AbstractCollection类并实现Set接口，AbstractSet类提供equals方法和hashCode方法的具体实现。-个规则集的散列码是这个规则集中所有元素散列码的和。由于AbstractSet类没有实现size方法和iterator方法，所以，AbstractSet类是一个抽象类。Set接口的三个具体类是：散列类HashSet、链式散列集LinkedHashSet和树形集TreeSet，如图22-3所示。PDG22.4.1散列集HashSetHashSet类是一个用于实现Set接口的具体类，可以使用它的无参构造方法来创建空的散列集，也可以由一个现有的集合创建散列集。默认情况下，初始容量为16而客座率是0.75。如果知道集合的大小，就可以在构造方法中指定初始容量和客座率。否则，就使用默认的设置。客座率的值在0.0到1.0之间
20·第22章Java集合框架nterfacejava.utf1.Co7lection<E>Ainterfacjava.utii.Set<E>AAjava.ut11.AbstractSet<E>interfaceTjavauilSortedSetcE>+firstO:EJavautilHshSetcES+lastO:E+headSet(toElement:E):SortedSet<E>+HashSet(+tai1Set(fromElement: E): SortedSet<E>+HashSet(c: Co1ection<? extends E>)A+HashSet(initiaiCapacfty:int)+HashSet(initialCapacity:int,loadFactor:float)-interfacesJavautllNavigableSeicEsjava.utiLLnkedHashSeES+pol1FirstO:E+polllastO:E+LinkedHashSetO+lower(e: E): E+LinkedHashSet(c:Collection<?extendsE>)+higher(e: E):E+LinkedHashSet(initialCapacity:int)+floor(e: ): E+LinkedHashSet(inftialCapacityint,loadFactor:float)+ceiling(e:E):EAjava.util.TreeSetcE+TreeSetO+TreeSet(c:Collection<?extendsE>)+TreeSet(comparatorComparator<?super E>)+TreeSet(s:SortedSet<E>)图22-3Java集合框架提供三个具体规则集类客座率（loadfactor）测量在增加规则集的容量之前，该规则集的饱满程度。当元素个数超过了容量与客座率的乘积，容量就会自动翻倍。例如，如果容量是16而客座率是0.75，那么当尺寸达到12（16×0.75=12）时，容量将会翻倍到32。比较高的客座率会降低空间开销，但是会增加查找时间。通常情况下，默认的客座率是0.75，它是在时间开销和空间开销上一个很好的权衡。HashSet类可以用来存储互不相同的任何元素。考虑到效率的因素，添加到散列集中的对象必须以一种正确分散散列码的方式来实现hashCode方法。回顾在object类中定义的hashCode，如果两个对象相等，那么这两个对象的散列码必须一样。两个不相等的对象可能会有相同的散列码，因此你应该实现hashCode方法以避免出现太多这样的情况。JavaAPI中的大多数类都实现了hashCode方法。例如，Integer类中的hashCode方法返回它的int值，Character类中的hashCode方法返回这个字符的统码，String类中的hashCode方法返回s.*31(-1)+s,*31(n-2)+...+s.-1，其中s是s.charAt（i)。程序清单22.1给出的程序创建了一个散列集来存储字符串，并且使用一个选代器来遍历这个规则集中的元素。程序清单22.1TestHashSet.javaPDG1 import java.util.*;23publicclassTestHashSet4pubiic static void main(Stringargs)(5// Create a hash.set6Set<String>set- new HashSet<String>O;
Java集合框架·21第22章78I/ Add strings to the set9Set.add("London");10set.add("Paris"):11set.add("New York");12set.add("San Francisco");13Set.add("Beijing");14set.add("New York");1516System.out.println(set):1718// Obtain an iterator for the hash set19Iterator<String> iterator- set.iteratorO;2021// Display the elements in the hash set22while(iterator.hasNextO){23System.out.print(iterator.nextO.toUpperCaseO+"");24125力263[San Francisco,NewYork,Paris,Beijing,London]CSAN FRANCISCO NEW YORK PARIS BEIJING LONDON该程序将多个字符申添加到规则集中（第9～14行）。"NewYork"被添加给规则集多次，但是只有一个被存储，因为规则集不允许有重复的元素。如输出所示，字符串没有按照它们被插入规则集时的顺序存储，因为散列集中的元素是没有特定的顺序的。要强加给它们一个顺序，就需要使用LinkedHashSet类，这个类将在下节中介绍。提示可以不使用选代器，而用for-each循环来简化第18～24行的代码，如下所示；for (Object element: set)System.out.print(element):这个循环可解释为“对规则集中的每个元素，做以下操作"。for-each循环可用在数组上（参见6.2.7节），也可用在任何Collection的实例上。由于一个规则集是Collection的一个实例，因此，所有定义在Co1lection中的方法都可以用在规则集上。程序清单22.2给出一个探究Co11ection接口中方法的例子。程序清单22.22TestMethodInCollection.java1publicclassTestMethodsInCo1lection(2public static void main(String args)3// Create setl4java.utii.Set<String>setl-newjava.util.HashSet<String>O;56// Add strings to setl福7setl.add("London");8setl.add("Paris");:9setl.add("New York");友10setl.add("San Francisco");11setl.add("Beijing"):1213System.out.println("setl is"+ setl);14System.out.println(setl.sizeO+"elements in seti");WPDG1516// Deletea string from setl17set1.remove("London");System.out.println("Insetl is"+set1);1819System.out.println(setl.sizeO+" elements in seti");2021// Create set2