Java技术及其应用：第5章 收集与数据结构应用

Java技术及其应用第5章收集与数据结构应用1如果我们知道多个对象的准确数量，可以用数组这种数据类型来存放这些对象。缺点：但在很多情况下，对象个数并不能事先确定，用数组保存就有困难。二是一旦数组创建后，数组的大小也就固定了，不能改变。Java设计了收集(collection)系列，提供了更复杂的方式保存对象，解决了数组无法解决的问题。所有收集系列均属于包：java.util25.1收集的概念收集是可以理解为用来在内存中存放一组对象的某种容器（就像数组），容器的大小可以动态变化，而且Java提供了实现了各种数据结构操作的收集类（也称容器类），不用程序员自己去实现了，使用起来非常方便。Java的收集形成了收集框架(collectionsframework)的体系结构。收集框架包含接口、抽象类和具体类组成。3【注意】Java收集只能存放引用类型的的数据，不能存放基本数据类型的数据。图7-1Java集合框架4图中，点线边框的是接口；折线边框的是抽象类；实线边框的是实现类。55.1收集的概念Java在设计收集结构时，把收集划成

3类：第一种是

List，提供的是一个有序的集合且List允许有重复的元素。第二种是

Set，提供的是一个无序的集合且它不允许包含重复的元素。第三种是

Map，键/值对元素的集合，Map提供键（

key）到值（value）的映射。一个Map中不能包含相同的key，每个key只能映射一个

value。Java收集框架中的接口65.1收集的概念Queue5.2Collection接口这是收集系列的根，具有最大的通用性，允许重复元素存在，不要求元素排序等，是其他特殊收集的“最小公倍数”。

