《JAVA語言程序設(shè)計(jì)教程》課件第6章

第6章泛型與集合6.1泛型6.2集合類概述6.3List實(shí)現(xiàn)6.4Set實(shí)現(xiàn)6.5Map實(shí)現(xiàn)6.6ArrayList<E>泛型類6.7LinkedList<E>泛型類6.8HashSet<E>泛型類6.9TreeSet<E>泛型類6.10HashMap<K,V>泛型類

6.1泛型

在編程中，即使再仔細(xì)地設(shè)計(jì)、編寫代碼和測試，bug總還是會(huì)出現(xiàn)。有些bug可以在編譯時(shí)被檢測到，編譯器會(huì)給出錯(cuò)誤提示，會(huì)相對(duì)容易解決。而有些bug，只有在程序運(yùn)行時(shí)才會(huì)出現(xiàn)，而且出現(xiàn)運(yùn)行錯(cuò)誤時(shí)的運(yùn)行代碼未必是bug的準(zhǔn)確位置，bug往往在運(yùn)行錯(cuò)誤之前的某處，這類bug比較難查找。

自從Java5開始，Java引入了泛型(Generics)。泛型將類型變?yōu)橐环N參數(shù)，可以讓一些bug在編譯時(shí)被檢測到，使程序更穩(wěn)定。此外，泛型可以增加代碼的重用性。6.1.1泛型的作用

與非泛型的代碼相比，使用泛型的代碼有如下優(yōu)點(diǎn)。

1.編譯時(shí)更強(qiáng)的類型檢查

對(duì)于泛型代碼，Java編譯器可以進(jìn)行強(qiáng)類型檢查。如果代碼中數(shù)據(jù)類型不準(zhǔn)確，會(huì)引起編譯錯(cuò)誤，這樣有利于在編譯時(shí)發(fā)現(xiàn)bug并修復(fù)。在編譯時(shí)修復(fù)bug要比運(yùn)行時(shí)容易，因?yàn)檫\(yùn)行時(shí)的bug一般較難定位。

2.無需類型轉(zhuǎn)換

下面的代碼沒有使用泛型，需要進(jìn)行數(shù)據(jù)類型的轉(zhuǎn)換：

Listlist=newArrayList();

list.add(“hello”);

Strings=(String)list.get(0);//取出的元素需轉(zhuǎn)為String類型如果使用泛型重寫這段代碼，那將不需要類型轉(zhuǎn)換：

List<String>list=newArrayList<String>();//使用泛型

list.add(“hello”);

Strings=list.get(0);//無類型轉(zhuǎn)換

3.增加代碼重用性

使用泛型后，程序員可以針對(duì)不同的數(shù)據(jù)類型，設(shè)計(jì)通用的算法。這樣的算法是類型安全的，重用性高，也易于使用。6.1.2泛型類

先使用一個(gè)簡單的例子演示如何定義泛型類。如果我們要定義一個(gè)Box類，里面可以存放任何一種類型的實(shí)例，且它只需要兩個(gè)方法set()和get()。set()方法用來添加一個(gè)對(duì)象，get()方法獲取這個(gè)對(duì)象。如果使用非泛型類，代碼如下：因?yàn)锽ox類能夠接收任何類型，你可以傳遞各種非基本類型的參數(shù)進(jìn)來。在編譯代碼時(shí)，是無法驗(yàn)證數(shù)據(jù)的類型是否正確的。假如你使用set()方法傳入一個(gè)StringBuilder對(duì)象，然后使用get()方法獲取到Box里面的對(duì)象后，需要將類型強(qiáng)制轉(zhuǎn)回StringBuilder，但由于粗心，錯(cuò)將類型強(qiáng)制轉(zhuǎn)為StringBuffer。這樣的錯(cuò)誤，在編譯時(shí)是無法檢測到的。泛型類的定義如下：

classname<T1,T2,...,Tn>{/*...*/}

