第十章Java集合框架

1、java集合框架本章內(nèi)容1. java集合框架概述集合框架概述2.list接口以及實(shí)現(xiàn)類接口以及實(shí)現(xiàn)類3.set接口以及實(shí)現(xiàn)類接口以及實(shí)現(xiàn)類4.map接口以及實(shí)現(xiàn)類接口以及實(shí)現(xiàn)類5.boxing/unboxing6.iterator以及以及enumeration接口接口7.collections和和arrays類類集合的概念集合就是將若干用途相同、近似的集合就是將若干用途相同、近似的“數(shù)據(jù)數(shù)據(jù)”結(jié)合成一個(gè)整體。結(jié)合成一個(gè)整體。集合從體系上分為三種：集合從體系上分為三種：(1) 列表列表(list):list集合區(qū)分元素的順序，允許包含相同的元素。集合區(qū)分元素的順序，允許包含相同的元素。(2)

2、集集(set):set集合不區(qū)分元素的順序，不允許包含相同的元集合不區(qū)分元素的順序，不允許包含相同的元素。素。(3) 映射映射(map):map集合保存的集合保存的”鍵鍵”-“值值”對，對，“鍵鍵”不能不能重復(fù)，而且一個(gè)重復(fù)，而且一個(gè)“鍵鍵”只能對應(yīng)一個(gè)只能對應(yīng)一個(gè)“值值”。javajava集合中只能保存引用數(shù)據(jù)類型，也就是保存的是對象的地集合中只能保存引用數(shù)據(jù)類型，也就是保存的是對象的地址，而非對象本身。集合中元素相當(dāng)于引用類型的變量。址，而非對象本身。集合中元素相當(dāng)于引用類型的變量。集合框架的類圖關(guān)系jdk所提供的容器所提供的容器api全部位于全部位于java.util包中。包中。容器容器

3、api的類圖關(guān)系如下：的類圖關(guān)系如下：collection接口中的方法(1) int size();(2) boolean isempty();(3) void clear();(4) boolean contains(object element);(5) boolean add(object element);(6) boolean remove(object element);(7) iterator iterator();(8) boolean containsall(collection c);(9) boolean addall(collection c)(10) boolean

4、removeall(collection c)(11) boolean retainall(collection c)(12) object toarray();list接口list是是collection的子接口，實(shí)現(xiàn)的子接口，實(shí)現(xiàn)list接口的容器中存放的對象接口的容器中存放的對象是有順序的，而且可以重復(fù)是有順序的，而且可以重復(fù)。list容器中存放的對象都有一個(gè)整數(shù)型的序號，記錄該對象在容容器中存放的對象都有一個(gè)整數(shù)型的序號，記錄該對象在容器中的位置，可以根據(jù)序號來訪問容器中的元素。器中的位置，可以根據(jù)序號來訪問容器中的元素。jdk提供實(shí)現(xiàn)提供實(shí)現(xiàn)list接口的類有接口的類有arrayli

5、st、linkedlist、vector等。等。 object get(int index) e set(int index,e obj) void add(int index,object obj) e remove(int index) int indexof(object obj) int lastindexof(object obj)list接口的實(shí)現(xiàn)類-arraylistjava.util.arraylist實(shí)現(xiàn)了實(shí)現(xiàn)了list接口，用于描述長度可變的數(shù)接口，用于描述長度可變的數(shù)組列表組列表(底層采用數(shù)組實(shí)現(xiàn)底層采用數(shù)組實(shí)現(xiàn))。arraylist允許元素取值為允許元素取值為null,

