1.  Java集合框架圖

Java平臺(tái)提供了一個(gè)全新的集合框架.“集合框架”主要由一組用來(lái)操作對(duì)象的接口組成.不同接口描述一組不同數(shù)據(jù)類型.

Java集合框架圖如下:

集合接口:6個(gè)接口(短虛線表示),表示不同集合類型,是集合框架的基礎(chǔ).

抽象類:5個(gè)抽象類(長(zhǎng)虛線表示),對(duì)集合接口的部分實(shí)現(xiàn).可擴(kuò)展為自定義集合類.

實(shí)現(xiàn)類:8個(gè)實(shí)現(xiàn)類(實(shí)線表示),對(duì)接口的具體實(shí)現(xiàn).

在很大程度上,一旦您理解了接口,您就理解了框架.雖然您總要?jiǎng)?chuàng)建接口特定的實(shí)現(xiàn),但訪問(wèn)實(shí)際集合的方法應(yīng)該限制在接口方法的使用上;因此,允許您更改基本的數(shù)據(jù)結(jié)構(gòu)而不必改變其它代碼.

Java集合的頂層接口是Collection,Collection 接口是一組允許重復(fù)的對(duì)象.Java集合框架主要由以下三個(gè)接口組成:

    (1) Set 接口繼承Collection,但不允許重復(fù),使用自己內(nèi)部的一個(gè)排列機(jī)制.

    (2) List 接口繼承Collection,允許重復(fù),以元素安插的次序來(lái)放置元素,不會(huì)重新排列.

(3) Map接口是一組成對(duì)的鍵-值對(duì)象,即所持有的是key-value pairs.Map中不能有重復(fù)的key,擁有自己的內(nèi)部排列機(jī)制.

容器中的元素類型都為Object,從容器取得元素時(shí),必須把它轉(zhuǎn)換成原來(lái)的類型.簡(jiǎn)化后的集合框架圖如下:

2.  接口Collection

    用于表示任何對(duì)象或元素組,想要盡可能以常規(guī)方式處理一組元素時(shí),就使用這一接口.

    (1) 單元素添加,、刪除操作:

    boolean add(Object o):將對(duì)象添加給集合

    boolean remove(Object o): 如果集合中有與o相匹配的對(duì)象,則刪除對(duì)象o

    (2) 查詢操作:

    int size():返回當(dāng)前集合中元素的數(shù)量

    boolean isEmpty():判斷集合中是否有任何元素

    boolean contains(Object o):查找集合中是否含有對(duì)象o

    Iterator iterator():返回一個(gè)迭代器,用來(lái)訪問(wèn)集合中的各個(gè)元素

    (3) 組操作:作用于元素組或整個(gè)集合

    boolean containsAll(Collection c): 查找集合中是否含有集合c 中所有元素

    boolean addAll(Collection c) : 將集合c 中所有元素添加給該集合

    void clear(): 刪除集合中所有元素

    void removeAll(Collection c) : 從集合中刪除集合c 中的所有元素

    void retainAll(Collection c) : 從集合中刪除集合c 中不包含的元素

    (4) Collection轉(zhuǎn)換為Object數(shù)組:

    Object[] toArray():返回一個(gè)內(nèi)含集合所有元素的array

Object[] toArray(Object[] a):返回一個(gè)內(nèi)含集合所有元素的array.運(yùn)行期返回的array和參數(shù)a的型別相同,需要轉(zhuǎn)換為正確型別.

此外,您還可以把集合轉(zhuǎn)換成其它任何其它的對(duì)象數(shù)組.但是,您不能直接把集合轉(zhuǎn)換成基本數(shù)據(jù)類型的數(shù)組,因?yàn)榧媳仨毘钟袑?duì)象.

斜體接口方法是可選的.因?yàn)橐粋€(gè)接口實(shí)現(xiàn)必須實(shí)現(xiàn)所有接口方法,調(diào)用程序就需要一種途徑來(lái)知道一個(gè)可選的方法是不是不受支持.如果調(diào)用一種可選方法時(shí),一個(gè) UnsupportedOperationException 被拋出,則操作失敗,因?yàn)榉椒ú皇苤С?/span>.此異常類繼承 RuntimeException 類,避免了將所有集合操作放入 try-catch 塊.

  Collection不提供get()方法.如果要遍歷Collectin中的元素,就必須用Iterator.

