Java技術(shù)及其應(yīng)用第5章收集與數(shù)據(jù)結(jié)構(gòu)應(yīng)用1如果我們知道多個對象的準確數(shù)量，可以用數(shù)組這種數(shù)據(jù)類型來存放這些對象。缺點：但在很多情況下，對象個數(shù)并不能事先確定，用數(shù)組保存就有困難。二是一旦數(shù)組創(chuàng)建后，數(shù)組的大小也就固定了，不能改變。Java設(shè)計了收集(collection)系列，提供了更復(fù)雜的方式保存對象，解決了數(shù)組無法解決的問題。所有收集系列均屬于包：java.util25.1收集的概念收集是可以理解為用來在內(nèi)存中存放一組對象的某種容器（就像數(shù)組），容器的大小可以動態(tài)變化，而且Java提供了實現(xiàn)了各種數(shù)據(jù)結(jié)構(gòu)操作的收集類（也稱容器類），不用程序員自己去實現(xiàn)了，使用起來非常方便。Java的收集形成了收集框架(collectionsframework)的體系結(jié)構(gòu)。收集框架包含接口、抽象類和具體類組成。3【注意】Java收集只能存放引用類型的的數(shù)據(jù)，不能存放基本數(shù)據(jù)類型的數(shù)據(jù)。圖7-1Java集合框架4圖中，點線邊框的是接口；折線邊框的是抽象類；實線邊框的是實現(xiàn)類。55.1收集的概念Java在設(shè)計收集結(jié)構(gòu)時，把收集劃成

3類：第一種是

List，提供的是一個有序的集合且List允許有重復(fù)的元素。第二種是

Set，提供的是一個無序的集合且它不允許包含重復(fù)的元素。第三種是

Map，鍵/值對元素的集合，Map提供鍵（

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

value。Java收集框架中的接口65.1收集的概念Queue5.2Collection接口這是收集系列的根，具有最大的通用性，允許重復(fù)元素存在，不要求元素排序等，是其他特殊收集的“最小公倍數(shù)”。

