集合總結（List、Map、Set）

集合要掌握的是ArrayList、LinkedList、Hashtable、HashMap、ConcurrentHashMap、HashSet的實作原理，當然能掌握CopyOnWrite容器和Queue是再好不過的了。

ArrayList實作原理

ArrayList是基于數組實作的，是一個動态數組，其容量能自動增長。  對于ArrayList而言，它實作List接口、底層使用數組儲存所有元素。其操作基本上是對數組的操作。
ArrayList基于數組實作，可以通過下标索引直接查找到指定位置的元素，是以查找效率高，但每次插入或删除元素，就要大量地移動元素，插入删除元素的效率低。ArrayList中允許元素為null。
           

LinkedList實作原理

LinkedList是基于雙向連結清單的，是List接口的雙向連結清單非同步實作，并允許包括null在内的所有元素。
對于順序通路集合中的元素進行了優化。特别是插入，删除元素的速度特比快。LinkedList即實作了List接口，也實作了Deque接口。是以可以作為棧來使用。當向LinkedList添加對象，實際上則是内部生成一個Entry對象。
           

Hashtable實作原理

Hashtable 是一個散清單，它存儲的内容是鍵值對(key-value)映射。它的key、value都不可以為null。此外，Hashtable中的映射不是有序的。
           

HashMap實作原理

HashMap是基于哈希表的Map接口的非同步實作，允許使用null值和null鍵，但不保證映射的順序。底層使用數組實作，數組中每一項是個連結清單，即數組和連結清單的結合體。
           

ConcurrentHashMap實作原理

ConcurrentHashMap 是一個并發散列映射表的實作，它允許完全并發的讀取，并且支援給定數量的并發更新。ConcurrentHashMap是一個線程安全的支援高并發的HashMap集合類。
![轉載自部落格http://www.cnblogs.com/ITtangtang/p/3948786.html](https://img-blog.csdn.net/20170301170049177?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvemhhbmdmZW5nemhhbmcxMjM=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
           

HashSet實作原理

HashSet采用雜湊演算法，底層用數組存儲資料。HashSet實作Set接口，由哈希表（實際上是一個HashMap執行個體）支援。它不保證set 的疊代順序；特别是它不保證該順序恒久不變。此類允許使用null元素。

CopyOnWrite實作原理

CopyOnWrite容器即寫時複制的容器。通俗的了解是當我們往一個容器添加元素的時候，不直接往目前容器添加，而是先将目前容器進行Copy，複制出一個新的容器，然後新的容器裡添加元素，添加完元素之後，再将原容器的引用指向新的容器。這樣做的好處是我們可以對CopyOnWrite容器進行并發的讀，而不需要加鎖，因為目前容器不會添加任何元素。是以CopyOnWrite容器也是一種讀寫分離的思想，讀和寫不同的容器。

CopyOnWriteArrayList就是ArrayList的并發實作。CopyOnWriteArrayList适合用于讀操作遠遠大于寫操作的情景中。

Queue實作原理

Queue用于模拟隊列資料結構，采用“先進先出”的方式。包括PriorityQueue實作類（儲存隊列元素的順序、按照隊列元素的大小進行重新排序）、Deque接口（代表一個雙端隊列。同時Deque不僅可以作為雙端隊列使用，而且可以被當成棧來使用，是以可以使用出棧，入棧的方法）、LinkedList實作類（LinkedList既可以當做雙端隊列來使用，也可以當做棧來使用）。