在類名的后面，尖括號(hào)<>內(nèi)的內(nèi)容為類型參數(shù)，可以定義多個(gè)類型參數(shù)。對(duì)于前面例子中的Box類，如定義成泛型類，需要將“publicclassBox”改寫為“publicclassBox<T>”。Box泛型類的定義如下：

publicclassBox<T>{

privateTt;

publicvoidset(Tt){this.t=t;}

publicTget(){returnt;}

}可以看出Box泛型類與非泛型類大致相同，唯一不同的地方是將所有的Object類型改寫為了T類型。T可以是任何非基本數(shù)據(jù)類型，如類、接口、數(shù)組等，但不可是基本數(shù)據(jù)類型(如int和double等)。

使用了泛型，編譯器可以在編譯時(shí)檢查數(shù)據(jù)類型的一致性，盡可能在編譯時(shí)發(fā)現(xiàn)bug，而不是留到運(yùn)行時(shí)出錯(cuò)。程序運(yùn)行結(jié)果如圖6.1所示。

圖6.1例6-1輸出結(jié)果

6.2集?合?類?概?述

Java中的集合類可以分為兩大類：一類是實(shí)現(xiàn)Collection接口；另一類是實(shí)現(xiàn)Map接口。Collection是一個(gè)基本的集合接口，Collection中可以容納一組集合元素(Element)。Map沒有繼承Collection接口，與Collection是并列關(guān)系。Map提供鍵(key)到值(value)的映射。一個(gè)Map中不能包含相同的鍵，每個(gè)鍵只能映射一個(gè)值。

Collection有兩個(gè)重要的子接口List和Set。List表達(dá)一個(gè)有序的集合，List中的每個(gè)元素都有索引，使用此接口能夠準(zhǔn)確的控制每個(gè)元素插入的位置。用戶也能夠使用索引來訪問List中的元素，List類似于Java的數(shù)組。

Set接口的特點(diǎn)是不能包含重復(fù)的元素。對(duì)Set中任意的兩個(gè)元素element1和element2都有element1.equals(element2)=false。另外，Set最多有一個(gè)null元素。此接口模仿了數(shù)學(xué)上的集合

概念。

Collection接口、List接口、Set接口以及相關(guān)類的關(guān)系如圖6.2所示。圖6.2Collection接口以及相關(guān)的子接口和類如前面提到的，Map接口與Collection接口不同，Map提供鍵到值的映射。Map接口提供三種Collection視圖，允許以鍵集、值集或鍵—值映射關(guān)系集的形式查看某個(gè)映射的內(nèi)容。Map接口及其相關(guān)類的關(guān)系如圖6.3所示。圖6.3Map接口以及相關(guān)的類使用Java提供的集合類有如下好處：

(1)降低編程難度：在編程中會(huì)經(jīng)常需要鏈表、向量等集合類，如果自己動(dòng)手寫代碼實(shí)現(xiàn)這些類，需要花費(fèi)較多的時(shí)間和精力。調(diào)用Java中提供的這些接口和類，可以很容易的處理數(shù)據(jù)。

(2)提升程序的運(yùn)行速度和質(zhì)量：Java提供的集合類具有較高的質(zhì)量，運(yùn)行時(shí)速度也較快。使用這些集合類提供的數(shù)據(jù)結(jié)構(gòu)，程序員可以從“重復(fù)造輪子”中解脫出來，將精力專注于提升程序的質(zhì)量和性能。

(3)無需再學(xué)習(xí)新的API：借助泛型，只要了解了這些類的使用方法，就可以將它們應(yīng)用到很多數(shù)據(jù)類型中。如果知道了LinkedList<String>的使用方法，那么當(dāng)然也會(huì)知道LinkedList<Double>怎么用，無需為每一種數(shù)據(jù)類型學(xué)習(xí)不同的API。

(4)增加代碼重用性：也是借助泛型，就算對(duì)集合類中的元素類型進(jìn)行了修改，集合類相關(guān)的代碼也幾乎不用修改。

