簡(jiǎn)介

1. 整理容器的基本知識(shí)
2. 整理關(guān)于不同容器線程安全方面的知識(shí)

根據(jù)以下資料整理

http://www.reibang.com/p/047e33fdefd2
http://blog.csdn.net/jiyiqinlovexx/article/details/51030720

常用容器關(guān)系圖

快速了解

Collection（接口）

1. 代表的是單個(gè)元素對(duì)象的序列嫂侍，（可以有序/無(wú)序，可重復(fù)/不可重復(fù) 等雕拼，具體依據(jù)具體的子接口Set扬霜，List，Queue等）稿存；
2. 調(diào)用toArray(T[] a)可以轉(zhuǎn)為數(shù)組
3. 區(qū)別于java.util.Collections:Collections是一個(gè)正對(duì)于Conllection的工具類笨篷，提供了許多實(shí)用的靜態(tài)方法

Map（接口）

1. 代表的是“鍵值對(duì)”對(duì)象的集合（同樣可以有序/無(wú)序 等依據(jù)具體實(shí)現(xiàn)）
2. 提供了三種遍歷方式：
3. Set<K> keySet(): 返回所有key的Set集合
4. Collection<V> values(): 返回所有values的集合
5. Set< Map.Entry< K, V>> entrySet()： 是將整個(gè)Entry對(duì)象（也就是返回鍵-值形式的集合）作為元素返回所有的數(shù)據(jù)，這種方式比先通過(guò)keySet()獲取所有key再根據(jù)key獲取值效率要高

List（Collection的子接口）

1. 一個(gè)有序的Collection（或者叫做序列）瓣履。使用這個(gè)接口可以精確掌控元素的插入率翅，還可以根據(jù)index獲取相應(yīng)位置的元素。
2. 可重復(fù)
3. 有順序
4. 提供了特殊的iterator遍歷器袖迎，叫做ListIterator冕臭。這種遍歷器允許遍歷時(shí)插入，替換燕锥，刪除辜贵，雙向訪問(wèn)。 并且還有一個(gè)重載方法允許從一個(gè)指定位置開始遍歷归形。

ArrayList（List接口的實(shí)現(xiàn)）

1. ArrayList是一個(gè)實(shí)現(xiàn)了List接口的可變數(shù)組
2. 可以插入null
3. 它的size, isEmpty, get, set, iterator,add這些方法的時(shí)間復(fù)雜度是O(1),如果add n個(gè)數(shù)據(jù)則時(shí)間復(fù)雜度是O(n).
4. ArrayList不是synchronized的托慨。

LinkedList（List接口的實(shí)現(xiàn)）

1. LinkedList是一個(gè)鏈表維護(hù)的序列容器。和ArrayList都是序列容器暇榴，一個(gè)使用數(shù)組存儲(chǔ)厚棵，一個(gè)使用鏈表存儲(chǔ)蕉世。
2. 數(shù)組和鏈表2種數(shù)據(jù)結(jié)構(gòu)的對(duì)比：
3. 查找方面。數(shù)組的效率更高婆硬，可以直接索引出查找讨彼，而鏈表必須從頭查找。
4. 插入刪除方面柿祈。特別是在中間進(jìn)行插入刪除哈误，這時(shí)候鏈表體現(xiàn)出了極大的便利性，只需要在插入或者刪除的地方斷掉鏈然后插入或者移除元素躏嚎，然后再將前后鏈重新組裝蜜自，但是數(shù)組必須重新復(fù)制一份將所有數(shù)據(jù)后移或者前移。
5. 在內(nèi)存申請(qǐng)方面卢佣，當(dāng)數(shù)組達(dá)到初始的申請(qǐng)長(zhǎng)度后重荠，需要重新申請(qǐng)一個(gè)更大的數(shù)組然后把數(shù)據(jù)遷移過(guò)去才行（所以當(dāng)創(chuàng)建ArrayList，最好能給一個(gè)合理的初始大小）虚茶。而鏈表只需要?jiǎng)討B(tài)創(chuàng)建即可戈鲁。
6. LinkedList還實(shí)現(xiàn)了Deque接口，Deque接口是繼承Queue的嘹叫。所以LinkedList還支持隊(duì)列的pop婆殿，push，peek操作

mark

Set（Collection的子接口）

