轉(zhuǎn)自http://www.cnblogs.com/mengheng/p/3669463.html

Java2中的集合框架是廣為人知的垛贤，本文打算從幾個(gè)方面來(lái)說(shuō)說(shuō)自己對(duì)這個(gè)框架的理解父晶。

我們常說(shuō)要繼承的話吮蛹，到底是寫(xiě)個(gè)抽象類(lèi)還是接口摹察，它們區(qū)別在于：如果子類(lèi)確實(shí)是父類(lèi)的一種，應(yīng)該使用抽象類(lèi)浆熔，描述是“is-a”的關(guān)系，而接口則表示一種行為赏酥，描述的是“l(fā)ike-a”的關(guān)系。但在Java類(lèi)庫(kù)里谆构，其實(shí)許多原則由于各種原因被打破了裸扶，比如在Collection框架里，List/Set都是Collection的一種搬素，為什么不把Collection定義為抽象類(lèi)呢呵晨？而ArrayList/LinkedList也都是List的一種，為什么不把List定義為抽象類(lèi)呢熬尺？這就是原則和實(shí)際的折衷摸屠。作為Java類(lèi)庫(kù)而言，不僅要考慮面向?qū)ο蟮囊恍┰瓌t猪杭，也要考慮擴(kuò)展性和語(yǔ)言本身的限制餐塘。能不能把Collection接口去掉妥衣，用AbstractCollection作為頂層皂吮？作為類(lèi)庫(kù)而言是不可以的，因?yàn)镴ava是單繼承的税手，如果把AbstractCollection作為頂層蜂筹，那么當(dāng)用戶自定義的類(lèi)既要繼承自己的父類(lèi)，又要具備集合的屬性芦倒，那么就做不到了(可以自定義集合接口艺挪，但就無(wú)法與Collection相互轉(zhuǎn)化)。因此兵扬，Java集合框架采取的是類(lèi)庫(kù)廣泛使用的接口+抽象類(lèi)的形式麻裳，以同時(shí)獲得接口和抽象類(lèi)的好處，所以我們看到ArrayList extends AbstractList implements List(AbstractList本身就是實(shí)現(xiàn)List的器钟，這里再寫(xiě)出implements List是為了使ArrayList的類(lèi)結(jié)構(gòu)更為清晰)津坑。

另外我們?cè)倏碨et接口，它的方法基本和Collection方法一模一樣傲霸，為什么要再寫(xiě)一遍疆瑰？一方面是作為類(lèi)庫(kù)而言要增加詳細(xì)注釋?zhuān)m然是同名的方法但實(shí)現(xiàn)的約束不同，比如Set的add方法是不會(huì)保存重復(fù)值的昙啄，另一方面是為了從Set接口本身能很清楚地看到它所提供的功能(比如size()方法穆役，和Collection是完全一個(gè)含義，也重新定義了一遍)梳凛，這是從類(lèi)庫(kù)易讀性來(lái)考慮耿币，對(duì)于我們自己編寫(xiě)的類(lèi)，基本就不需要這樣韧拒。

說(shuō)多了淹接，回到集合框架本身秘狞。

Iterable基本是個(gè)標(biāo)識(shí)接口，同時(shí)約定了所有線性集合(數(shù)組蹈集、隊(duì)列烁试、棧這種一維的都屬于線性集合，Map就屬于二維拢肆，不要求遍歷)必須是可以遍歷的(集合要給出遍歷結(jié)構(gòu))减响，同時(shí)提供了配套的Iterator頂級(jí)接口，實(shí)現(xiàn)hasNext()郭怪、next()和remove()方法來(lái)完成遍歷功能支示。為什么這里要定義remove接口方法卻不定義add/set方法？個(gè)人覺(jué)得這可能是考慮在類(lèi)庫(kù)的使用過(guò)程中remove的頻率更高鄙才，而add的方法頻率要低颂鸿，set的使用場(chǎng)景就更少了。

