第8章集合類8.1線性結(jié)構(gòu)簡介8.2集合與集合框架8.3Collection接口8.4List接口與實現(xiàn)類8.5Set接口8.6Map接口8.7Collections算法類

8.1線性結(jié)構(gòu)簡介

常見的數(shù)據(jù)結(jié)構(gòu)有：表示1?:?1關(guān)系的線性結(jié)構(gòu)、表示1?:?n關(guān)系的樹結(jié)構(gòu)、表示m:n關(guān)系的圖結(jié)構(gòu)、只屬于同一個集合而沒有任何關(guān)系的集合?；镜拇鎯Y(jié)構(gòu)(物理結(jié)構(gòu))是順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。在實際應(yīng)用中，把線性結(jié)構(gòu)進一步分為線性表、棧、隊列、字符串等。每一種線性結(jié)構(gòu)都可用順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)兩種不同的存儲結(jié)構(gòu)來存儲，并在相應(yīng)的存儲結(jié)構(gòu)上實現(xiàn)相應(yīng)的算法。為介紹java.util包中集合之方便，本節(jié)先簡要地回顧一下線性表、棧、隊列的有關(guān)概念。1．線性表

(1)線性表的定義：線性表是n個具有相同數(shù)據(jù)類型的數(shù)據(jù)元素的有限序列，表示如下：

(a1，a2，a3，…，an)

其中，n為線性表的長度(n≥0)，n=0的表稱為空表。在這個序列中，除第一個元素a1外，每個元素都有且只有一個前驅(qū)元素；除最后一個元素an外，每個元素都有且只有一個后繼元素。

(2)線性表的存儲結(jié)構(gòu)：線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈接存儲結(jié)構(gòu)。用順序存儲結(jié)構(gòu)存儲的線性表稱為順序表，用鏈接存儲結(jié)構(gòu)存儲的線性表稱為鏈表。

(3)順序表：用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，元素的邏輯次序與物理(存儲)次序一定相同，因此，數(shù)據(jù)元素間的前驅(qū)、后繼關(guān)系就隱含于其存儲位置的相鄰上。在Java程序中通常用一維數(shù)組來實現(xiàn)順序表。

(4)鏈表：用任意的存儲單元存儲線性表的數(shù)據(jù)元素。鏈表的最主要特點是數(shù)據(jù)元素的物理(存儲)次序與其邏輯次序不一定相同，因此，數(shù)據(jù)元素間的前驅(qū)、后繼關(guān)系就需要通過表示鏈接關(guān)系的“指針”來顯式地指出。

2．棧

(1)棧(Stack)的定義：棧是一種操作受限的線性表，限定只能在表的一端進行插入和刪除操作。允許插入和刪除的一端稱為棧頂，另一端稱為棧底，如圖8.1所示。棧的操作特性是后進先出(LIFO)。

(2)棧的存儲結(jié)構(gòu)：棧既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈式存儲結(jié)構(gòu)。采用順序存儲結(jié)構(gòu)的棧稱為順序棧；采用鏈式存儲結(jié)構(gòu)的棧稱為鏈棧。圖8.1是一個順序棧。圖8.1棧操作

3．隊列

(1)隊列(Queue)的定義：隊列也是一種操作受限的線性表，限定所有的插入操作只能在表的一端(稱表尾或隊尾，Rear)進行，而所有的刪除操作都在表的另一端(稱表頭或隊頭，F(xiàn)ront)進行，如圖8.2所示。隊列的操作是按先進先出(FIFO)的原則進行的。

(2)隊列的存儲結(jié)構(gòu)：隊列既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈接存儲結(jié)構(gòu)。圖8.2隊列操作

8.2集合與集合框架

8.2.1集合(Collection)

數(shù)組作為Java提供的一種容器，可以存儲一組具有基本類型的數(shù)據(jù)或一組對象，常用于線性結(jié)構(gòu)中元素的順序存儲。然而，當創(chuàng)建一個數(shù)組之后，它的元素個數(shù)及元素的數(shù)據(jù)類型就不能改變了。如果在編寫程序時不清楚數(shù)據(jù)元素的個數(shù)及其數(shù)據(jù)類型，就不能使用數(shù)組來存儲，而需要特殊的存儲容器。java.util包提供了我們需要的一套比較完整的被稱為集合(Collection)的容器類來存儲各種類型的對象，其中最基本的容器類型是List(列表)、Set(集)、Queue(隊列)、Map(映射)。需要注意的是，集合容器的大小可以靈活調(diào)整，但只能存儲對象，而不能存儲Java中的基本類型數(shù)據(jù)。java.util包提供的基本集合如下：

(1)?Set：與數(shù)學中集合的概念相似，Set不保證元素的次序，但保證沒有重復(fù)元素。

(2)?List：是一個列表集合，元素間有序，允許有重復(fù)元素。

(3)?Map：是一個映射集合，每一個元素包含key-value對(鍵-值對)。key不能重復(fù)，但value對象可以重復(fù)。

(4)?Queue：是一個隊列集合，強調(diào)對象先進先出的操作順序。8.2.2集合框架