Set、List和Queue都继承了Collection。通用目的的各种收集在实现时都用Collection做构造方法的参数，方便转换收集的类型。集合系列不以具体的类型来处理对象，他们所有的对象都按Object类型来处理。所以容器不能保存基本数据类型。7Collection接口的结构publicinterfaceCollection<E>extendsIterable<E>{//基本操作intsize();//收集中有多少元素booleanisEmpty();//收集中有无元素Iterator<E>iterator();//列举收集元素

//成批操作booleancontainsAll(Collection<?>c);//目标收集是否有指定收集的所有元素booleanaddAll(Collection<?extendsE>c);//(可选)加入指定元素到目标收集//数组操作

Object[]toArray();//收集元素放进Object数组

<T>T[]toArray(T[]a);//收集元素放进T类型数组}85.2Collection接口1.遍历收集把收集中的对象列举出来叫遍历收集，可以用for-each结构遍历，比如：for(Objecto:collection)System.out.println(o);Collection接口的iterator()方法返回一个Iterator对象。还可以用Iterator接口遍历收集。95.2Collection接口2.Iterator接口迭代器(Iterator)给我们提供了一种通用的方式来访问集合中的元素。接口中包含三个方法：BooleanhasNext()

//如果仍有元素可以迭代，则返回true。

Enext()

//返回迭代的下一个元素。

voidremove()

//从迭代器指向的集合中移除迭代器上一次访问返回的元素(可选)。本方法必须紧跟在一个元素的访问后执行。105.2Collection接口收集与数组间的操作Collection接口有一个toArray()方法可返回包含此collection中所有元素的数组。比如：Object[]a=c.toArray();将Collection对象c的内容导进Object数组中，数组长度与c元素个数相同。反之（p1505.9.3节）Util包中的Arrays类有一个asList()方法可返回一个受指定数组支持的固定大小的列表。且返回的List不支持remove()方法。Listlist=Arrays.asList(a);115.2Collection接口5.3SetSet是不能包含重复元素的Collection。Set接口的方法仅继承了Collection的方法，并增加不允许重复元素的限制。125.3.1Set的实现Java平台有三种通用目的的Set实现：HashSet用哈希表存放元素，实现性能最好，但不保证列举顺序。TreeSet按元素值排次序，比HashSet慢。我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。LinkedHashSet是链表实现的哈希表，按元素插入集合的顺序排次序，次序不混乱。性能介于前二者之间。13SortedSetSetHashSet

LinkedHashSet

TreeSet

示例Myset.javaimportjava.util.*;publicclassMyset_1{publicstaticvoidmain(String[]args){

Set<String>s=newHashSet<String>();String[]s1={"a","book","a","pen"};for(Strings2:s1){ if(!s.add(s2)){ System.out.println("Findduplicateelement:"+s2); }System.out.println("Total:"+s.size()+"distinctelements:"+s);}}}145.3.1Set的实现示例Myset.java运行结果Findduplicateelement:aTotal3distinctelements:[pen,a,book]打印顺序：如果上例的HashSet改为TreeSet，运行结果变成[a,book,pen]，是按字母顺序排列的.155.3.1Set的实现5.3.2Set的数学应用假设a和b是Seta.containsAll(b)可以判断b是否a的子集a.addAll(b)形成a并ba.retainAll(b)形成a交ba.removeAll(b)形成a与b的差16示例Setop.javaSet<String>aub=newHashSet<String>(a);aub.addAll(b);

//a中加入bSet<String>aib=newHashSet<String>(a);aib.retainAll(b);//a中保留b的元素aub.removeAll(aib);

//a并b减a交b运行结果Union:[pen,have,a,book,I]Intersection:[have,a,I]Symmetricdifference:[pen,book]175.3.2Set的数学应用5.4ListList接口是Collection接口的子接口。List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。可以包含重复元素。List接口继承了Collection的方法，删除操作总是删除列表中第一个出现的指定元素，加入操作总是加在列表的末尾。18List方法publicinterfaceList<E>extendsCollection<E>{

//按位置访问

Eget(intindex);//取指定下标的元素

Eset(intindex,Eelement);//(可选)设置指定下标的元素，返回原元素

//搜索

intindexOf(Objecto);//返回列表中第一次出现的指定元素的下标，或-1（无）

intlastIndexOf(Objecto);//返回列表中最后出现的指定元素的下标，或-1（无）

//列举

ListIterator<E>listIterator();//从表头开始列举

ListIterator<E>listIterator(intindex);//从指定位置开始列举

//范围视图

List<E>subList(intfrom,intto);}195.4List5.4.1List的实现Java平台有两种通用目的的List实现：ArrayList和LinkedList。如果要支持随机访问，而不必在除尾部的任何位置插入或除去元素，那么，ArrayList更好；但如果要频繁的从列表的中间位置添加和除去元素，那么，用LinkedList实现更好。20ListArrayList

LinkedList