Set、List和Queue都繼承了Collection。通用目的的各種收集在實現(xiàn)時都用Collection做構(gòu)造方法的參數(shù)，方便轉(zhuǎn)換收集的類型。集合系列不以具體的類型來處理對象，他們所有的對象都按Object類型來處理。所以容器不能保存基本數(shù)據(jù)類型。7Collection接口的結(jié)構(gòu)publicinterfaceCollection<E>extendsIterable<E>{//基本操作intsize();//收集中有多少元素booleanisEmpty();//收集中有無元素Iterator<E>iterator();//列舉收集元素

//成批操作booleancontainsAll(Collection<?>c);//目標(biāo)收集是否有指定收集的所有元素booleanaddAll(Collection<?extendsE>c);//(可選)加入指定元素到目標(biāo)收集//數(shù)組操作

Object[]toArray();//收集元素放進Object數(shù)組

<T>T[]toArray(T[]a);//收集元素放進T類型數(shù)組}85.2Collection接口1.遍歷收集把收集中的對象列舉出來叫遍歷收集，可以用for-each結(jié)構(gòu)遍歷，比如：for(Objecto:collection)System.out.println(o);Collection接口的iterator()方法返回一個Iterator對象。還可以用Iterator接口遍歷收集。95.2Collection接口2.Iterator接口迭代器(Iterator)給我們提供了一種通用的方式來訪問集合中的元素。接口中包含三個方法：BooleanhasNext()

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

Enext()

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

voidremove()

//從迭代器指向的集合中移除迭代器上一次訪問返回的元素(可選)。本方法必須緊跟在一個元素的訪問后執(zhí)行。105.2Collection接口收集與數(shù)組間的操作Collection接口有一個toArray()方法可返回包含此collection中所有元素的數(shù)組。比如：Object[]a=c.toArray();將Collection對象c的內(nèi)容導(dǎo)進Object數(shù)組中，數(shù)組長度與c元素個數(shù)相同。反之（p1505.9.3節(jié)）Util包中的Arrays類有一個asList()方法可返回一個受指定數(shù)組支持的固定大小的列表。且返回的List不支持remove()方法。Listlist=Arrays.asList(a);115.2Collection接口5.3SetSet是不能包含重復(fù)元素的Collection。Set接口的方法僅繼承了Collection的方法，并增加不允許重復(fù)元素的限制。125.3.1Set的實現(xiàn)Java平臺有三種通用目的的Set實現(xiàn)：HashSet用哈希表存放元素，實現(xiàn)性能最好，但不保證列舉順序。TreeSet按元素值排次序，比HashSet慢。我們通常都應(yīng)該使用HashSet，在我們需要排序的功能時，我們才使用TreeSet。LinkedHashSet是鏈表實現(xiàn)的哈希表，按元素插入集合的順序排次序，次序不混亂。性能介于前二者之間。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的實現(xiàn)示例Myset.java運行結(jié)果Findduplicateelement:aTotal3distinctelements:[pen,a,book]打印順序：如果上例的HashSet改為TreeSet，運行結(jié)果變成[a,book,pen]，是按字母順序排列的.155.3.1Set的實現(xiàn)5.3.2Set的數(shù)學(xué)應(yīng)用假設(shè)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運行結(jié)果Union:[pen,have,a,book,I]Intersection:[have,a,I]Symmetricdifference:[pen,book]175.3.2Set的數(shù)學(xué)應(yīng)用5.4ListList接口是Collection接口的子接口。List是有序的Collection，使用此接口能夠精確的控制每個元素插入的位置。用戶能夠使用索引（元素在List中的位置，類似于數(shù)組下標(biāo)）來訪問List中的元素，這類似于Java的數(shù)組。可以包含重復(fù)元素。List接口繼承了Collection的方法，刪除操作總是刪除列表中第一個出現(xiàn)的指定元素，加入操作總是加在列表的末尾。18List方法publicinterfaceList<E>extendsCollection<E>{

//按位置訪問

Eget(intindex);//取指定下標(biāo)的元素

Eset(intindex,Eelement);//(可選)設(shè)置指定下標(biāo)的元素，返回原元素

//搜索

intindexOf(Objecto);//返回列表中第一次出現(xiàn)的指定元素的下標(biāo)，或-1（無）

intlastIndexOf(Objecto);//返回列表中最后出現(xiàn)的指定元素的下標(biāo)，或-1（無）

//列舉

ListIterator<E>listIterator();//從表頭開始列舉

ListIterator<E>listIterator(intindex);//從指定位置開始列舉

//范圍視圖

List<E>subList(intfrom,intto);}195.4List5.4.1List的實現(xiàn)Java平臺有兩種通用目的的List實現(xiàn)：ArrayList和LinkedList。如果要支持隨機訪問，而不必在除尾部的任何位置插入或除去元素，那么，ArrayList更好；但如果要頻繁的從列表的中間位置添加和除去元素，那么，用LinkedList實現(xiàn)更好。20ListArrayList

LinkedList

