從最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu) 數(shù)組|鏈表|樹 開始蔚舀，基于這些基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)通過各種設(shè)計(jì)組合成具備特定功能的數(shù)據(jù)結(jié)構(gòu)诀紊，這些結(jié)構(gòu)是編碼的基礎(chǔ)和核心孕荠。比如C++的vector痹升，jdk自帶了大量這些數(shù)據(jù)結(jié)構(gòu)叨橱，統(tǒng)稱為集合典蜕。

1、基本知識(shí)

I罗洗、接口

集合主要是倆類三種結(jié)構(gòu)愉舔，一類是線性表，只存儲(chǔ)數(shù)據(jù)本身栖博，有List和Set兩種屑宠，區(qū)別是Set不可重復(fù)；另一類是Key-Value鍵值對(duì)仇让，有索引功能.

II典奉、迭代接口 - Iterator

老的框架還有Enumeration 接口，Iterator接口也是23種設(shè)計(jì)模式中的經(jīng)典模式丧叽；在List和Set的接口中都有iterator接口卫玖，而map本質(zhì)上是一個(gè)Set和Map接口的聯(lián)合實(shí)現(xiàn)，也有iterator訪問方法踊淳。

為何使用Iterator假瞬？

封裝了對(duì)象的內(nèi)部實(shí)現(xiàn)，通過iterator接口提供其內(nèi)部數(shù)據(jù)的訪問迂尝，而無需知道內(nèi)部的數(shù)據(jù)結(jié)構(gòu)脱茉。還有一個(gè)非常重要的用途，集合提供了一個(gè)快速失敗的功能 fast failture垄开，當(dāng)多個(gè)同時(shí)操作集合時(shí)琴许，能夠迅速感知到 modCount(修改次數(shù))的變化

III、常用集合 - 基本實(shí)現(xiàn)

HashSet/TreeSet

ArrayList/LinkedList

HashMap/HashTable/TreeMap

IV溉躲、歷史集合

Vector/HashTable/Stack/Dictionary/Properties ... 很多集合開始使用榜田，后來被拋棄，最后又重寫了

V锻梳、特殊集合 - Collections封裝接口

a箭券、只讀集合 unmodifiableList | unmodifiableMap | unmodifiableSet

b、線程安全 synchronizedList | synchronizedMap | synchronizedSet

c疑枯、副本集合 單例 singleton | 多個(gè)重復(fù)填充值 | nCopies

VI辩块、算法集合 - Collections封裝接口

a、排序 sort

b、檢索 binarySearch

c庆捺、求值 max/min

d古今、操作 fill-填充/shuffle-打亂/reverse-反轉(zhuǎn)

...

下面開始一些具體數(shù)據(jù)結(jié)構(gòu)的精講，源碼閱讀滔以。jdk的集合中，所有采用數(shù)組這種原始結(jié)構(gòu)的氓拼，都大量采用了底層實(shí)現(xiàn)你画，以實(shí)現(xiàn)數(shù)組元素間的快速拷貝和數(shù)據(jù)轉(zhuǎn)移，比如桃漾， System.arraycopy 是 native 函數(shù)坏匪，jdk 類庫底層 C++ 實(shí)現(xiàn)直接實(shí)現(xiàn) 內(nèi)存的拷貝，比如Arrays.copyOf 只是在 System.arraycopy 做了封裝撬统，以支持泛型等等适滓。這是理解很多集合實(shí)現(xiàn)的一個(gè)重要點(diǎn)，不然大規(guī)模頻繁的轉(zhuǎn)移數(shù)據(jù)恋追，實(shí)現(xiàn)上肯定是低效的凭迹。jdk通過折中達(dá)到 ?內(nèi)存占用，使用效率苦囱，靈活性的一個(gè)平衡嗅绸。

2、List精講

I撕彤、ArrayList - 數(shù)組實(shí)現(xiàn)

既然是數(shù)組實(shí)現(xiàn)鱼鸠，最重要的就是容量的設(shè)定和回收，設(shè)計(jì)的太小羹铅，放不下;設(shè)計(jì)的太大蚀狰，內(nèi)存浪費(fèi)

