《JAVA語言程序設計教程》課件第6章

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

6.1泛型

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

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

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

1.編譯時更強的類型檢查

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

2.無需類型轉(zhuǎ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.增加代碼重用性

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

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

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

在類名的后面，尖括號<>內(nèi)的內(nèi)容為類型參數(shù)，可以定義多個類型參數(shù)。對于前面例子中的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ù)據(jù)類型的一致性，盡可能在編譯時發(fā)現(xiàn)bug，而不是留到運行時出錯。程序運行結(jié)果如圖6.1所示。

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

6.2集?合?類?概?述

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

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

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

概念。

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

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

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

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

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

6.3List實現(xiàn)

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

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

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

6.4Set實現(xiàn)

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

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

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

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

6.5Map實現(xiàn)

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

6.6ArrayList<E>泛型類

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

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

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

6.7LinkedList<E>泛型類

LinkedList<E>實現(xiàn)了List接口，能夠構(gòu)建一個雙向鏈表，鏈式中能夠存儲所有的非基本數(shù)據(jù)類型(包括null)。LinkedList<E>適用于如下幾種情況：

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

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

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

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

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

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

6.8HashSet<E>泛型類

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

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

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

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

6.9TreeSet<E>泛型類

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

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

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

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

6.10HashMap<K,V>泛型類

HashMap<K,V>是基于哈希