摘要：解決沖突開放定址法拉鏈法表解決沖突開放定址法再哈希法鏈地址法建立公共溢出區并發包中的線程安全的集合容器線程安全的，不允許為，默認個的數組，每個中實現就是了，通過定位。基于數組，線程安全的集合類，容量可以限制。

　　List?元素是有序的、可重復，實現List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

　　ArrayList：動態數組；默認容量為10,每次增加元素時會進行容量檢查,當容量到達size-1時進行擴容(add(E e)中先調用了ensureCapacity(size+1)方法，之后將元素的索引賦給elementData[size]，而后size自增)，擴容0.5倍+1，如?ArrayList的容量為10，一次擴容后是容量為16；非同步，查詢速度快，擅長于隨機訪問(?size、isEmpty、get、set、iterator 和 listIterator )；線程安全的arraylist:Collections.synchronizedList(List l)函數返回一個線程安全的ArrayList類(synchronized代碼塊)，也可以使用concurrent并發包下的CopyOnWriteArrayList類(add、remove方法：final ReentrantLock lock = this.lock;lock.lock();)。

　　LinkedList：雙向鏈表；非同步，通過較低的代價在List中進行插入和刪除操作(get，remove，insert)(prev，next)。

　　Vector：數組；默認容量為10，加載因子為1：即當元素個數超過容量長度時，進行擴容擴容增量：原容量的1倍，如?Vector的容量為10，一次擴容后是容量為20；同步(源代碼中Vector的成員方法都加了synchronized)。

　　Stack：Stack繼承自Vector(基本的push和pop 方法，還有peek方法得到棧頂的元素，empty方法測試堆棧是否為空，search方法檢測一個元素在堆棧中的位置)。

　　Set是一種不包括重復元素的Collection，實現了Set接口的集合有：EnumSet、HashSet、TreeSet。

　　EnumSet：是枚舉的專用Set。所有的元素都是枚舉類型。

　　HashSet：?堪稱查詢速度最快的集合，底層實現是一個HashMap（保存數據）(HashSet所有的構造都是構造出一個新的HashMap)，實現Set接口，內部以HashCode來實現的。它內部元素的順序是由哈希碼來決定的，所以它不保證set 的迭代順序；特別是它不保證該順序恒久不變；默認初始容量為16，加載因子為0.75，擴容增量：原容量的1倍；線程不安全，存取速度快。

　　TreeSet：??基于TreeMap，內部以TreeMap來實現。它是使用元素的自然順序對元素進行排序，或者根據創建Set 時提供的Comparator?進行排序，具體取決于使用的構造方法。

　　Map是一個雙列集合，沒有繼承Collection，實現map的有：HashMap、TreeMap、HashTable、Properties、EnumMap。

　　HashMap：以哈希表數據結構實現，查找對象時通過哈希函數計算其位置，它是為快速查詢而設計的，其內部定義了一個hash表數組（Entry[] table），元素會通過哈希轉換函數將元素的哈希地址轉換成數組中存放的索引，如果有沖突，則使用散列鏈表的形式(JDK8 中哈希沖突過多，鏈表會轉紅黑樹)將所有相同哈希地址的元素串起來(沖突的節點放在鏈表的最下面)，通過查看HashMap.Entry的源碼它是一個單鏈表結構(數組(散列桶)與鏈表的組合體)；默認初始容量為16，加載因子為0.75，擴容增量：原容量的1倍；線程不安全，Collections類中存在一個靜態方法：synchronizedMap()，該方法創建了一個線程安全的Map對象；基于AbstractMap;允許存在一個為null的key和任意個為null的value(?當HashMap遇到為null的key時，它會調用putForNullKey方法來進行處理。對于value沒有進行任何處理，只要是對象都可以)。

　　TreeMap：鍵以某種排序規則排序，內部以red-black（紅-黑）樹數據結構實現，實現了SortedMap接口。

　　HashTable：也是以哈希表數據結構實現的，解決沖突時與HashMap也一樣也是采用了散列鏈表的形式；線程安全(synchronized方法);基于Dictionary類;key和value都不允許為null。

　　隊列，它主要分為兩大類，一類是阻塞式隊列，隊列滿了以后再插入元素則會拋出異常，主要包括ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。另一種隊列則是雙端隊列，支持在頭、尾兩端插入和移除元素，主要包括：ArrayDeque、LinkedBlockingDeque、LinkedList。

對List的選擇：

對于隨機查詢與迭代遍歷操作，數組比所有的容器都要快。所以在隨機訪問中一般使用ArrayList。

LinkedList使用雙向鏈表對元素的增加和刪除提供了非常好的支持，而ArrayList執行增加和刪除元素需要進行元素位移。

對于Vector而已，我們一般都是避免使用。

將ArrayList當做首選，畢竟對于集合元素而已我們都是進行遍歷，只有當程序的性能因為List的頻繁插入和刪除而降低時，再考慮LinkedList。

對Set的選擇：

HashSet由于使用HashCode實現，所以在某種程度上來說它的性能永遠比TreeSet要好，尤其是進行增加和查找操作。

雖然TreeSet沒有HashSet性能好，但是由于它可以維持元素的排序，所以它還是存在用武之地的。