a、容量管理

i职员、初始容量：默認(rèn) 容量是 10麻蹋，可以初始化指定

ii、擴(kuò)容：ensureCapacity 擴(kuò)容并沒有完全按照用戶設(shè)置的值 minCapacity 擴(kuò)容廉邑，而是用 用戶擴(kuò)充的容量 和 原始數(shù)據(jù)容量的 1.5 倍比哥蔚，取其大值

目的是，不用頻繁去擴(kuò)容

iii蛛蒙、回收容量 trimToSize 壓縮空余的數(shù)組內(nèi)存空間

-- 正如上所說糙箍，擴(kuò)容和回收都需要移動(dòng)數(shù)據(jù)位置，采用了系統(tǒng)函數(shù)提高效率

b牵祟、尋址/索引

指定位置 index - 因?yàn)閿?shù)組下表本身就帶有地址索引信息深夯，所以指定位置直接指向即可

尋找對(duì)象的位置 indexOf/lastIndexOf，因?yàn)槭菬o序數(shù)組，所以咕晋，只能循環(huán)查找;需要注意的是雹拄，尋找的原則是equals函數(shù)，所以如果不是以對(duì)象引用查找掌呜，而是以對(duì)象的內(nèi)容作為查找的話滓玖，一定需要覆蓋equals方法

c、存取操作

順序增加 add(Element)| 指定位置增加 add(index,Element) | 批量增加 addAll(Collection)

指定位置修改 set(index,Element)

指定位置刪除 remove(index) | 刪除對(duì)象 remove(Element) |?另外质蕉，提供了快速刪除势篡，即不需要取刪除的數(shù)據(jù)，直接移位

指定位置獲取 get(index)

-- 指定位置的操作都依賴于尋址;除了修改和順序增加外模暗，所有操作都涉及數(shù)組對(duì)象的移位操作禁悠；增加操作前，都調(diào)用擴(kuò)容方法檢查是否真的需要擴(kuò)容

d兑宇、其他操作

轉(zhuǎn)換數(shù)組 toArray

序列化 readObject | writeObject

支持 null 對(duì)象

II碍侦、LinkedList - 雙向環(huán)形鏈表實(shí)現(xiàn)

鏈表實(shí)現(xiàn)，就沒有容量的概念隶糕，為了維持鏈表結(jié)構(gòu)瓷产，就需要保留一個(gè)前向、后向的引用

a若厚、尋址/索引

指定位置 entry(index) - 因?yàn)殒湵頉]有位置索引拦英，為了優(yōu)化尋找，根據(jù)index大小判斷從頭部正向?qū)ふ也饨眨€是從尾部逆向?qū)ふ?/p>

尋找對(duì)象的位置, 這點(diǎn)和ArrayList一樣

b疤估、存取操作

順序增加 addBefore(Element) addLast offer | 指定位置增加 add(index,Element) | 批量增加 addAll(Collection)

指定位置修改 set(index,Element)

指定位置刪除 remove(index) removeFirst removeLast | 刪除對(duì)象 remove(Element)

指定位置獲取 get(index) getFirst getLast peek

c、其他操作

同ArrayList

III霎冯、ArrayList VS LinkedList

a铃拇、首先從內(nèi)存空間使用上看 ArrayList 有兩難境界，規(guī)劃空間小頻繁擴(kuò)容沈撞，規(guī)劃空間多慷荔，浪費(fèi)比較多。特別是多次操作后缠俺，需要及時(shí)回收显晶，否則內(nèi)存就會(huì)浪費(fèi)泄漏；LinkedList存儲(chǔ)只有本身節(jié)點(diǎn)（需要另外存儲(chǔ) 引用壹士，每個(gè)元素需要多8個(gè)字節(jié)）

b磷雇、從尋址上看，指定位置操作 ArrayList只需要 O(1) 常量時(shí)間, 而LinkedList需要 O(N)

c躏救、從存取操作看唯笙，ArrayList需要頻繁內(nèi)存拷貝螟蒸，而LinkedList只需要改變一下指針