ListIterator相比Iterator就多提供了很多功能攒庵，包括上面提到的add/set嘴纺，還有獲得索引的nextIndex、previousIndex浓冒、以及往回迭代的hasPrevious()/previous()栽渴。給針對(duì)線性表的操作者更多的便利，事實(shí)上在AbstractList里就提供了iterator()和listIterator()兩種方法來(lái)提供給開(kāi)發(fā)者更多選擇稳懒。相應(yīng)的闲擦，在HashMap里頭，也提供了實(shí)現(xiàn)Iterator接口的HashIterator內(nèi)部抽象類(lèi)场梆，而在Apache Commons Collections下甚至單獨(dú)寫(xiě)出MapIterator extends Iterator墅冷，由此可見(jiàn)，作為類(lèi)庫(kù)的設(shè)計(jì)者或油，在Iterator和ListIterator/HashMapIterator上是做了便捷性/易用性以及使用場(chǎng)景上的權(quán)衡的寞忿。

ArrayList內(nèi)部結(jié)構(gòu)是個(gè)數(shù)組，默認(rèn)是10装哆，在創(chuàng)建ArrayList對(duì)象時(shí)此數(shù)組是空的(Object[] EMPTY_ELEMENTDATA = {})只有當(dāng)add的時(shí)候才擴(kuò)容(如果擴(kuò)容容量小于DEFAULT_CAPACITY,也就是10罐脊，就一次性擴(kuò)容到10)。其擴(kuò)容的機(jī)制是：當(dāng)前數(shù)組容量已經(jīng)無(wú)法放入更多元素的時(shí)候蜕琴，增加原有數(shù)組的一半萍桌，

intoldCapacity = elementData.length;

intnewCapacity = oldCapacity + (oldCapacity >> 1);

if(newCapacity - minCapacity < 0)

? ? ? ? ? ? newCapacity = minCapacity;

if(newCapacity - MAX_ARRAY_SIZE > 0)

? ? ? ? ? ? newCapacity = hugeCapacity(minCapacity);

// minCapacity is usually close to size, so this is a win:

? ? ? ? elementData = Arrays.copyOf(elementData, newCapacity);

此數(shù)組的最大值是Integer.MAX_VALUE，也就是2^31-1凌简。數(shù)組擴(kuò)容的時(shí)候要考慮到當(dāng)容量再度擴(kuò)容一半的時(shí)候會(huì)越界上炎，所以單獨(dú)做了判斷處理。數(shù)組擴(kuò)容是在調(diào)用了本地方法去分配新的空間區(qū)域(下面是Arrays.CopyOf的代碼)

publicstaticint[] copyOf(int[] original,intnewLength) {

int[] copy =newint[newLength];

? ? ? ? System.arraycopy(original, 0, copy, 0,

? ? ? ? ? ? ? ? ? ? ? ? Math.min(original.length, newLength));

returncopy;

? ? }

System.arraycopy的代碼如下

publicstaticnativevoidarraycopy(Object src,intsrcPos,

Object dest,intdestPos,

intlength);

按照理論上來(lái)說(shuō)，對(duì)于能預(yù)先知道數(shù)組大小的藕施，應(yīng)該在定義ArrayList的時(shí)候指定其容量以減少擴(kuò)容次數(shù)寇损，但是經(jīng)過(guò)以下代碼試驗(yàn)(虛擬機(jī)64位Client模式，JDK1.7.0_45)

inttimes=1000000;

longstartTime=newDate().getTime();

List arrayList=newArrayList(times);

for(inti=0;i

? ? arrayList.add(i);

}

longendTime=newDate().getTime();

System.out.println("ArrayList增加"+times+"次,耗費(fèi)時(shí)間="+(endTime-startTime));

對(duì)于1百萬(wàn)次增加裳食，使用new ArrayList(times)時(shí)耗費(fèi)時(shí)間是90ms矛市，而使用new ArrayList()的耗費(fèi)時(shí)間竟然要短一些，只要81ms诲祸；把times擴(kuò)大到1千萬(wàn)的時(shí)候浊吏，差距更明顯，指定容量的要5秒多救氯，而不指定容量的只要3秒多找田。具體是哪慢了不好下結(jié)論，推測(cè)應(yīng)該是當(dāng)實(shí)際元素較少的時(shí)候着憨，大數(shù)組在尋址墩衙、計(jì)算等方面要慢一些，反過(guò)來(lái)說(shuō)System.arraycopy的效率并沒(méi)有傳說(shuō)中的那么低甲抖，這也是為什么用的本地方法的原因漆改。

