集合
常用集合關(guān)系圖
集合分為單列集合和雙列集合兩種：
一.單列集合：
Collection是單列集合的頂級(jí)接口：
其中有三類集合：
1.List（ArrayList,LinkedList,Vector等）
有序的可以重復(fù)的集合，JDK1.6和JDK1.7的時(shí)候創(chuàng)建集合時(shí)初始容量是10，而JDK1.8中默認(rèn)容量是0，首次添加元素不超過10時(shí)，容量變?yōu)?0。
List的加載因子系數(shù)<=1，即當(dāng)元素個(gè)數(shù)超過（容器長度*加載因子系數(shù)）時(shí)，進(jìn)行擴(kuò)容
①ArrayList集合是動(dòng)態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，它的隨機(jī)訪問和遍歷的效率比較高，在需要頻繁的讀取集合中的元素的時(shí)候，推薦使用ArrayList，但是增刪操作要影響數(shù)組內(nèi)的其他數(shù)據(jù)的下標(biāo)，所以增刪操作的效率比較慢。
ArrayList每次擴(kuò)增容量為原本的1.5倍，JDK1.8之后算法為oldCapacity+(oldCapacity >>1)。
ArrayList的擴(kuò)容上限約21億，int的最大值。
②LinkedList集合是雙向的鏈表的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，沒有下標(biāo)，通過鏈來連接數(shù)據(jù)，在非首尾的增加和刪除操作時(shí)，LinkedList比ArrayList的效率要高，推薦使用LinkedList，但是查詢的時(shí)候，每次都要從首位移動(dòng)指針往后依次查找，所以查詢的效率比較慢。
③Vector集合與ArrayList集合類似，內(nèi)部都是維護(hù)一個(gè)數(shù)組，只不過前者在方法上加上了synchronized關(guān)鍵字、線程安全、效率低，后者線程不安全，但是效率高。
Vector每次擴(kuò)增容量為原來的兩倍。
2.Set（HashSet等）
除了TreeSet集合外元素?zé)o序，不允許元素重復(fù)。
Set的擴(kuò)容量為原來的2倍，加載因子為0.75。
①HashSet集合是基于HashMap實(shí)現(xiàn)的，HashSet底層使用HashMap來保存元素，HashMap是數(shù)組和鏈表的數(shù)據(jù)結(jié)構(gòu)（下面HashMap具體介紹），HashSet和HashMap的初始容量都是16
3.Queue/Deque
①Q(mào)ueue隊(duì)列，隊(duì)列是一種特殊的線性表，它只允許在表的前端進(jìn)行刪除操作，而在表的后端進(jìn)行插入操作，LinkedList類實(shí)現(xiàn)了Queue接口，可以吧LinkedList當(dāng)成Queue來用
②Deque雙端隊(duì)列，可以在兩端進(jìn)行插入和刪除操作
二.雙列集合：
1.Map（HashMap,Hashtable等）
①HashMap集合線程非安全，使用鍵值對(duì)（key-value）的方式存儲(chǔ)數(shù)據(jù)，允許key和value為null，鍵（key）不能重復(fù)，值（value）可以重復(fù)，它和HashSet是基于哈希表的鏈表散列的數(shù)據(jù)結(jié)構(gòu)，即底層是數(shù)組和鏈表（模擬指針）實(shí)現(xiàn)的，到了JDK1.8后變成了數(shù)組+鏈表+紅黑樹。
HashMap底層是通過一個(gè)transient（防止反序列化） Node[]table node數(shù)組實(shí)現(xiàn)的,接下來單個(gè)Node數(shù)據(jù)類型：是HanshMap靜態(tài)內(nèi)部類。靜態(tài)內(nèi)部類中有一個(gè)成員變量：
Node<K,V>next;
?通過該成員變量，其實(shí)底層用的是單向鏈表,性能低
HashMap 基于 Hash 算法實(shí)現(xiàn)的，我們通過 put(key,value)存儲(chǔ)，get(key)來獲取。當(dāng)傳入 key 時(shí)，HashMap 會(huì)根據(jù) key. hashCode() 計(jì)算出 hash 值，根據(jù) hash 值將 value 保存在 bucket 里。當(dāng)計(jì)算出的 hash 值相同時(shí)并且equals比較的值不同時(shí)，我們稱之為 hash 沖突，HashMap 的做法是用鏈表和紅黑樹存儲(chǔ)相同 hash 值的 value。當(dāng) hash 沖突的個(gè)數(shù)比較少時(shí)，使用鏈表否則使用紅黑樹。
在向HashMap中添加數(shù)據(jù)的時(shí)候，會(huì)先調(diào)用hashCode方法計(jì)算并比較hash值，當(dāng)hash相同的情況在調(diào)用equals方法比較，當(dāng)兩個(gè)均不相同時(shí)判定集合中不存在，然后將數(shù)據(jù)插入到集合中。兩個(gè)對(duì)象的hash值相同，但是不一定是同一個(gè)對(duì)象，也就是說自身的值可能會(huì)不相同。
（例如：String a ="通話";String b="重地";這兩個(gè)字符串生成的hash值同為1179395，但是其自身的值卻不相同）
從圖中可以看出：?
1）HashMap繼承于AbstractMap類，實(shí)現(xiàn)了Map接口。Map是"key-value鍵值對(duì)"接口，AbstractMap實(shí)現(xiàn)了"鍵值對(duì)"的通用函數(shù)接口。?
2）HashMap是通過"拉鏈法"實(shí)現(xiàn)的哈希表。它包括幾個(gè)重要的成員變量：table,?size,?threshold,?loadFactor,?modCount。
table是一個(gè)Entry[]數(shù)組類型，而Entry實(shí)際上就是一個(gè)單向鏈表。哈希表的"key-value鍵值對(duì)"都是存儲(chǔ)在Entry數(shù)組中的。
size是HashMap的大小，它是HashMap保存的鍵值對(duì)的數(shù)量。?
threshold是HashMap的閾值，用于判斷是否需要調(diào)整HashMap的容量。threshold的值="容量*加載因子"，當(dāng)HashMap中存儲(chǔ)數(shù)據(jù)的數(shù)量達(dá)到threshold時(shí)，就需要將HashMap的容量加倍。
loadFactor就是加載因子。?
modCount是用來實(shí)現(xiàn)fail-fast機(jī)制的。
LinkedHashMap:底層也是一個(gè)Entry<k,v>數(shù)組，接下來單個(gè)Entry數(shù)據(jù)類型
Entry<K,V>before,after;
②Hashtable線程安全，是線程安全的，但是其同步鎖是全局鎖，效率很低，所以Hashtable現(xiàn)在是保留類不建議使用。
單線程的情況下HashMap效率高，推薦使用；多線程的情況下可以使用java.util.concurrent包下的ConcurrentHashMap替代，它之前采用Segment方式的分段同步鎖，將所有的數(shù)據(jù)分割成幾部分的數(shù)據(jù)區(qū)域，一個(gè)區(qū)域一把鎖，訪問不同區(qū)域時(shí)不會(huì)收到影響，JDK1.8版本之后采用優(yōu)化后的synchronized，將每一個(gè)數(shù)據(jù)分別鎖住，不同數(shù)據(jù)間的訪問不會(huì)收到影響，效率大大增加，并且線程是安全的，多線程并發(fā)情況下很推薦使用！
雙列集合的五種遍歷方式
1）通過map.keySey();獲取所有的key的Set集合，然后可以通過增強(qiáng)for自動(dòng)迭代，也可以獲取迭代器iterator然后用while循環(huán)進(jìn)行手動(dòng)遍歷
2）通過map.values();獲得所有的value的集合，返回值為Collecton，然后用增強(qiáng)for自動(dòng)迭代
3）（推薦）通過map.entrySet();獲取所有的鍵值對(duì)的Set集合，Set集合中保存的是每一個(gè)鍵值對(duì)（Map.Entry），然后可以通過增強(qiáng)for自動(dòng)迭代，也可以獲取迭代器iterator然后用while循環(huán)進(jìn)行手動(dòng)遍歷
三.關(guān)于迭代器
迭代器是Iterator接口：該接口中有三個(gè)核心方法 ，維護(hù)指針可以向下移動(dòng)（next），移動(dòng)到指定位置后，取出當(dāng)前位置的元素（next），以及重置指針操作（remove）。
為什么數(shù)組和集合可以使用for循環(huán)進(jìn)行迭代遍歷？
解析：所有的數(shù)組和集合都實(shí)現(xiàn)了Iterable接口，Iterable接口中只有一個(gè)方法，iterator方法返回值類型是Iterator類型，我們將思路轉(zhuǎn)到Iterator，我們發(fā)現(xiàn)該接口三個(gè)方法。hasNext，next和remove，最主要的是hasNext和next。他們?cè)诘讓訋臀覀內(nèi)ゾS護(hù)的可以被迭代數(shù)組或者集合的迭代策略。
四.JDK版本差異更新
排序算法
線程安全的集合
集合擴(kuò)容的算法
五.集合在特定場景下的應(yīng)用方案
最近瀏覽可以選取LinkedList
先進(jìn)先出可以考慮Queue隊(duì)列
先進(jìn)后出可以考慮Stack，遞歸，壓棧 ，彈棧?
