1、ArrayList
先看其源碼：
private static final int DEFAULT_CAPACITY = 10; //初始內存大小
transient Object[] elementData; //真實數據存放地， 被 transient 修飾的屬性變量不會被序列化(不被網絡傳輸、持久化)
實現是基於動態數組的數據結構，每個元素在內存中存儲地址是連續的。每次擴容會固定為1.5倍，所以當你ArrayList達到一定量之後會是一種很大的浪費，並且每次擴容的過程是內部複製數組到新數組；對於每個元素的檢索，ArrayList要優於LinkedList。非線程安全
ArrayList默認容量是10，如果初始化時一開始指定了容量，或者通過集合作為元素，則容量為指定的大小或參數集合的大小。每次擴容時新容量按老容量1.5倍計算，如果新容量數大於所需最小容量則為新增後所需的最小容量。如果計算後的新容量數超過限制的容量數 MAX_ARRAY_SIZE ( Integer.MAX_VALUE - 8 )，則用所需的最小容量與 MAX_ARRAY_SIZE 進行判斷，超過則指定為 Integer 的最大值，否則指定為限制容量大小。然後通過數組的複製將原數據複製到一個更大(新的容量大小)的數組。
Vector與其大致相同，都是基於數組的數據結構，但是線程安全（擴容等方法加了synchronized），vector每次擴容容量是翻倍，即為原來的2倍
2、LinkedList
transient int size = 0;
LinkedList是採用鏈表的方式來實現List接口的,它本身有自己特定的方法，如: addFirst(),addLast(),getFirst(),removeFirst()等. 由於是採用鏈表實現的,因此在進行 新增 和 刪除 動作時在效率上要比ArrayList要好得多 ! 適合用來實現Stack(堆棧)與Queue(隊列),前者先進後出，後者是先進先出。非線程安全
理論上效率好，實際得看新增、刪除位置或者說實際中數據量小，效率差異忽略不計。
3、HashSet
內部也是基於 Hashmap 實現，不允許有重複元素。無序。初始容量16，擴容因子0.75 。在HashSet中，元素都存到HashMap鍵值對的Key上面，而Value時有一個統一的值private static final Object PRESENT = new Object();定義一個虛擬的Object對象作為HashMap的value，將此對象定義為static final。
4、LinkedHashSet
集成 HashSet ，但內部也是基於 LinkedHashMap ，與HashSet 相比無新方法，但元素是有序的。
5、TreeSet
內部基於TreeMap，TreeSet中存放的元素是有序的（不是插入時的順序，是有按關鍵字大小排序的），且元素不能重複。存放自定義對象，需自定義對象實現Comparable 接口，並重寫接口中的compareTo方法，當 compareTo方法
- 返回 0 時 只會存一個元素，認為是相同的元素，這時就不再向TreeSet中插入相同的新元素。
- 返回負數會倒序存儲，認為新插入的元素比上一個元素小，於是二叉樹存儲時，會存在根的左側，讀取時就是倒序序排列的。
- 返回自然數時 認為新插入的元素比上一個元素大，於是二叉樹存儲時，會存在根的右側，讀取時就是正序排列的。
6、HashMap
無序，非線程安全，無重複key，允許key和value空值 ，key為空值時其hashCode值定為了0，從而將其存放在哈希表的第0個bucket中。默認的初始化大小為16，之後每次擴充為原來的2倍。
a. JDK7中HashMap採用的是 數組（位桶）+鏈表的方式，即我們常說的散列鏈表的方式，
transient Entry
HashMap 在底層將 key-value 當成一個整體進行處理，這個整體就是一個 Entry 對象。HashMap 底層採用一個 Entry[] 數組來保存所有的 key-value 對，當需要存儲一個 Entry 對象時，會根據hash算法來決定其在數組中的存儲位置，在根據equals方法決定其在該數組位置上的鏈表中的存儲位置；當需要取出一個Entry時，也會根據hash算法找到其在數組中的存儲位置，再根據equals方法從該位置上的鏈表中取出該Entry。
HashMap的resize（rehash）
當HashMap中的元素越來越多的時候，hash衝突的幾率也就越來越高，因為數組的長度是固定的。所以為了提高查詢的效率，就要對HashMap的數組進行擴容，數組擴容這個操作也會出現在ArrayList中，這是一個常用的操作，而在HashMap數組擴容之後，最消耗性能的點就出現了：原數組中的數據必須重新計算其在新數組中的位置，並放進去，這就是resize。
那麼HashMap什麼時候進行擴容呢？當HashMap中的元素個數超過數組大小loadFactor時，就會進行數組擴容，loadFactor的默認值為0.75，這是一個折中的取值。也就是說，默認情況下，數組大小為16，那麼當HashMap中元素個數超過160.75=12的時候，就把數組的大小擴展為 2*16=32，即擴大一倍，然後重新計算每個元素在數組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經預知HashMap中元素的個數，那麼預設元素的個數能夠有效的提高HashMap的性能。
HashMap的性能參數
HashMap 包含如下幾個構造器：
- HashMap()：構建一個初始容量為 16，負載因子為 0.75 的 HashMap。
- ashMap(int initialCapacity)：構建一個初始容量為 initialCapacity，負載因子為 0.75 的 HashMap。
- HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的負載因子創建一個 HashMap。
HashMap的基礎構造器HashMap(int initialCapacity, float loadFactor)帶有兩個參數，它們是初始容量initialCapacity和負載因子loadFactor。
負載因子loadFactor衡量的是一個散列表的空間的使用程度，負載因子越大表示散列表的裝填程度越高，反之愈小。對於使用鏈表法的散列表來說，查找一個元素的平均時間是O(1+a)，因此如果負載因子越大，對空間的利用更充分，然而後果是查找效率的降低；如果負載因子太小，那麼散列表的數據將過於稀疏，對空間造成嚴重浪費。
HashMap的實現中，通過threshold字段來判斷HashMap的最大容量：
threshold = (int)(capacity * loadFactor);
結合負載因子的定義公式可知，threshold就是在此loadFactor和capacity對應下允許的最大元素數目，超過這個數目就重新resize，以降低實際的負載因子。默認的的負載因子0.75是對空間和時間效率的一個平衡選擇。當容量超出此最大容量時， resize後的HashMap容量是容量的兩倍。
b、JDK8中採用的是數組（位桶）+鏈表/紅黑樹（有關紅黑樹請查看紅黑樹）的方式，也是非線程安全的。當某個位桶的鏈表的長度達到某個閥值的時候，這個鏈表就將轉換成紅黑樹。當同一個hash值的節點數不小於8時，將不再以單鏈表的形式存儲了，會被調整成一顆紅黑樹。這就是JDK7與JDK8中HashMap實現的最大區別。
transient Node
R-B Tree，全稱是Red-Black Tree，又稱為“紅黑樹”，它一種特殊的二叉查找樹。紅黑樹的每個節點上都有存儲位表示節點的顏色，可以是紅(Red)或黑(Black)。
7、HashTable
無序，線程安全，無重複key，不允許key和value空值，HashTable默認的初始大小為11，之後每次擴充為原來的2n+1。內部是採用synchronized來保證線程安全的，但在線程競爭激烈的情況下HashTable的效率下降得很快因為synchronized關鍵字會造成代碼塊或方法成為為臨界區(對同一個對象加互斥鎖)，當一個線程訪問臨界區的代碼時，其他線程也訪問同一臨界區時，會進入阻塞或輪詢狀態。究其原因，實際上是有獲取鎖意向的線程的數目增加，但是鎖還是隻有單個，導致大量的線程處於輪詢或阻塞，導致同一時間段有效執行的線程的增量遠不及線程總體增量。
8、LinkedHashMap
有序，非線程安全，Key和Value都允許空，繼承了HashMap。維護一個額外的雙向鏈表保證了迭代順序。
源碼內部有Entry
9、CocurrentHashMap
不允許key、value為null，
利用鎖分段技術增加了鎖的數目，從而使爭奪同一把鎖的線程的數目得到控制。 鎖分段技術就是對數據集進行分段，每段競爭一把鎖，不同數據段的數據不存在鎖競爭，從而有效提高 高併發訪問效率。CocurrentHashMap在get方法是無需加鎖的，因為用到的共享變量都採用volatile關鍵字修飾，保證共享變量在線程之間的可見性(每次讀取都先同步緩存和內存，直接從內存中獲取值，雖然不是原子操作，但根據JAVA內存模型的happen before原則，對volatile字段的寫入操作先於讀操作，能夠保證不會髒讀),volatile為了讓變量提供線程之間的內存可見性，會禁止程序執行結果的重排序（導致緩存優化的效果降低）。
實際使用中 Map
比較
- JDK6,7中的ConcurrentHashmap主要使用Segment來實現減小鎖（ReentrantLock）粒度，把HashMap分割成若干個Segment（分段），在put的時候需要鎖住Segment，get時候不加鎖，使用volatile來保證可見性，當要統計全局時（比如size），首先會嘗試多次計算modcount 來確定，這幾次嘗試中，是否有其他線程進行了修改操作，如果沒有，則直接返回size。如果有，則需要依次鎖住所有的Segment來計算；
- jdk7中ConcurrentHashmap中，當長度過長碰撞會很頻繁，鏈表的增改刪查操作都會消耗很長的時間，影響性能,所以jdk8 中完全重寫了concurrentHashmap, 主要設計上的變化有以下幾點:
- 不採用segment而採用node，鎖住node來實現減小鎖粒度。
- 設計了MOVED狀態 當resize的中過程中 線程2還在put數據，線程2會幫助resize。
- 使用3個CAS操作來確保node的一些操作的原子性，這種方式代替了鎖。
- sizeCtl的不同值來代表不同含義，起到了控制的作用。
JDK8中使用synchronized而不是ReentrantLock，
10.TreeMap
- 有序的key-value集合，它是通過紅黑樹實現的。該映射根據其鍵的自然順序進行排序，默認是升序的，如果我們需要改變排序方式，則需要使用比較器：Comparator ，該方法主要是根據第一個參數o1,小於、等於或者大於o2分別返回負整數、0或者正整數。TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。
11 cas原理
CAS:Compare and Swap, 翻譯成比較並交換。 CAS有3個操作數，內存值V，舊的預期值A，要修改的新值B。當且僅當預期值A和內存值V相同時，將內存值V修改為B，否則什麼都不做。
CAS通過調用JNI的代碼實現的。JNI:Java Native Interface為JAVA本地調用，允許java調用其他語言。
而compareAndSwapInt就是藉助C來調用CPU底層指令實現的。
閱讀更多 碼農筆記Day 的文章