Java集合框架API是用來表示和操作集合的統(tǒng)一框架。為了使整個集合框架中的類便于使用，Java提供了標準的接口，允許不同類型的集合以相同的方式和高度互操作方式工作，使得集合容易擴展或修改。集合框架包含了三部分：接口、實現(xiàn)及算法。

(1)接口：它表示集合的抽象數(shù)據(jù)類型。java.util包中主要接口的繼承關(guān)系如圖8.3所示。圖8.4列出了集合框架中的核心集合接口，它封裝了不同類型的集合，提供了不同集合的獨立操作。核心集合接口提供了兩個獨立的接口樹來表示對象的存儲方式。其中Collection接口的存儲方式是將元素作為單個對象存儲，而Map接口的存儲方式是將元素作為一組key-value對對象存儲。常用的集合接口框架如表8.1所示。圖8.3主要接口的繼承關(guān)系圖8.4核心集合接口表8.1常用的集合接口框架

(2)實現(xiàn)：集合接口的具體實現(xiàn)，是可重用的數(shù)據(jù)結(jié)構(gòu)。集合接口、實現(xiàn)類之間的相互關(guān)系如圖8.5所示。圖中左邊是實現(xiàn)類，右邊是接口。對于繼承而言，不管是類之間還是接口之間均用實線表示。例如，Stack類是Vector類的子類，Set和List接口是Collection的子接口。圖中虛線將右邊的接口與左邊的直接實現(xiàn)該接口的類連接起來，說明每個接口由相應(yīng)的類實現(xiàn)。例如，ArrayList類是一種直接實現(xiàn)List接口的類。圖8.5集合接口、實現(xiàn)類之間的相互關(guān)系

(3)算法：java.util包的Collections類中提供了豐富的靜態(tài)方法幫助我們輕松完成諸如搜索、查找、排序等常用的算法。而且Collections類提供的算法是可以被所有的集合利用的標準方法。

8.3Collection接口

8.3.1Collection接口簡介

Collection作為集合層次結(jié)構(gòu)的根，它存儲元素的方式可以是Set型或List型。它提供的通用方法是集合框架中所有集合都將擁有的核心方法。在需要最大程度的通用性的情況下，可以使用Collection接口傳遞對象的集合。JDK不提供Collection接口的任何直接實現(xiàn)，而是通過它的子接口(例如Set和List)來實現(xiàn)的。Collection接口提供的對集合中元素的基本操作如下。

1)添加元素的方法

booleanadd(Objectobj)：添加一個元素。

booleanaddAll(Collectionc)：添加一個集合中的所有元素。

2)刪除元素的方法

booleanremove(Objectobj)：刪除一個元素。

booleanremoveAll(Collectionc)：刪除一個集合中的所有元素。

voidclear(?)：清空，刪除所有元素。

3)求交集的方法

booleanretainAll(Collectionc)：取兩個集合中的相同元素。

4)獲取元素個數(shù)的方法。

intsize(?)：獲取集合中的元素個數(shù)。

5)判斷的方法

booleanisEmpty(?)：判斷該集合是否為空。

booleancontains(Objecto)：判斷是否包含指定元素。

booleancontainsAll(Collectionc)：判斷是否包含參數(shù)中指定集合的所有元素。

6)將集合變成數(shù)組的方法

Object[]toArray(?)：返回包含此Collection中所有元素的數(shù)組。

<T>T[]toArray(T[]a)：返回包含此Collection中所有元素的數(shù)組；返回數(shù)組的運行時類型與指定數(shù)組的運行時類型相同。注意，不能直接把集合轉(zhuǎn)換成基本數(shù)據(jù)類型的數(shù)組(例如int、char)，因為集合必須持有對象。其中<T>中的T表示泛型類型的變量，它的值可以是傳遞過來的任何類型(例如Integer、Character、自已定義的對象等)，但它不能是任何基本數(shù)據(jù)類型(例如int、char)。

7)迭代器

terator?iterator(?)：遍歷Collection中的每一個元素。8.3.2Iterator迭代器

Java提供遍歷集合元素的方法有如下兩種。

1．for-each結(jié)構(gòu)

for-each結(jié)構(gòu)的格式：

for(Objecto:collection)System.out.println(o);//表示一行輸出一個元素

2．Iterator(迭代器)

Collection接口擴展了Iterator接口。Collection接口中的iterator(?)方法返回一個Iterator對象，通過這個對象可以逐一訪問Collection集合中的每一個元素。典型的用法如下：

Iteratorit=collection.iterator(?); //創(chuàng)建一個迭代器對象

while(it.hasNext(?))//其中的hasNext(?)用于判斷迭代器中是否存在下一個元素

{Objectobj=it.next(?);

} //取下一個元素

Iterator中的hasNext(?)方法檢查迭代器中是否有下一個元素，若有則返回true。Iterator中的next(?)方法返回迭代器中的下一個元素。下面用示例程序來說明。

【示例程序C8_f1.java】T泛型類型的簡單操作。

classBox<T>{

privateTt;

voidg1(Tt1)

{t=t1;}

Tget(?)

{returnt;}

}