6、提供了一些新增的方法來提供了一些新增的方法來操作操作列表容量的大小列表容量的大小。public arraylist()(默認(rèn)大小是默認(rèn)大小是10)public arraylist(int initialcapacity)public void ensurecapacity(int mincapacity) 確保它至少能夠容納最小容量參數(shù)所指定的元素?cái)?shù)public void trimtosize() 將此 arraylist 實(shí)例的容量調(diào)整為列表的當(dāng)前大小 arraylist舉例 arraylist list=new arraylist(6);list.add(“hello);list.add(

7、new integer(10);list.add(new double(10.5); system.out.println(list.size();object item=list.toarray();for(int i=0;iitem.length;i+) system.out.println(itemi); list.trimtosize(); 見源文件見源文件:arraylist/arraylisttest.javalist接口的實(shí)現(xiàn)類-linkedlistjava.util.linkedlist實(shí)現(xiàn)了實(shí)現(xiàn)了list接口，底層采用鏈表實(shí)現(xiàn)。接口，底層采用鏈表實(shí)現(xiàn)?？梢援?dāng)做可以當(dāng)做隊(duì)列隊(duì)列

8、、棧棧等數(shù)據(jù)結(jié)構(gòu)來使用。等數(shù)據(jù)結(jié)構(gòu)來使用。新增方法：新增方法：(1) void addfirst(object obj)(2) void addlast(object obj)(3) object peek() 獲取但不移除列表的第一個(gè)元素獲取但不移除列表的第一個(gè)元素(4) object poll() 獲取并移除列表中的第一個(gè)元素獲取并移除列表中的第一個(gè)元素(5) object set(int index, object element) 見源文件：見源文件：linkedlist/linkedlist.javaarraylist和linkedlist的比較1在在arraylist的中間插入或刪

9、除一個(gè)元素意味著這個(gè)列表中剩余的元素的中間插入或刪除一個(gè)元素意味著這個(gè)列表中剩余的元素都會被移動；而在都會被移動；而在linkedlist的中間插入或刪除一個(gè)元素的開銷是固定的。的中間插入或刪除一個(gè)元素的開銷是固定的。 2linkedlist不支持高效的隨機(jī)元素訪問，不支持高效的隨機(jī)元素訪問，arraylist支持高效的隨機(jī)訪問。支持高效的隨機(jī)訪問。 3arraylist的空間浪費(fèi)主要體現(xiàn)在在的空間浪費(fèi)主要體現(xiàn)在在list列表的結(jié)尾預(yù)留一定的容量空間，列表的結(jié)尾預(yù)留一定的容量空間，而而linkedlist的空間花費(fèi)則體現(xiàn)在它的每一個(gè)元素都需要消耗相當(dāng)?shù)目臻g的空間花費(fèi)則體現(xiàn)在它的每一個(gè)元素都需要

10、消耗相當(dāng)?shù)目臻g 所以：當(dāng)操作是在所以：當(dāng)操作是在一列數(shù)據(jù)的后面添加數(shù)據(jù)而不是在前面或中間一列數(shù)據(jù)的后面添加數(shù)據(jù)而不是在前面或中間,并且需要并且需要隨機(jī)地訪問其中的元素時(shí)隨機(jī)地訪問其中的元素時(shí),使用使用arraylist會提供比較好的性能會提供比較好的性能；當(dāng)操作是在；當(dāng)操作是在一列數(shù)據(jù)的一列數(shù)據(jù)的前面或中間添加或刪除數(shù)據(jù)前面或中間添加或刪除數(shù)據(jù),并且按照順序訪問其中的元素時(shí)并且按照順序訪問其中的元素時(shí),應(yīng)應(yīng)該使用該使用linkedlist。list接口的實(shí)現(xiàn)類-vectorjava.util.vector實(shí)現(xiàn)了實(shí)現(xiàn)了list接口，用于描述長度可變的數(shù)組向量接口，用于描述長度可變的數(shù)組向量(底層

11、采用數(shù)組實(shí)現(xiàn)底層采用數(shù)組實(shí)現(xiàn))。與與arraylist的區(qū)別：的區(qū)別：vectorvector是線程安全的是線程安全的( (同步同步),),用在多線程環(huán)用在多線程環(huán)境中，運(yùn)行效率慢。境中，運(yùn)行效率慢。arraylistarraylist不是線程安全的，用在單線程不是線程安全的，用在單線程環(huán)境中。環(huán)境中。vector類的新增方法：類的新增方法：public vector()(默認(rèn)大小是默認(rèn)大小是10)void addelement(e obj)e elementat(int index)boolean removeelement(object obj)boolean removeelementa

12、t(int index)void removeallelements()void insertelement(object obj,int index)object toarray()stack類java.util.statck繼承自繼承自vector類，對應(yīng)類，對應(yīng)”first in,last out”的數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)-棧。棧。stack類的常用方法類的常用方法:public statck()public object push(object obj)public object pop()public object peek()public boolean isempty()public

