java Collections Framework

一、集合類的引入

通常，程序總是根據(jù)運(yùn)行時(shí)才知道某些條件去創(chuàng)建對(duì)象，在此之前，不知道所需對(duì)象的數(shù)量，甚至不知道確切的類型。為解決這個(gè)普遍的編程問題，需要在任何時(shí)刻和任何位置創(chuàng)建任何數(shù)量的對(duì)象，就不能創(chuàng)建命名的引用來持有每一個(gè)對(duì)象。 MyType aReference;

Java有多重形式保存對(duì)象，如數(shù)組。但是數(shù)組有固定的尺寸，在更一般的情況中，很多的時(shí)候是你在程序中不知道需要?jiǎng)?chuàng)建多少個(gè)對(duì)象，或者是否需要更復(fù)雜的方式來存儲(chǔ)對(duì)象，因此數(shù)組尺寸固定這一限制過于受限了。

所以在Java實(shí)用類庫(kù)中專門提供了一套動(dòng)態(tài)對(duì)象數(shù)組的操作類——類集框架，在Java中類集框架實(shí)際上也就是對(duì)數(shù)據(jù)結(jié)構(gòu)的Java實(shí)現(xiàn)。集合框架是為表示和操作集合而規(guī)定的一種統(tǒng)一的標(biāo)準(zhǔn)的體系結(jié)構(gòu)。任何集合框架都包含三大塊內(nèi)容：對(duì)外的接口、接口的實(shí)現(xiàn)和對(duì)集合運(yùn)算的算法。其中最基本的類型是Collection(List，Set，Queue)，Map。

容器類只能容納對(duì)象引用，基本類型會(huì)自動(dòng)裝箱，一個(gè)數(shù)組，既可以直接容納基本類型的數(shù)據(jù)，亦可容納指向?qū)ο蟮囊谩?/p>

二、什么是集合框架

那么有了集合的概念，什么是集合框架呢？集合框架是為表示和操作集合而規(guī)定的一種統(tǒng)一的標(biāo)準(zhǔn)的體系結(jié)構(gòu)。任何集合框架都包含三大塊內(nèi)容：對(duì)外的接口、接口的實(shí)現(xiàn)和對(duì)集合運(yùn)算的算法。

接口：即表示集合的抽象數(shù)據(jù)類型。接口提供了讓我們對(duì)集合中所表示的內(nèi)容進(jìn)行單獨(dú)操作的可能。

實(shí)現(xiàn)：也就是集合框架中接口的具體實(shí)現(xiàn)。實(shí)際它們就是那些可復(fù)用的數(shù)據(jù)結(jié)構(gòu)。

算法：在一個(gè)實(shí)現(xiàn)了某個(gè)集合框架中的接口的對(duì)象身上完成某種有用的計(jì)算的方法，例如查找、排序等。這些算法通常是多態(tài)的，因?yàn)橄嗤姆椒梢栽谕粋€(gè)接口被多個(gè)類實(shí)現(xiàn)時(shí)有不同的表現(xiàn)。

三、使用集合框架的好處

1、它減少了程序設(shè)計(jì)的辛勞

集合框架通過提供有用的數(shù)據(jù)結(jié)構(gòu)和算法使你能集中注意力于你的程序的重要部分上，而不是為了讓程序能正常運(yùn)轉(zhuǎn)而將注意力于低層設(shè)計(jì)上。通過這些在無關(guān)API之間的簡(jiǎn)易的互用性，使你免除了為改編對(duì)象或轉(zhuǎn)換代碼以便聯(lián)合這些API而去寫大量的代碼。

2、它提高了程序速度和質(zhì)量

集合框架通過提供對(duì)有用的數(shù)據(jù)結(jié)構(gòu)和算法的高性能和高質(zhì)量的實(shí)現(xiàn)使你的程序速度和質(zhì)量得到提高。因?yàn)槊總€(gè)接口的實(shí)現(xiàn)是可互換的，所以你的程序可以很容易的通過改變一個(gè)實(shí)現(xiàn)而進(jìn)行調(diào)整。另外，你將可以從寫你自己的數(shù)據(jù)結(jié)構(gòu)的苦差事中解脫出來，從而有更多時(shí)間關(guān)注于程序其它部分的質(zhì)量和性能。

3、減少去學(xué)習(xí)和使用新的API 的辛勞

許多API天生的有對(duì)集合的存儲(chǔ)和獲取。在過去，這樣的API都有一些子API幫助操縱它的集合內(nèi)容，因此在那些特殊的子API之間就會(huì)缺乏一致性，你也不得不從零開始學(xué)習(xí)，并且在使用時(shí)也很容易犯錯(cuò)。而標(biāo)準(zhǔn)集合框架接口的出現(xiàn)使這個(gè)問題迎刃而解。

4、減少了設(shè)計(jì)新API的努力