6.3List實(shí)現(xiàn)

在List實(shí)現(xiàn)中，ArrayList<E>和LinkedList<E>是兩個(gè)常用的類。在大多數(shù)情況下，建議使用ArrayList<E>。在讀取元素的時(shí)候，ArrayList<E>所需時(shí)長是固定的(所需時(shí)間不隨元素個(gè)數(shù)而變化)，速度比較快。在ArrayList<E>中，并不需為每個(gè)元素申請(qǐng)一個(gè)對(duì)象節(jié)點(diǎn)，所以如果需要一次復(fù)制幾個(gè)元素，可以利用System.arraycopy來提升運(yùn)行速度。需要注意的是，多線程時(shí)ArrayList<E>的操作是不安全的。如果需要頻繁的往一個(gè)序列的頭部添加元素，或者頻繁刪除序列中的某些元素，應(yīng)該使用LinkedList<E>。這些操作在LinkedList<E>中所需時(shí)長是固定的(所需時(shí)間不隨數(shù)組長度變長而變多)。在ArrayList<E>中進(jìn)行這些操作會(huì)使得程序的效率下降很多。讀取元素ArrayList<E>占優(yōu)勢，而刪除元素等操作LinkedList<E>占優(yōu)勢。在編程中該如何選擇呢？建議在代碼中測試這兩個(gè)類，分別獲取它們的運(yùn)行耗時(shí)，選擇耗時(shí)少速度快的類。

ArrayList<E>比LinkedList<E>多一個(gè)參數(shù)，這個(gè)參數(shù)是初始容量。這個(gè)初始容量參數(shù)與StringBuilder<E>類中的初始容量參數(shù)一樣，用于指定ArrayList<E>的初始存儲(chǔ)空間。LinkedList<E>沒有初始容量參數(shù)，但是比ArrayList<E>多了7個(gè)方法。這7個(gè)方法是clone()、addFirst()、getFirst()、removeFirst()、addLast()、getLast()和removeLast()。

前面提到，ArrayList<E>是線程不安全的。如果希望在多線程間同步，可以使用Vector類。雖然可以使用Collections.synchronizedList()(注意是Collections類，不是Collection接口)對(duì)ArrayList<E>實(shí)現(xiàn)多線程間的同步，但是Vector類的效率更高一些。

6.4Set實(shí)現(xiàn)

Set接口的實(shí)現(xiàn)中有三個(gè)常用類：HashSet<E>、TreeSet<E>和LinkedHashSet<E>。HashSet<E>要比TreeSet<E>快很多，對(duì)于大多數(shù)操作來說，HashSet<E>只需要較短的時(shí)間即可完成，而TreeSet<E>用的時(shí)間要長很多。如果你需要SortedSet<E>接口里的方法，或者操作是跟排序后的元素相關(guān)，請(qǐng)用TreeSet<E>，否則使用HashSet<E>。大多數(shù)情況下，需要使用的是HashSet<E>。

LinkedHashSet<E>介于HashSet<E>和TreeSet<E>之間，它實(shí)現(xiàn)了一個(gè)哈希表，并用鏈表將里面的元素連起來，所以LinkedHashSet<E>具有跟HashSet<E>一樣的運(yùn)行速度。

關(guān)于HashSet<E>需要注意的是：讀取HashSet<E>里的某個(gè)元素所用時(shí)長是線性的，跟哈希表的入口和容量的大小成正比。因此如果初始容量設(shè)得太大，既浪費(fèi)存儲(chǔ)空間，又浪費(fèi)檢索時(shí)間；但是如果將初始容量設(shè)置得太小，那么在需要擴(kuò)大容量時(shí)，又不得不花費(fèi)時(shí)間復(fù)制數(shù)據(jù)。兩個(gè)方面的優(yōu)勢很難兼得。初始容量可以使用HashSet<E>類的構(gòu)造方法來設(shè)置，設(shè)置初始容量為64的代碼如下：