2.1 抽象類AbstractCollection

    AbstractCollection 類提供具體“集合框架”類的基本功能.雖然您可以自行實(shí)現(xiàn) Collection 接口的所有方法,但是,除了iterator()和size()方法在恰當(dāng)?shù)淖宇愔袑?shí)現(xiàn)以外,其它所有方法都由 AbstractCollection 類來(lái)提供實(shí)現(xiàn).如果子類不覆蓋某些方法,可選的如add()之類的方法將拋出異常.

2.2 接口Iterator

    Collection 接口的iterator()方法返回一個(gè) Iterator.Iterator接口方法能以迭代方式逐個(gè)訪問(wèn)集合中各個(gè)元素,并安全的從Collection 中除去適當(dāng)?shù)脑?/span>.

    (1) boolean hasNext(): 判斷是否存在另一個(gè)可訪問(wèn)的元素

    Object next(): 返回要訪問(wèn)的下一個(gè)元素.如果到達(dá)集合結(jié)尾,則拋出NoSuchElementException異常.

    (2) void  remove(): 刪除上次訪問(wèn)返回的對(duì)象.本方法必須緊跟在一個(gè)元素的訪問(wèn)后執(zhí)行.如果上次訪問(wèn)后集合已被修改,方法將拋出IllegalStateException.

Iterator中刪除操作對(duì)底層Collection也有影響.

 迭代器是故障快速修復(fù)(fail-fast)的.這意味著,當(dāng)另一個(gè)線程修改底層集合的時(shí)候,如果您正在用 Iterator 遍歷集合,那么,Iterator就會(huì)拋出 ConcurrentModificationException (一種 RuntimeException異常)異常并立刻失敗.

在遍歷Iterator時(shí)不能對(duì)底層Collection執(zhí)行remove()操作.

3. 接口List

     List 接口繼承了 Collection 接口以定義一個(gè)允許重復(fù)項(xiàng)的有序集合.該接口不但能夠?qū)α斜淼囊徊糠诌M(jìn)行處理,還添加了面向位置的操作.

    (1)  面向位置的操作包括插入某個(gè)元素或 Collection 的功能,還包括獲取,、除去或更改元素的功能.在 List 中搜索元素可以從列表的頭部或尾部開(kāi)始,如果找到元素,還將報(bào)告元素所在的位置 :

    void add(int index, Object element): 在指定位置index上添加元素element

    boolean addAll(int index, Collection c): 將集合c的所有元素添加到指定位置index

    Object get(int index): 返回List中指定位置的元素

    int indexOf(Object o): 返回第一個(gè)出現(xiàn)元素o的位置,否則返回-1

    int lastIndexOf(Object o):返回最后一個(gè)出現(xiàn)元素o的位置,否則返回-1

    Object remove(int index) :刪除指定位置上的元素

    Object set(int index, Object element):用元素element取代位置index上的元素,并且返回舊的元素

    (2) List 接口不但以位置序列迭代的遍歷整個(gè)列表,還能處理集合的子集:

    ListIterator listIterator() : 返回一個(gè)列表迭代器,用來(lái)訪問(wèn)列表中的元素

    ListIterator listIterator(int index) : 返回一個(gè)列表迭代器,用來(lái)從指定位置index開(kāi)始訪問(wèn)列表中的元素

    List subList(int fromIndex, int toIndex):返回從指定位置fromIndex(包含)到toIndex(不包含)范圍中各個(gè)元素的列表視圖

    對(duì)子列表的更改(如 add(),、remove() 和 set() 調(diào)用)對(duì)底層 List 也有影響.

  3.1 接口ListIterator

  ListIterator 接口繼承 Iterator 接口以支持添加或更改底層集合中的元素,還支持雙向訪問(wèn).ListIterator沒(méi)有當(dāng)前位置,光標(biāo)位于調(diào)用previous和next方法返回的值之間.一個(gè)長(zhǎng)度為n的列表,有n+1個(gè)有效索引值:

    (1) void add(Object o): 將對(duì)象o添加到當(dāng)前位置的前面

    void set(Object o): 用對(duì)象o替代next或previous方法訪問(wèn)的上一個(gè)元素.如果上次調(diào)用后列表結(jié)構(gòu)被修改了,那么將拋出IllegalStateException異常.

    (2)  boolean hasPrevious(): 判斷向后迭代時(shí)是否有元素可訪問(wèn)

    Object previous():返回上一個(gè)對(duì)象

    int nextIndex(): 返回下次調(diào)用next方法時(shí)將返回的元素的索引

    int previousIndex(): 返回下次調(diào)用previous方法時(shí)將返回的元素的索引