搜索操作List有兩個搜索方法Indexof()方法找列表中第一次出現(xiàn)的指定元素所在位置，沒有則返回-1Lastindexof()找列表中最后出現(xiàn)指定元素所在位置，沒有則返回-1215.4.1List的實現(xiàn)搜索操作示例P137例5.4SearchList.javalist.add(r.nextInt(10));list.indexOf(5);list.lastIndexOf(6);運行結(jié)果：[8,5,3,1,1,9,8,0,2,7]1-1225.4.1List的實現(xiàn)列舉操作List使用的列舉ListIterator擴充了Collection接口的iterator，可實現(xiàn)更復(fù)雜的列舉操作?？梢詮膬蓚€方向遍歷列表235.4.1List的實現(xiàn)ListIterator接口結(jié)構(gòu)publicinterfaceListIterator<E>extendsIterator<E>{booleanhasNext();Enext();

//下一個元素

booleanhasPrevious();Eprevious();

//前一個元素

intnextIndex();

//下一個下標(biāo)

intpreviousIndex();

//前一個下標(biāo)

voidremove();

//(可選)刪除next()或previous()返回的元素

voidset(Ee);

//(可選)用指定元素設(shè)置next()或previous()返回的元素

voidadd(Ee);

//(可選)在當(dāng)前下標(biāo)前加入指定元素}245.4.1List的實現(xiàn)范圍視圖操作方法subList(intfrom,intto)返回從from下標(biāo)到to下標(biāo)前的子列表【P138例5.5】list.subList(4,6)

//取下標(biāo)4-5的元素

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

//刪除下標(biāo)3-6的元素示例【P136例5.4】：SimpleSublist.java運行結(jié)果：[5,1,6,2,5,1,6,8,2,3][5,1][5,1,6,8,2,3]255.4.1List的實現(xiàn)5.4.2List的數(shù)據(jù)結(jié)構(gòu)應(yīng)用Collections類有許多算法適用于List，方便我們對數(shù)據(jù)進行處理。如:合并排序(sort)、隨機攪亂(shuffle)、序列反向(reverse)、循環(huán)(rotate)、元素交換(swap)、全部替換(replaceAll)、填充(fill)、拷貝(copy)等26排序示例【P137例5.6】ListApp.javaCollections.sort(list);Collections.reverse(list);運行結(jié)果：[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的數(shù)據(jù)結(jié)構(gòu)應(yīng)用5.5QueueQueue是保持元素重于處理元素的Collection，通常是按先進先出方式安排元素，插入元素是在隊尾，刪除元素是在隊頭。但優(yōu)先隊列不同.28Queue方法接口Queue增加了一些方法：

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

//返回隊頭元素，空隊則拋異常

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

Epeek();//返回隊頭元素，空隊返回nullEpoll();//刪除并返回隊頭元素，空隊則拋異常

Eremove();

//刪除并返回隊頭元素，空隊返回null}295.5Queue5.5.1Queue的實現(xiàn)Queue的實現(xiàn)類LinkedList類實現(xiàn)了Queue接口，提供了先進先出隊列的操作PriorityQueue類是基于優(yōu)先堆數(shù)據(jù)結(jié)構(gòu)的優(yōu)先隊列，也實現(xiàn)了Queue接口30LinkedList

QueuePriorityQueue

LinkedList類的底層實現(xiàn)方式為雙向循環(huán)鏈表，很方便實現(xiàn)隊列，棧和雙向隊列等。LinkedList類具有以下方法：addLast()getFirst()removeLast()Removefirst();雙端隊列方法見表5.1315.5.1Queue的實現(xiàn)雙端隊列ArrayDeque示例【P140例5.7】Simpledeque.javadq.addFirst(i);

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

//在后端刪除一個元素dq.removeFirst();

//在前端刪除一個元素運行結(jié)果：[9,8,7,6,5,4,3,2,1,0][8,7,6,5,4,3,2,1]325.5.1Queue的實現(xiàn)5.5.2Queue的數(shù)據(jù)結(jié)構(gòu)應(yīng)用PriorityQueue例子PriorityQueue并非先到先服務(wù)，里面包含一個優(yōu)先級。一個基于優(yōu)先級堆的極大優(yōu)先級隊列。此隊列按照在構(gòu)造時所指定的順序?qū)υ嘏判?，既可以根?jù)元素的自然順序來指定排序（參閱Comparable），也可以根據(jù)Comparator來指定。用優(yōu)先隊列實現(xiàn)堆排序。先創(chuàng)建一個隨機列表，然后把隨機列表放入PriorityQueue構(gòu)造方法中形成堆，優(yōu)先隊列中刪除的每個元素依次加入列表中，輸出的列表已排好序。33堆排序示例Myheapsort.javawhile(!q.isEmpty())r.add(q.remove());刪q一個元素(堆頂)加到r中運行結(jié)果：[6,5,1,4,0,0,2,8,5,6][0,0,1,2,4,5,5,6,6,8]345.5.2Queue的數(shù)據(jù)結(jié)構(gòu)應(yīng)用5.6MapMap是把鍵(key)映射到值(value)的對象，映射不能包含重復(fù)的鍵，一個鍵至少可以映射一個值，它是數(shù)學(xué)函數(shù)抽象的模型。35Map接口的結(jié)構(gòu)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接口的結(jié)構(gòu)5.6Map5.6.1Map的實現(xiàn)Java平臺有三種通用目的的Map實現(xiàn)：HashMap，TreeMap和LinkedHashMap它們的性能與HashSet，TreeSet和LinkedHashSet類似。HashMap速度最快，TreeMap能夠排序，LinkedHashMap性能接近HashMap并保持插入順序。38SortedMapMapHashMap

LinkedHashMap

TreeMap

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

key,V

value)將指定的值與此映射中的指定鍵相關(guān)聯(lián)get(Object

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

key)如果此映射包含指定鍵的映射關(guān)系，則返回truecontainsValue(Object

value)