搜索操作List有两个搜索方法Indexof()方法找列表中第一次出现的指定元素所在位置，没有则返回-1Lastindexof()找列表中最后出现指定元素所在位置，没有则返回-1215.4.1List的实现搜索操作示例P137例5.4SearchList.javalist.add(r.nextInt(10));list.indexOf(5);list.lastIndexOf(6);运行结果：[8,5,3,1,1,9,8,0,2,7]1-1225.4.1List的实现列举操作List使用的列举ListIterator扩充了Collection接口的iterator，可实现更复杂的列举操作。可以从两个方向遍历列表235.4.1List的实现ListIterator接口结构publicinterfaceListIterator<E>extendsIterator<E>{booleanhasNext();Enext();

//下一个元素

booleanhasPrevious();Eprevious();

//前一个元素

intnextIndex();

//下一个下标

intpreviousIndex();

//前一个下标

voidremove();

//(可选)删除next()或previous()返回的元素

voidset(Ee);

//(可选)用指定元素设置next()或previous()返回的元素

voidadd(Ee);

//(可选)在当前下标前加入指定元素}245.4.1List的实现范围视图操作方法subList(intfrom,intto)返回从from下标到to下标前的子列表【P138例5.5】list.subList(4,6)

//取下标4-5的元素

list.subList(3,7).clear()

//删除下标3-6的元素示例【P136例5.4】：SimpleSublist.java运行结果：[5,1,6,2,5,1,6,8,2,3][5,1][5,1,6,8,2,3]255.4.1List的实现5.4.2List的数据结构应用Collections类有许多算法适用于List，方便我们对数据进行处理。如:合并排序(sort)、随机搅乱(shuffle)、序列反向(reverse)、循环(rotate)、元素交换(swap)、全部替换(replaceAll)、填充(fill)、拷贝(copy)等26排序示例【P137例5.6】ListApp.javaCollections.sort(list);Collections.reverse(list);运行结果：[1,7,7,4,2,3,6,5,0,5][0,1,2,3,4,5,5,6,7,7][7,7,6,5,5,4,3,2,1,0]275.4.2List的数据结构应用5.5QueueQueue是保持元素重于处理元素的Collection，通常是按先进先出方式安排元素，插入元素是在队尾，删除元素是在队头。但优先队列不同.28Queue方法接口Queue增加了一些方法：

publicinterfaceQueue<E>extendsCollection<E>{Eelement();

//返回队头元素，空队则抛异常

booleanoffer(Ee);//在限界队列里加入元素

Epeek();//返回队头元素，空队返回nullEpoll();//删除并返回队头元素，空队则抛异常

Eremove();

//删除并返回队头元素，空队返回null}295.5Queue5.5.1Queue的实现Queue的实现类LinkedList类实现了Queue接口，提供了先进先出队列的操作PriorityQueue类是基于优先堆数据结构的优先队列，也实现了Queue接口30LinkedList

QueuePriorityQueue

LinkedList类的底层实现方式为双向循环链表，很方便实现队列，栈和双向队列等。LinkedList类具有以下方法：addLast()getFirst()removeLast()Removefirst();双端队列方法见表5.1315.5.1Queue的实现双端队列ArrayDeque示例【P140例5.7】Simpledeque.javadq.addFirst(i);

//在前端加入idq.removeLast();

//在后端删除一个元素dq.removeFirst();

//在前端删除一个元素运行结果：[9,8,7,6,5,4,3,2,1,0][8,7,6,5,4,3,2,1]325.5.1Queue的实现5.5.2Queue的数据结构应用PriorityQueue例子PriorityQueue并非先到先服务，里面包含一个优先级。一个基于优先级堆的极大优先级队列。此队列按照在构造时所指定的顺序对元素排序，既可以根据元素的自然顺序来指定排序（参阅Comparable），也可以根据Comparator来指定。用优先队列实现堆排序。先创建一个随机列表，然后把随机列表放入PriorityQueue构造方法中形成堆，优先队列中删除的每个元素依次加入列表中，输出的列表已排好序。33堆排序示例Myheapsort.javawhile(!q.isEmpty())r.add(q.remove());删q一个元素(堆顶)加到r中运行结果：[6,5,1,4,0,0,2,8,5,6][0,0,1,2,4,5,5,6,6,8]345.5.2Queue的数据结构应用5.6MapMap是把键(key)映射到值(value)的对象，映射不能包含重复的键，一个键至少可以映射一个值，它是数学函数抽象的模型。35Map接口的结构publicinterfaceMap<K,V>{//基本操作

Vput(Kkey,Vvalue);Vget(Objectkey);Vremove(Objectkey);booleancontainsKey(Objectkey);booleancontainsValue(Objectvalue);intsize();booleanisEmpty();365.6Map//成批操作

voidputAll(Map<?extendsK,?extendsV>m);//把m全部键与值加入目的Mapvoidclear();

//收集视图

publicSet<K>keySet();//取Map中键的集合

publicCollection<V>values();//取Map中值的收集

publicSet<Map.Entry<K,V>>entrySet();//取Map中键-值对的集合

//entrySet元素接口

publicinterfaceEntry{KgetKey();VgetValue();VsetValue(Vvalue);}}37Map接口的结构5.6Map5.6.1Map的实现Java平台有三种通用目的的Map实现：HashMap，TreeMap和LinkedHashMap它们的性能与HashSet，TreeSet和LinkedHashSet类似。HashMap速度最快，TreeMap能够排序，LinkedHashMap性能接近HashMap并保持插入顺序。38SortedMapMapHashMap

LinkedHashMap

TreeMap

基本操作Map的基本操作是put(K

key,V

value)将指定的值与此映射中的指定键相关联get(Object

key)返回此映射中映射到指定键的值containsKey(Object

key)如果此映射包含指定键的映射关系，则返回truecontainsValue(Object

value)

如果此映射为指定值映射一个或多个键，则返回truesize()返回此映射中的键-值映射关系数isEmpty()如果此映射未包含键-值映射关系，则返回true395.6.1Map的实现基本操作实例Simplemap.java运行结果：{Physics=82,Chemistry=75,Math=68,English=90}Havegoodresult!如果用TreeMap构造Map对象，输出按字母顺序排列键：{Chemistry=75,English=90,Math=68,Physics=82}Havegoodresult!如果用LinkedHashMap构造Map对象，输出按插入顺序排列键：{Math=68,Physics=82,English=90,Chemistry=75}Havegoodresult!405.6.1Map的实现【P143例5.9】收集视图收集视图方法用三种方式查看Map：取Map的键的集合keySet()取Map中值的收集values()取Map中键-值对的集合,提供了列举Map全部内容的唯一方法，即用entrySet()Map有个嵌套的接口Map.Entry，可以按键-值对列举Map：for(Map.Entry<KeyType,ValType>e:m.entrySet())System.out.println(e.getKey()+":"+e.getValue());415.6.1Map的实现收集视图操作实例【P144例5.10】

Mapop.java运行结果：{Physics=97,Chemistry=95,Math=48,English=27}PhysicsisgoodChemistryisgood425.6.1Map的实现5.6.2Map的数学应用containsAll()、removeAll()、retainAll()等成批操作支持Map运算.containsAll()该集合是否包含指定集合的所有元素removeAll()移除此集合中指定集合的所有元素retainAll()保留此集合中包含指定集合的元素43数学应用实例Mapop2.java运行结果：{Physics=2,Chemistry=51,Math=39,English=23}{Physics=2,Chemistry=51,Math=39,English=23}m1containsm2{}{Physics=2,Chemistry=51,Math=39,English=23}功能：第一个Map删去与第二个Map相同的元素。

445.6.2Map的数学应用5.7SortedSetSortedSet是按升序维护元素的Set，集合中的元素如果没有实现java.lang包的Comparable接口无法比较，SortedSet就要提供java.util包的Comparator接口方法控制元素的次序。45常用类与自然排序Byte类，按符号数排列Character类，按无符号数排列Long类，按符号数排列Integer类，按符号数排列Short类，按符号数排列Double类，按符号数排列Float类，按符号数排列BigInteger类，按符号数排列BigDecimal类，按符号数排列Boolean类，按Boolean.FALSE<Boolean.TRUE排列File类，路径名按系统相关的字典顺序排列String类，按字典顺序排列Date类，按年月日顺序排列CollationKey类，按指定地点的字典顺序排列465.7SortedSetSortedSet的实现TreeSet类实现了SortedSet接口它有四个构造方法：TreeSet()TreeSet(Collection<?extendsE>c)TreeSet(Comparator<?superE>comparator)TreeSet(SortedSet<E>s)前两个按元素的自然顺序排序，后两个按指定comparator排序。Comparator接口在util包中。475.7SortedSet

范围视图操作subset()方法取子集，结果包含低端元素，而不包含高端元素，即半开区间。headSet()方法返回从最低端到指定元素前的元素，不包括指定元素本身。tailSet()方法返回从指定元素到最高端元素的元素，包括最高端元素。485.7SortedSetSortedSet示例Simplesortedset.javass.subSet(3,8)ss.headSet(3,8)ss.tailSet(3,8)运行结果：[1,2,3,6,7,8,9][3,6,7][1,2,3][6,7,8,9]495.7SortedSet5.8SortedMapSortedMap是按升序维护元素的Map.Map中的元素按键的自然顺序排列，或者按Comparator接口方法控制元素的次序。50SortedMap接口的实现TreeMap类实现了SortedMap接口

构造一个TreeMap类对象，有四个构造方法。TreeMap()

Constructsanew,emptymap,sortedaccordingtothekeys'naturalorder.TreeMap(Comparator<?superK>

c)