3.2 抽象類AbstractList和AbstractSequentialList

有兩個(gè)抽象的 List 實(shí)現(xiàn)類:AbstractList 和 AbstractSequentialList.像 AbstractSet 類一樣,它們覆蓋了 equals() 和 hashCode() 方法以確保兩個(gè)相等的集合返回相同的哈希碼.若兩個(gè)列表大小相等且包含順序相同的相同元素,則這兩個(gè)列表相等.這里的 hashCode() 實(shí)現(xiàn)在 List 接口定義中指定,而在這里實(shí)現(xiàn).

除了equals()和hashCode(),AbstractList和AbstractSequentialList實(shí)現(xiàn)了其余 List 方法的一部分.因?yàn)閿?shù)據(jù)的隨機(jī)訪問(wèn)和順序訪問(wèn)是分別實(shí)現(xiàn)的,使得具體列表實(shí)現(xiàn)的創(chuàng)建更為容易.需要定義的一套方法取決于您希望支持的行為.您永遠(yuǎn)不必親自提供的是 iterator方法的實(shí)現(xiàn).

3.3 類LinkedList,、ArrayList和Vector

在“集合框架”中有兩種常規(guī)的 List 實(shí)現(xiàn):ArrayList 和 LinkedList.使用兩種 List 實(shí)現(xiàn)的哪一種取決于您特定的需要.如果要支持隨機(jī)訪問(wèn),而不必在除尾部的任何位置插入或除去元素,那么,ArrayList 提供了可選的集合.但如果,您要頻繁的從列表的中間位置添加和除去元素,而只要順序的訪問(wèn)列表元素,那么,LinkedList 實(shí)現(xiàn)更好.

ArrayList 和 LinkedList 都實(shí)現(xiàn) Cloneable 接口,都提供了兩個(gè)構(gòu)造函數(shù),一個(gè)無(wú)參的,一個(gè)接受另一個(gè)Collection

  3.1.1 類LinkedList

    LinkedList類添加了一些處理列表兩端元素的方法.

    (1)  void addFirst(Object o): 將對(duì)象o添加到列表的開(kāi)頭

    void addLast(Object o):將對(duì)象o添加到列表的結(jié)尾

    (2)  Object getFirst(): 返回列表開(kāi)頭的元素

    Object getLast(): 返回列表結(jié)尾的元素

    (3)  Object removeFirst(): 刪除并且返回列表開(kāi)頭的元素

    Object removeLast():刪除并且返回列表結(jié)尾的元素

    (4)  LinkedList(): 構(gòu)建一個(gè)空的鏈接列表

LinkedList(Collection c): 構(gòu)建一個(gè)鏈接列表,并且添加集合c的所有元素

    使用這些新方法,您就可以輕松的把 LinkedList 當(dāng)作一個(gè)堆棧,、隊(duì)列或其它面向端點(diǎn)的數(shù)據(jù)結(jié)構(gòu).

  3.1.2 類ArrayList