設(shè)計(jì)者和實(shí)現(xiàn)者不用再在每次創(chuàng)建一種依賴于集合內(nèi)容的API時(shí)重新設(shè)計(jì)，他們只要使用標(biāo)準(zhǔn)集合框架的接口即可。

5、集合框架鼓勵(lì)軟件的復(fù)用

對(duì)于遵照標(biāo)準(zhǔn)集合框架接口的新的數(shù)據(jù)結(jié)構(gòu)天生即是可復(fù)用的。同樣對(duì)于操作一個(gè)實(shí)現(xiàn)了這些接口的對(duì)象的算法也是如此。

四、Java1.2之前的容器類庫(kù)

在Java2之前，Java是沒有完整的集合框架的。它只有一些簡(jiǎn)單的可以自擴(kuò)展的容器類，比如Vector，Stack，HashTable等。

1、Vector

Vector中包含的元素可以通過一個(gè)整型的索引值取得，它的大小可以在添加或移除元素時(shí)自動(dòng)增加或縮小。然而，Vector的設(shè)計(jì)卻存在極多缺陷（下面會(huì)說到）。

2、Stack

Stack是一種后進(jìn)先出（LIFO）的堆棧序列，重要特點(diǎn)是先放入的東西最后才能被取出。

3、Hashtable

Hashtable與Java2中的Map類似，可以看成一種關(guān)聯(lián)或映射數(shù)組，可以將兩個(gè)或多個(gè)毫無關(guān)系的對(duì)象相關(guān)聯(lián)，與數(shù)組不同的是它的大小可以動(dòng)態(tài)變化。

五、Java2中的容器類庫(kù)

 簡(jiǎn)化后

六、公用類

集合框架中還有兩個(gè)很實(shí)用的公用類：Collections和Arrays。

6.1、Collections

Collections提供了對(duì)一個(gè)Collection容器進(jìn)行諸如排序、復(fù)制、查找和填充等一些非常有用的方法，Arrays則是對(duì)一個(gè)數(shù)組進(jìn)行類似的操作。

6.2、Arrays類

java.util里面有一個(gè)Arrays類，它包括了一組可用于數(shù)組的static方法，這些方法都是一些實(shí)用工具。其中有四個(gè)基本方法：用來比較兩個(gè)數(shù)組是否相等的equals()；用來填充的fill()；用來對(duì)數(shù)組進(jìn)行排序的sort()；以及用于在一個(gè)已排序的數(shù)組中查找元素的binarySearch()。所有這些方法都對(duì)PRimitive和Object進(jìn)行了重載。此外還有一個(gè)asList()方法，它接受一個(gè)數(shù)組，然后把它轉(zhuǎn)成一個(gè)List容器。

七、主要集合類

Java中類集框架實(shí)際上也就是對(duì)數(shù)據(jù)結(jié)構(gòu)的Java實(shí)現(xiàn)。其中最基本的類型是Collection(List，Set，Queue)、Map。

7.1、List

List的最重要的特征就是有序；它會(huì)確保以插入順序保存元素，允許重復(fù)。

List在Collection的基礎(chǔ)上添加了大量方法，使之能在序列中間插入和刪除元素。（只對(duì)LinkedList推薦使用）List可以制造ListIterator對(duì)象，你除了能用它在List的中間插入和刪除元素之外，還能用它沿兩個(gè)方法遍歷List。

7.1.1、ArrayList

ArrayList*：一個(gè)用數(shù)組實(shí)現(xiàn)的List。能進(jìn)行快速的隨機(jī)訪問，但是往列表中間插入和刪除元素的時(shí)候比較慢。

7.1.2、LinkedList

內(nèi)部實(shí)現(xiàn)是鏈表，它適合于在鏈表中間需要頻繁進(jìn)行插入和刪除操作。

LinkedList：對(duì)順序訪問進(jìn)行了優(yōu)化。在List中間插入和刪除元素的代價(jià)也不高。隨機(jī)訪問的速度相對(duì)較慢。此外它還有addFirst()，addLast()，getFirst()，getLast()，removeFirst()和removeLast()等方法，你能把它當(dāng)成棧（stack），隊(duì)列（queue）或雙向隊(duì)列（deque）來用。

7.1.3、LinkedList的用途

用LinkedList做一個(gè)棧

“棧（stack）”有時(shí)也被稱為“后進(jìn)先出”（LIFO）的容器。就是說，最后一個(gè)被“壓”進(jìn)棧中的東西，會(huì)第一個(gè)“彈”出來。LinkedList的方法能直接實(shí)現(xiàn)棧的功能，所以你完全可以不寫Stack而直接使用LinkedList。

用LinkedList做一個(gè)隊(duì)列

隊(duì)列（queue）是一個(gè)“先進(jìn)先出”（FIFO）容器。也就是，你把一端把東西放進(jìn)去，從另一端把東西取出來。所以你放東西的順序也就是取東西的順序。LinkedList有支持隊(duì)列的功能的方法，所以它也能被當(dāng)作Queue來用。

用LinkedList做一個(gè)deque（雙向隊(duì)列）

