集合類型主要有3種：set(集）针姿、list(列表）和map(映射)赖欣。
集合接口分為：Collection和Map
? ? ? ? ? ? ? ? ? ? ? ? ? ?其中l(wèi)ist、set實現(xiàn)了Collection接口
為什么Map不實現(xiàn)Collection接口瓢颅？
答：因為Map包含key-value對课蔬，它提供抽取key或value列表集合的方法，但是它不適合“一組對象”規(guī)范容客。
? ? ? Map里面有?
? ? ? ? ? ? ? ?Set keySet
? ? ? ? ? ? ? ?Collection values
? ? ? ?兩個集合氛悬。
1.集合包
? ? 集合包最常用的有Collection和Map兩個接口的實現(xiàn)類，Colleciton用于存放多個單對象耘柱，Map用于存放Key-Value形式的鍵值對如捅。
? Collection中最常用的又分為兩種類型的接口：List和Set，兩者最明顯的差別為List支持放入重復(fù)的元素调煎，而Set不支持镜遣。
? List最常用的實現(xiàn)類有：ArrayList、LinkedList、Vector及Stack悲关；Set接口常用的實現(xiàn)類有：HashSet谎僻、TreeSet。
1.1 ArrayList
? ArrayList基于數(shù)組方式實現(xiàn)寓辱，默認(rèn)構(gòu)造器通過調(diào)用ArrayList(int)來完成創(chuàng)建艘绍，傳入的值為10，實例化了一個Object數(shù)組秫筏，并將此數(shù)組賦給了當(dāng)前實例的elementData屬性诱鞠，此Object數(shù)組的大小即為傳入的initialCapacity，因此調(diào)用空構(gòu)造器的情況下會創(chuàng)建一個大小為10的Object數(shù)組这敬。
插入對象：add(E)
????基于已有元素數(shù)量加1作為名叫minCapacity的變量航夺，比較此值和Object數(shù)組的大小，若大于數(shù)組值崔涂，那么先將當(dāng)前Object數(shù)組值賦給一個數(shù)組對象阳掐，接著產(chǎn)生一個鑫的數(shù)組容量值。此值的計算方法為當(dāng)前數(shù)組值*1.5+1冷蚂，如得出的容量值仍然小于minCapacity缭保，那么就以minCapacity作為新的容量值，調(diào)用Arrays.copyOf來生成新的數(shù)組對象蝙茶。
????還提供了add(int,E)這樣的方法將元素直接插入指定的int位置上涮俄，將目前index及其后的數(shù)據(jù)都往后挪一位，然后才能將指定的index位置的賦值為傳入的對象尸闸，這種方式要多付出一次復(fù)制數(shù)組的代價。還提供了addAll
?刪除對象：remove(E)
? ?這里調(diào)用了faseRemove方法將index后的對象往前復(fù)制一位孕锄，并將數(shù)組中的最后一個元素的值設(shè)置為null吮廉，即釋放了對此對象的引用。 還提供了remove(int)方法來刪除指定位置的對象畸肆，remove(int)的實現(xiàn)比remove(E)多了一個數(shù)組范圍的檢測宦芦，但少了對象位置的查找，因此性能會更好轴脐。
獲取單個對象：get(int)
遍歷對象：iterator()
判斷對象是否存在：contains(E)
?總結(jié)：
????1调卑，ArrayList基于數(shù)組方式實現(xiàn)，無容量的限制大咱；
????2恬涧，ArrayList在執(zhí)行插入元素時可能要擴容，在刪除元素時并不會減小數(shù)組的容量（如希望相應(yīng)的縮小數(shù)組容量碴巾，可以調(diào)用ArrayList的trimToSize()）溯捆，在查找元素時要遍歷數(shù)組，對于非null的元素采取equals的方式尋找厦瓢；
????3提揍，ArrayList是非線程安全的啤月。
1.2 LinkedList
????LinkedList基于雙向鏈表機制，所謂雙向鏈表機制劳跃，就是集合中的每個元素都知道其前一個元素及其后一個元素的位置谎仲。在LinkedList中，以一個內(nèi)部的Entry類來代表集合中的元素刨仑，元素的值賦給element屬性郑诺，Entry中的next屬性指向元素的后一個元素，Entry中的previous屬性指向元素的前一個元素贸人，基于這樣的機制可以快速實現(xiàn)集合中元素的移動间景。
總結(jié)：
????1，LinkedList基于雙向鏈表機制實現(xiàn)艺智；
????2倘要，LinkedList在插入元素時，須創(chuàng)建一個新的Entry對象十拣，并切換相應(yīng)元素的前后元素的引用封拧；在查找元素時，須遍歷鏈表夭问；在刪除元素時泽西，要遍歷鏈表，找到要刪除的元素缰趋，然后從鏈表上將此元素刪除即可捧杉，此時原有的前后元素改變引用連在一起；
????3秘血，LinkedList是非線程安全的味抖。
1.3 Vector
? ? 其add、remove灰粮、get(int)方法都加了synchronized關(guān)鍵字仔涩，默認(rèn)創(chuàng)建一個大小為10的Object數(shù)組，并將capacityIncrement設(shè)置為0粘舟。容量擴充策略：如果capacityIncrement大于0熔脂，則將Object數(shù)組的大小擴大為現(xiàn)有size加上capacityIncrement的值；如果capacity等于或小于0柑肴，則將Object數(shù)組的大小擴大為現(xiàn)有size的兩倍霞揉，這種容量的控制策略比ArrayList更為可控。
????Vector是基于Synchronized實現(xiàn)的線程安全的ArrayList晰骑，但在插入元素時容量擴充的機制和ArrayList稍有不同零聚，并可通過傳入capacityIncrement來控制容量的擴充。
1.4 Stack
????Stack繼承于Vector，在其基礎(chǔ)上實現(xiàn)了Stack所要求的后進先出(LIFO)的彈出與壓入操作隶症，其提供了push政模、pop、peek三個主要的方法：
????push操作通過調(diào)用Vector中的addElement來完成蚂会；
????pop操作通過調(diào)用peek來獲取元素淋样，并同時刪除數(shù)組中的最后一個元素；
????peek操作通過獲取當(dāng)前Object數(shù)組的大小胁住，并獲取數(shù)組上的最后一個元素趁猴。
1.5 HashSet
????默認(rèn)構(gòu)造創(chuàng)建一個HashMap對象
add(E)：調(diào)用HashMap的put方法來完成此操作，將需要增加的元素作為Map中的key彪见，value則傳入一個之前已創(chuàng)建的Object對象儡司。
remove(E)：調(diào)用HashMap的remove(E)方法完成此操作。
contains(E)：HashMap的containsKey
iterator()：調(diào)用HashMap的keySet的iterator方法余指。
HashSet不支持通過get(int)獲取指定位置的元素捕犬，只能自行通過iterator方法來獲取。
總結(jié)：
????1酵镜，HashSet基于HashMap實現(xiàn)碉碉，無容量限制；
????2淮韭，HashSet是非線程安全的垢粮。
1.6 TreeSet
????TreeSet和HashSet的主要不同在于TreeSet對于排序的支持，TreeSet基于TreeMap實現(xiàn)靠粪。
1.7?HashMap
????HashMap空構(gòu)造蜡吧，將loadFactor設(shè)為默認(rèn)的0.75，threshold設(shè)置為12占键，并創(chuàng)建一個大小為16的Entry對象數(shù)組昔善。
????基于數(shù)組+鏈表的結(jié)合體(鏈表散列)實現(xiàn)，將key-value看成一個整體捞慌，存放于Entity[]數(shù)組，put的時候根據(jù)key hash后的hashcode和數(shù)組length-1按位與的結(jié)果值判斷放在數(shù)組的哪個位置柬批，如果該數(shù)組位置上若已經(jīng)存放其他元素啸澡，則在這個位置上的元素以鏈表的形式存放。如果該位置上沒有元素則直接存放氮帐。
當(dāng)系統(tǒng)決定存儲HashMap中的key-value對時嗅虏，完全沒有考慮Entry中的value，僅僅只是根據(jù)key來計算并決定每個Entry的存儲位置上沐。我們完全可以把Map集合中的value當(dāng)成key的附屬皮服，當(dāng)系統(tǒng)決定了key的存儲位置之后，value隨之保存在那里即可。get取值也是根據(jù)key的hashCode確定在數(shù)組的位置龄广，在根據(jù)key的equals確定在鏈表處的位置硫眯。
1 while (capacity < initialCapacity)
2? ? ? capacity <<= 1;
以上代碼保證了初始化時HashMap的容量總是2的n次方，即底層數(shù)組的長度總是為2的n次方择同。它通過h & (table.length -1)?來得到該對象的保存位两入，若length為奇數(shù)值，則與運算產(chǎn)生相同結(jié)果敲才，便會形成鏈表裹纳，盡可能的少出現(xiàn)鏈表才能提升hashMap的效率，所以這是hashMap速度上的優(yōu)化紧武。
擴容resize():
當(dāng)HashMap中的元素越來越多的時候剃氧，hash沖突的幾率也就越來越高，因為數(shù)組的長度是固定的阻星。所以為了提高查詢的效率朋鞍，就要對HashMap的數(shù)組進行擴容，而在HashMap數(shù)組擴容之后迫横，最消耗性能的點就出現(xiàn)了：原數(shù)組中的數(shù)據(jù)必須重新計算其在新數(shù)組中的位置番舆，并放進去，這就是resize矾踱。那么HashMap什么時候進行擴容呢恨狈？當(dāng)HashMap中的元素個數(shù)超過數(shù)組大小*loadFactor時，就會進行數(shù)組擴容呛讲，loadFactor的默認(rèn)值為0.75禾怠，這是一個折中的取值。
負(fù)載因子衡量的是一個散列表的空間的使用程度贝搁，負(fù)載因子越大表示散列表的裝填程度越高吗氏，反之愈小。負(fù)載因子越大雷逆，對空間的利用更充分弦讽，然而后果是查找效率的降低；如果負(fù)載因子太小膀哲，那么散列表的數(shù)據(jù)將過于稀疏往产，對空間造成嚴(yán)重浪費。
HashMap的實現(xiàn)中某宪，通過threshold字段來判斷HashMap的最大容量仿村。threshold就是在此loadFactor和capacity對應(yīng)下允許的最大元素數(shù)目，超過這個數(shù)目就重新resize兴喂，以降低實際的負(fù)載因子蔼囊。默認(rèn)的的負(fù)載因子0.75是對空間和時間效率的一個平衡選擇焚志。
initialCapacity*2，成倍擴大容量畏鼓，HashMap(int initialCapacity, float loadFactor)：以指定初始容量酱酬、指定的負(fù)載因子創(chuàng)建一個?HashMap。不設(shè)定參數(shù)滴肿，則初始容量值為16岳悟，默認(rèn)的負(fù)載因子為0.75，不宜過大也不宜過小泼差，過大影響效率贵少，過小浪費空間。擴容后需要重新計算每個元素在數(shù)組中的位置堆缘，是一個非常消耗性能的操作滔灶，所以如果我們已經(jīng)預(yù)知HashMap中元素的個數(shù)，那么預(yù)設(shè)元素的個數(shù)能夠有效的提高HashMap的性能吼肥。
? ? ?HashTable數(shù)據(jù)結(jié)構(gòu)的原理大致一樣录平，區(qū)別在于put、get時加了同步關(guān)鍵字缀皱，而且HashTable不可存放null值斗这。
在高并發(fā)時可以使用ConcurrentHashMap，其內(nèi)部使用鎖分段技術(shù)啤斗，維持這鎖Segment的數(shù)組表箭，在數(shù)組中又存放著Entity[]數(shù)組，內(nèi)部hash算法將數(shù)據(jù)較均勻分布在不同鎖中钮莲。
總結(jié)：
????1免钻，HashMap采用數(shù)組方式存儲key、value構(gòu)成的Entry對象崔拥，無容量限制极舔；
????2，HashMap基于key hash尋找Entry對象存放到數(shù)組的位置链瓦，對于hash沖突采用鏈表的方式解決拆魏；
????3，HashMap在插入元素時可能會擴大數(shù)組的容量慈俯，在擴大容量時須要重新計算hash渤刃，并復(fù)制對象到新的數(shù)組中；
????4肥卡，HashMap是非線程安全的溪掀。
詳細(xì)說明：http://zhangshixi.iteye.com/blog/672697?
Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析：
? ? ? ?http://www.importnew.com/28263.html
1.8 TreeMap
????TreeMap基于紅黑樹的實現(xiàn)事镣，因此它要求一定要有key比較的方法步鉴，要么傳入Comparator實現(xiàn)揪胃，要么key對象實現(xiàn)Comparable借口。在put操作時氛琢，基于紅黑樹的方式遍歷喊递，基于comparator來比較key應(yīng)放在樹的左邊還是右邊，如找到相等的key阳似，則直接替換掉value骚勘。