ArrayList類封裝了一個(gè)動(dòng)態(tài)再分配的Object[]數(shù)組.每個(gè)ArrayList對(duì)象有一個(gè)capacity.這個(gè)capacity表示存儲(chǔ)列表中元素的數(shù)組的容量.當(dāng)元素添加到ArrayList時(shí),它的capacity在常量時(shí)間內(nèi)自動(dòng)增加.

    在向一個(gè)ArrayList對(duì)象添加大量元素的程序中,可使用ensureCapacity方法增加capacity.這可以減少增加重分配的數(shù)量.

    (1)  void ensureCapacity(int minCapacity): 將ArrayList對(duì)象容量增加minCapacity

    (2)  void trimToSize(): 整理ArrayList對(duì)象容量為列表當(dāng)前大小.程序可使用這個(gè)操作減少ArrayList對(duì)象存儲(chǔ)空間.

  3.1.3 類Vector

    Vector類似于ArrayList.從API的角度來(lái)看這兩個(gè)類非常相似.Vector是同步的,這個(gè)類中的一些方法保證了Vector中的對(duì)象是線程安全的.而ArrayList則是異步的,因此ArrayList中的對(duì)象并不是線程安全的.

  3.1.4 三者之間的區(qū)別

  3.1.4.1    LinkedList與ArrayList的區(qū)別

      ArrayList:支持隨機(jī)訪問(wèn),不必在除尾部的任何位置插入或除去元素.

      LinkedList:頻繁的從列表的中間位置添加和除去元素,而只要順序的訪問(wèn)列表元素.

  3.1.4.2    Vector與ArrayList的區(qū)別

  (1) 同步性

    Vector是同步的.這個(gè)類中的一些方法保證了Vector中的對(duì)象是線程安全的.而ArrayList則是異步的,因此ArrayList中的對(duì)象并不是線程安全的.因?yàn)橥降囊髸?huì)影響執(zhí)行的效率,所以如果你不需要線程安全的集合那么使用ArrayList是一個(gè)很好的選擇,這樣可以避免由于同步帶來(lái)的不必要的性能開(kāi)銷.

  (2) 數(shù)據(jù)增長(zhǎng)

    從內(nèi)部實(shí)現(xiàn)機(jī)制來(lái)講ArrayList和Vector都是使用數(shù)組(Array)來(lái)控制集合中的對(duì)象.當(dāng)你向這兩種類型中增加元素的時(shí)候,如果元素的數(shù)目超出了內(nèi)部數(shù)組目前的長(zhǎng)度它們都需要擴(kuò)展內(nèi)部數(shù)組的長(zhǎng)度,Vector缺省情況下自動(dòng)增長(zhǎng)原來(lái)一倍的數(shù)組長(zhǎng)度,ArrayList是原來(lái)的50%,所以最后你獲得的這個(gè)集合所占的空間總是比你實(shí)際需要的要大.所以如果你要在集合中保存大量的數(shù)據(jù)那么使用Vector有一些優(yōu)勢(shì),因?yàn)槟憧梢酝ㄟ^(guò)設(shè)置集合的初始化大小來(lái)避免不必要的資源開(kāi)銷.

  (3) 使用模式

在ArrayList和Vector中,從一個(gè)指定的位置(通過(guò)索引)查找數(shù)據(jù)或是在集合的末尾增加,、移除一個(gè)元素所花費(fèi)的時(shí)間是一樣的,這個(gè)時(shí)間我們用O(1)表示.但是,如果在集合的其他位置增加或移除元素那么花費(fèi)的時(shí)間會(huì)呈線形增長(zhǎng):O(n-i),其中n代表集合中元素的個(gè)數(shù),i代表元素增加或移除元素的索引位置.為什么會(huì)這樣呢?以為在進(jìn)行上述操作的時(shí)候集合中第i和第i個(gè)元素之后的所有元素都要執(zhí)行位移的操作.這一切意味著什么呢?

這意味著,你只是查找特定位置的元素或只在集合的末端增加,、移除元素,那么使用Vector或ArrayList都可以.如果是其他操作,你最好選擇其他的集合操作類.比如,LinkList集合類在增加或移除集合中任何位置的元素所花費(fèi)的時(shí)間都是一樣的-O(1),但它在索引一個(gè)元素的使用卻比較慢-O(i),其中i是索引的位置.使用ArrayList也很容易,因?yàn)槟憧梢院?jiǎn)單的使用索引來(lái)代替創(chuàng)建iterator對(duì)象的操作.LinkList也會(huì)為每個(gè)插入的元素創(chuàng)建對(duì)象,所有你要明白它也會(huì)帶來(lái)額外的開(kāi)銷.

最后,在《Practical Java》一書(shū)中Peter Haggar建議使用一個(gè)簡(jiǎn)單的數(shù)組(Array)來(lái)代替Vector或ArrayList.尤其是對(duì)于執(zhí)行效率要求高的程序更應(yīng)如此.因?yàn)槭褂脭?shù)組(Array)避免了同步,、額外的方法調(diào)用和不必要的重新分配空間的操作.

4. 接口Set

    Set 接口繼承 Collection 接口,而且它不允許集合中存在重復(fù)項(xiàng),每個(gè)具體的 Set 實(shí)現(xiàn)類依賴添加的對(duì)象的 equals()方法來(lái)檢查獨(dú)一性,因此加入Set的Object必須定義equals()方法以確保對(duì)象的唯一性.Set接口沒(méi)有引入新方法,所以Set就是一個(gè)Collection,只不過(guò)其行為不同.

4.1 Hash表

Hash表是一種數(shù)據(jù)結(jié)構(gòu),用來(lái)查找對(duì)象.Hash表為每個(gè)對(duì)象計(jì)算出一個(gè)整數(shù),稱為Hash Code(哈希碼).Hash表是個(gè)鏈接式列表的陣列.每個(gè)列表稱為一個(gè)buckets(哈希表元).對(duì)象位置的計(jì)算 index = HashCode % buckets (HashCode為對(duì)象哈希碼,buckets為哈希表元總數(shù)).