綜合來看, 數(shù)據(jù)創(chuàng)建后比較少變動(dòng)的，需要隨機(jī)訪問的崩掘，適合使用ArrayList, 頻繁操作的 則適合使用 LinkedList七嫌； 舉兩個(gè)應(yīng)用場(chǎng)景，常用的消費(fèi)者生產(chǎn)者模式苞慢，使用隊(duì)列就應(yīng)該使用LinkedList诵原，因?yàn)閿?shù)據(jù)一直在變；從數(shù)據(jù)庫讀取一批數(shù)據(jù)在內(nèi)存中給后續(xù)程序使用枉疼，使用ArrayList更合理一點(diǎn)

3皮假、Map精講

I、HashMap -- 哈希表實(shí)現(xiàn) (數(shù)組+鏈表)

HashMap的實(shí)現(xiàn)應(yīng)該是集合里面最重要的數(shù)據(jù)結(jié)構(gòu)了骂维，對(duì)于哈希算法，使用了數(shù)組做桶贺纲，鏈表作為沖突的解決方法航闺。

哈希表的優(yōu)勢(shì)之一就是尋址/存儲(chǔ)都是線性時(shí)間，所以引用也是最為廣泛

a猴誊、容量

初始容量： 默認(rèn)是 capacity 16 | 最大容量 2^31 | 負(fù)載因子 loadfactor 0.75

容量*負(fù)載因子潦刃，共同決定數(shù)組的門限 threshold

需要注意的是，初始化容量后懈叹，數(shù)組容量并不是 指定的容量乖杠，而是 2 ^ N 這個(gè)數(shù)剛好大于指定容量 X 即 容量 2 ^N-1 <= X <= 2^N

擴(kuò)容：resize

擴(kuò)容是創(chuàng)建一個(gè)新的 大小 *2 的數(shù)組，然后把原先 數(shù)組的數(shù)據(jù) 通過 transfer 方法全部移到新表里面

這里有一個(gè)注意點(diǎn)澄成，就是 原先在一個(gè)鏈表的數(shù)據(jù) 哈希取模后相同的數(shù)據(jù)胧洒，在新的表容量取模可能不在同一個(gè)表中（比如 1 和 257 按 256 取模都是在 1 這個(gè)槽位墨状，而 按新的 512 取模就不在同一個(gè)槽了）

所以卫漫，這里transfer 方法，對(duì)數(shù)據(jù)的元素都進(jìn)行了迭代肾砂；因此列赎，擴(kuò)容基本對(duì)所有元素都訪問一次，對(duì)效率影響較大镐确。需要減少頻繁擴(kuò)容

-- 這也是哈希算法的劣勢(shì)之一包吝，要預(yù)先考慮好桶容量

b、尋址/索引 indexFor

針對(duì)hashcode 再計(jì)算一次 hash源葫，用hash值 & leng -1 進(jìn)行索引定位诗越，因?yàn)楸砀翊笮apacity 都是 2 的倍數(shù)，使用 & length - 1效率更高臼氨；尋址表格后掺喻，再利用 equals 進(jìn)行循環(huán)查找 相同的key

c、存取操作

獲取：get 根據(jù)key值找到value, 根據(jù)indexFor尋址 通過 hashcode 找到數(shù)組感耙，通過equals 迭代鏈表找到數(shù)據(jù)

存儲(chǔ)：put 也是根據(jù)key值尋址褂乍，因?yàn)镠ashMap不區(qū)分增加/修改，所以都是迭代鏈表直到找到為止即硼，如果沒有找到逃片，則把新節(jié)點(diǎn)鏈表放在table[index]位置，如果找到則覆蓋

批量存儲(chǔ)：putAll 首先需要計(jì)算容量只酥，然后再迭代插入

刪除：同獲取過程類似

Null的特殊處理褥实，因?yàn)镹ull沒有hashcode，所以默認(rèn)放在第 0 個(gè)桶裂允，value也支持null -- putForNullKey/getForNullKey

d损离、其他重要知識(shí)點(diǎn)

keySet -- 返回的key值的set集合,通過HashMap提供Entry的iterator迭代器訪問

values -- 返回的value值的collection集合,通過HashMap提供Entry的iterator迭代器訪問