LinkedList我們知道內(nèi)部結(jié)構(gòu)是個(gè)線性鏈表，首先看它繼承的不是AbstractList惧眠，而是繼承自AbstractSequentialList籽懦，這是AbstractList的子類(lèi)于个，實(shí)現(xiàn)了線性鏈表的骨架方法氛魁，如get/set，均是通過(guò)ListIterator迭代器來(lái)遍歷實(shí)現(xiàn)厅篓。為什么要?jiǎng)?chuàng)造出AbstractSequentialList這個(gè)類(lèi)秀存？因?yàn)榫€性的不只有鏈表，但線性的都只有通過(guò)迭代器才能找到元素羽氮，與之對(duì)應(yīng)的是隨機(jī)讀取——也就是數(shù)組或链，因此在AbstractSequentialList的類(lèi)注釋里明確說(shuō)明：如果是隨機(jī)讀取的，則使用AbstractList更合適(AbstractList并沒(méi)有提供隨機(jī)讀取的實(shí)現(xiàn)档押，類(lèi)注釋的意思只是說(shuō)如要隨機(jī)讀取澳盐，則AbstractSequentialList沒(méi)有任何幫助，不如實(shí)現(xiàn)AbstractList更準(zhǔn)確)令宿。事實(shí)上叼耙，為了表明集合是否可以根據(jù)索引隨機(jī)讀取，Collection框架專(zhuān)門(mén)定義了一個(gè)空接口RandomAccess粒没，以標(biāo)識(shí)該類(lèi)是否可隨機(jī)讀筛婉，ArrayList、Vector都實(shí)現(xiàn)了這個(gè)接口癞松，而沒(méi)有實(shí)現(xiàn)這個(gè)接口的爽撒，則是不可以通過(guò)下標(biāo)索引來(lái)尋址的入蛆。

LinkedList有比ArrayList在接口上有更豐富的功能，比如addFirst()硕勿、addLast()哨毁、push()、pop(),源武、indexOf()挑庶，同時(shí)它的listIterator()也要比iterator()更常用一些。我們以前常說(shuō)對(duì)于經(jīng)常刪除软能、增加的集合迎捺，使用LinkedList比ArrayList效率要高，這是容易被誤解的查排，LinkedList的尋址相比數(shù)組來(lái)說(shuō)非常地慢凳枝，如果在頻繁增/刪之前需要尋址定位，那么仍然比ArrayList要慢很多跋核，數(shù)十倍地慢岖瑰，所以使用它的時(shí)候要謹(jǐn)慎，不能耍小聰明砂代。LinkedList根據(jù)索引尋址的get(int index)方法蹋订，使用的是簡(jiǎn)單的“二分法”，即如果index小于size的一半刻伊，則從前往后迭代露戒；大于size一半則從后往前迭代。這也是沒(méi)有辦法的事情捶箱，LinkedList是需要保證插入順序的智什，所以不能做任何排序，也就不能使用任何如冒泡丁屎、快速排序之類(lèi)的算法荠锭。有沒(méi)有不需要保證插入順序從而能夠快速尋址的集合呢？TreeSet/HashSet可以快速尋址晨川，但不能有重復(fù)值证九；TreeMap/HashMap同樣是不能有重復(fù)值；Collection框架并沒(méi)有給出能有重復(fù)值同時(shí)又能允許排序的List共虑，應(yīng)該是他們認(rèn)為ArrayList就可以滿足這種場(chǎng)景了愧怜，但類(lèi)庫(kù)中有個(gè)類(lèi)IdentityHashMap，它的hash()方法用的是System.identityHashCode()而不是HashMap所用的key.hashCode看蚜。System.identityHashCode()意思是不管對(duì)象是否實(shí)現(xiàn)了hashCode叫搁，都取Object的hashCode也就是對(duì)象的內(nèi)存地址來(lái)作為key，這樣即使兩個(gè)對(duì)象hashCode相等，也會(huì)被重復(fù)插入(在該類(lèi)的注釋中說(shuō)到了它的一些使用場(chǎng)景渴逻，有興趣的可以仔細(xì)看下)疾党。