1. 存儲(chǔ)不重復(fù)的元素集合

HashSet（Set接口的實(shí)現(xiàn)）

1. 基于HashMap進(jìn)行存儲(chǔ)（所以所有的add罩扇，remove等操作其實(shí)都是HashMap的add婆芦、remove操作。遍歷操作其實(shí)就是HashMap的keySet的遍歷）
2. 不保證順序喂饥，且不保證下次遍歷的順序和之前一樣
3. 允許null元素

LinkedHashSet（Set接口的實(shí)現(xiàn)）

1. 基于LinkedHashMap
2. 相對(duì)于HashSet來(lái)說(shuō)就是一個(gè)可以保持順序的Set集合

TreeSet（Set接口的實(shí)現(xiàn)）

1. 基于TreeMap
2. TreeSet內(nèi)的元素必須實(shí)現(xiàn)Comparable接口
3. 一組有次序的集合消约，如果沒(méi)有指定排序規(guī)則Comparator，則會(huì)按照自然排序员帮。（自然排序即e1.compareTo(e2) == 0作為比較）

mark

Queue（Collection的子接口）

Map

HashMap

1. 最基礎(chǔ)最常用的一種Map或粮，它無(wú)序，以散列表的方式進(jìn)行存儲(chǔ)

LinkedHashMap

1. 相對(duì)于HashMap來(lái)說(shuō)區(qū)別是捞高，LinkedHashMap遍歷的時(shí)候具有順序氯材，可以保存插入的順序，（還可以設(shè)置最近訪問(wèn)的元素也放在前面棠枉，即LRU）
2. 其實(shí)LinkedHashMap的存儲(chǔ)還是跟HashMap一樣浓体，采用哈希表方法存儲(chǔ)泡挺，只不過(guò)LinkedHashMap多維護(hù)了一份head辈讶，tail鏈表。

TreeMap

1. TreeMap平時(shí)用的不多娄猫，TreeMap會(huì)實(shí)現(xiàn)SortMap接口贱除，定義一個(gè)排序規(guī)則生闲，這樣當(dāng)遍歷TreeMap的時(shí)候，會(huì)根據(jù)規(guī)定的排序規(guī)則返回元素月幌。

WeakHashMap

1. 特點(diǎn)是碍讯，當(dāng)除了自身有對(duì)key的引用外，此key沒(méi)有其他引用那么此map會(huì)自動(dòng)丟棄此值

mark

以上扯躺，感謝http://www.reibang.com/p/047e33fdefd2 捉兴，如有冒犯，請(qǐng)聯(lián)系我刪除

關(guān)于容器的線程安全

同步容器類

JDK1.0開始有兩個(gè)很老的同步容器類：Vector和HashTable
JDK1.2之后Collections工具類中添加了一些工廠方法返回類似的同步封裝器類：
Collections.synchronizedXXX(XXX xxx)

實(shí)現(xiàn)方式：

將它們的狀態(tài)封裝起來(lái)录语，并對(duì)每一個(gè)公有方法進(jìn)行同步倍啥。
其中Vector就是Object[]+synchronized方法，Hashtable是HashtableEntry[]+synchronized方法澎埠。而synchronizedXXX()方法返回的同步封裝器類更是簡(jiǎn)單地將傳進(jìn)來(lái)的Collection的所有方法封裝為synchronized方法而已虽缕。

缺點(diǎn)：

1. 通過(guò)同步方法將訪問(wèn)操作串行化，導(dǎo)致并發(fā)環(huán)境下效率低下

2. 復(fù)合操作（迭代蒲稳、條件運(yùn)算如沒(méi)有則添加等）非線程安全氮趋，需要客戶端代碼來(lái)實(shí)現(xiàn)加鎖。

并發(fā)容器類

并發(fā)容器出現(xiàn)的最大的需求就是提升同步容器類的性能江耀！
可以對(duì)比（非并發(fā)容器類）看看剩胁，將單線程版本和并發(fā)版本做一個(gè)比較。

HashMap和HashSet的并發(fā)版本