entrySet -- 返回的key-value集合

返回的這三個(gè)對(duì)象都是空對(duì)象，通過iterator 迭代器完成訪問

modCount -- Fast Failture 迅速失敗,并發(fā)場(chǎng)景下保證數(shù)據(jù)一致性

序列化

補(bǔ)充點(diǎn)：傳統(tǒng)的哈希表 實(shí)現(xiàn)绝编，有個(gè)比較麻煩的問題僻澎，就是哈希碰撞，極端情況下操作就變成了單純鏈表操作,O(N),所以一直到Java8,對(duì)哈希表進(jìn)行了改造十饥。

優(yōu)化1：正常情況下就是普通哈希表實(shí)現(xiàn)窟勃，put時(shí)檢查，當(dāng)鏈表長度達(dá)到8時(shí)逗堵，立即把該鏈表轉(zhuǎn)成紅黑樹秉氧，這樣效率就會(huì)是紅黑樹O(LogN)，resize時(shí)蜒秤，當(dāng)長度小于6時(shí)汁咏，還蛻化為鏈表。增加了put和get垦藏、resize等操作的復(fù)雜度梆暖。

優(yōu)化2：索引和轉(zhuǎn)移鏈表時(shí)進(jìn)行了優(yōu)化，新增元素也是追加到鏈表尾掂骏，而不是放在表頭轰驳，不像原先HashMap轉(zhuǎn)移鏈表會(huì)反置鏈表

更詳細(xì)的描述參見?http://www.importnew.com/20386.html

II、TreeMap - 紅黑樹

既然使用了紅黑樹弟灼，那保證了數(shù)據(jù)的有序,優(yōu)點(diǎn)和哈希表類似, 插入和查找都非臣督猓快,O(logN),相比哈希表 紅黑樹占用空間只是本節(jié)點(diǎn)，而哈希表需要預(yù)留很多空間田绑。從這點(diǎn)來看勤哗，有點(diǎn)類似 ArrayList和LinkedList的區(qū)別

但HashMap的哈希表情況更糟糕一些，因?yàn)樾枰h(huán)迭代掩驱，而不能像ArrayList底層內(nèi)存拷貝芒划。不過紅黑樹的效率要低于哈希表冬竟，特別是熱點(diǎn)數(shù)據(jù)，需要頻繁對(duì)樹進(jìn)行旋轉(zhuǎn)民逼。

a泵殴、尋址/索引

getEntry 對(duì)對(duì)象進(jìn)行比較，然后迭代樹的子樹拼苍。所以對(duì)于TreeMap使用的數(shù)據(jù)類型笑诅，就需要實(shí)現(xiàn) Comparable 接口

b、存取操作

獲却辍：get 根據(jù)key值尋址到樹的節(jié)點(diǎn)吆你，通過 compareTo 比較獲取對(duì)應(yīng)節(jié)點(diǎn)的value

存儲(chǔ)：put 根據(jù)key值尋址，找到節(jié)點(diǎn)俊犯，如果相等則 更新妇多，否則插入節(jié)點(diǎn)，并進(jìn)行紅黑樹的旋轉(zhuǎn)燕侠；

批量存儲(chǔ)：循環(huán)調(diào)用put進(jìn)行存儲(chǔ)

刪除：remove根據(jù)key值尋址后砌梆，用了一點(diǎn)技巧，并沒有真正刪除贬循，而是用當(dāng)前節(jié)點(diǎn)的一個(gè)葉子節(jié)點(diǎn)（左分支的最右邊，右分支的最左邊）來替換當(dāng)前節(jié)點(diǎn)桃序，然后平衡杖虾，刪除葉子節(jié)點(diǎn)。

TreeMap類型的還支持媒熊，除了精確查找外的奇适，一些模糊查找返回 子樹集合。

紅黑樹不支持Null芦鳍。

c嚷往、其他重要知識(shí)點(diǎn)

同HashMap基本一樣，通過iterator提供三個(gè)對(duì)象的訪問柠衅，支持modCount

III皮仁、Hashtable - 同HashMap的底層結(jié)構(gòu)