如果此映射為指定值映射一個或多個鍵，則返回truesize()返回此映射中的鍵-值映射關(guān)系數(shù)isEmpty()如果此映射未包含鍵-值映射關(guān)系，則返回true395.6.1Map的實現(xiàn)基本操作實例Simplemap.java運行結(jié)果：{Physics=82,Chemistry=75,Math=68,English=90}Havegoodresult!如果用TreeMap構(gòu)造Map對象，輸出按字母順序排列鍵：{Chemistry=75,English=90,Math=68,Physics=82}Havegoodresult!如果用LinkedHashMap構(gòu)造Map對象，輸出按插入順序排列鍵：{Math=68,Physics=82,English=90,Chemistry=75}Havegoodresult!405.6.1Map的實現(xiàn)【P143例5.9】收集視圖收集視圖方法用三種方式查看Map：取Map的鍵的集合keySet()取Map中值的收集values()取Map中鍵-值對的集合,提供了列舉Map全部內(nèi)容的唯一方法，即用entrySet()Map有個嵌套的接口Map.Entry，可以按鍵-值對列舉Map：for(Map.Entry<KeyType,ValType>e:m.entrySet())System.out.println(e.getKey()+":"+e.getValue());415.6.1Map的實現(xiàn)收集視圖操作實例【P144例5.10】

Mapop.java運行結(jié)果：{Physics=97,Chemistry=95,Math=48,English=27}PhysicsisgoodChemistryisgood425.6.1Map的實現(xiàn)5.6.2Map的數(shù)學(xué)應(yīng)用containsAll()、removeAll()、retainAll()等成批操作支持Map運算.containsAll()該集合是否包含指定集合的所有元素removeAll()移除此集合中指定集合的所有元素retainAll()保留此集合中包含指定集合的元素43數(shù)學(xué)應(yīng)用實例Mapop2.java運行結(jié)果：{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的數(shù)學(xué)應(yīng)用5.7SortedSetSortedSet是按升序維護元素的Set，集合中的元素如果沒有實現(xiàn)java.lang包的Comparable接口無法比較，SortedSet就要提供java.util包的Comparator接口方法控制元素的次序。45常用類與自然排序Byte類，按符號數(shù)排列Character類，按無符號數(shù)排列Long類，按符號數(shù)排列Integer類，按符號數(shù)排列Short類，按符號數(shù)排列Double類，按符號數(shù)排列Float類，按符號數(shù)排列BigInteger類，按符號數(shù)排列BigDecimal類，按符號數(shù)排列Boolean類，按Boolean.FALSE<Boolean.TRUE排列File類，路徑名按系統(tǒng)相關(guān)的字典順序排列String類，按字典順序排列Date類，按年月日順序排列CollationKey類，按指定地點的字典順序排列465.7SortedSetSortedSet的實現(xiàn)TreeSet類實現(xiàn)了SortedSet接口它有四個構(gòu)造方法：TreeSet()TreeSet(Collection<?extendsE>c)TreeSet(Comparator<?superE>comparator)TreeSet(SortedSet<E>s)前兩個按元素的自然順序排序，后兩個按指定comparator排序。Comparator接口在util包中。475.7SortedSet

范圍視圖操作subset()方法取子集，結(jié)果包含低端元素，而不包含高端元素，即半開區(qū)間。headSet()方法返回從最低端到指定元素前的元素，不包括指定元素本身。tailSet()方法返回從指定元素到最高端元素的元素，包括最高端元素。485.7SortedSetSortedSet示例Simplesortedset.javass.subSet(3,8)ss.headSet(3,8)ss.tailSet(3,8)運行結(jié)果：[1,2,3,6,7,8,9][3,6,7][1,2,3][6,7,8,9]495.7SortedSet5.8SortedMapSortedMap是按升序維護元素的Map.Map中的元素按鍵的自然順序排列，或者按Comparator接口方法控制元素的次序。50SortedMap接口的實現(xiàn)TreeMap類實現(xiàn)了SortedMap接口

構(gòu)造一個TreeMap類對象，有四個構(gòu)造方法。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”)運行結(jié)果：{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收集框架的一個成員，它包含大量靜態(tài)方法操縱或返回收集。java.util.Collections類中定義了多種集合操作方法，實現(xiàn)了對集合元素的排序、取極值、批量拷貝、集合結(jié)構(gòu)轉(zhuǎn)換、循環(huán)移位以及匹配性檢查等功能，此類完全由在Collection上進行操作或返回Collection的靜態(tài)方法組成。535.9.1靜態(tài)方法Collections類的方法都是靜態(tài)的sort(List<T>list)可以按自然排序?qū)ist進行升序排序，還有一個重載的sort方法。binarySearch()、copy()、fill()、reverse()、rotate()、shuffle()等靜態(tài)方法操縱List對象。disjoint()、enumeration()、frequency()、max()、min()等靜態(tài)方法操縱Collection對象.對Set和Map也提供了一些靜態(tài)方法。545.9Collections類排序示例【P149例5.14】

