經(jīng)過(guò)十一篇文章的分析渗柿，終于把一些主要的集合類的實(shí)現(xiàn)原理分析完了饱亮。本文矾芙，我們將對(duì)之前分析的知識(shí)點(diǎn)做一次總結(jié)。
集合框架：集合有兩個(gè)根接口近上，分別是Collection和Map剔宪。其中Collection中又分為L(zhǎng)ist、Set和Queue壹无。
List
List是一種有序不唯一的元素集合葱绒，有ArrayList和LinkedList等多個(gè)實(shí)現(xiàn)類。
ArrayList
ArrayList實(shí)現(xiàn)了RandomAccess等接口斗锭，支持快速隨機(jī)訪問(wèn)地淀。它是基于數(shù)組實(shí)現(xiàn)的，內(nèi)部維護(hù)了一個(gè)默認(rèn)初始容量為10的elementData數(shù)組岖是。此數(shù)組是一個(gè)動(dòng)態(tài)數(shù)組帮毁，在數(shù)組容量不足以容納當(dāng)前元素的時(shí)候會(huì)進(jìn)行擴(kuò)容，擴(kuò)容到原數(shù)組的3/2豺撑，但是容量最大不超過(guò)0x7fffffff(是一個(gè)16進(jìn)制的數(shù)烈疚，值為：2^31 - 1，是最大的int數(shù)值)聪轿。ArrayList的get和set方法都是通過(guò)操作角標(biāo)完成對(duì)數(shù)組的操作爷肝，所以相對(duì)來(lái)說(shuō)比較快。而add和remove方法屹电，由于涉及到數(shù)組的拷貝阶剑，所以會(huì)比較慢。尤其是在add方法執(zhí)行的過(guò)程中危号，如果當(dāng)前數(shù)組容量不足以容納元素牧愁，會(huì)進(jìn)行擴(kuò)容。所以外莲，在知道最大容量的情況下猪半，最好給它一個(gè)初始容量值兔朦。
LinkedList
LinkedList實(shí)現(xiàn)了Deque等接口，可以當(dāng)作雙端隊(duì)列來(lái)使用磨确。它是基于私有的內(nèi)部類Node完成的對(duì)數(shù)據(jù)的操作沽甥，而Node是一個(gè)雙向鏈表類型的類，所以LinkedList是基于雙向鏈表實(shí)現(xiàn)的乏奥。在Node中存儲(chǔ)著上個(gè)節(jié)點(diǎn)和下個(gè)節(jié)點(diǎn)的信息以及當(dāng)前節(jié)點(diǎn)的值摆舟。對(duì)于LinkedList來(lái)說(shuō)，它的get和set方法執(zhí)行過(guò)程中邓了，會(huì)先將要操作的索引與(當(dāng)前鏈表長(zhǎng)度/2)做比較恨诱，以確定是從前往后遍歷鏈表還是從后往前遍歷鏈表，然后再執(zhí)行相關(guān)的操作骗炉。而add和remove方法中照宝，則是通過(guò)改變鏈表中節(jié)點(diǎn)指針的指向來(lái)完成操作。因此它是的特點(diǎn)是增刪塊句葵，改查慢厕鹃。LinkedList沒有大小限制，可以無(wú)限擴(kuò)容乍丈。
集合中剂碴，還有一種集合Vector，它是一個(gè)線程同步的集合诗赌。不過(guò)現(xiàn)在很少用它汗茄，現(xiàn)在不做具體分析了。之后铭若，我們還會(huì)將線程同步的集合類洪碳，到時(shí)候，再將它們做比較叼屠。
Set
Set是一種無(wú)序且唯一的元素集合瞳腌，對(duì)兩個(gè)元素的比較不是使用"=="而是使用"equals"。它包含HashSet镜雨、TreeSet即EnumSet等等嫂侍。
HashSet
HashSet是基于HashMap實(shí)現(xiàn)的，它的構(gòu)造函數(shù)的作用就是初始化一個(gè)HashMap對(duì)象荚坞。對(duì)其中元素的操作都是通過(guò)調(diào)用HashMap對(duì)應(yīng)的方法完成的挑宠。HashSet的元素就是底層HashMap的key，而底層HashMap的value是一個(gè)Object類型的PRESENT對(duì)象颓影。
Java集合(九)--基于Map實(shí)現(xiàn)的Set簡(jiǎn)析
LinkedHashSet
LinkedHashSet是HashSet的子類各淀，與其不同的是，LinkedHashSet維護(hù)了一個(gè)貫穿其所有條目的雙向鏈表诡挂，鏈表中的元素按照其插入順序排序碎浇，且LinkedHashSet是基于LinkedHashMap實(shí)現(xiàn)的临谱。
Java集合(九)--基于Map實(shí)現(xiàn)的Set簡(jiǎn)析
TreeSet
TreeSet是基于TreeMap實(shí)現(xiàn)的，內(nèi)部的元素通過(guò)其自然順序或者是構(gòu)建時(shí)傳入的Comparator進(jìn)行排序奴璃，它不支持null元素悉默。它的構(gòu)造方法就是實(shí)例化一個(gè)TreeMap對(duì)象，且對(duì)元素的操作都是通過(guò)調(diào)用TreeMap中的相關(guān)方法實(shí)現(xiàn)的苟穆。它的元素就是底層TreeMap的key抄课，而底層TreeMap的value是一個(gè)Object類型的PRESENT對(duì)象。
Java集合(九)--基于Map實(shí)現(xiàn)的Set簡(jiǎn)析
EnumSet
不同于上面的Set類雳旅，EnumSet不是基于Map實(shí)現(xiàn)的剖膳。它繼承了Enum類，實(shí)現(xiàn)了AbstractSet等接口岭辣。EnumSet中的所有元素必須來(lái)自單個(gè)枚舉類型，枚舉集在其內(nèi)部表示為位向量甸饱，即使用一個(gè)位表示一個(gè)元素的狀態(tài)沦童。它不允許有空值，但可以檢測(cè)是否有空值叹话。EnumSet元素按照在枚舉類中的枚舉常量的順序進(jìn)行排序偷遗，且在迭代過(guò)程中，不會(huì)出現(xiàn)fail-fast驼壶。
EnumSet是一個(gè)抽象類氏豌，以枚舉類中是否包含64個(gè)枚舉常量為分界線，EnumSet分別會(huì)實(shí)例化RegularEnumSet(小于等于64)和JumboEnumSet(大于64)兩種EnumSet的實(shí)現(xiàn)類的對(duì)象來(lái)進(jìn)行實(shí)際的操作热凹。在RegularEnumSet中使用long類型的elements泵喘，通過(guò)其二進(jìn)制表現(xiàn)形式上不同位的狀態(tài)來(lái)表述數(shù)據(jù)是否存儲(chǔ)。而JumboEnumSet則是維護(hù)了一個(gè)long類型的elements數(shù)組般妙，具體操作原理同RegularEnumSet類似纪铺。
Map
Map是通過(guò)鍵值對(duì)的映射關(guān)系來(lái)存儲(chǔ)數(shù)據(jù)的，它包含HashMap碟渺、TreeMap及EnumMap等多個(gè)實(shí)現(xiàn)類鲜锚。
HashMap
HashMap中是一個(gè)基于拉鏈法實(shí)現(xiàn)的散列表，內(nèi)部由數(shù)組苫拍、鏈表和紅黑樹實(shí)現(xiàn)芜繁。其中，數(shù)組用來(lái)通過(guò)索引確定鍵值對(duì)的位置绒极，而鏈表和紅黑樹則用來(lái)保存數(shù)據(jù)骏令，包括key所對(duì)應(yīng)的hash值(進(jìn)過(guò)處理)，key集峦、value和下個(gè)節(jié)點(diǎn)的地址伏社。HashMap通過(guò)容量和加載因子來(lái)確定是否對(duì)數(shù)組擴(kuò)容抠刺。其中，默認(rèn)初始容量為16(容量的增長(zhǎng)必須以2的次方式增長(zhǎng)摘昌，且小于1<<30)速妖，默認(rèn)加載因子為0.75。加載因子其實(shí)就是控制是時(shí)間換空間聪黎，還是空間換時(shí)間罕容。
HashMap在擴(kuò)容的時(shí)候，會(huì)判斷鏈表長(zhǎng)度稿饰，當(dāng)鏈表長(zhǎng)度為8的時(shí)候锦秒，會(huì)判斷是擴(kuò)容還是轉(zhuǎn)為紅黑樹結(jié)構(gòu)(判斷依據(jù)是數(shù)組長(zhǎng)度是否大于64)。而當(dāng)鏈表長(zhǎng)度小于6的時(shí)候喉镰，又會(huì)將紅黑樹轉(zhuǎn)換為鏈表旅择。
LinkedHashMap
LinkedHashMap是HashMap的子類，與HashMap的不同的是它維護(hù)了一個(gè)貫穿其所有條目的雙向鏈表侣姆。它通過(guò)布爾屬性的accessOrder來(lái)決定迭代順序生真，true為訪問(wèn)順序，false為插入順序捺宗。他在使用put或get等方法時(shí)柱蟀，會(huì)判斷如果是按照訪問(wèn)順序排序，則會(huì)將剛剛操作的元素放到鏈表的尾部蚜厉，這樣就形成了一個(gè)簡(jiǎn)單的LRU长已。
Java集合(十)--LinkedHashMap簡(jiǎn)析
TreeMap
TreeMap是基于紅黑樹實(shí)現(xiàn)的，它的鍵根據(jù)自然順序或者是創(chuàng)建時(shí)傳入的Comparator進(jìn)行排序昼牛，其key應(yīng)該是實(shí)現(xiàn)了Comparable接口的對(duì)象术瓮。對(duì)其中的元素做增刪操作后，需要對(duì)元素做修正贰健，以保證還是紅黑樹結(jié)構(gòu)斤斧。
WeakHashMap
WeakHashMap是一個(gè)帶弱鍵的單鏈表的Map，與HashMap類似霎烙，他也是通過(guò)容量和加載因子來(lái)控制其擴(kuò)容撬讽。當(dāng)某個(gè)鍵不再正常使用的時(shí)候，對(duì)應(yīng)的鍵值對(duì)就會(huì)被移除悬垃。這種操作是通過(guò)ReferenceQueue和Reference完成的游昼。其原理為，當(dāng)WeakHashMap的某個(gè)鍵被GC時(shí)尝蠕，該鍵會(huì)被添加到queue中烘豌。然后，在執(zhí)行某個(gè)操作的過(guò)程中看彼，會(huì)先去刪除與queue中對(duì)應(yīng)的元素廊佩，接著再去執(zhí)行相應(yīng)的操作囚聚。
Java集合(七)--WeakHashMap簡(jiǎn)析
EnumMap
EnumMap是用于枚舉類型鍵的專用Map實(shí)現(xiàn)。其映射中的所有鍵必須來(lái)自創(chuàng)建映射時(shí)顯式或隱式指定的單個(gè)枚舉類型标锄，枚舉映射在內(nèi)部表示為數(shù)組顽铸。 EnumMap的鍵按其鍵的自然順序（枚舉常量的聲明順序）維護(hù)，且在迭代過(guò)程中料皇，不會(huì)出現(xiàn)fail-fast谓松。EnumMap不允許使用空鍵，但是践剂，可以測(cè)試是否存在空鍵或刪除空鍵鬼譬，且允許空值。它內(nèi)部維護(hù)了keyUniverse和vals兩個(gè)數(shù)組逊脯。其中优质，keyUniverse數(shù)組中包含的元素，是指定的枚舉類型中所有的枚舉常量军洼。vals數(shù)組長(zhǎng)度與keyUniverse數(shù)組長(zhǎng)度相同盆赤，且EnumMap的鍵值對(duì)的映射是keyUniverse數(shù)組與vals數(shù)組中相同位置的元素的映射。
還有一個(gè)HashTable歉眷，它繼承自Dictionary類，是同步的颤枪，鍵值不可以為空『辜瘢現(xiàn)在一般不用了，等分析ConCurrentHashMap的時(shí)候會(huì)把它拿出來(lái)說(shuō)一說(shuō)畏纲。
Collections
這是一個(gè)為集合提供的工具類,可以為集合提供排序扇住、查找、替換及同步控制等輔助方法盗胀。比如艘蹋，上面提到的集合都可以使用Collections提供的SynchronizedXXX(XXX代表：Collection、List票灰、Set及Map)方法實(shí)現(xiàn)同步女阀。
好了，到此非同步的集合類就分析完成了屑迂。年底要做項(xiàng)目了浸策，博客先放一放。