Hashtable 重寫后繼承了Map接口，實(shí)現(xiàn)原理同HashMap菲宴，只是Hashtable繼承的是老的對(duì)象 Dictionary,

但細(xì)節(jié)上有很多差異贷祈，在容量設(shè)定、擴(kuò)容喝峦，尋址代碼(采用了&fff這種方式)實(shí)現(xiàn)層面都有差異势誊，大的差異參見下面

HashMap VS TreeMap

從內(nèi)存空間來看，HashMap通骋ゴ溃空間要大于TreeMap,兩者都有引用,但HashMap數(shù)組要預(yù)留很多桶

從操作效率來看粟耻，HashMap要由于TreeMap O(1) 要比 O(logN)快的多查近，而且紅黑樹熱點(diǎn)旋轉(zhuǎn)的話，就非臣访Γ苦逼了

另外霜威，TreeMap是有序的結(jié)構(gòu)，如果需要存儲(chǔ)數(shù)據(jù)出來是有序的話饭玲，則肯定使用TreeMap

HashMap VS Hashtable

最大的差異在 Hashtable 每個(gè)存取方法都加了 synchronized 同步方法侥祭，所以是線程安全的，也慢了很多

其次在對(duì)于null的操作上茄厘，Hashtable沒有對(duì)null的特殊處理矮冬，即key和value都不能放入Hashtable

再次迭代器的使用 HashMap使用了fail-fast，其他線程修改結(jié)構(gòu)(set 值不改變結(jié)構(gòu)并不會(huì)導(dǎo)致失敗)后迅速失敗次哈，Hashtable 還有老的 enumerator迭代器

還有一個(gè)小差異胎署，Hashtable的contains方法，HashMap改成了 ContainsKey和ContainsValue窑滞，更清晰

ConcurrentHashMap已經(jīng)取代了Hashtable

4琼牧、Set精講

HashSet 和 TreeSet 分別復(fù)用了 HashMap和TreeMap的實(shí)現(xiàn), 作為其Key的使用，沒有單獨(dú)定義數(shù)據(jù)結(jié)構(gòu)

5哀卫、并發(fā)編程集合

最簡(jiǎn)單的并發(fā)處理巨坊，就是對(duì)象存取操作串行化，Collections 提供的線程安全集合此改，就是這個(gè)思路趾撵。但這樣效率極低。那如何實(shí)現(xiàn)高效的并發(fā)編程集合呢

可以借鑒數(shù)據(jù)庫對(duì)待 鎖的思路

思路1：分割數(shù)據(jù)共啃，減小 鎖的范圍和 鎖的粒度 - 比如行鎖占调，頁鎖，表鎖

思路2：讀寫分離移剪，區(qū)別對(duì)待讀和寫 - 讀共享鎖究珊，寫排他鎖

本章節(jié)出現(xiàn)的很多 并發(fā)編程概念，請(qǐng)參照本博 《java 并發(fā)編程精華一頁紙》

I纵苛、CopyOnWriteXXX

首先從最簡(jiǎn)單的集合類型剿涮，寫時(shí)復(fù)制。這就是讀寫分離的思路赶站。Copy On write的策略使用范圍非常廣幔虏，比如 Redis內(nèi)存數(shù)據(jù)庫在持久化時(shí)使用該策略保證父子進(jìn)程讀寫不受干擾。

以 CopyOnWriteArrayList 為例

讀時(shí)贝椿，不加鎖想括，一旦出現(xiàn)修改時(shí)，加鎖烙博，然后生成新的數(shù)組對(duì)象瑟蜈。

和數(shù)據(jù)庫的隔離級(jí)別一樣烟逊。 這里有一個(gè)問題，就是在操作瞬間讀數(shù)據(jù)時(shí)铺根，并不能保證一致性宪躯，這里約等于 數(shù)據(jù)庫的 READ_COMMITED 會(huì)有不可重復(fù)讀和幻讀出現(xiàn)。

使用CopyOnWrite只適用于大量多少量寫的場(chǎng)景位迂，比如 經(jīng)常使用的 緩存的元數(shù)據(jù)访雪，用戶信息、設(shè)備信息 變更極少掂林。