Set<String>s=newHashSet<String>(64);

6.5Map實(shí)現(xiàn)

Map接口的實(shí)現(xiàn)中也有三個(gè)常用類：HashMap、TreeMap和LinkedHashMap。如果你需要SortedMap接口中的方法，或者需要可排序的鍵視圖，請(qǐng)使用TreeMap；如果你希望速度快，并不關(guān)心元素的順序，請(qǐng)使用HashMap；如果你希望速度跟HashMap類似，并關(guān)心元素的存儲(chǔ)順序，請(qǐng)使用LinkedHashMap。Map的實(shí)現(xiàn)類跟Set的實(shí)現(xiàn)類在某種程度上有一定的相似性，上一節(jié)中提到的關(guān)于Set的特點(diǎn)，多數(shù)對(duì)Map同樣有效。

6.6ArrayList<E>泛型類

ArrayList<E>實(shí)現(xiàn)了大小可變的數(shù)組。ArrayList<E>泛型類中的常用方法如表6.1所示。程序的輸出結(jié)果如圖6.4所示。圖6.4例6-2的輸出結(jié)果注意ArrayList<E>沒有辦法進(jìn)行同步。如果多個(gè)線程同時(shí)訪問一個(gè)ArrayList<E>鏈表，則必須自己實(shí)現(xiàn)訪問同步。一種解決方法是在創(chuàng)建對(duì)象時(shí)使用Collections類中的靜態(tài)方法，來構(gòu)造一個(gè)同步的鏈表：

Listlist=Collections.synchronizedList(newArrayList(...));

另一種解決方法是使用Vector<E>類。Vector<E>類比前一種方法實(shí)現(xiàn)同步的速度更快，更值得推薦。

6.7LinkedList<E>泛型類

LinkedList<E>實(shí)現(xiàn)了List接口，能夠構(gòu)建一個(gè)雙向鏈表，鏈?zhǔn)街心軌虼鎯?chǔ)所有的非基本數(shù)據(jù)類型(包括null)。LinkedList<E>適用于如下幾種情況：

(1)需要處理的對(duì)象數(shù)目不定。

(2)序列中元素都是對(duì)象，而不是基本數(shù)據(jù)類型的變量。

(3)需要做頻繁的元素插入和刪除。

(4)需要定位序列中的對(duì)象或其它查找操作。注意LinkedList<E>也沒有方法進(jìn)行同步。如果多個(gè)線程同時(shí)訪問一個(gè)LinkedList<E>鏈表，則必須自己實(shí)現(xiàn)訪問同步。一種解決方法是在創(chuàng)建對(duì)象時(shí)使用Collections類中的靜態(tài)方法，來構(gòu)造一個(gè)同步的鏈表：

Listlist=Collections.synchronizedList(newLinkedList(...));

LinkedList<E>的用法跟ArrayList<E>的用法類似，只是多了7個(gè)方法。這七個(gè)方法是clone()、addFirst()、getFirst()、removeFirst()、addLast()、getLast()和removeLast()。在此不再贅述。

6.8HashSet<E>泛型類

HashSet<E>實(shí)現(xiàn)Set接口，由哈希表(實(shí)際上是一個(gè)HashMap實(shí)例)支持。該類不保證set里面元素的順序，也不保證元素的順序不會(huì)發(fā)生變化。該類中允許使用null元素。

HashSet<E>類為基本操作提供了常數(shù)時(shí)間保證，這些基本操作包括add、remove、contains和size。這個(gè)類假定哈希函數(shù)將這些元素正確地分布在桶中。獲取某個(gè)元素所需的時(shí)間與HashSet實(shí)例的大小(元素的數(shù)量)和底層HashMap實(shí)例(桶的數(shù)量)的“容量”和成正比。因此，如果很看重查詢?cè)氐男阅?，則不應(yīng)將初始容量設(shè)置得太高(或?qū)⒓虞d因子設(shè)置得太低)。注意，此實(shí)現(xiàn)不是同步的。如果多個(gè)線程同時(shí)訪問一個(gè)哈希set，而其中至少一個(gè)線程修改了該set，那么它必須保持外部同步。這通常是通過對(duì)自然封裝該set的對(duì)象執(zhí)行同步操作來完成的。如果不存在這樣的對(duì)象，則應(yīng)該使用Collections.synchronizedSet方法來“包裝”set。最好在創(chuàng)建時(shí)完成這一操作，以防多線程對(duì)該set進(jìn)行意外的不同步訪問。