publicclassC8_f1{

publicstaticvoidmain(String[?]args)

{

Box<Integer>intBox=newBox<Integer>(?);

//創(chuàng)建整數(shù)類型對象

Box<String>strBox=newBox<String>(?); //創(chuàng)建字符串類型對象

intBox.g1(10); //實參為整數(shù)類型對象

strBox.g1("abc"); //實參為字符串類型對象

IntegersomeInt=intBox.get(?); //得到整數(shù)類型對象

Stringstr=strBox.get(?); //得到字符串類型對象

System.out.println(someInt);

System.out.println(str);

}

}該程序的運行結(jié)果如下：

10

abc

程序中Box類名之后的<T>告訴編譯器T是一個參數(shù)化的類型，在類被使用時將會被實際類型替換。在程序的main(?)方法中，“Box<Integer>intBox=newBox<Integer>(?);”語句創(chuàng)建整數(shù)類型對象，T為整數(shù)類型Integer，即用Integer替換T。“Box<String>strBox=newBox<String>(?);”語句創(chuàng)建字符串類型對象，T為字符串類型String，即用String替換T。

【示例程序C8_1.java】實現(xiàn)Collection接口，并進行簡單操作。

importjava.util.ArrayList;

importjava.util.Arrays;

importjava.util.Collection;

importjava.util.Iterator;

publicclassC8_1{

publicstaticvoidmain(String[?]args){

Character[?]c={‘A’,‘B’,‘C’,‘D’,‘E’}; //創(chuàng)建元素為字符對象的c數(shù)組

System.out.print(“輸出元素為字符對象的c數(shù)組”);

for(inti=0;i<c.length;i++){System.out.print(c[i]+",");}

System.out.println(

);

//創(chuàng)建ArrayList，并轉(zhuǎn)型為Collection

//Arrays.asList(c)表示c數(shù)組的元素是ArrayList的元素

Collection<Character>cl=newArrayList<Character>(Arrays.asList(c));

cl.add((Character)'f?'); //添加一個元素

System.out.println("輸出集合中添加f后的所有元素"+cl);

cl.remove((Character)'B'); //刪除一個元素

System.out.println("用迭代器輸出集合中刪除B后的所有元素");

Iterator<Character>it=cl.iterator(?); //創(chuàng)建一個迭代器對象

while(it.hasNext(?)) //判斷迭代器中是否有下一個元素

{Characteri=it.next(?); //取下一個元素

System.out.print(i+",");

}

System.out.println(?);

Object[?]cc=cl.toArray(?);

System.out.print("輸出集合轉(zhuǎn)數(shù)組后數(shù)組的所有元素:");

for(inti=0;i<c.length;i++){System.out.print(cc[i]+",");}

System.out.println(?);

}

}該程序的運行結(jié)果如下：

輸出元素為字符對象的c數(shù)組A,B,C,D,E,

輸出集合中添加f后的所有元素[A,B,C,D,E,f]

用迭代器輸出集合中刪除B后的所有元素

A,C,D,E,f,

輸出集合轉(zhuǎn)數(shù)組后數(shù)組的所有元素:A,C,D,E,f,

程序說明：程序中的語句

Collection<Character>cl=newArrayList<Character>(Arrays.asList(c));表示Collection中的元素類型是Character。這是一種泛型構(gòu)造方法，通過使用泛型，我們可以在集合中存儲自己定義的類的對象。ArrayList類可以創(chuàng)建如同Java數(shù)組那樣的容器，具體內(nèi)容見8.4.1節(jié)。

8.4List接口與實現(xiàn)類

List接口是Collection接口的子接口，它是Collection的有序集合，為實現(xiàn)線性結(jié)構(gòu)提供了一個框架，提供了線性表的順序存儲和鏈接存儲兩類存儲結(jié)構(gòu)。實現(xiàn)List的通用類是ArrayList類和LinkedList類。8.4.1List接口簡介

從圖8.5中可以看出，List接口繼承了Collection接口，因此它包含了Collection接口的所有方法。實現(xiàn)List的通用類是ArrayList類和LinkedList類。需要注意的是，這兩個類沒有同步的方法，如果多個線程同時訪問一個List，則必須自己實現(xiàn)訪問的同步。

(1)?ArrayList類。它采用數(shù)組來存儲線性表的元素，是線性表的順序存儲結(jié)構(gòu)。因此，它的隨機訪問速度快，對中間元素的插入、刪除操作速度慢。它與Java數(shù)組的主要區(qū)別是數(shù)組作為容器大小是不可變的，而ArrayList作為容器大小是可變的。由于ArrayList內(nèi)部封裝了數(shù)組，所以數(shù)組的執(zhí)行效率比ArrayList高。

(2)?LinkedList類。它采用鏈接存儲結(jié)構(gòu)來存儲線性表中的元素。由鏈接存儲結(jié)構(gòu)的特點可知，它適用于元素的插入、刪除操作，或者說執(zhí)行插入、刪除元素操作的效率較高。

在List接口中增加的特有的操作如下。

1)添加元素

voidadd(int

index,E

element)：插入一個元素到指定位置。

booleanaddAll(int

index,Collection<?extendsE>

c)：插入集合中的所有元素到指定位置。其中：E