1. ConcurrentHashMap<K, V>（HashMap的并發(fā)版本）
   版本：JDK5
   目標(biāo)：代替Hashtable祥国、synchronizedMap摧冀，支持復(fù)合操作
   原理：采用一種更加細(xì)粒度的加鎖機(jī)制“分段鎖”，任意數(shù)量讀取線程可以并發(fā)讀取系宫，任意數(shù)量的讀取線程和一個(gè)寫線程可以并發(fā)訪問(wèn)索昂，一定數(shù)量的寫入線程可以并發(fā)訪問(wèn)。并發(fā)環(huán)境下ConcurrentHashMap帶來(lái)了更高的吞吐量扩借，而在單線程環(huán)境下只損失了很小的性能椒惨。

2. CopyOnWriteArraySet<E>（HashSet的并發(fā)版本）
   版本：JDK5
   目標(biāo)：代替synchronizedSet
   原理：CopyOnWriteArraySet基于CopyOnWriteArrayList實(shí)現(xiàn)，其唯一的不同是在add時(shí)調(diào)用的是CopyOnWriteArrayList的addIfAbsent方法潮罪，其遍歷當(dāng)前Object數(shù)組康谆，如Object數(shù)組中已有了當(dāng)前元素，則直接返回嫉到，如果沒(méi)有則放入Object數(shù)組的尾部沃暗，并返回。

TreeMap和TreeSet的并發(fā)版本

1. ConcurrentSkipListMap<K, V>（TreeMap的并發(fā)版本）
   版本：JDK6
   目標(biāo)：代替synchronizedSortedMap(TreeMap)
   原理：Skip list（跳表）是一種可以代替平衡樹的數(shù)據(jù)結(jié)構(gòu)何恶，默認(rèn)是按照Key值升序的孽锥。Skip list讓已排序的數(shù)據(jù)分布在多層鏈表中，以0-1隨機(jī)數(shù)決定一個(gè)數(shù)據(jù)的向上攀升與否，通過(guò)"空間來(lái)?yè)Q取時(shí)間"的一個(gè)算法惜辑。ConcurrentSkipListMap提供了一種線程安全的并發(fā)訪問(wèn)的排序映射表唬涧。內(nèi)部是SkipList（跳表）結(jié)構(gòu)實(shí)現(xiàn)，在理論上能夠在O（log（n））時(shí)間內(nèi)完成查找盛撑、插入碎节、刪除操作。

2. ConcurrentSkipListSet<E>（TreeSet的并發(fā)版本）
   版本：JDK6
   目標(biāo)：代替synchronizedSortedSet
   原理：內(nèi)部基于ConcurrentSkipListMap實(shí)現(xiàn)抵卫！

ArrayList和LinkedList的并發(fā)版本

1. CopyOnWriteArrayList<E>（ArrayList的并發(fā)版本）
   目標(biāo)：代替Vector狮荔、synchronizedList
   原理：CopyOnWriteArrayList的核心思想是利用高并發(fā)往往是讀多寫少的特性，對(duì)讀操作不加鎖介粘，對(duì)寫操作轴合，先復(fù)制一份新的集合，在新的集合上面修改碗短，然后將新集合賦值給舊的引用受葛，并通過(guò)volatile 保證其可見性，當(dāng)然寫操作的鎖是必不可少的了偎谁。

2. ConcurrentLinkedQueue<E>（LinkedList的并發(fā)版本）
   目標(biāo)：代替Vector总滩、synchronizedList
   特點(diǎn)：基于鏈表實(shí)現(xiàn)的FIFO隊(duì)列，特別注意單線程環(huán)境中LinkedList除了可以用作鏈表巡雨，也可用作隊(duì)列闰渔，并發(fā)版本也一樣

阻塞隊(duì)列：BlockingQueue

版本：JDK1.5
特點(diǎn)：拓展了Queue，增加了可阻塞的插入和獲取等操作
實(shí)現(xiàn)類
LinkedBlockingQueue：基于鏈表實(shí)現(xiàn)的可阻塞的FIFO隊(duì)列
ArrayBlockingQueue：基于數(shù)組實(shí)現(xiàn)的可阻塞的FIFO隊(duì)列
PriorityBlockingQueue：按優(yōu)先級(jí)排序的隊(duì)列
原理：通過(guò)ReentrantLock實(shí)現(xiàn)線程安全铐望，通過(guò)Condition實(shí)現(xiàn)阻塞和喚醒冈涧。

以上，感謝http://blog.csdn.net/jiyiqinlovexx/article/details/51030720 正蛙，如有冒犯督弓，請(qǐng)聯(lián)系我刪除