我們知道通常的集合都是非線程安全的，表現(xiàn)在多個(gè)線程同時(shí)增/刪時(shí)惨奕，集合大小會(huì)不可預(yù)測(cè)雪位，同時(shí)Iterator盡量保證在迭代過(guò)程中操作是安全的(不保證準(zhǔn)確，但盡量保證不會(huì)有越界問(wèn)題)梨撞，即當(dāng)某線程迭代讀取集合時(shí)雹洗，如有其他線程修改此集合的結(jié)構(gòu)(擴(kuò)大/縮小)，則會(huì)拋出ConcurrentModificationException卧波。那么它是如何實(shí)現(xiàn)的呢时肿？在集合中都會(huì)維護(hù)一個(gè)內(nèi)部計(jì)數(shù)器modCount，如果有影響集合結(jié)構(gòu)的操作(增加港粱、刪除螃成、合并等，而修改不是)查坪，modCount都會(huì)自增1寸宏。在對(duì)集合迭代時(shí)，都會(huì)檢查當(dāng)前迭代時(shí)的操作計(jì)數(shù)器副本expectedModCount(迭代前初始化為和modCount相等)和modCount是否相等

intexpectedModCount = modCount;

finalvoidcheckForComodification() {

if(modCount != expectedModCount)

thrownewConcurrentModificationException();

? ? ? ? }

同樣偿曙，Set氮凝、Map(獲得Entry的HashIterator迭代器)中都有modCount這樣的操作計(jì)數(shù)器。

Set用的相對(duì)少一些望忆，同時(shí)它基本是依托于Map實(shí)現(xiàn)的罩阵。HashSet依托于HashMap，TreeSet依托與TreeMap炭臭，所以先從Map說(shuō)起永脓。

都知道Map是不繼承自Collection的，是頂級(jí)接口鞋仍，為什么這么設(shè)計(jì)？從根本上來(lái)說(shuō)搅吁，Collection是一維的威创，而Map是二維的，那么是否存在三維的谎懦？j2se并沒(méi)有提供這樣的類(lèi)庫(kù)肚豺，但google的guava框架提供了這樣的，如com.google.common.collect.Table界拦，其中R是行key吸申、C是列key，而V就是對(duì)應(yīng)的值，也就是說(shuō)j2se類(lèi)庫(kù)考慮的情況會(huì)比較多截碴，而各開(kāi)源框架就可以根據(jù)自己的定位設(shè)計(jì)出更專(zhuān)業(yè)化的類(lèi)庫(kù)梳侨。

Map接口的方法和Collection差不多，不過(guò)從鍵的維度日丹、值的維度以及把鍵值作為一個(gè)整體的維度走哺，有了keySet()、values()哲虾、entrySet()這樣的接口方法丙躏。

Map提供了抽象類(lèi)AbstractMap，使用entrySet的迭代器循環(huán)束凑，提供如get晒旅、remove、containKey這樣的默認(rèn)實(shí)現(xiàn)汪诉。為什么Map不實(shí)現(xiàn)Iterable接口呢敢朱？我覺(jué)得沒(méi)有必然的原因，Map實(shí)現(xiàn)Iterable接口也無(wú)不可摩瞎，本身它內(nèi)部就有以entrySet的Iterator來(lái)做遍歷的使用拴签，只是作為Map這樣的結(jié)構(gòu)來(lái)說(shuō)，實(shí)現(xiàn)Iterable有些混淆旗们，到底是迭代K呢蚓哩，還是迭代V呢，或者是迭代整體上渴？所以干脆Map本身就不提供迭代器岸梨，而是提供了分別按鍵、值稠氮、鍵值對(duì)三個(gè)迭代器接口曹阔。

HashMap也就是哈希表，我們都知道它內(nèi)部是一個(gè)數(shù)組鏈表的結(jié)構(gòu)隔披，即一個(gè)數(shù)組赃份，

transient Entry[] table = (Entry[]) EMPTY_TABLE;

其中放的是Entry對(duì)象的引用，而每個(gè)Entry內(nèi)部又維持hash相同的下一個(gè)Entry引用形成鏈表奢米。

staticclassEntry implements Map.Entry {

? ? ? ? final K key;

Vvalue;

? ? ? ? Entry next;

inthash;

Entry(inth, K k, V v, Entry n) {

value= v;

? ? ? ? ? ? next = n;

? ? ? ? ? ? key = k;

? ? ? ? ? ? hash = h;

? ? ? ? }

同List一樣抓韩，在其內(nèi)部也維護(hù)叫size的變量，保存元素個(gè)數(shù)鬓长。在new HashMap()的時(shí)候谒拴，table數(shù)組是空的，一旦put則會(huì)擴(kuò)容涉波，

privatevoidinflateTable(inttoSize) {

// Find a power of 2 >= toSize

intcapacity = roundUpToPowerOf2(toSize);

threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);

table =newEntry[capacity];

? ? ? ? initHashSeedAsNeeded(capacity);

? ? }