element表示一個元素，E表示該元素element的類型變量(泛型類型，例如E為Integer)；<?extendsE>表示未知類型是E的子類型或E類型，符號“?”稱為通配符，是未知類型，E是泛型類型；c表示包含要添加到此列表的元素的Collection。

2)刪除元素

Eremove(int

index)：刪除列表中指定位置的元素。

3)獲取

Eget(int

index)：返回列表中指定位置的元素。

intindexOf(Object

o)：獲取列表中第一次出現(xiàn)的指定元素的下標；如果該元素不存在，則返回?-1。

intlastIndexOf(Object

o)：獲取列表中最后出現(xiàn)的指定元素的下標；如果該元素不存在，則返回?-1。

4)修改

Eset(int

index,E

element)：用指定元素替換列表中指定位置的元素。

5)迭代器

ListIterator<E>listIterator(

)：列表迭代器。

ListIterator<E>listIterator(int

index)：從列表的指定位置開始迭代。

下面用示例程序來說明。

【示例程序C8_f2.java】E泛型類型的簡單操作。

importjava.util.ArrayList;

publicclassC8_f2<E>extendsArrayList<E>

{

voidswap(inti,intj)

{

Etemp=this.get(i);

this.set(i,this.get(j));

this.set(j,temp);

}

publicstaticvoidmain(String[?]args)

{

C8_f2<String>list=newC8_f2<String>(?);//創(chuàng)建字符串類型對象

list.add("a1");

list.add("b1");

System.out.println(list.get(0)+""+list.get(1));

list.swap(0,1);

System.out.println(list.get(0)+""+list.get(1));

}

}該程序的運行結(jié)果如下：

a1b1

b1a1

程序中C8_f2類名之后的<E>告訴編譯器E是一個參數(shù)化的類型，在類被使用時將會被實際類型替換，類型變量E常用在集合中。在程序的main(?)方法中，“C8_f2<String>list=newC8_f2<String>();”語句用于創(chuàng)建字符串類型對象，此時E為字符串類型。

【示例程序C8_2.java】實現(xiàn)List接口，并進行簡單操作。

importjava.util.ArrayList;

importjava.util.List;

publicclassC8_2

{

publicstaticvoidmain(String[?]args)

{

//創(chuàng)建ArrayList，并轉(zhuǎn)型為List

List<String>cl=newArrayList<String>();

cl.add(“A1”);cl.add(“B2”);cl.add(“C3”);

System.out.println(“輸出集合的所有元素”+cl);

cl.add(1,"f1"); //下標1的位置插入一個元素

System.out.println("元素下標1的位置插入f1后，輸出所有元素"+cl);

Stringb="B2";

intn=cl.indexOf(b); //查找指定元素的下標

cl.remove(n); //刪除指定下標的元素

System.out.println("n="+n+"刪除n元素后輸出集合中所有元素");

for(inti=0;i<cl.size(?);i++){System.out.print(cl.get(i)+",");}

System.out.println(?);

}

}該程序的運行結(jié)果如下：

輸出集合的所有元素[A1,B2,C3]

元素下標1的位置插入f1后，輸出所有元素[A1,f1,B2,C3]

n=2刪除n元素后輸出集合中所有元素

A1,f1,C3,8.4.2ArrayList類

ArrayList類使用數(shù)組來實現(xiàn)AbstractList類，實現(xiàn)List接口。下面用示例程序來說明。

【示例程序C8_3.java】創(chuàng)建ArrayList，并進行簡單操作。

packagech8;

importjava.util.ArrayList;

publicclassC8_3{

publicstaticvoidmain(String[?]args)

{//創(chuàng)建ArrayList

ArrayList<Integer>nl=newArrayList<Integer>();

nl.add((Integer)1);

nl.add((Integer)2);

nl.add((Integer)3);

System.out.println("輸出集合的所有元素"+nl);

System.out.println("輸出下標為2的元素:"+nl.get(2));

nl.add(1,(Integer)4); //下標1的位置插入一個元素

System.out.println("元素下標1的位置插入4后，輸出所有元素"+nl);

Integerb=(Integer)1;

intn=nl.indexOf(b); //查找指定元素的下標

nl.remove(n); //刪除指定下標的元素

System.out.println("n="+n+"刪除n元素后輸出集合中所有元素");

for(Integeri:nl){System.out.print(i+",");}

System.out.println(?);

}

}該程序的運行結(jié)果如下：

輸出集合的所有元素[1,2,3]

輸出下標為2的元素：3

元素下標1的位置插入4后，輸出所有元素[1,4,2,3]

n=0刪除n元素后輸出集合中所有元素

4,2,3,8.4.3LinkedList類

LinkedList使用雙向循環(huán)鏈表結(jié)構(gòu)實現(xiàn)了AbstractSequentialList類和List接口。LinkedList類除實現(xiàn)了

AbstractSequentialList類及List接口的所有操作外，還提供了用作棧(stack)、隊列(queue)或雙向隊列(deque)的操作。LinkedList類中特有的操作方法如下。

1)添加元素

voidaddFirst(Ee)：將指定元素插入此列表的開頭。

voidaddLast(Ee)：將指定元素添加到此列表的結(jié)尾。

