前言

關(guān)于Java集合框架(Java Collections Framework, JCF)的資料較于C++的STL少之甚少，JCF的設(shè)計(jì)參考了STL，但其定位不是Java版的STL，而是要實(shí)現(xiàn)一個(gè)精簡(jiǎn)緊湊的集合框架，STL的教程/資料不能替代對(duì)JCK。

以下筆者閱讀《Java編程思想》第11章和第17章，以及網(wǎng)上的參考資料(見參考資料)，梳理、深入理解Java集合框架。

容器，就是可以容納其他Java對(duì)象的對(duì)象。Java Collections Framework（JCF）為Java開發(fā)者提供了通用的容器，其始于JDK 1.2，優(yōu)點(diǎn)是:

• 降低編程難度
• 提高程序性能
• 提高API間的互操作性
• 降低學(xué)習(xí)難度
• 降低設(shè)計(jì)和實(shí)現(xiàn)相關(guān)API的難度
• 增加程序的重用性

在Java 2之前，Java是沒有完整的集合框架的。它只有一些簡(jiǎn)單的可以自擴(kuò)展的容器類，比如Vector，Stack，Hashtable等。這些容器類在使用的過(guò)程中由于效率問題飽受詬病，因此在Java 2中，Java設(shè)計(jì)者們進(jìn)行了大刀闊斧的整改，重新設(shè)計(jì)，于是就有了現(xiàn)在的集合框架。需要注意的是，之前的那些容器類庫(kù)并沒有被棄用而是進(jìn)行了保留，主要是為了向下兼容的目的，但我們?cè)谄綍r(shí)使用中還是應(yīng)該盡量少用。

正文

容器主要包括 Collection 和 Map 兩種，Collection 存儲(chǔ)著對(duì)象的集合，而 Map 存儲(chǔ)著鍵值對(duì)（兩個(gè)對(duì)象）的映射表。

集合接口

集合接口

Map接口沒有繼承自Collection接口，因?yàn)镸ap表示的是關(guān)聯(lián)式容器而不是集合。但Java為我們提供了從Map轉(zhuǎn)換到Collection的方法，可以方便的將Map切換到集合視圖。 上圖中提供了Queue接口，卻沒有Stack，這是因?yàn)镾tack的功能已被JDK 1.6引入的Deque取代。

集合實(shí)現(xiàn)

上述接口的通用實(shí)現(xiàn)見下表：

集合實(shí)現(xiàn)

Collection

1. List: 存儲(chǔ)一組不唯一(可以有多個(gè)元素引用相同的對(duì)象)，有序的對(duì)象。

• ArrayList: Object數(shù)組，基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn)，支持隨機(jī)訪問。
• Vector: Object數(shù)組，它是線程安全的。
• LinkedList: 雙向鏈表(JDK1.6之前為循環(huán)鏈表，JDK1.7取消了循環(huán)) ，只能順序訪問，但是可以快速地在鏈表中間插入和刪除元素。

2. Set: 不允許重復(fù)的集合。不會(huì)有多個(gè)元素引用相同的對(duì)象。

• HashSet(無(wú)序，唯一): 基于HashMap實(shí)現(xiàn)的，底層采用HashMap來(lái)保存元素，支持快速查找，但不支持有序性操作。
• LinkedHashSet: LinkedHashSet繼承與HashSet，并且其內(nèi)部是通過(guò)LinkedHashMap來(lái)實(shí)現(xiàn)的，具有HashSet的查找效率，且內(nèi)部使用雙向鏈表維護(hù)元素的插入順序。
• TreeSet(有序，唯一): 紅黑樹(自平衡的排序二叉樹)，支持有序性操作，例如根據(jù)一個(gè)范圍查找元素的操作。但是查找效率不如HashSet，HashSet查找的時(shí)間復(fù)雜度為O(1)，TreeSet則為 O(logN)。

3. Queue: 先進(jìn)先出(FIFO)的容器

• LinkedList: 實(shí)現(xiàn)了Queue接口，提供了方法以支持隊(duì)列的行為。
• PriorityQueue: 基于堆結(jié)構(gòu)實(shí)現(xiàn)，可以用它來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列。

Map

使用鍵值對(duì)存儲(chǔ)。Map會(huì)維護(hù)與Key有關(guān)聯(lián)的值。兩個(gè)Key可以引用相同的對(duì)象，但Key不能重復(fù)，典型的Key是String類型，但也可以是任何對(duì)象。

• HashMap: JDK1.8之前HashMap由數(shù)組+鏈表組成的，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8以后在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時(shí)間
• LinkedHashMap: LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈?zhǔn)缴⒘薪Y(jié)構(gòu)即由數(shù)組和鏈表或紅黑樹組成。另外，LinkedHashMap 在上面結(jié)構(gòu)的基礎(chǔ)上，增加了一條雙向鏈表，使得上面的結(jié)構(gòu)可以保持鍵值對(duì)的插入順序。同時(shí)通過(guò)對(duì)鏈表進(jìn)行相應(yīng)的操作，實(shí)現(xiàn)了訪問順序相關(guān)邏輯。
• HashTable: 數(shù)組+鏈表組成的，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的，線程安全的，這意味著同一時(shí)刻多個(gè)線程可以同時(shí)寫入 HashTable 并且不會(huì)導(dǎo)致數(shù)據(jù)不一致。它是遺留類，不應(yīng)該去使用它?，F(xiàn)在可以使用 ConcurrentHashMap 來(lái)支持線程安全，并且 ConcurrentHashMap 的效率會(huì)更高，因?yàn)?ConcurrentHashMap 引入了分段鎖。
• TreeMap: 紅黑樹（自平衡的排序二叉樹）

集合的選用方式: 主要根據(jù)集合的特點(diǎn)來(lái)選用，比如我們需要根據(jù)鍵值獲取到元素值時(shí)就選用Map接口下的集合，需要排序時(shí)選擇TreeMap,不需要排序時(shí)就選擇HashMap,需要保證線程安全就選用ConcurrentHashMap.當(dāng)我們只需要存放元素值時(shí)，就選擇實(shí)現(xiàn)Collection接口的集合，需要保證元素唯一時(shí)選擇實(shí)現(xiàn)Set接口的集合比如TreeSet或HashSet，不需要就選擇實(shí)現(xiàn)List接口的比如ArrayList或LinkedList，然后再根據(jù)實(shí)現(xiàn)這些接口的集合的特點(diǎn)來(lái)選用。

課后作業(yè)

• List, Set, Map三者的區(qū)別?

參考文獻(xiàn):

• Eckel B. Java 編程思想 [M]. 機(jī)械工業(yè)出版社, 2002.
• Collections Framework Overview
• 【Java學(xué)習(xí)+面試指南】 一份涵蓋大部分Java程序員所需要掌握的核心知識(shí)
• 深入理解Java集合框架