Constructsanew,emptymap,sortedaccordingtothegivencomparator.TreeMap(Map<?extendsK,?extendsV>

m)

Constructsanewmapcontainingthesamemappingsasthegivenmap,sortedaccordingtothekeys'naturalorder.TreeMap(SortedMap<K,?extendsV>

m)

ConstructsanewmapcontainingthesamemappingsasthegivenSortedMap,sortedaccordingtothesameordering.515.8SortedMapSortedMap示例Simplesoriedmap.javam.headMap(“go”)m.tailMap(“go”)m.firstKey(“go”)运行结果：{I=42,a=78,am=75,go=63,school=57,student=60,to=93}{I=42,a=78,am=75}{go=63,school=57,student=60,to=93}I525.8SortedMap5.9Collections类这个类是Java收集框架的一个成员，它包含大量静态方法操纵或返回收集。java.util.Collections类中定义了多种集合操作方法，实现了对集合元素的排序、取极值、批量拷贝、集合结构转换、循环移位以及匹配性检查等功能，此类完全由在Collection上进行操作或返回Collection的静态方法组成。535.9.1静态方法Collections类的方法都是静态的sort(List<T>list)可以按自然排序对List进行升序排序，还有一个重载的sort方法。binarySearch()、copy()、fill()、reverse()、rotate()、shuffle()等静态方法操纵List对象。disjoint()、enumeration()、frequency()、max()、min()等静态方法操纵Collection对象.对Set和Map也提供了一些静态方法。545.9Collections类排序示例【P149例5.14】