初始擴(kuò)容的容量是16

staticfinalintDEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

英上，在擴(kuò)容的過(guò)程中同時(shí)會(huì)計(jì)算下次擴(kuò)容的閾值threshold炭序，它=數(shù)組大小*負(fù)載因子。為什么在達(dá)到threshold的時(shí)候擴(kuò)容而不是在達(dá)到數(shù)組最大長(zhǎng)度的時(shí)候苍日？這是為了減少每個(gè)數(shù)組元素上的Entry數(shù)惭聂，因?yàn)楦鶕?jù)hash()方法，在把table數(shù)組占滿之前易遣，很可能在其他元素上已經(jīng)有多個(gè)了(從概率角度)彼妻，但負(fù)載因子又不能太小，否則會(huì)造成很多空間浪費(fèi)豆茫，所以作者權(quán)衡(這里可能也是根據(jù)hash()或某些數(shù)學(xué)原理)取0.75作為負(fù)載因子侨歉，即達(dá)到table數(shù)組3/4時(shí)就擴(kuò)容，并且是擴(kuò)容2倍揩魂，不是ArrayList那樣擴(kuò)容一半

voidaddEntry(inthash, K key, Vvalue,intbucketIndex) {

if((size >= threshold) && (null!= table[bucketIndex])) {

? ? ? ? ? ? resize(2 * table.length);

hash = (null!= key) ? hash(key) : 0;

? ? ? ? ? ? bucketIndex = indexFor(hash, table.length);

? ? ? ? }

createEntry(hash, key,value, bucketIndex);

? ? }

其原因和hash的算法有關(guān)幽邓。為了提高效率，在HashMap里大量使用了&火脉、>>>這樣的二進(jìn)制運(yùn)算牵舵，比如HashMap初始化是1<<<4，在用hashCode在table數(shù)組中取模求余時(shí)用的是hashCode&table.length-1

staticintindexFor(inth,intlength) {

// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";

returnh & (length-1);

? ? }

所以數(shù)組大小保持是2的倍數(shù)倦挂，才能使用這些快速的二進(jìn)制方式畸颅。

關(guān)于上面indexFor我們可以用兩組數(shù)來(lái)算下：

假設(shè)hashCode是17，數(shù)組長(zhǎng)度是7方援，那么就是10001&00110=00000没炒，而正確結(jié)果是17%7=3；假設(shè)數(shù)組長(zhǎng)度是8犯戏，那么就是10001&00111=00001送火，與正確結(jié)果17%8=1相一致。所以保持?jǐn)?shù)組長(zhǎng)度是2的倍數(shù)先匪，就是為了提高HashMap的效率所做的一個(gè)小技巧种吸，同時(shí)在內(nèi)存分配上等都要更快一些。

在根據(jù)key來(lái)定位其hashCode的時(shí)候呀非，并不是簡(jiǎn)單調(diào)用key.hashCode()坚俗，而是再度進(jìn)行了一些運(yùn)算，其目的是為了使最終哈希出來(lái)的值更均勻姜钳，

finalinthash(Object k) {

inth = hashSeed;

if(0 != h && k instanceof String) {

returnsun.misc.Hashing.stringHash32((String) k);

? ? ? ? }

? ? ? ? h ^= k.hashCode();

// This function ensures that hashCodes that differ only by

// constant multiples at each bit position have a bounded

// number of collisions (approximately 8 at default load factor).

? ? ? ? h ^= (h >>> 20) ^ (h >>> 12);

returnh ^ (h >>> 7) ^ (h >>> 4);

? ? }

至于為什么這么做坦冠，比較復(fù)雜，我也沒(méi)搞太清哥桥，尤其是其中為什么選擇20、12激涤、7拟糕、4這樣的來(lái)右移判呕。還有hashSeed的選擇也不太清楚。

這里必須要提下HashMap擴(kuò)容的效率問(wèn)題送滞。前面提到ArrayList的擴(kuò)容性能并不差侠草，而HashMap就完全不一樣了，經(jīng)實(shí)驗(yàn)犁嗅，擴(kuò)容至少帶來(lái)性能下降1半以上边涕，但有臨界點(diǎn)，元素超過(guò)10萬(wàn)數(shù)量級(jí)差距就不明顯了褂微。下面是代碼和測(cè)試結(jié)果