13、 void clear()public int search(object obj) 見源文件見源文件:stack/stacktest.java set接口set接口是接口是collection的子接口，的子接口，set接口沒有提供新增接口沒有提供新增的方法，的方法，但實(shí)現(xiàn)但實(shí)現(xiàn)set接口的容器中元素是沒有順序的且接口的容器中元素是沒有順序的且不可以重復(fù)不可以重復(fù)。set容器可以與數(shù)學(xué)中的容器可以與數(shù)學(xué)中的“集合集合”概念相對應(yīng)。概念相對應(yīng)。jdk中提供的實(shí)現(xiàn)中提供的實(shí)現(xiàn)set接口的類有接口的類有hashset、treeset等。等。hashsethashset 底層采用底層采用 hashma

14、p 來保存所有元素。來保存所有元素。 hashset hs=new hashset(); hs.add(first); hs.add(second); hs.add(third); hs.add(fourth); hs.add(first); hs.add(new date(); system.out.println(哈希表的大小哈希表的大小:+hs.size(); system.out.println(hs); 見源文件見源文件: hashset/hashsettest.java關(guān)于set中的重復(fù)元素思考：思考：set中不能存放重復(fù)的元素，那么請問什么樣的中不能存放重復(fù)的元素，那么請問什么樣

15、的元素屬于重復(fù)元素。元素屬于重復(fù)元素。 見源文件：見源文件：hashset/settest.java set集合中不能存放這樣的元素集合中不能存放這樣的元素: e1.equals(e2)為為true。注意：注意：hashset集合在設(shè)計(jì)時(shí)，為了避免多次調(diào)用集合在設(shè)計(jì)時(shí)，為了避免多次調(diào)用equals方法帶來的效率降方法帶來的效率降低問題，當(dāng)新添加對象時(shí)，首先調(diào)用該對象的低問題，當(dāng)新添加對象時(shí)，首先調(diào)用該對象的hashcode()方法，如果方法，如果hashcode()得到的地址沒有被對象占據(jù)，就將該新對象插入；如果得到的地址沒有被對象占據(jù)，就將該新對象插入；如果hashcode()值已經(jīng)被占用了

16、，再調(diào)用值已經(jīng)被占用了，再調(diào)用equals()方法與占用該位置的對象方法與占用該位置的對象比較，如果為比較，如果為true，這兩個(gè)對象才是認(rèn)為是重復(fù)元素，新對象就不會被添，這兩個(gè)對象才是認(rèn)為是重復(fù)元素，新對象就不會被添加進(jìn)來；如果為加進(jìn)來；如果為false，再利用散列算法放到其它地址上。，再利用散列算法放到其它地址上。 加入到加入到hashset集合中的對象，一定要重寫集合中的對象，一定要重寫equas()和和hashcode()兩個(gè)方法。兩個(gè)方法。hashcode()方法的進(jìn)一步探討 一旦一個(gè)對象加入到一旦一個(gè)對象加入到hashset集合中后，就不集合中后，就不要再改變那些參與計(jì)算該對象要再

17、改變那些參與計(jì)算該對象hashcode值的值的屬性的值了。否則就會改變該對象在屬性的值了。否則就會改變該對象在hashset中的位置，而造成內(nèi)存泄露。中的位置，而造成內(nèi)存泄露。 見源文件：見源文件：hashset/settest3.javaset接口與集合操作相關(guān)的幾個(gè)方法set s1=new hashset();set s2=new hashset();s1.add(a);s1.add(b);s1.add(c);s2.add(b);s2.add(c);s2.add(d);set s3=new hashset(s1);s3.retainall(s2);/求交集求交集set s4=new has

18、hset(s2);s4.addall(s1);/求并集求并集 set s5=new hashset(s1); s5.removeall(s3);/求差求差system.out.println(s3);system.out.println(s4); system.out.println(s5); 見源文件見源文件: hashset/settest2.javaset接口的實(shí)現(xiàn)類-treesettreeset描述的是描述的是set的一個(gè)變體的一個(gè)變體-可實(shí)現(xiàn)排序功可實(shí)現(xiàn)排序功能的集合能的集合。將對象插入到將對象插入到treeset中時(shí)，中時(shí)，會按照某種比較規(guī)會按照某種比較規(guī)則將對象插入到一個(gè)有序序列

19、中則將對象插入到一個(gè)有序序列中，以保證，以保證treeset集合中的對象序列保持集合中的對象序列保持“升序升序”排列。排列。 見源文件：見源文件：treeset/treesettest.javacomparable接口問題：問題：treesettreeset中的排序方法是根據(jù)什么確定對象之間的中的排序方法是根據(jù)什么確定對象之間的”大小大小”關(guān)系呢關(guān)系呢? ?所有可排序的類都實(shí)現(xiàn)了所有可排序的類都實(shí)現(xiàn)了java.lang.comparable接口，該接口接口，該接口中只有一個(gè)抽象方法中只有一個(gè)抽象方法: public int compareto(object obj) 注意：用戶在實(shí)現(xiàn)注意：用戶

20、在實(shí)現(xiàn)compareto()compareto()方法確定比較邏輯時(shí)，比較結(jié)果方法確定比較邏輯時(shí)，比較結(jié)果應(yīng)該和應(yīng)該和equals()equals()方法比較的結(jié)果一致。方法比較的結(jié)果一致。 見源文件見源文件:comparable/treesettest2.java:comparable/treesettest2.javamap接口實(shí)現(xiàn)實(shí)現(xiàn)map接口的類用來存儲接口的類用來存儲”鍵鍵-值值”對對。 可理解為一張二維表，這個(gè)二維表只有兩列，一列是可理解為一張二維表，這個(gè)二維表只有兩列，一列是key，一列是，一列是value。map中存儲的中存儲的“鍵鍵-值值”對由對由鍵來標(biāo)識鍵來標(biāo)識，所以，所以

21、鍵不能重復(fù)鍵不能重復(fù)。map接口的實(shí)現(xiàn)類有接口的實(shí)現(xiàn)類有hashmap和和treemap。map接口的常用方法：接口的常用方法：v put(k key,v value)v get(k key)v remove(k key)boolean containskey(k key)boolean containsvalue(v value)int size()boolean isempty()void putall(map t)void clear()map接口的實(shí)現(xiàn)類-hashmapjava.util.hashmap類實(shí)現(xiàn)了類實(shí)現(xiàn)了java.util.map接口，基接口，基于哈希表實(shí)現(xiàn)于哈希表實(shí)現(xiàn)“

22、鍵鍵”-“值值”對的映射關(guān)系。對的映射關(guān)系。hashmap不確定不確定“k”-”value”對的先后順序，允許對的先后順序，允許使用使用null “k”和和null”value”。影響影響hashmap性能的兩個(gè)因素：性能的兩個(gè)因素： 初始容量初始容量(initial capacity) 加載因子加載因子(load factor) (小于小于1的數(shù)的數(shù)) 見源文件見源文件: hashmap/hashmaptest1.javamap接口的實(shí)現(xiàn)類-hashtable java.util.hashtable實(shí)現(xiàn)了實(shí)現(xiàn)了java.util.map接口，也是接口，也是采用哈希表的形式將采用哈希表的形式將

23、”key”映射到映射到”value”，用法，用法與與hashmap基本相同。基本相同。 hashmap與與hashtable的區(qū)別：的區(qū)別： (1) hashtable中的中的“key”和和“value”都不允許都不允許null，而，而hashmap允許。允許。 (2) hashtable是線程安全是線程安全的，適合在多用戶環(huán)境中使用，效率的，適合在多用戶環(huán)境中使用，效率稍低；稍低；hashmap不是線程安全的不是線程安全的，效率稍高，適合在單線程，效率稍高，適合在單線程環(huán)境下使用。環(huán)境下使用。map接口-練習(xí)1. 結(jié)合結(jié)合map接口來統(tǒng)計(jì)字符串?dāng)?shù)組中不同字符串的個(gè)數(shù)。接口來統(tǒng)計(jì)字符串?dāng)?shù)組中不