booleanofferFirst(Ee)：在此列表的開頭插入指定的元素。

booleanofferLast(Ee)：在此列表的結(jié)尾插入指定的元素。

2)刪除元素

EremoveFirst(?)：移除并返回此列表的第一個元素。

EremoveLast(?)：移除并返回此列表的最后一個元素。

EpollFirst(?)：獲取并移除此列表的第一個元素；如果此列表為空，則返回null。

EpollLast(?)：獲取并移除此列表的最后一個元素；如果此列表為空，則返回null。

3)獲取元素

EgetFirst(?)：返回此列表的第一個元素。

EgetLast(?)：返回此列表的最后一個元素。

EpollFirst(?)：獲取并移除此列表的第一個元素；如果此列表為空，則返回null。

EpollLast(?)：獲取并移除此列表的最后一個元素；如果此列表為空，則返回null。

4)棧(stack)操作

voidpush(Ee)：將元素推入此列表所表示的堆棧。

Epop(?)：從此列表所表示的堆棧處彈出一個元素。

Epeek(?)：獲取但不移除此列表的頭(第一個元素)。

下面通過一個程序來說明。

【示例程序C8_4.java】用LinkedList實現(xiàn)一個棧(stack)，并進行棧的基本操作。

packagech8;

importjava.util.LinkedList;

publicclassC8_4extendsLinkedList

{

publicstaticvoidmain(String[?]args)

{C8_4stack=newC8_4(?);

stack.push("a1"); //入棧操作

stack.push(“a2”);

stack.push(“a3”);

System.out.println(stack.pop(?)); //出棧操作

System.out.println(stack.peek(?)); //取棧頂元素操作

System.out.println(stack.pop(?)); //出棧操作

System.out.println(stack.isEmpty(?)); //判斷?？詹僮?/p>

}

}

該程序的運行結(jié)果如下：

a3a2a2false

【示例程序C8_5.java】用LinkedList實現(xiàn)隊列(queue)，并進行隊列的基本操作。

packagech8;

importjava.util.LinkedList;

publicclassC8_5extendsLinkedList

{

publicstaticvoidmain(String[?]args)

{C8_5queue=newC8_5(?);

queue.addLast(“a11”); //入隊操作

queue.addLast(“a22”);

queue.addLast("a33");

System.out.println(queue.removeFirst(?)); //出隊操作

System.out.println(queue.getFirst(?)); //取隊頭元素操作

System.out.println(queue.removeFirst(?));

System.out.println(queue.isEmpty(?)); //判斷隊空操作

}

}

該程序的運行結(jié)果如下：

a11a22a22false

8.5Set接口

8.5.1Set接口簡介

Set是不保存重復(fù)元素的Collection。Set接口模擬數(shù)學上的集合概念，為實現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的集合提供了一個框架。Set接口只包含從Collection接口繼承的方法，并且增加了禁止重復(fù)元素的限制。實現(xiàn)Set接口的通用類是HashSet、LinkedHashSet和TreeSet類。使用時注意這三個類沒有同步機制。

(1)HashSet類。HashSet采用hashCode算法(散列函數(shù))存放元素，元素的存放順序與插入順序無關(guān)。HashSet是為快速查找而實現(xiàn)的Set。

(2)?TreeSet類。TreeSet類采用紅黑樹數(shù)據(jù)結(jié)構(gòu)對元素排序，是保持元素字母排列順序的Set。它的查找速度比HashSet慢。

(3)?LinkedHashSet類。LinkedHashSet是HashSet的子類，它的內(nèi)部使用散列以加快查詢速度，同時使用鏈表維護元素的排序。它是保證元素插入順序的Set。LinkedHashSet在迭代訪問Set中的全部元素時，性能比HashSet好，但是插入時性能稍微遜色于HashSet。

下面用示例程序來說明。

【示例程序C8_6.java】實現(xiàn)Set接口，并進行簡單操作。

importjava.util.HashSet;

importjava.util.Iterator;

importjava.util.Set;

publicclassC8_6

{

privatestaticvoidload(Setset)

{

set.add(“Cu”); set.add(“Ir”); set.add(“La”);

set.add(“Om”); set.add(“Pe”);set.add(“Cu”);

}

privatestaticvoiddump(Setset)

{

Iterator<Character>it=set.iterator(?);

while(it.hasNext(?))

{System.out.print(it.next(?)+",");}

System.out.println("set.size(?)="+set.size(?));

}

publicstaticvoidmain(String[?]args)

{

Set<String>set1=newHashSet<String>(?);//?HashSet轉(zhuǎn)型為Set

load(set1);dump(set1);

}

}該程序的運行結(jié)果如下：

Pe,Om,Cu,La,Ir,set.size(

)=5

注意：程序中的Set不保存重復(fù)元素，不保證元素的插入順序。

【示例程序C8_7.java】用Set進行簡單的并、交、差操作。

importjava.util.HashSet;

importjava.util.Set;

