轉(zhuǎn)載
本文轉(zhuǎn)載自：https://github.com/CarpenterLee/JCFInternals
說(shuō)明
對(duì)于JDK源碼分析的文章，僅僅記錄我認(rèn)為重要的地方。源碼的細(xì)節(jié)實(shí)在太多，不可能面面俱到地寫(xiě)清每個(gè)邏輯。所以我的JDK源碼分析，著重在JDK的體系架構(gòu)層面，具體源碼可以參考：http://www.cnblogs.com/skywang12345/category/455711.html。
概覽
容器，就是可以容納其他Java對(duì)象的對(duì)象。Java Collections Framework（JCF）為Java開(kāi)發(fā)者提供了通用的容器，其始于JDK 1.2，優(yōu)點(diǎn)是：
- 降低編程難度
- 提高程序性能
- 提高API間的互操作性
- 降低學(xué)習(xí)難度
- 降低設(shè)計(jì)和實(shí)現(xiàn)相關(guān)API的難度
- 增加程序的重用性
Java容器里只能放對(duì)象，對(duì)于基本類(lèi)型（int, long, float, double等），需要將其包裝成對(duì)象類(lèi)型后（Integer, Long, Float, Double等）才能放到容器里。很多時(shí)候拆包裝和解包裝能夠自動(dòng)完成。這雖然會(huì)導(dǎo)致額外的性能和空間開(kāi)銷(xiāo)，但簡(jiǎn)化了設(shè)計(jì)和編程。
泛型（Generics）
Java容器能夠容納任何類(lèi)型的對(duì)象，這一點(diǎn)表面上是通過(guò)泛型機(jī)制完成，Java泛型不是什么神奇的東西，只是編譯器為我們提供的一個(gè)“語(yǔ)法糖”，泛型本身并不需要Java虛擬機(jī)的支持，只需要在編譯階段做一下簡(jiǎn)單的字符串替換即可。實(shí)質(zhì)上Java的單繼承機(jī)制才是保證這一特性的根本，因?yàn)樗械膶?duì)象都是Object的子類(lèi)，容器里只要能夠存放Object對(duì)象就行了。
事實(shí)上，所有容器的內(nèi)部存放的都是Object對(duì)象，泛型機(jī)制只是簡(jiǎn)化了編程，由編譯器自動(dòng)幫我們完成了強(qiáng)制類(lèi)型轉(zhuǎn)換而已。JDK 1.4以及之前版本不支持泛型，類(lèi)型轉(zhuǎn)換需要程序員顯式完成。
//JDK 1.4 or before
ArrayList list = new ArrayList();
list.add(new String("Monday"));
list.add(new String("Tuesday"));
list.add(new String("Wensday"));
for(int i = 0; i < list.size(); i++){
String weekday = (String)list.get(i);//顯式類(lèi)型轉(zhuǎn)換
System.out.println(weekday.toUpperCase());
}
//JDK 1.5 or latter
ArrayList<String> list = new ArrayList<String>();//參數(shù)化類(lèi)型
list.add(new String("Monday"));
list.add(new String("Tuesday"));
list.add(new String("Wensday"));
for(int i = 0; i < list.size(); i++){
String weekday = list.get(i);//隱式類(lèi)型轉(zhuǎn)換，編譯器自動(dòng)完成
System.out.println(weekday.toUpperCase());
}
內(nèi)存管理
跟C++復(fù)雜的內(nèi)存管理機(jī)制不同，Java GC自動(dòng)包攬了一切，Java程序并不需要處理令人頭疼的內(nèi)存問(wèn)題，因此JCF并不像C++ STL那樣需要專(zhuān)門(mén)的空間適配器（alloctor）。
另外，由于Java里對(duì)象都在堆上，且對(duì)象只能通過(guò)引用（reference，跟C++中的引用不是同一個(gè)概念，可以理解成經(jīng)過(guò)包裝后的指針）訪(fǎng)問(wèn)，容器里放的其實(shí)是對(duì)象的引用而不是對(duì)象本身，也就不存在C++容器的復(fù)制拷貝問(wèn)題。
接口和實(shí)現(xiàn)（Interfaces and Implementations）
接口
為了規(guī)范容器的行為，統(tǒng)一設(shè)計(jì)，JCF定義了14種容器接口（collection interfaces），它們的關(guān)系如下圖所示：
Map接口沒(méi)有繼承自Collection接口，因?yàn)?em>Map表示的是關(guān)聯(lián)式容器而不是集合。但Java為我們提供了從Map轉(zhuǎn)換到Collection的方法，可以方便的將Map切換到集合視圖。
上圖中提供了Queue接口，卻沒(méi)有Stack，這是因?yàn)?em>Stack的功能已被JDK 1.6引入的Deque取代。
實(shí)現(xiàn)
上述接口的通用實(shí)現(xiàn)見(jiàn)下表：
接下來(lái)的篇幅，會(huì)逐個(gè)介紹上表中容器的數(shù)據(jù)結(jié)構(gòu)以及用到的算法。
迭代器（Iterator）
跟C++ STL一樣，JCF的迭代器（Iterator）為我們提供了遍歷容器中元素的方法。只有容器本身清楚容器里元素的組織方式，因此迭代器只能通過(guò)容器本身得到。每個(gè)容器都會(huì)通過(guò)內(nèi)部類(lèi)的形式實(shí)現(xiàn)自己的迭代器。相比STL的迭代器，JCF的迭代器更容易使用。
//visit a list with iterator
ArrayList<String> list = new ArrayList<String>();
list.add(new String("Monday"));
list.add(new String("Tuesday"));
list.add(new String("Wensday"));
Iterator<String> it = list.iterator();//得到迭代器
while(it.hasNext()){
String weekday = it.next();//訪(fǎng)問(wèn)元素
System.out.println(weekday.toUpperCase());
}
JDK 1.5 引入了增強(qiáng)的for循環(huán)，簡(jiǎn)化了迭代容器時(shí)的寫(xiě)法。
//使用增強(qiáng)for迭代
ArrayList<String> list = new ArrayList<String>();
list.add(new String("Monday"));
list.add(new String("Tuesday"));
list.add(new String("Wensday"));
for(String weekday : list){//enhanced for statement
System.out.println(weekday.toUpperCase());
}
源代碼
JDK安裝目錄下的src.zip包含了Java core API的源代碼，本文采用的是JDK 1.7u79的源碼，下載地址。這里復(fù)制了一份。