對Map的選擇：

HashMap與HashSet同樣，支持快速查詢。雖然HashTable速度的速度也不慢，但是在HashMap面前還是稍微慢了些，所以HashMap在查詢方面可以取代HashTable。

由于TreeMap需要維持內部元素的順序，所以它通常要比HashMap和HashTable慢。

解決hash沖突
　　開放定址法、拉鏈法

hash表解決沖突
　　開放定址法、再哈希法、鏈地址法、建立公共溢出區

?　　ConcurrentMap(線程安全的hashMap，key、value不允許為null)，默認16個segment的數組，每個segment中實現就是hashMap了，通過hash定位segment。put操作是在segment層上加鎖的，這樣可以減少并發的沖突；讀操作大多數情況下無鎖操作（僅僅找到的hashentry對應的對象為null時，有鎖操作）。

　　CopyOnWriteArrayList,線程安全，讀操作時無鎖的ArrayList；在寫時，copy一個ArrayList，寫完成后，指針指向新的對象。

　　CopyOnWriteArraySet,基于CopyOnWriteArrayList實現。
　　ArrayBlockQueue,基于數組，FIFO,線程安全的集合類，容量可以限制。

　　jdk1.7中采用 Segment + HashEntry?的方式進行實現，?Segment大小默認為16
　　場景：?線程?A和線程B同時執行相同 Segment 對象的
　　put 方法
　　1. 線程A執行 tryLock() 方法成功獲取鎖，則把 HashEntry 對象插入到相應的位置；
　　2. 線程B獲取鎖失敗，則執行 scanAndLockForPut() 方法，在 scanAndLockForPut 方法中，會通過重復執行 `tryLock() 方法嘗試獲取鎖，在多 處理器 環境下，重復次數為64，單處理器重復次數為1，當執行 tryLock() 方法的次數超過上限時，則執行 lock() 方法掛起線程B；
　　3. 當線程A執行完插入操作時，會通過 unlock() 方法釋放鎖，接著喚醒線程B繼續執行；

　　size計算：先采用不加鎖的方式，連續計算元素的個數，最多計算3次：
　　1. 如果前后兩次計算結果相同，則說明計算出來的元素個數是準確的；
　　2. 如果前后兩次計算結果都不同，則給每個 Segment 進行加鎖，再計算一次元素的個數；

　　1.8中放棄了 Segment 臃腫的設計，取而代之的是采用Node+CAS+ Synchronized 來保證并發安全進行實現，只有在執行第一次put方法時才會調用?initTable() 初始化Node數組
　　當執行?put 方法插入數據時，根據key的hash值，在 Node 數組中找到相應的位置，實現如下：
　　1. 如果相應位置的 Node 還未初始化，則通過CAS插入相應的數據；
　　2. 如果相應位置的 Node 不為空，且當前該節點不處于移動狀態，則對該節點加 synchronized 鎖，如果該節點的 hash 不小于0，則 遍歷 鏈表更新節點或插入新節點；
　　3. 如果該節點是 TreeBin 類型的節點，說明是紅黑樹結構，則通過 putTreeVal 方法往紅黑樹中插入節點；
　　4. 如果 binCount 不為0，說明 put 操作對數據產生了影響，如果當前鏈表的個數達到8個，則通過 treeifyBin 方法轉化為紅黑樹，如果 oldVal 不為空，說明是一次更新操作，沒有對元素個數產生影響，則直接返回舊值；
　　5. 如果插入的是一個新節點，則執行 addCount() 方法嘗試更新元素個數 baseCount ；

　　size實現
　　1.8中使用一個 volatile 類型的變量 baseCount 記錄元素的個數，當插入新數據或則刪除數據時，會通過 addCount() 方法更新 baseCount ，實現如下：
　　1. 初始化時 counterCells 為空，在并發量很高時，如果存在兩個線程同時執行 CAS 修改 baseCount 值，則失敗的線程會繼續執行方法體中的邏輯，使用 CounterCell 記錄元素個數的變化；
　　2. 如果 CounterCell 數組 counterCells 為空，調用 fullAddCount() 方法進行初始化，并插入對應的記錄數，通過 CAS 設置cellsBusy字段，只有設置成功的線程才能初始化 CounterCell 數組，實現如下：
　　3. 如果通過 CAS 設置cellsBusy字段失敗的話，則繼續嘗試通過 CAS 修改 baseCount 字段，如果修改 baseCount 字段成功的話，就退出循環，否則繼續循環插入 CounterCell 對象；
　　所以在1.8中的 size 實現比1.7簡單多，因為元素個數保存 baseCount 中，部分元素的變化個數保存在 CounterCell 數組中，實現如下：
通過累加?baseCount 和 CounterCell 數組中的數量，即可得到元素的總個數；

　　要實現無鎖（lock-free）的非阻塞算法有多種實現方法，其中 CAS（比較與交換，Compare and swap） 是一種有名的無鎖算法。
　　CAS有3個操作數，內存值V，舊的預期值A，要修改的新值B。當且僅當預期值A和內存值V相同時，將內存值V修改為B，否則什么都不做。
?
?
?
?
?
?
?
?
?
?
?
?
?
?