Simplesort.javaCollections.shuffle(llist);//把原列表攪亂Collections.sort(llist);//把原列表排序555.9.1靜態(tài)方法5.9Collections類5.9.2包裝器java1.1中的類Vector（ArrayList）、Stack（其中的EmentAt（）方法）Hashtable（HashMap）和Propeties類。包裝器(wrapper)對指定收集加入新功能，有同步包裝器(synchronizationwrapper)、不許修改包裝器(unmodifiablewrapper)和檢查接口包裝器(checkedinterfacewrapper)等。Collections類的靜態(tài)方法對六種收集接口對象Collection、Set、List、Map、SortedSet、SortedMap都提供了包裝器。比較而言，Vector較同步包裝器還是要快一些，但它包含一些繼承的操作，使用起來要小心些。565.9.3方便實現(xiàn)有些方法可以簡單地實現(xiàn)收集對象，比如Arrays.asList()就是用數(shù)組做參數(shù)而形成的列表，但是不能修改。Collections類也有一些方便方法。Collections.nCopies()方法產(chǎn)生一個包含n個相同元素的不可變列表，例如：List<String>list=newArrayList<String>(Collections.nCopies(50,"abc");這就很方便地生成了一個含50個“abc”的列表。575.9.4Collections類的數(shù)據(jù)結(jié)構(gòu)應(yīng)用Collections類的靜態(tài)方法排序(Sorting)采用稍微優(yōu)化的合并排序，時間復(fù)雜度是nlog(n)攪亂(Shuffling)按隨機性把原序列攪亂，相當(dāng)于洗牌。常規(guī)數(shù)據(jù)處理(RoutineDataManipulation)包括反向、填充、拷貝、交換、全加入等搜索(Searching)二分搜索組合(Composition)計算收集中元素出現(xiàn)頻率，還有判定兩個收集是否不相交尋找極值(FindingExtremeValues)等六類。58示例Myalgo.java運行結(jié)果：[1,0,0,2,5,6,5,1,2,8]2[1,2,3,6,5,4,7,8,9,0]false595.9.4Collections類的數(shù)據(jù)結(jié)構(gòu)應(yīng)用Arrays類在java.util類庫中可以找到Arrays類，它包含很多static方法，提供操作數(shù)組的使用功能。Equals（）比較連個數(shù)組是否相等Fill（）用每個值填充整個數(shù)組Sort（）對數(shù)組排序binarySearch（）在已經(jīng)排好序的數(shù)組中查找元素asList（）接受數(shù)組為參數(shù)，并將其轉(zhuǎn)化為List容器System.arraycopy（）復(fù)制數(shù)組605.9.4Collections類的數(shù)據(jù)結(jié)構(gòu)應(yīng)用5.10抽象實現(xiàn)java.util包有幾個抽象類，是Java平臺提供的收集的抽象實現(xiàn)機制，使用戶可以自己實現(xiàn)收集接口，以增加功能或提高性能。它們分別是AbstractCollection，AbstractSet，Abst