Simplesort.javaCollections.shuffle(llist);//把原列表搅乱Collections.sort(llist);//把原列表排序555.9.1静态方法5.9Collections类5.9.2包装器java1.1中的类Vector（ArrayList）、Stack（其中的EmentAt（）方法）Hashtable（HashMap）和Propeties类。包装器(wrapper)对指定收集加入新功能，有同步包装器(synchronizationwrapper)、不许修改包装器(unmodifiablewrapper)和检查接口包装器(checkedinterfacewrapper)等。Collections类的静态方法对六种收集接口对象Collection、Set、List、Map、SortedSet、SortedMap都提供了包装器。比较而言，Vector较同步包装器还是要快一些，但它包含一些继承的操作，使用起来要小心些。565.9.3方便实现有些方法可以简单地实现收集对象，比如Arrays.asList()就是用数组做参数而形成的列表，但是不能修改。Collections类也有一些方便方法。Collections.nCopies()方法产生一个包含n个相同元素的不可变列表，例如：List<String>list=newArrayList<String>(Collections.nCopies(50,"abc");这就很方便地生成了一个含50个“abc”的列表。575.9.4Collections类的数据结构应用Collections类的静态方法排序(Sorting)采用稍微优化的合并排序，时间复杂度是nlog(n)搅乱(Shuffling)按随机性把原序列搅乱，相当于洗牌。常规数据处理(RoutineDataManipulation)包括反向、填充、拷贝、交换、全加入等搜索(Searching)二分搜索组合(Composition)计算收集中元素出现频率，还有判定两个收集是否不相交寻找极值(FindingExtremeValues)等六类。58示例Myalgo.java运行结果：[1,0,0,2,5,6,5,1,2,8]2[1,2,3,6,5,4,7,8,9,0]false595.9.4Collections类的数据结构应用Arrays类在java.util类库中可以找到Arrays类，它包含很多static方法，提供操作数组的使用功能。Equals（）比较连个数组是否相等Fill（）用每个值填充整个数组Sort（）对数组排序binarySearch（）在已经排好序的数组中查找元素asList（）接受数组为参数，并将其转化为List容器System.arraycopy（）复制数组605.9.4Collections类的数据结构应用5.10抽象实现java.util包有几个抽象类，是Java平台提供的收集的抽象实现机制，使用户可以自己实现收集接口，以增加功能或提高性能。它们分别是AbstractCollection，AbstractSet，Abst