publicclassC8_7{

publicstaticvoidmain(String[?]args)

{Set<String>set1=newHashSet<String>(?);

Set<String>set2=newHashSet<String>(?);

Set<String>set3=newHashSet<String>(?);

set1.add("Sa");set1.add("Mi");set1.add("Ji");set1.add("Vi");

set3.add("Sa");set3.add("Mi");set3.add("Ti");

set2.addAll(set1);//將set1的元素全部添加到set2中

System.out.println("set1="+set1);

System.out.println("set2="+set2);

System.out.println("set3="+set3);

set1.add("Cu");set1.add("Po");

System.out.println("添加元素后的set1="+set1);

System.out.println("判斷set2是否是set1的子集:"+set1.containsAll(set2));

set3.removeAll(set2); //將set3轉(zhuǎn)換為set3和set2的差集

System.out.println("將set3轉(zhuǎn)換為set3和set2的差集:"+set3);

set3.addAll(set2); //將set3轉(zhuǎn)換為set3和set2的并集

System.out.println("將set3轉(zhuǎn)換為set3和set2的并集:"+set3);

set3.retainAll(set2); //將set3轉(zhuǎn)換為set3和set2的交集

System.out.println("將set3轉(zhuǎn)換為set3和set2的交集:"+set3);

}

}該程序的運行結(jié)果如下：

set1=[Mi,Ji,Vi,Sa]

set2=[Mi,Ji,Vi,Sa]

set3=[Mi,Ti,Sa]

添加元素后的set1=[Mi,Ji,Po,Cu,Vi,Sa]

判斷set2是否是set1的子集：true

將set3轉(zhuǎn)換為set3和set2的差集：[Ti]

將set3轉(zhuǎn)換為set3和set2的并集：[Mi,Ji,Ti,Vi,Sa]

將set3轉(zhuǎn)換為set3和set2的交集：[Mi,Ji,Vi,Sa]

【示例程序C8_8.java】HashSet、LinkedHashSet及TreeSet輸出結(jié)果的比較。

packagech8;

importjava.util.*;

publicclassC8_8{

publicstaticvoidmain(String[?]args)

{LinkedHashSet<String>s1=newLinkedHashSet<String>(?);

HashSet<String>s2=newHashSet<String>(?);

TreeSet<String>s3=newTreeSet<String>(?);

String[?]str={“B”,“A”,“C”,“D”};

Collection<String>list=newArrayList<String>(Arrays.asList(str));

s1.addAll(list);//將list的元素全部添加到s1中

s2.addAll(list);//將list的元素全部添加到s2中

s3.addAll(list);//將list的元素全部添加到s3中

System.out.println(“s1=”+s1);

System.out.println(“s2=”+s2);

System.out.println(“s3=”+s3);

}

}

該程序的運行結(jié)果如下：

s1=[B,A,C,D]s2=[D,A,B,C]s3=[A,B,C,D]從輸出的結(jié)果可以看出，由于s1是用LinkedHashSet構(gòu)造的，其輸出保持了原來的次序；s2是用HashSet構(gòu)造的，輸出結(jié)果與原來的次序有所不同；s3是用TreeSet構(gòu)造的，其輸出結(jié)果是對元素按字母的升序排列的。8.5.2SortedSet接口

SortedSet接口是Set接口的子接口，是一種按升序維護其元素的Set。它是根據(jù)元素的自然順序進行排序(自然排序)的，或者根據(jù)在創(chuàng)建SortedSet時提供的Comparator進行排序(定制排序)。實現(xiàn)SortedSet接口的類是TreeSet類。SortedSet接口除了繼承Set接口的操作外，還提供了如下一些操作。

(1)?Comparator<?superE>comparator()：返回對此Set中的元素進行排序的比較器，如果此Set使用其元素的自然順序，則返回null。其中，<?superE>表示未知類型是E的超類型或E類型；符號“?”稱為通配符，是未知類型；E是泛型類型。

(2)?Efirst()：返回集合中的第一個元素。

(3)?Elast()：返回集合中的最后一個元素。

(4)?SortedSet<E>headset(EtoElement)：返回此Set中元素值嚴格小于toElement的元素子集。

(5)?SortedSet<E>subset(EfromElement，EtoElement)：返回此Set的子集合，范圍從fromElement(包括)到toElement(不包括)。

下面用示例程序來說明。

【示例程序C8_9.java】用SortedSet進行簡單操作。

packagech8;

importjava.util.*;

publicclassC8_9{

publicstaticvoidmain(String[?]args)

{SortedSet<String>set1=newTreeSet<String>();

String[?]str={"B","A","C","D"};

Collection<String>list=newArrayList<String>(Arrays.asList(str));

set1.addAll(list);//將s1元素全部添加到s2中

System.out.println("set1="+set1);

System.out.println("headSet('C')="+set1.headSet("C"));

System.out.println("subSet('B','D')="+set1.subSet("B","D"));

System.out.println(“first(?)=”+set1.first(?));

System.out.println(“l(fā)ast(?)=”+set1.last(?));

}

}

該程序的運行結(jié)果如下：

set1=[A,B,C,D]

headSet(‘C’)=[A,B]

subSet(‘B’,‘D’)=[B,C]

first(?)=A

last(?)=D

8.6Map接口

8.6.1Map接口簡介