II臣缀、Queue 消費(fèi)者隊(duì)列

阻塞 or 非阻塞

阻塞隊(duì)列： 單向 BlockingQueue | 雙向 BlockingDeQue 也有數(shù)組和鏈表的兩種實(shí)現(xiàn)

原理都是入棧和出棧都加鎖。不同的 ArrayBlockingQueue是 一把鎖泻帮，而LinkedBlockingQueue 是兩把鎖精置， 寫鎖當(dāng)容量滿時(shí) 等待notFull的喚醒、發(fā)出NotEmpty的喚醒信號(hào)锣杂； 讀鎖當(dāng)容量空時(shí) 等待NotEmpty的喚醒、發(fā)出NotFull的喚醒信號(hào)

優(yōu)先級(jí)隊(duì)列 PriorBlockingOueue 具有優(yōu)先級(jí)的隊(duì)列元莫，內(nèi)部是 紅黑樹的實(shí)現(xiàn)，可以保證offer出來的值有一定順序

非阻塞隊(duì)列： ConcurrentLinkedQueue

基本上非阻塞的原理都是采用 CAS 技術(shù) 即 不斷循環(huán)嘗試踱蠢，利用底層的 CAS 進(jìn)行修改。ConcurrentLinkedQueue 入隊(duì)和出對(duì)都是不斷的嘗試朽基，直到出隊(duì)和入隊(duì)成功

III离陶、ConcurrentHashMap

java6和7 的實(shí)現(xiàn)稼虎，其實(shí)就是 分割數(shù)據(jù)的思路，把Hashtable的全局鎖招刨，改成分段鎖霎俩，數(shù)據(jù)也分段處理

多線程編寫原則變量隔離,不跨線程訪問 > 變量改成不可變 > 同步，從這個(gè)原則來看ConcurrentHashMap的設(shè)計(jì)沉眶，就能更清楚了

a打却、容量

ConcurrentHashMap的容量比單純的HashMap要復(fù)雜一點(diǎn)，增加了一個(gè) concurrencyLevel 并發(fā)度的參數(shù)谎倔。容量不是單純的一個(gè)數(shù)組

而是 兩層數(shù)組柳击，第一層是 segment數(shù)組,由并發(fā)度決定，第二層根據(jù)容量 / segement片习，以決定每個(gè)segment大概有幾個(gè)元素

初始容量：和HashMap一致捌肴，并發(fā)度也是 16

擴(kuò)容：rehash 和 HashMap的擴(kuò)容差不多也是需要移動(dòng)鏈表數(shù)據(jù)蹬叭，做了一點(diǎn)優(yōu)化

i、首先注意擴(kuò)容状知，并沒有改變并發(fā)度秽五，也就是說segment數(shù)組沒有變，這點(diǎn)很重要饥悴；因?yàn)楸砻靼凑崭呶宦湓谀膫€(gè)segment沒有變化坦喘。不牽涉跨段操作。

ii西设、因?yàn)閿U(kuò)容是翻倍的瓣铣，所以 最終在segment內(nèi)的位置只有兩種情況：保持不變 i ；或者舊容量 capcity + 位置 i

比如 1 or 17 % 16 都是 1 济榨，擴(kuò)容后 1 or 17 % 32坯沪， 一個(gè)是1 保存不變，一個(gè)是 16 + 1

jdk做的優(yōu)化是擒滑，掃描一遍鏈表腐晾，如果發(fā)現(xiàn)鏈表某個(gè)位置到尾部，都是沒有位置變化的元素丐一，那這部分元素保持不變藻糖，只把鏈表前面部分重新根據(jù)hash分組處理

并發(fā)度的設(shè)置需要通盤考慮，如果并發(fā)度過大库车，極端情況和數(shù)組容量一樣大，則每次需要跨段處理洋满；并發(fā)度過小牺勾，極端情況就是1阵漏，則和Hashtable一樣

b履怯、尋址/索引

i叹洲、首先計(jì)算一次hash

ii、調(diào)用 segmentFor仅叫，使用hash后的值 高位 & segment.length诫咱，計(jì)算出數(shù)據(jù)在哪個(gè)號(hào)段