24、同字符串的個(gè)數(shù)。(字符串?dāng)?shù)組由字符串?dāng)?shù)組由main()方法的參數(shù)獲方法的參數(shù)獲取取) for(int i=0;iargs.length;i+) if(!m1.containskey(argsi) m1.put(argsi,1); 見源文件見源文件:hashmap/maptest1.java2. 結(jié)合結(jié)合map接口來統(tǒng)計(jì)字符串?dāng)?shù)組中不同字符串的個(gè)數(shù)接口來統(tǒng)計(jì)字符串?dāng)?shù)組中不同字符串的個(gè)數(shù),輸出這些不同的字符串和輸出這些不同的字符串和出現(xiàn)的次數(shù)。出現(xiàn)的次數(shù)。(字符串?dāng)?shù)組由字符串?dāng)?shù)組由main()方法的參數(shù)獲取方法的參數(shù)獲取) for(int i=0;iargs.length;i+) if(!m1.c

25、ontainskey(argsi) m1.put(argsi,1); else int count=m1.get(argsi); m1.put(argsi,count+1); 見源文件見源文件:hashmap/maptest2.javaiterator接口iterator(稱作迭代器稱作迭代器)接口主要提供了對容器中元接口主要提供了對容器中元素進(jìn)行遍歷的方法。素進(jìn)行遍歷的方法。所有實(shí)現(xiàn)了所有實(shí)現(xiàn)了collection接口的類都有一個(gè)接口的類都有一個(gè)iterator()方法來返回一個(gè)實(shí)現(xiàn)了方法來返回一個(gè)實(shí)現(xiàn)了iterator接口接口的類的對象。的類的對象。 該接口中定義了如下抽象方法：該接口中定

26、義了如下抽象方法：iterator接口boolean hasnext() /判斷游標(biāo)右邊是否還有元素判斷游標(biāo)右邊是否還有元素object next()/返回游標(biāo)右邊的元素并將游標(biāo)移動到該元素后返回游標(biāo)右邊的元素并將游標(biāo)移動到該元素后void remove() /刪除游標(biāo)左邊的元素，通常在刪除游標(biāo)左邊的元素，通常在next()方法之后執(zhí)行，只執(zhí)行一方法之后執(zhí)行，只執(zhí)行一次。次。iterator接口舉例 collection c=new arraylist(); c.add(hello world); c.add(new integer(100); c.add(new float(99.9f);

27、iterator it=c.iterator(); while(it.hasnext() object obj=it.next(); system.out.println(obj); it.remove(); system.out.println(c); 見源文件見源文件:iterator/iteratortest.javaenumeration接口enumeration接口的功能與接口的功能與iterator接口類似，也能夠接口類似，也能夠?qū)现械脑剡M(jìn)行遍歷。對集合中的元素進(jìn)行遍歷。但是但是enumeration接口接口只對只對vector、hashtable類提供遍歷方法，并且不類提供

28、遍歷方法，并且不支持移除操作。支持移除操作。 boolean hasmoreelements() /判斷此枚舉中是否有下一個(gè)元素判斷此枚舉中是否有下一個(gè)元素 object nextelement() /返回枚舉中的下一個(gè)元素返回枚舉中的下一個(gè)元素 見源文件：見源文件：enumeraiton/enumerationtest.javalist常用算法-由collections類實(shí)現(xiàn)java.util.collections類提供了一些類提供了一些靜態(tài)靜態(tài)方法，實(shí)現(xiàn)了基于方法，實(shí)現(xiàn)了基于list容容器器的常用算法。的常用算法。void sort(list list) 對容器內(nèi)的元素進(jìn)行升序排序?qū)θ萜?/p>

29、內(nèi)的元素進(jìn)行升序排序void reverse(list list) 對容器內(nèi)的元素進(jìn)行逆序排列對容器內(nèi)的元素進(jìn)行逆序排列void shuffle(list list) 對對list容器內(nèi)的元素進(jìn)行隨機(jī)排列容器內(nèi)的元素進(jìn)行隨機(jī)排列void fill(list list,object obj) 對特定的對象來填充對特定的對象來填充listvoid copy(list des,list src) 將將src容器中的內(nèi)容拷貝到容器中的內(nèi)容拷貝到des容器中容器中object max(colletion c) object min(collection c)void rotate(list list,int distance) 對列表中元素按對列表中元素按distance進(jìn)行移位操作進(jìn)行移位操作int binarysearch(list list,object obj)采用折半查找在采用折半查找在list中尋找中尋找obj對象，返回這個(gè)對象在容器中的位置對