Sets=Collections.synchronizedSet(newHashSet(...));

HashSet<E>泛型類類似于數(shù)學(xué)上的集合概念，不允許重復(fù)的元素出現(xiàn)，也可以進(jìn)行集合的交、并與差運(yùn)算。程序的運(yùn)行結(jié)果如圖6.5所示。圖6.5例6-3的輸出結(jié)果程序輸出結(jié)果如圖6.6所示。圖6.6例6-4的輸出結(jié)果

6.9TreeSet<E>泛型類

TreeSet<E>泛型類是一個(gè)有序集合，使用元素的自然順序?qū)υ剡M(jìn)行排序，或者根據(jù)創(chuàng)建set時(shí)提供的Comparator進(jìn)行排序，也就是說TreeSet<E>中的對(duì)象元素需要實(shí)現(xiàn)Comparable接口。下面這個(gè)例子演示TreeSet<E>中的元素排序。需要注意的是TreeSet類中跟HashSet類一樣也沒有g(shù)et()方法，用來獲取列表中的元素，所以也只能通過迭代器方法來獲取。例6-5的輸出結(jié)果如圖6.7所示。可以看出，TreeSet<E>中元素的存儲(chǔ)順序跟插入的順序無關(guān)，String類型的元素是按照字典順序排列的，標(biāo)點(diǎn)在最前，大寫字母在其后，小寫字母在最后。圖6.7例6-5的輸出結(jié)果在TreeSet<E>類中，基本的操作(add()、remove()和contains())所需的時(shí)間復(fù)雜度為O(log(n))。所以在時(shí)間效率方面，它要劣于HashSet<E>類。

如果TreeSet<E>類中的元素為自定義類型，那么這個(gè)類需要實(shí)現(xiàn)Comparable接口。在Comparable接口的compareTo()方法中，定義如何對(duì)元素排序。例如下面這個(gè)例子，自定義類Person實(shí)現(xiàn)了接口Comparable，compareTo()方法中有兩行代碼(只能使用一行)，第一行代碼是根據(jù)age變量對(duì)元素進(jìn)行排序；如果希望根據(jù)name變量對(duì)元素進(jìn)行排序，請(qǐng)使用第二行代碼。程序運(yùn)行結(jié)果如圖6.8所示。

可以看出排序標(biāo)準(zhǔn)為整數(shù)age，按從小到大排列。如果注釋掉compareTo()方法中的第一行代碼，改用第二行代碼，那么將使用字符串name變量進(jìn)行排序，運(yùn)行結(jié)果如圖6.9所示。圖6.8TreeSet<E>中的排序標(biāo)準(zhǔn)為年齡時(shí)的輸出結(jié)果圖6.9TreeSet<E>中的排序標(biāo)準(zhǔn)為姓名時(shí)的輸出結(jié)果注意，TreeSet<E>不是同步的。如果多個(gè)線程同時(shí)訪問一個(gè)TreeSet<E>實(shí)例，而其中至少一個(gè)線程修改了該set，那么它必須同步?？梢允褂肅ollections.synchronizedSortedSet()方法來“包裝”TreeSet<E>，使之是多線程安全的。此操作最好在創(chuàng)建時(shí)進(jìn)行，以防多個(gè)線程進(jìn)行意外非同步訪問。

SortedSets=Collections.synchronizedSortedSet(newTreeSet(...));

6.10HashMap<K,V>泛型類

HashMap<K,V>是基于哈希