Map接口與Collection接口無繼承關(guān)系。Map作為一個映射集合，每一個元素包含key-value對(鍵-值對)。Map中的value(值)對象可以重復(fù)，但key(鍵)不能重復(fù)。Map也被稱為關(guān)聯(lián)數(shù)組，因為它們可以用兩個并列數(shù)組加以實現(xiàn)：鍵處在一個數(shù)組中，值處在另一個數(shù)組中。實現(xiàn)Map接口常用的通用類是HashMap、TreeMap和LinkedHashMap類。使用時應(yīng)注意這三個類沒有同步機制。

(1)?HashMap類。HashMap類與HashSet類基本相同，都采用hashCode算法(散列函數(shù))對元素進行排序。HashMap不保證元素的插入順序，是為快速查找而設(shè)計的Map。

(2)TreeMap類。TreeMap類與TreeSet類基本相同，都采用紅黑樹數(shù)據(jù)結(jié)構(gòu)對元素排序。TreeMap按key保持元素的字母排列順序，它的查找速度比HashMap慢。

(3)?LinkedHashMap類。LinkedHashMap類與LinkedHashSet類基本相同，它是HashMap的子類，它的內(nèi)部使用散列以加快查詢速度，同時使用鏈表維護元素的排序。它是保證元素插入順序的Map。LinkedHashMap在迭代訪問Map中的全部元素時，性能比HashMap好，但是插入時性能稍微遜色于HashMap。8.6.2Map接口的常用操作

1．添加、刪除操作

Vput(K

key,V

value)：將指定的值value與此映射中的指定鍵key關(guān)聯(lián)。

Vremove(Object

key)：如果存在一個鍵的映射關(guān)系，則將其從此映射中移除。

voidputAll(Map<?extendsK,?extendsV>

m)：從指定映射中將所有映射關(guān)系復(fù)制到此映射中。

voidclear(?)：從此映射中移除所有映射關(guān)系。

其中，K表示鍵變量泛型類型，V表示值變量泛型類型。

2．查詢操作

Vget(Objectkey)：返回指定鍵key所映射的值；如果此映射不包含該鍵的映射關(guān)系，則返回null。

booleancontainsKey(Objectkey)：判斷映射中是否存在關(guān)鍵字key。

booleancontainsValue(Objectvalue)：判斷映射中是否存在值value。

intsize(?)：返回此映射中的鍵-值映射關(guān)系數(shù)。

booleanisEmpty(?)：判斷此映射是否存在映射關(guān)系。

3．處理映射中鍵/值對組的視圖操作

Set<K>keySet(?)：返回此映射中包含的鍵的Set視圖。

Collection<V>values(?)：返回此映射中包含的值的Collection視圖。

Set<Map.Entry<K,V>>entrySet(?)：返回此映射中包含的映射關(guān)系的Set視圖。8.6.3Map.Entry接口的常用操作

Map.Entry是Map內(nèi)部定義的一個接口，專門用來存儲key-value(鍵-值)對。常用的方法如下：

(1)?KgetKey(?)：返回與此項對應(yīng)的鍵。

(2)?VgetValue(?)：返回與此項對應(yīng)的值。

(3)?VsetValue(Objectvalue)：用指定的值替換與此項對應(yīng)的值。

(4)?booleanequals(Object

ob)

：比較指定對象ob與此項的相等性。

(5)?Map.entrySet(?)：返回映射的Set視圖。下面用示例程序來說明。

【示例程序C8_10.java】實現(xiàn)Map的添加元素和讀取元素操作。

importjava.util.*;

publicclassC8_10{

publicstaticvoidmain(String[?]args){

Map<String,String>map=newHashMap<String,String>(?);

map.put(“書”,“Java”);

map.put(“學生”,“張麗”);

map.put(“班級”,“201201”);

System.out.println("map=:"+map.toString(?)); //輸出Map

if(map.containsKey("書")) //查找是否存在Key=書

{

System.out.print("查找Key=書存在");

Stringval=map.get("書"); //根據(jù)Key求出value

System.out.println("書="+val);

}

else{System.out.println("查找Key=書不存在");}

//全部輸出Key

Set<String>keys=map.keySet(?); //得到全部的key

Iterator<String>iter1=keys.iterator(?);

System.out.print("全部的key：");

while(iter1.hasNext(?)){

Stringstr=iter1.next(?);

System.out.print(str+"、");

}

Collection<String>values=map.values(?); //得到全部的value

Iterator<String>iter2=values.iterator(?);

System.out.print("\n全部的value：");

while(iter2.hasNext(?)){

Stringstr=iter2.next(?);

System.out.print(str+"、");

}

System.out.println();

}

}該程序的運行結(jié)果如下：

map=:{學生=張麗,班級=201201,書=Java}

查找Key=書存在書=Java

全部的key：學生、班級、書、

全部的value：張麗、201201、Java、

程序說明：在程序中聲明Map對象的key和value的泛型類型為String，Map不能保證元素的插入順序。不能直接使用Iterator迭代器輸出Map中的全部內(nèi)容。因為Map中的每個位置存放的是key-value，而Iterator中每次只能找到一個值。如果要使用Iterator則必須按照以下步驟完成：

