摘要：解決沖突開放定址法拉鏈法表解決沖突開放定址法再哈希法鏈地址法建立公共溢出區(qū)并發(fā)包中的線程安全的集合容器線程安全的，不允許為，默認(rèn)個(gè)的數(shù)組，每個(gè)中實(shí)現(xiàn)就是了，通過定位?；跀?shù)組，線程安全的集合類，容量可以限制。

　　List?元素是有序的、可重復(fù)，實(shí)現(xiàn)List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

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

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

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

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

　　Set是一種不包括重復(fù)元素的Collection，實(shí)現(xiàn)了Set接口的集合有：EnumSet、HashSet、TreeSet。

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

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

　　TreeSet：??基于TreeMap，內(nèi)部以TreeMap來實(shí)現(xiàn)。它是使用元素的自然順序?qū)υ剡M(jìn)行排序，或者根據(jù)創(chuàng)建Set 時(shí)提供的Comparator?進(jìn)行排序，具體取決于使用的構(gòu)造方法。

　　Map是一個(gè)雙列集合，沒有繼承Collection，實(shí)現(xiàn)map的有：HashMap、TreeMap、HashTable、Properties、EnumMap。

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

　　TreeMap：鍵以某種排序規(guī)則排序，內(nèi)部以red-black（紅-黑）樹數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，實(shí)現(xiàn)了SortedMap接口。

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

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

對(duì)List的選擇：

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

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

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

將ArrayList當(dāng)做首選，畢竟對(duì)于集合元素而已我們都是進(jìn)行遍歷，只有當(dāng)程序的性能因?yàn)長ist的頻繁插入和刪除而降低時(shí)，再考慮LinkedList。

對(duì)Set的選擇：

HashSet由于使用HashCode實(shí)現(xiàn)，所以在某種程度上來說它的性能永遠(yuǎn)比TreeSet要好，尤其是進(jìn)行增加和查找操作。

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

對(duì)Map的選擇：

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

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

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

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

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

　　CopyOnWriteArrayList,線程安全，讀操作時(shí)無鎖的ArrayList；在寫時(shí)，copy一個(gè)ArrayList，寫完成后，指針指向新的對(duì)象。

　　CopyOnWriteArraySet,基于CopyOnWriteArrayList實(shí)現(xiàn)。
　　ArrayBlockQueue,基于數(shù)組，F(xiàn)IFO,線程安全的集合類，容量可以限制。

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

　　size計(jì)算：先采用不加鎖的方式，連續(xù)計(jì)算元素的個(gè)數(shù)，最多計(jì)算3次：
　　1. 如果前后兩次計(jì)算結(jié)果相同，則說明計(jì)算出來的元素個(gè)數(shù)是準(zhǔn)確的；
　　2. 如果前后兩次計(jì)算結(jié)果都不同，則給每個(gè) Segment 進(jìn)行加鎖，再計(jì)算一次元素的個(gè)數(shù)；

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

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

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