iii、得到具體的Segment竟痰，HashEntry.length & hash 坏快，找到在段數(shù)組的具體位置

c莽鸿、存取操作

講解存儲(chǔ)操作之前拾给，先看節(jié)點(diǎn) HsahEntry的設(shè)計(jì)蒋得， hash和key都是final常量不允許修改额衙；value 是volatile窍侧，鏈表指針在6中是final伟件，7中是volatile锋爪。所有的數(shù)據(jù)都為并發(fā)做了修訂其骄。

首先常量部分不會(huì)發(fā)生變動(dòng)拯爽，volatile在修改時(shí)能夠?qū)崟r(shí)被感知钧忽。

java 6的存取操作最后都是代理給 Segment 進(jìn)行操作，到了7-8就徹底改成了Unsafe對(duì)象的操作

獲取: get 尋址數(shù)據(jù)過程如上篮幢，找到槽位后三椿，鏈表迭代搜锰；get沒有加鎖耿战，原因如下(只適合6)

如果有線程在修改value狈涮，因?yàn)関olatile所以無需加鎖

如果有線程在增加鹏倘，讀到null時(shí)纤泵，再加鎖讀一次

如果有線程在刪除，采用了類似CopyOnWrite的技術(shù)玻褪，保證能讀到

存儲(chǔ)：put/putIfAbsent/putAll 也是先尋找數(shù)據(jù)带射，需要加鎖

刪除：remove 因?yàn)閚ext 不可變窟社，所以要把刪除節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)全部復(fù)制一遍(CopyOnWrite)灿里；原先的鏈表如果此時(shí)正在訪問到這個(gè)部分可以繼續(xù)訪問

全局操作：size|containsValue 操作和普通的操作不同匣吊，要遍歷所有的號(hào)段segment色鸳，多線程操作時(shí)蒜哀，作者用了一個(gè)小技巧咏雌，并沒有一開始就鎖表赊抖，而是迭代3次處理氛雪，無法獲取(獲取結(jié)果不一致)报亩，才加鎖操作

不支持Null 存儲(chǔ) (key/value)這么設(shè)計(jì)的原因是在ConcurrentHashMap中岳链，一旦value出現(xiàn)null掸哑，則代表HashEntry的key/value沒有映射完成就被其他線程所見苗分，需要特殊處理摔癣。

java8 實(shí)現(xiàn)

同HashMap一樣择浊，ConcurrentHashMap 在java8做了大幅改進(jìn), 傳統(tǒng)的數(shù)組+鏈表的哈希表方法琢岩，改成同時(shí)支持紅黑樹擴(kuò)展。所以表結(jié)構(gòu)方面采用了HashMap的大體思路

采用了在并發(fā)編程中的底層實(shí)現(xiàn) CAS危彩，不斷比較并替換(看起來是不是和NIO娩缰、AIO的思想很接近）

a拼坎、容量

初始容量：和HashMap一致 16

擴(kuò)容： addCount 判斷容量是否需要擴(kuò)容泰鸡；helpTransfer 和 transfer 進(jìn)行擴(kuò)容盛龄；擴(kuò)容后新的表需要把原先數(shù)據(jù)進(jìn)行遷移余舶，這和HashMap都一樣。

首先某一個(gè)線程在 執(zhí)行 addCount時(shí)赂摆，發(fā)現(xiàn)需要擴(kuò)容曲楚，此時(shí) 初始化 nextTable 2 倍容量

然后該線程開始 進(jìn)行 數(shù)據(jù)節(jié)點(diǎn)遷移(遷移過程和6龙誊、7 版本里差不多趟大，也使用了i， i+capcity 的思路)叽讳，遷移時(shí)岛蚤，循環(huán)迭代table，發(fā)現(xiàn)表頭為空時(shí)涤妒，插入forward節(jié)點(diǎn)

此時(shí)如果有線程進(jìn)行put等操作時(shí),發(fā)現(xiàn)正在擴(kuò)容時(shí)(只有 table 表頭是forward節(jié)點(diǎn)才能發(fā)現(xiàn)),執(zhí)行helpTransfer參與擴(kuò)容

每個(gè)線程處理完當(dāng)前節(jié)點(diǎn)后硅堆，把當(dāng)前節(jié)點(diǎn)標(biāo)記為 forward 節(jié)點(diǎn)，其他線程發(fā)現(xiàn)為 forward 節(jié)點(diǎn)后贿讹，就不再處理該節(jié)點(diǎn)渐逃；在處理過程中對(duì)該節(jié)點(diǎn)加鎖，保證一致性

b围详、尋址/索引

tabAt 根據(jù)哈希和數(shù)組朴乖，尋找到當(dāng)前tab中的位置

c、存取操作

獲戎蕖：get 獲取數(shù)據(jù)沒有加鎖买羞，索引找到 tab 位置后

判斷 頭節(jié)點(diǎn) hash值，如果<0 說明此時(shí)正在進(jìn)行擴(kuò)容雹食，則委托 forward 節(jié)點(diǎn)的 find方法尋找

如果 沒有擴(kuò)容畜普，則迭代節(jié)點(diǎn)尋址街立，因?yàn)?Node節(jié)點(diǎn)的 volatile 保證了修改的可見性，新增節(jié)點(diǎn)時(shí)會(huì)鎖住頭節(jié)點(diǎn)，所以保證了一致性