它很像隊(duì)列，只是你可以從任意一端添加和刪除元素。

7.2、Set

Set接口也是Collection的一種擴(kuò)展,與List不同的是，在Set中的對(duì)象元素不能重復(fù)。加入Set的每個(gè)元素必須是唯一的；否則，Set是不會(huì)把它加進(jìn)去的。它的常用具體實(shí)現(xiàn)有HashSet和TreeSet類、LinkedHashSet類。他們保存對(duì)象的順序是和不一樣的，這是因?yàn)樗鼈兪怯貌煌姆椒▉泶鎯?chǔ)和查找元素的。（TreeSet用了一種叫紅黑樹的數(shù)據(jù)結(jié)構(gòu)【red-black tree datastructure】來為元素排序，而HashSet則用了“專為快速查找而設(shè)計(jì)”的散列函數(shù)。LinkedHashSet在內(nèi)部用散列來提高查詢速度，但是它看上去像是用鏈表來保存元素的插入順序的。）

7.2.1、HashSet

為優(yōu)化查詢速度而設(shè)計(jì)的Set，能快速定位一個(gè)元素。要放進(jìn)HashSet里面的Object還得定義hashCode()。

7.2.2、TreeSet

TreeSet則將放入其中的元素按序存放，這就要求你放入其中的對(duì)象是可排序的，這就用到了集合框架提供的另外兩個(gè)實(shí)用類Comparable和Comparator。一個(gè)類是可排序的，它就應(yīng)該實(shí)現(xiàn)Comparable接口。

7.2.3、LinkedHashSet

一個(gè)在內(nèi)部使用鏈表的Set，既有HashSet的查詢速度，又能保存元素被加進(jìn)去的順序（插入順序）。用Iterator遍歷Set的時(shí)候，它是按插入順序進(jìn)行訪問的。

7.3、Map

Map是一種把鍵對(duì)象和值對(duì)象進(jìn)行關(guān)聯(lián)的容器，一個(gè)Map容器中的鍵對(duì)象不允許重復(fù)，這是為了保持查找結(jié)果的一致性;如果有兩個(gè)鍵對(duì)象一樣，那你想得到那個(gè)鍵對(duì)象所對(duì)應(yīng)的值對(duì)象時(shí)就有問題了，可能你得到的并不是你想的那個(gè)值對(duì)象，結(jié)果會(huì)造成混亂，

鍵和值的關(guān)聯(lián)很簡(jiǎn)單，用put(Objectkey,Objectvalue)方法即可將一個(gè)鍵與一個(gè)值對(duì)象相關(guān)聯(lián)。用get(Object key)可得到與此key對(duì)象所對(duì)應(yīng)的值對(duì)象。也可以用containsKey()和containsValue()測(cè)試Map是否包含有某個(gè)鍵或值。

Java標(biāo)準(zhǔn)類庫(kù)里有好幾種Map：HashMap，TreeMap，LinkedHashMap

7.3.1、HashMap：

基于hash表的實(shí)現(xiàn)。（用它來代替Hashtable）提供時(shí)間恒定的插入與查詢。在構(gòu)造函數(shù)種可以設(shè)置hash表的capacity和load factor。可以通過構(gòu)造函數(shù)來調(diào)節(jié)其性能。

7.3.2、TreeMap

基于紅黑樹數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。它們是按順序排列的。TreeMap是Map中唯一有subMap()方法的實(shí)現(xiàn)。這個(gè)方法能讓你獲取這個(gè)樹中的一部分。

7.3.3、LinkedHashMap

很像HashMap，但是用Iterator進(jìn)行遍歷的時(shí)候，它會(huì)按插入順序或最先使用的順序（least-recently-used(LRU)order）進(jìn)行訪問。除了用Iterator外，其他情況下，只是比HashMap稍慢一點(diǎn)。用Iterator的情況下，由于是使用鏈表來保存內(nèi)部順序，因此速度會(huì)更快。

7.4、Queue：

隊(duì)列通常（但并非一定）以 FIFO（先進(jìn)先出）的方式排序各個(gè)元素。

7.4.1、LinkedList:

提供了方法支持隊(duì)列的行為，因此可以作為Queue的一種實(shí)現(xiàn)，將LinkedList向上轉(zhuǎn)型為Queue使用。

7.4.2、PriorityQueue

一個(gè)基于優(yōu)先級(jí)堆的無界優(yōu)先級(jí)隊(duì)列。優(yōu)先級(jí)隊(duì)列的元素按照其自然順序進(jìn)行排序，或者根據(jù)構(gòu)造隊(duì)列時(shí)提供的Comparator進(jìn)行排序，具體取決于所使用的構(gòu)造方法。優(yōu)先級(jí)隊(duì)列不允許使用null元素。依靠自然順序的優(yōu)先級(jí)隊(duì)列還不允許插入不可比較的對(duì)象（這樣做可能導(dǎo)致ClassCastException）。