(1)將Map的實例通過entrySet(?)方法變?yōu)镾et接口對象；

(2)通過Set接口實例為Iterator實例化；

(3)通過Iterator迭代輸出，每個內(nèi)容都是Map.Entry的對象；

(4)通過Map.Entry進行key-value的分離。

【示例程序C8_11.java】用Iterator輸出Map的操作。

importjava.util.HashMap;

importjava.util.Iterator;

importjava.util.Map;

importjava.util.Set;

publicclassC8_11{

publicstaticvoidmain(String[?]args){

Map<String,String>map=newHashMap<String,String>(?);

map.put(“書”,“Java”);

map.put(“學生”,“張麗”);

map.put("班級","201201");

Set<Map.Entry<String,String>>allSet=map.entrySet(?);//將Map接口轉(zhuǎn)換為Set接口

Iterator<Map.Entry<String,String>>iter=allSet.iterator(?);

while(iter.hasNext(?)){

Map.Entry<String,String>me=iter.next(?);

System.out.println(me.getKey(?)+“-”+me.getValue(?));

}

}

}

該程序的運行結(jié)果如下：

學生-張麗班級-201201書-Java8.6.4SortedMap接口

SortedMap接口是Map接口的子接口，是排序的Map。實現(xiàn)了此接口的子類都屬于排序的子類。實現(xiàn)該接口的常用的類是TreeMap類。SortedMap除了繼承Map接口的操作外，還提供了一些如表8.2中所示的擴展方法。表8.2SortedMap接口的擴展方法

下面用示例程序來說明。

【示例程序C8_12.java】用TreeMap進行簡單操作。

importjava.util.SortedMap;

importjava.util.TreeMap;

publicclassC8_12{

publicstaticvoidmain(String[?]args)

{SortedMap<String,String>smap=newTreeMap<String,String>(?);

smap.put(“D”,“04”);

smap.put(“A”,“01”);

smap.put(“C”,“03”);

smap.put("B","02");

System.out.println("sortMap="+smap);

System.out.println("headMap('C')="+smap.headMap("C"));

System.out.println("subMap('B','D')="+smap.subMap("B","D"));

System.out.println("first(?)="+smap.firstKey(?));

System.out.println("last(?)="+smap.lastKey(?));

}

}該程序的運行結(jié)果如下：

sortMap={A=01,B=02,C=03,D=04}

headMap(‘C’)={A=01,B=02}

subMap(‘B’,‘D’)={B=02,C=03}

first(?)=A

last(?)=D

8.7Collections算法類

Collection是集合類的接口，是所有集合類的父類，它提供了關(guān)于集合的一些操作，如插入、刪除、遍歷、判斷一個元素是否是其成員等。而Collections是一個算法類，進一步提供一系列的靜態(tài)方法，實現(xiàn)對集合的排序、替換、交換、搜索、拷貝等操作。下面通過幾個示例程序來說明具體的方法及其使用。8.7.1為集合增加元素的addAll(?)方法

使用Collections類中的addAll(Collection<?superT>

c,T…

elements)方法可以將所有指定元素添加到指定Collection中。此方法可以接收可變參數(shù)，所以可以傳遞任意多的參數(shù)作為集合的內(nèi)容。

【示例程序C8_13.java】為集合增加元素。

importjava.util.ArrayList;

importjava.util.Collections;

importjava.util.Iterator;

importjava.util.List;

publicclassC8_13

{

publicstaticvoidmain(String[?]args)

{

List<String>all=newArrayList<String>(?);

Collections.addAll(all,“B”,“E”,“A”); //增加元素

Collections.addAll(all,“D”,“C”);

Iterator<String>iter=all.iterator(?);

while(iter.hasNext(?))

{System.out.print(iter.next(?)+“、”); //迭代輸出}

}

}

該程序的運行結(jié)果如下：

B、E、A、D、C、8.7.2sort(?)和reverse(?)方法

以List為參數(shù)，使用Collections類中的sort(List<T>

list)方法是根據(jù)元素的自然順序?qū)χ付斜戆瓷蜻M行排序，而reverse(List<?>

list)方法用于反轉(zhuǎn)指定列表中元素的順序。sort(List<T>

list,Comparator<?superT>

c)方法是以Comparator比較器為參數(shù)，根據(jù)指定比較器產(chǎn)生的順序?qū)χ付斜磉M行排序。

【示例程序C8_14.java】以List為參數(shù)，利用sort(?)方法和reverse(?)方法對指定列表進行排序。

importjava.util.ArrayList;

importjava.util.Collections;

importjava.util.Iterator;

importjava.util.List;

publicclassC8_14

{

publicstaticvoidmain(String[?]args)

{

List<String>all=newArrayList<String>(?);

Collections.addAll(all,"B","E","A","D","C");

System.out.print("排序之前的集合：");

Iterator<String>iter=all.iterator(?);

while(iter.hasNext(?))

{System.out.print(iter.next(?)+"、");}

Collections.sort(all); //集合排序

System.out.print("\nsort(?)方法排序后的集合：");

iter=all.iterator(?);

while(iter.hasNext(?))

{System.out.print(iter.next(?)+"、")