存儲(chǔ)：put 方法，索引到 tab位置后

發(fā)現(xiàn)table 頭節(jié)點(diǎn)正在擴(kuò)容朵栖，參與擴(kuò)容。 -- 因?yàn)橛衒or循環(huán)(死循環(huán)),只有插入成功才會(huì)退出，所以擴(kuò)容完成后，繼續(xù)插入

發(fā)現(xiàn)空節(jié)點(diǎn)通過CAS技術(shù)的 casTabAt 插入 -- 因?yàn)榇藭r(shí)粒度是表級(jí)临梗，通過cas可以減少鎖的影響

不為空什猖，則鎖住節(jié)點(diǎn)摇零，進(jìn)行插入 -- 找到節(jié)點(diǎn)后雾家，此時(shí)粒度是 槽位節(jié)點(diǎn)對(duì)應(yīng)的鏈表級(jí)別，可以加鎖

刪除：remove方法芬位，索引到 tab位置后

發(fā)現(xiàn)正在擴(kuò)容被饿，參與擴(kuò)容

然后鎖住節(jié)點(diǎn)迭代檢查并刪除

大小：size 因?yàn)樗胁僮鞫紩?huì)更新 baseCount ；雖然baseCount 是volatile损俭，但同時(shí)多個(gè)線程同時(shí)操作有先后攒砖，讀取的值只是瞬間的操作值受神，并不能保證完全準(zhǔn)確

不支持Null

ConcurrentHashmap 總結(jié)：

a撑教、forward 節(jié)點(diǎn)作為 擴(kuò)容時(shí)的代理節(jié)點(diǎn)，作用有兩個(gè)傍念，一是作為擴(kuò)容時(shí)，多個(gè)線程交互的標(biāo)記延蟹；另一個(gè)作為擴(kuò)容過程中高帖，代理查詢節(jié)點(diǎn)的查詢請(qǐng)求

b拉背、根據(jù)容量動(dòng)態(tài)調(diào)整 鏈表和紅黑樹

c齐蔽、鎖的粒度是表格桶的每一個(gè)槽位，取的操作不加鎖勺美，操作數(shù)據(jù)時(shí)對(duì)槽位加鎖占卧；同時(shí)利用 cas 技術(shù)友多，不用對(duì)表整體加鎖，提高了效率

IV、其他

除了 哈希表(數(shù)組+鏈表) 紅黑樹恒傻，并發(fā)編程集合里面也有跳躍表的實(shí)現(xiàn)脸侥， 因?yàn)樘S表占用內(nèi)存較多，只有在 紅黑樹熱點(diǎn)比較明顯的情況下盈厘，作為替代睁枕，平時(shí)用的比較少。

對(duì)于CAS技術(shù)沸手，可以參照 《java 并發(fā)編程精華一頁紙》