java集合提供兩大接口衍生：Collection和Map接口
1.Collection接口包含一批對象的集合运挫；
2.Map接口在Collection基礎(chǔ)上纸巷，為每個對象指定key身辨，并使用Entry保存每個key-value對，實(shí)現(xiàn)通過key快速定位到對象；
3.List類集合
? ? ?List接口繼承自Collection，用于定義以列表形式存儲的集合鼎姐，List接口為集合中的每個對象分配了一個索引(index)，標(biāo)記該對象在List中的位置，并可以通過index定位到指定位置的對象炕桨。
4.List接口常用的實(shí)現(xiàn)類
? ? ? ?4.1ArrayList：基于數(shù)組來實(shí)現(xiàn)集合的功能饭尝，其內(nèi)部維護(hù)了一個可變長的對象數(shù)組，集合內(nèi)所有對象存儲于這個數(shù)組中献宫，并實(shí)現(xiàn)該數(shù)組長度的動態(tài)伸縮钥平。
? ? ? ?4.2LinkedList：基于鏈表來實(shí)現(xiàn)集合的功能，其實(shí)現(xiàn)了靜態(tài)類Node姊途，集合中的每個對象都由一個Node保存涉瘾，每個Node都擁有到自己的前一個和后一個Node的引用
注意：1）ArrayList隨機(jī)訪問高，基于數(shù)組實(shí)現(xiàn)可直接定位目標(biāo)對象捷兰，ListedList需從頭Node或尾Node遍歷才能定位到目標(biāo)對象立叛。
2）linkedList在頭/尾節(jié)點(diǎn)執(zhí)行插入/刪除操作的效率比ArrayList要高
3）ArrayList每次擴(kuò)容的容量是當(dāng)前的1.5倍，所以LinkedList所占的內(nèi)存空間要更小一些
4）兩者遍歷效率接近贡茅，LinkedList遍歷需要iterator方式囚巴，不使用get()方式，否則效率很低友扰。
? ? ? ? 4.3Vector：與ArrayList一樣都是基于數(shù)組實(shí)現(xiàn)的集合，區(qū)別在于vector是線程安全（常用方法基本都是synchronized）庶柿；vector可以定義數(shù)組長度擴(kuò)容因子村怪，ArrayList不能。
? ? ? ? 4.4CopyOnWriteArrayList：可以認(rèn)為ArrayList線程安全版浮庐，主要 CopyOnWriteArrayList在寫操作會先復(fù)制出一個副本甚负，在新的副本上執(zhí)行操作，然后修改引用审残。這種機(jī)制讓 CopyOnWriteArrayList可以對讀操作不加鎖梭域，這就使CopyOnWriteArrayList的讀效率遠(yuǎn)高于Vector。 CopyOnWriteArrayList的理念比較類似讀寫分離搅轿，適合讀多寫少的多線程場景病涨。但要注意，CopyOnWriteArrayList只能保證數(shù)據(jù)的最終一致性璧坟，并不能保證數(shù)據(jù)的實(shí)時一致性既穆，如果一個寫操作正在進(jìn)行中且并未完成，此時的讀操作無法保證能讀到這個寫操作的結(jié)果雀鹃。
注意：二者均是線程安全的幻工、基于數(shù)組實(shí)現(xiàn)的List
Vector是【絕對】線程安全的，CopyOnWriteArrayList只能保證讀線程會讀到【已完成】的寫結(jié)果黎茎，但無法像Vector一樣實(shí)現(xiàn)讀操作的【等待寫操作完成后再讀最新值】的能力
CopyOnWriteArrayList讀性能遠(yuǎn)高于Vector囊颅，并發(fā)線程越多優(yōu)勢越明顯
CopyOnWriteArrayList占用更多的內(nèi)存空間
5.Map類集合
? ? ? ?將key和value封裝至Entry對象中，Map存儲的元素實(shí)際是Entry。調(diào)用keySet()和values()時才將keySet和values對象實(shí)例化踢代。
Map接口常用實(shí)現(xiàn)類：
? ? ? ?5.1.HashMap:將Entry對象存儲在數(shù)組中盲憎，通過哈希表實(shí)現(xiàn)對Entry的快速訪問。每個Entry中key的哈希值決定Entry在數(shù)組中的位置奸鬓。通過key快速找到Entry焙畔，獲得key對應(yīng)的value。如果兩個不同key計算的index一樣串远，也就是兩個不同的key對應(yīng)數(shù)組同一個位置（哈希沖突）宏多，HashMap處理沖突的方法是拉鏈法，也就說每個位置保存實(shí)際是一個Entry鏈表澡罚，鏈表中每個Entry都擁有指向鏈表中后一個Entry引用伸但。當(dāng)發(fā)生哈希沖突時，沖突的Entry追加至鏈表的頭部留搔。當(dāng)HashMap尋址時發(fā)現(xiàn)某個Key對應(yīng)數(shù)組index上有多個Entry更胖，便會遍歷該位置上Entry鏈表。直到找到隔显。
? ? ? ?5.2.HashTable實(shí)現(xiàn)思路和HashMap一致却妨，都是通過數(shù)組存儲Entry，以key的哈希值計算Entry在數(shù)組中index括眠，用拉鏈法解決哈希沖突彪标。最大的區(qū)別HashTable是線程安全的
? ? ? 5.3.ConcurrentHashMap:是HashMap線程安全版，比HashTable更加高效的并發(fā)性能掷豺。
? ? ? ?HashTable在讀寫會鎖定整個Entry數(shù)組捞烟，所以數(shù)據(jù)越多性能越差。ConcurrentHashMap使用分離鎖思路解決并發(fā)性能当船，將Entry數(shù)組拆分16個Segment中题画，通過Hash算法決定Entry應(yīng)存儲在那個Segment。這樣實(shí)現(xiàn)寫操作只對一個Segment加鎖德频。提高并發(fā)寫性能苍息。
在讀操作，ConcurrentHashMap絕大多數(shù)不需要加鎖抱婉，其Entry中value是volatile档叔，保證value被修改時線程可見性，無需加鎖便實(shí)現(xiàn)線程安全的讀操作蒸绩。
HashEntry類
static final class HashEntry {
final int hash;
final K key;
volatile V value;
volatile HashEntry next;
}
? ? ? 注意：ConcurrentHashMap保證讀操作能獲取到已存在Entry的value的最新值衙四，同時也能保證讀操作可獲取到已完成的寫操作的內(nèi)容，但如果寫操作是在創(chuàng)建一個新的Entry患亿，那么在寫操作沒有完成時传蹈，讀操作是有可能獲取不到這個Entry的押逼。
總結(jié)：1.三者數(shù)據(jù)存儲機(jī)制原理基本一致
? ? ? ? ?2.HashMap不是線程安全的，多線程除了不能保證數(shù)據(jù)一致性惦界，還可能在rehash階段引發(fā)Entry鏈表成環(huán)挑格，導(dǎo)致死循環(huán)
? ? ? ? ?3.HashTable線程安全，保證數(shù)據(jù)一致但性能問題沾歪，并發(fā)越多性能越差
? ? ? ? ?4.ConcurrentHashMap線程是線程安全的漂彤，使用分離鎖和volatile方法極大提升讀寫性能，同時保證大多數(shù)情況下數(shù)據(jù)一致性灾搏。但不能絕對保證（一個線程向Map加入Entry還沒結(jié)束之前挫望，其他線程不能讀到新加入的Entry）
? ? ? ??5.4LinkedHashMap 與HashMap一致，不同在于前者在Entry基礎(chǔ)上增加到前一個插入和后一個插入Entry的引用狂窑，實(shí)現(xiàn)按照Entry插入順序進(jìn)行遍歷媳板。
? ? ? ? 5.5TreeMap 基于紅黑樹實(shí)現(xiàn)Map，其Entry類擁有左右子節(jié)點(diǎn)和父節(jié)點(diǎn)的引用泉哈，同時記錄自己的顏色
static final class Entry implements Map.Entry {
K key;
V value;
Entry left = null;
Entry right = null;
Entry parent;
boolean color = BLACK;
}
紅黑樹是高效的平衡二叉樹蛉幸，及任何結(jié)點(diǎn)值都大于左結(jié)點(diǎn)，小于右節(jié)點(diǎn)丛晦，所以TreeMap能夠?qū)崿F(xiàn)Entry排序和快速查找奕纫。
6.Set類集合
? ? ? ?set接口繼承Collection，存儲不含重復(fù)元素烫沙。每個Set內(nèi)都有一個同類型Map實(shí)例若锁，set把元素作為key存儲在自己Map實(shí)例中，value則是一個空的Object斧吐。
Set的常用實(shí)現(xiàn)也包括 HashSet、TreeSet仲器、ConcurrentSkipListSet等煤率，原理和對應(yīng)的Map實(shí)現(xiàn)完全一致
7.Queue/Deque類集合
? ? ? ? Queue和Deque接口繼承Collection接口，實(shí)現(xiàn)FIFO（先進(jìn)先出）的集合乏冀。二者的區(qū)別在于蝶糯，Queue只能在隊尾入隊，隊頭出隊辆沦，而Deque接口則在隊頭和隊尾都可以執(zhí)行出/入隊操作
ConcurrentLinkedQueue是基于鏈表實(shí)現(xiàn)的隊列昼捍，隊列中每個Node擁有到下一個Node的引用。由于Node類的成員都是volatile的肢扯，所以ConcurrentLinkedQueue自然是線程安全的
面試題：
1.ArrayList和LinkedList有什么區(qū)別
? ? ? ? ArrayList是基于動態(tài)數(shù)組的結(jié)構(gòu)妒茬，使用索引在數(shù)組中查找和讀取速度很快，時間復(fù)雜度O(1)蔚晨，刪除數(shù)據(jù)開銷很大乍钻。LinkedList插入或刪除效率高時間復(fù)雜度O(1)肛循，它不需要改變數(shù)組大小，也不需要裝滿后重新裝入新數(shù)組银择。LinkedList需要更多的內(nèi)存每個節(jié)點(diǎn)都會存儲數(shù)據(jù)和前后節(jié)點(diǎn)的位置多糠。
2.用過哪些Map類，都有什么區(qū)別浩考，HashMap是線程安全的嗎,并發(fā)下使用的Map是什么夹孔，他們內(nèi)部原理分別是什么，比如存儲方式析孽，hashcode搭伤，擴(kuò)容，默認(rèn)容量等绿淋？
? ? ? 2.1.HashMap線程不安全闷畸，允許有null值，HashTable線程安全吞滞，不允許有null值佑菩，效率低，每個方法都是synchronized
? ? ? 2.2 HashMap將Entry存儲在數(shù)組中裁赠，通過哈希值實(shí)現(xiàn)Entry快速訪問殿漠，當(dāng)產(chǎn)生HashMap沖突采用拉鏈法。
? ? ? ? 2.3 ConcurrentHashMap是hashMap線程安全版佩捞，HashTable在讀寫鎖定整個Entry數(shù)組性能差绞幌，ConcurrentHashMap使用分離鎖思路解決并發(fā)性能，將Entry數(shù)組拆分16個Segment中一忱，通過Hash算法決定Entry應(yīng)存儲在那個Segment莲蜘。這樣實(shí)現(xiàn)寫操作只對一個Segment加鎖提高并發(fā)寫性能，在讀操作時帘营，value值通過volatile修飾的樱调，達(dá)到線程可見性酵幕。
? ? ? ? 2.4HashTable默認(rèn)的初始大小為11侮腹，之后每次擴(kuò)充為原來的2n+1菠镇。HashMap默認(rèn)的初始化大小為16，之后每次擴(kuò)充為原來的2倍禀梳。
3.JAVA8的ConcurrentHashMap為什么放棄了分段鎖杜窄，有什么問題嗎，如果你來設(shè)計怎么設(shè)計算途？
? ? ? ?JDK8放棄Segment分段鎖塞耕，啟用全新的方式：CAS算法，其實(shí)底層依然使用數(shù)組”+鏈表+紅黑樹方式思想嘴瓤。
4. 有沒順序的Map實(shí)現(xiàn)類荷科，如果有唯咬，他們是怎么保證有序的 ？
? ? ? ?TreeMap和LinkedHashMap是有序的畏浆。（TreeMap默認(rèn)升序胆胰，LinkedHashMap則記錄了插入順序）。
5.hashset與hashMap區(qū)別
? ? ? ? HashSet實(shí)現(xiàn)了Set接口刻获，它不允許集合中有重復(fù)的值蜀涨，當(dāng)我們提到HashSet時，第一件事情就是在將對象存儲在HashSet之前蝎毡，要先確保對象重寫equals()和hashCode()方法厚柳，這樣才能比較對象的值是否相等，以確保set中沒有儲存相等的對象沐兵。如果我們沒有重寫這兩個方法别垮，將會使用這個方法的默認(rèn)實(shí)現(xiàn)。
public boolean add(Object o)方法用來在Set中添加元素扎谎，當(dāng)元素值重復(fù)時則會立即返回false碳想，如果成功添加的話會返回true。
HashSet和HashMap的區(qū)別
*HashMap**HashSet*
HashMap實(shí)現(xiàn)了Map接口HashSet實(shí)現(xiàn)了Set接口
HashMap儲存鍵值對HashSet僅僅存儲對象
使用put()方法將元素放入map中使用add()方法將元素放入set中
HashMap中使用鍵對象來計算hashcode值HashSet使用成員對象來計算hashcode值毁靶，對于兩個對象來說hashcode可能相同胧奔，所以equals()方法用來判斷對象的相等性，如果兩個對象不同的話预吆，那么返回false
HashMap比較快龙填，因為是使用唯一的鍵來獲取對象HashSet較HashMap來說比較慢
參考：http://weizhan.51cto.com/article/view/591c117ef2dd875f6f298f42?is_share=1