import java.util.Date;

import java.util.HashMap;

import java.util.Map;

publicclassResizePerformanceTest {

publicstaticvoidmain(String[] args) {

? ? ? ? run(1000);

? ? ? ? run(10000);

? ? ? ? run(100000);

? ? ? ? run(1000000);

? ? ? ? run(10000000);

? ? }

publicstaticvoidrun(inttimes) {

System.out.println("增加"+times+"次");

longstartTime=newDate().getTime();

Map map=newHashMap();

for(inti=0;i

? ? ? ? ? ? map.put(i, i);

? ? ? ? }

longendTime=newDate().getTime();

System.out.println("HashMap自動(dòng)擴(kuò)容的方式,增加"+times+"次,耗費(fèi)時(shí)間="+(endTime-startTime));

longstartTime1=newDate().getTime();

Map map1=newHashMap(times);

for(inti=0;i

? ? ? ? ? ? map1.put(i, i);

? ? ? ? }

longendTime1=newDate().getTime();

System.out.println("HashMap預(yù)先指定空間的方式,增加"+times+"次,耗費(fèi)時(shí)間="+(endTime1-startTime1));

? ? }

}

增加1000次

HashMap自動(dòng)擴(kuò)容的方式,增加1000次,耗費(fèi)時(shí)間=2

HashMap預(yù)先指定空間的方式,增加1000次,耗費(fèi)時(shí)間=1

增加10000次

HashMap自動(dòng)擴(kuò)容的方式,增加10000次,耗費(fèi)時(shí)間=15

HashMap預(yù)先指定空間的方式,增加10000次,耗費(fèi)時(shí)間=6

增加100000次

HashMap自動(dòng)擴(kuò)容的方式,增加100000次,耗費(fèi)時(shí)間=25

HashMap預(yù)先指定空間的方式,增加100000次,耗費(fèi)時(shí)間=21

增加1000000次

HashMap自動(dòng)擴(kuò)容的方式,增加1000000次,耗費(fèi)時(shí)間=1707

HashMap預(yù)先指定空間的方式,增加1000000次,耗費(fèi)時(shí)間=1611

增加10000000次

HashMap自動(dòng)擴(kuò)容的方式,增加10000000次,耗費(fèi)時(shí)間=21054

HashMap預(yù)先指定空間的方式,增加10000000次,耗費(fèi)時(shí)間=17820

HashMap大約就說(shuō)這么多功蜓，再說(shuō)說(shuō)TreeMap。TreeMap是種紅黑樹(shù)的結(jié)構(gòu)宠蚂，能夠?qū)υ嘏判?紅黑樹(shù)式撼、數(shù)據(jù)庫(kù)的B樹(shù)、B+樹(shù)求厕，還有冒泡算法著隆、快速排序算法這些算法領(lǐng)域的，現(xiàn)在還真是不那么掌握牢固)呀癣。為了保證排序美浦，提供了兩種方式：一種是Key對(duì)象實(shí)現(xiàn)Comparable接口，另外一種方式是單獨(dú)提供Comparator實(shí)現(xiàn)類(lèi)

publicTreeMap(Comparator comparator) {

this.comparator = comparator;

? ? }

如果本身Key對(duì)象的排序是確定的项栏，比如Integer按大小排序浦辨，String按照字典排序，這些是無(wú)疑義的忘嫉，所以它們都實(shí)現(xiàn)了Comparable接口荤牍，但假如說(shuō)Person對(duì)象，有時(shí)需要按年齡排序庆冕，有時(shí)需要按身高排序康吵，有時(shí)需要按薪酬排序，所以就沒(méi)辦法使用Comparable接口了访递，此時(shí)可以根據(jù)不同排序方式創(chuàng)建相應(yīng)的Comparator類(lèi)晦嵌。

既然是按照順序排列的樹(shù)，那自然就需要提供一些數(shù)據(jù)結(jié)構(gòu)方面的方法拷姿，所以TreeMap有了firstKey()惭载、lastKey()、pollFirstEntry()响巢、lowerEntry(K)描滔、floorEntry(K)、headMap(K)踪古、tailMap(K)含长、desendintMap()這樣的方便方法券腔。