當(dāng)你添加元素時(shí),有時(shí)你會(huì)遇到已經(jīng)填充了元素的哈希表元,這種情況稱為Hash Collisions(哈希沖突).這時(shí),你必須判斷該元素是否已經(jīng)存在于該哈希表中.

如果哈希碼是合理地隨機(jī)分布的,并且哈希表元的數(shù)量足夠大,那么哈希沖突的數(shù)量就會(huì)減少.同時(shí),你也可以通過(guò)設(shè)定一個(gè)初始的哈希表元數(shù)量來(lái)更好地控制哈希表的運(yùn)行.初始哈希表元的數(shù)量為 buckets = size * 150% + 1 (size為預(yù)期元素的數(shù)量).

如果哈希表中的元素放得太滿,就必須進(jìn)行rehashing(再哈希).再哈希使哈希表元數(shù)增倍,并將原有的對(duì)象重新導(dǎo)入新的哈希表元中,而原始的哈希表元被刪除.load factor(加載因子)決定何時(shí)要對(duì)哈希表進(jìn)行再哈希.在Java編程語(yǔ)言中,加載因子默認(rèn)值為0.75,默認(rèn)哈希表元為101.

    4.2 接口Comparable與Comparator

  在“集合框架”中有兩種比較接口:Comparable接口和Comparator接口.像String和Integer等Java內(nèi)建類實(shí)現(xiàn)Comparable接口以提供一定排序方式,但這樣只能實(shí)現(xiàn)該接口一次.對(duì)于那些沒(méi)有實(shí)現(xiàn)Comparable接口的類、或者自定義的類,您可以通過(guò)Comparator接口來(lái)定義您自己的比較方式.

    4.2.1 接口Comparable

  在java.lang包中,Comparable接口適用于一個(gè)類有自然順序的時(shí)候.假定對(duì)象集合是同一類型,該接口允許您把集合排序成自然順序.

  (1) int compareTo(Object o): 比較當(dāng)前實(shí)例對(duì)象與對(duì)象o,如果位于對(duì)象o之前,返回負(fù)值,如果兩個(gè)對(duì)象在排序中位置相同,則返回0,如果位于對(duì)象o后面,則返回正值

  在 Java 2 SDK版本1.4中有二十四個(gè)類實(shí)現(xiàn)Comparable接口.下表展示了8種基本類型的自然排序.雖然一些類共享同一種自然排序,但只有相互可比的類才能排序.

    類

    排序

    BigDecimal,BigInteger,Byte, Double,

    Float,Integer,Long,Short

    按數(shù)字大小排序

    Character

    按 Unicode 值的數(shù)字大小排序

    String

    按字符串中字符 Unicode 值排序

  利用Comparable接口創(chuàng)建您自己的類的排序順序,只是實(shí)現(xiàn)compareTo()方法的問(wèn)題.通常就是依賴幾個(gè)數(shù)據(jù)成員的自然排序.同時(shí)類也應(yīng)該覆蓋equals()和hashCode()以確保兩個(gè)相等的對(duì)象返回同一個(gè)哈希碼.

    4.2.2 接口Comparator

  若一個(gè)類不能用于實(shí)現(xiàn)java.lang.Comparable,或者您不喜歡缺省的Comparable行為并想提供自己的排序順序(可能多種排序方式),你可以實(shí)現(xiàn)Comparator接口,從而定義一個(gè)比較器.

  (1)int compare(Object o1, Object o2): 對(duì)兩個(gè)對(duì)象o1和o2進(jìn)行比較,如果o1位于o2的前面,則返回負(fù)值,如果在排序順序中認(rèn)為o1和o2是相同的,返回0,如果o1位于o2的后面,則返回正值

  與Comparable相似,0返回值不表示元素相等.一個(gè)0返回值只是表示兩個(gè)對(duì)象排在同一位置.由Comparator用戶決定如何處理.如果兩個(gè)不相等的元素比較的結(jié)果為零,您首先應(yīng)該確信那就是您要的結(jié)果,然后記錄行為.

    (2)boolean equals(Object obj): 指示對(duì)象obj是否和比較器相等.

  該方法覆寫Object的equals()方法,檢查的是Comparator實(shí)現(xiàn)的等同性,不是處于比較狀態(tài)下的對(duì)象.

    4.3 接口SortedSet

  “集合框架”提供了個(gè)特殊的Set接口:SortedSet,它保持元素的有序順序.SortedSet接口為集的視圖(子集