相比HashMap，TreeMap還有個(gè)很大的不同拘泞，就是它不僅是繼承AbstractMap纷纫，還實(shí)現(xiàn)了NavigableMap，NavigableMap繼承自SortedMap陪腌，SortedMap繼承自Map辱魁。SortedMap定義了什么？firstkey()诗鸭、lastKey()染簇、headMap(K)、tailMap(K)只泼、subMap(K,K),NavigableMap定義了pollFirstEntry()剖笙、lowerEntry(K)、floorEntry(K)等方法请唱。為什么這么設(shè)計(jì)弥咪？SortedMap是好理解的，針對(duì)可以排序的Map單獨(dú)設(shè)一個(gè)接口十绑，但為什么要NavigableMap呢聚至？它的lowerEntry(K)之類(lèi)的方法為什么不能合并到SortedMap里去？個(gè)人覺(jué)得這應(yīng)該是兩個(gè)版本時(shí)期導(dǎo)致的本橙，NavigableMap是JDK1.6時(shí)加入的扳躬，此時(shí)已經(jīng)有了不少SortedMap的子類(lèi)，不是很有必要讓子類(lèi)也去實(shí)現(xiàn)這些方法甚亭，所以新加了個(gè)NavigableMap類(lèi)贷币，在需要lower的時(shí)候?qū)崿F(xiàn)它即可，不需要時(shí)就直接實(shí)現(xiàn)SortedMap亏狰。也就是設(shè)計(jì)這種類(lèi)庫(kù)接口時(shí)的粒度問(wèn)題役纹，基本的方法在上一級(jí)接口定義，雖然另外一些方法也是正常使用暇唾，但根據(jù)它的頻率促脉、約束性有所不同可以下放，同時(shí)又要考慮不能使接口數(shù)量太多加大復(fù)雜性策州。

理解了Map瘸味，再來(lái)看Set就很簡(jiǎn)單了。HashSet內(nèi)部完全是以Set元素為key够挂，new Object()為value的HashMap

// Dummy value to associate with an Object in the backing Map

privatestaticfinal Object PRESENT =newObject();

它的一些如size()旁仿、contain()方法都是直接調(diào)用map的方法。

publicintsize() {

returnmap.size();

? ? }

publicboolean add(E e) {

returnmap.put(e, PRESENT)==null;

? ? }

TreeSet也是一樣孽糖，且也有相配套的NavigableSet丁逝、SortedSet汁胆。

從整體來(lái)說(shuō)梭姓，感覺(jué)Set設(shè)計(jì)地不是太好霜幼，其大多數(shù)功能和List很像，僅非重復(fù)這個(gè)頻率并不高的場(chǎng)景不足以單獨(dú)列這一套接口誉尖，而其實(shí)現(xiàn)上又基本上完全依托于Map罪既。如果開(kāi)發(fā)者真有這種場(chǎng)景，完全可以自行用HashMap來(lái)代替铡恕。

集合框架中還有兩個(gè)很有用的輔助類(lèi)琢感，分別是Collections和Arrays，這兩個(gè)就不多介紹了探熔。Collections提供了一系列synchronized集合驹针、unmodified集合以及很少用的Checked集合(類(lèi)型檢查的)，以及toArray(toArray(T[] a)更好用诀艰，因?yàn)槟苤付ǚ祷財(cái)?shù)組的元素類(lèi)型)柬甥、binarySearch(快速查找算法，需要參數(shù)列表元素能排序其垄，否則結(jié)果就不準(zhǔn)確)苛蒲。而Arrays提供了一些如sort、merge绿满、binarySearch臂外、copyOf、asList這樣有效的方法喇颁，注意這里的asList返回的Arrays內(nèi)部實(shí)現(xiàn)的一個(gè)ArrayList漏健，有些方法不支持，比如add橘霎、remove蔫浆，除了set之外基本上就是一個(gè)只讀列表，如果需要可add/remove茎毁，還是需要使用集合的相應(yīng)構(gòu)造函數(shù)或者Collections的copy方法)克懊。

最后兩個(gè)需要說(shuō)的是雖然是在java.util根目錄下，但基本是為java.util.concurrent準(zhǔn)備的七蜘，就是Queue(隊(duì)列)和Deque(雙向隊(duì)列)谭溉。Queue的一系列子類(lèi)如DelayQueue、LinkedBlockQueue更多地是和并發(fā)有關(guān)橡卤，這放到將來(lái)的JUC框架時(shí)再講吧扮念。