[[423400]]

從面試角度作為切入點(diǎn)提升大家的 Java 內(nèi)功，所謂根基不牢，地動山搖。

碼哥在 《Redis 系列》的開篇 Redis 為什么這么快中說過：學(xué)習(xí)一個技術(shù)，通常只接觸了零散的技術(shù)點(diǎn)，沒有在腦海里建立一個完整的知識框架和架構(gòu)體系，沒有系統(tǒng)觀。這樣會很吃力，而且會出現(xiàn)一看好像自己會，過后就忘記，一臉懵圈。

我們需要一個系統(tǒng)觀，清晰完整的去學(xué)習(xí)技術(shù)，在「面霸篇：Java 核心基礎(chǔ)大滿貫(卷一)」中，碼哥梳理了 Java 高頻核心知識點(diǎn)。

本篇將一舉攻破 Java 集合容器知識點(diǎn)，跟著「碼哥」一起來提綱挈領(lǐng)，梳理一個完整的 Java 容器開發(fā)技術(shù)能力圖譜，將基礎(chǔ)夯實(shí)。

集合容器概述

什么是集合?

顧名思義，集合就是用于存儲數(shù)據(jù)的容器。

集合框架是為表示和操作集合而規(guī)定的一種統(tǒng)一的標(biāo)準(zhǔn)的體系結(jié)構(gòu)。任何集合框架都包含三大塊內(nèi)容：對外的接口、接口的實(shí)現(xiàn)和對集合運(yùn)算的算法。

碼老濕，可以說下集合框架的三大塊內(nèi)容具體指的是什么嗎?

接口

面向接口編程，抽象出集合類型，使得我們可以在操作集合的時候不必關(guān)心具體實(shí)現(xiàn)，達(dá)到「多態(tài)」。

就好比密碼箱，我們只關(guān)心能打開箱子，存放東西，并且關(guān)閉箱子，至于怎么加密咱們不關(guān)心。

接口實(shí)現(xiàn)

每種集合的具體實(shí)現(xiàn)，是重用性很高的數(shù)據(jù)結(jié)構(gòu)。

算法

集合提供了數(shù)據(jù)存放以及查找、排序等功能，集合有很多種，也就是算法通常也是多態(tài)的，因?yàn)橄嗤姆椒梢栽谕粋€接口被多個類實(shí)現(xiàn)時有不同的表現(xiàn)。

事實(shí)上，算法是可復(fù)用的函數(shù)。它減少了程序設(shè)計的辛勞。

集合框架通過提供有用的數(shù)據(jù)結(jié)構(gòu)和算法使你能集中注意力于你的程序的重要部分上，而不是為了讓程序能正常運(yùn)轉(zhuǎn)而將注意力于低層設(shè)計上。

集合的特點(diǎn)

• 對象封裝數(shù)據(jù)，多個對象需要用集合存儲;
• 對象的個數(shù)可以確定使用數(shù)組更高效，不確定個數(shù)的情況下可以使用集合，因?yàn)榧鲜强勺冮L度。

集合與數(shù)組的區(qū)別

• 數(shù)組是固定長度的;集合可變長度的。
• 數(shù)組可以存儲基本數(shù)據(jù)類型，也可以存儲引用數(shù)據(jù)類型;集合只能存儲引用數(shù)據(jù)類型。
• 數(shù)組存儲的元素必須是同一個數(shù)據(jù)類型;集合存儲的對象可以是不同數(shù)據(jù)類型。

由于有多種集合容器，因?yàn)槊恳粋€容器的自身特點(diǎn)不同，其實(shí)原理在于每個容器的內(nèi)部數(shù)據(jù)結(jié)構(gòu)不同。

集合容器在不斷向上抽取過程中，出現(xiàn)了集合體系。在使用一個體系的原則：參閱頂層內(nèi)容。建立底層對象。

集合框架有哪些優(yōu)勢

• 容量自動增長擴(kuò)容;
• 提供高性能的數(shù)據(jù)結(jié)構(gòu)和算法;
• 可以方便地擴(kuò)展或改寫集合，提高代碼復(fù)用性和可操作性。
• 通過使用 JDK 自帶的集合類，可以降低代碼維護(hù)和學(xué)習(xí)新 API 成本。

有哪些常用的集合類

Java 容器分為 Collection 和 Map 兩大類，Collection 集合的子接口有 Set、List、Queue 三種子接口。

我們比較常用的是 Set、List，Map 接口不是 collection 的子接口。

Collection 集合主要有 List 和 Set 兩大接口

• List：一個有序(元素存入集合的順序和取出的順序一致)容器，元素可以重復(fù)，可以插入多個 null 元素，元素都有索引。常用的實(shí)現(xiàn)類有 ArrayList、LinkedList 和 Vector。
• Set：一個無序(存入和取出順序有可能不一致)容器，不可以存儲重復(fù)元素，只允許存入一個 null 元素，必須保證元素唯一性。
• Set 接口常用實(shí)現(xiàn)類是 HashSet、LinkedHashSet 以及 TreeSet。

Map 是一個鍵值對集合，存儲鍵、值和之間的映射。Key 無序，唯一;value 不要求有序，允許重復(fù)。

Map 沒有繼承于 Collection 接口，從 Map 集合中檢索元素時，只要給出鍵對象，就會返回對應(yīng)的值對象。

Map 的常用實(shí)現(xiàn)類：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap

集合的底層數(shù)據(jù)結(jié)構(gòu)

Collection

1.List

• ArrayList：Object 數(shù)組;
• Vector：Object 數(shù)組;
• LinkedList：雙向循環(huán)鏈表;

2.Set

HashSet：唯一，無序?；?HashMap 實(shí)現(xiàn)，底層采用 HashMap 保存數(shù)據(jù)。

它不允許集合中有重復(fù)的值，當(dāng)我們提到 HashSet 時，第一件事情就是在將對象存儲在 HashSet 之前，要先確保對象重寫 equals()和 hashCode()方法，這樣才能比較對象的值是否相等，以確保 set 中沒有儲存相等的對象。

如果我們沒有重寫這兩個方法，將會使用這個方法的默認(rèn)實(shí)現(xiàn)。

LinkedHashSet：LinkedHashSet 繼承與 HashSet，底層使用 LinkedHashMap 來保存所有元素。

TreeSet(有序，唯一)：紅黑樹(自平衡的排序二叉樹。)

Map

HashMap：JDK1.8 之前 HashMap 由數(shù)組+鏈表組成的，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的(“拉鏈法”解決沖突)。

JDK1.8 以后在解決哈希沖突時有了較大的變化，當(dāng)鏈表長度大于閾值(默認(rèn)為 8)時，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間。

LinkedHashMap：LinkedHashMap 繼承自 HashMap，所以它的底層仍然是基于拉鏈?zhǔn)缴⒘薪Y(jié)構(gòu)即由數(shù)組和鏈表或紅黑樹組成。

內(nèi)部還有一個雙向鏈表維護(hù)鍵值對的順序，每個鍵值對既位于哈希表中，也位于雙向鏈表中。

LinkedHashMap 支持兩種順序插入順序 、 訪問順序。

插入順序：先添加的在前面，后添加的在后面。修改操作不影響順序

訪問順序：所謂訪問指的是 get/put 操作，對一個鍵執(zhí)行 get/put 操作后，其對應(yīng)的鍵值對會移動到鏈表末尾，所以最末尾的是最近訪問的，最開始的是最久沒有被訪問的，這就是訪問順序。

HashTable：數(shù)組+鏈表組成的，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的

TreeMap：紅黑樹(自平衡的排序二叉樹)

集合的 fail-fast 快速失敗機(jī)制

Java 集合的一種錯誤檢測機(jī)制，當(dāng)多個線程對集合進(jìn)行結(jié)構(gòu)上的改變的操作時，有可能會產(chǎn)生 fail-fast 機(jī)制。

原因：迭代器在遍歷時直接訪問集合中的內(nèi)容，并且在遍歷過程中使用一個 modCount 變量。

集合在被遍歷期間如果內(nèi)容發(fā)生變化，就會改變 modCount 的值。

每當(dāng)?shù)魇褂?hashNext()/next()遍歷下一個元素之前，都會檢測 modCount 變量是否為 expectedmodCount 值，是的話就返回遍歷;否則拋出異常，終止遍歷。

解決辦法：

1. 在遍歷過程中，所有涉及到改變 modCount 值得地方全部加上 synchronized。
2. 使用 CopyOnWriteArrayList 來替換 ArrayList

Collection 接口

List 接口

Itertator 是什么

Iterator 接口提供遍歷任何 Collection 的接口。我們可以從一個 Collection 中使用迭代器方法來獲取迭代器實(shí)例。

迭代器取代了 Java 集合框架中的 Enumeration，迭代器允許調(diào)用者在迭代過程中移除元素。

List<String> list = new ArrayList<>(); 
Iterator<String> it = list. iterator(); 
while(it. hasNext()){ 
  String obj = it. next(); 
  System. out. println(obj); 
} 

如何邊遍歷邊移除 Collection 中的元素?

Iterator<Integer> it = list.iterator(); 
while(it.hasNext()){ 
   *// do something* 
   it.remove(); 
} 

一種最常見的錯誤代碼如下：

for(Integer i : list){ 
   list.remove(i) 
} 

運(yùn)行以上錯誤代碼會報 ConcurrentModificationException 異常。

如何實(shí)現(xiàn)數(shù)組和 List 之間的轉(zhuǎn)換?

• 數(shù)組轉(zhuǎn) List：使用 Arrays. asList(array) 進(jìn)行轉(zhuǎn)換。
• List 轉(zhuǎn)數(shù)組：使用 List 自帶的 toArray() 方法。

ArrayList 和 LinkedList 的區(qū)別是什么?

• 數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)：ArrayList 是動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，而 LinkedList 是雙向鏈表的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。
• 隨機(jī)訪問效率：ArrayList 比 LinkedList 在隨機(jī)訪問的時候效率要高，因?yàn)?LinkedList 是線性的數(shù)據(jù)存儲方式，所以需要移動指針從前往后依次查找。
• 增加和刪除效率：在非首尾的增加和刪除操作，LinkedList 要比 ArrayList 效率要高，因?yàn)?ArrayList 增刪操作要影響數(shù)組內(nèi)的其他數(shù)據(jù)的下標(biāo)。
• 內(nèi)存空間占用：LinkedList 比 ArrayList 更占內(nèi)存，因?yàn)?LinkedList 的節(jié)點(diǎn)除了存儲數(shù)據(jù)，還存儲了兩個引用，一個指向前一個元素，一個指向后一個元素。
• 線程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全;

綜合來說，在需要頻繁讀取集合中的元素時，更推薦使用 ArrayList，而在插入和刪除操作較多時，更推薦使用 LinkedList。

為什么 ArrayList 的 elementData 加上 transient 修飾?

ArrayList 中的數(shù)組定義如下：

private transient Object[] elementData; 

ArrayList 的定義：

public class ArrayList<E> extends AbstractList<E> 
     implements List<E>, RandomAccess, Cloneable, java.io.Serializable 

ArrayList 實(shí)現(xiàn)了 Serializable 接口，這意味著 ArrayList 支持序列化。

transient 的作用是說不希望 elementData 數(shù)組被序列化。

每次序列化時，先調(diào)用 defaultWriteObject()方法序列化 ArrayList中的非 transient元素，然后遍歷 elementData，只序列化已存入的元素，這樣既加快了序列化的速度，又減小了序列化之后的文件大小。

介紹下 CopyOnWriteArrayList?

CopyOnWriteArrayList 是 ArrayList 的線程安全版本，也是大名鼎鼎的 copy-on-write(COW，寫時復(fù)制)的一種實(shí)現(xiàn)。

在讀操作時不加鎖，跟 ArrayList 類似;在寫操作時，復(fù)制出一個新的數(shù)組，在新數(shù)組上進(jìn)行操作，操作完了，將底層數(shù)組指針指向新數(shù)組。

適合使用在讀多寫少的場景。例如 add(Ee)方法的操作流程如下：使用 ReentrantLock 加鎖，拿到原數(shù)組的 length，使用 Arrays.copyOf 方法從原數(shù)組復(fù)制一個新的數(shù)組(length+1)，將要添加的元素放到新數(shù)組的下標(biāo) length 位置，最后將底層數(shù)組指針指向新數(shù)組。

List、Set、Map 三者的區(qū)別?

• List(對付順序的好幫手)：存儲的對象是可重復(fù)的、有序的。
• Set(注重獨(dú)一無二的性質(zhì))：存儲的對象是不可重復(fù)的、無序的。
• Map(用 Key 來搜索的專業(yè)戶):存儲鍵值對(key-value)，不能包含重復(fù)的鍵(key)，每個鍵只能映射到一個值。

Set 接口

說一下 HashSet 的實(shí)現(xiàn)原理?

• HashSet底層原理完全就是包裝了一下HashMap
• HashSet的唯一性保證是依賴與hashCode()和equals()兩個方法，所以存入對象的時候一定要自己重寫這兩個方法來設(shè)置去重的規(guī)則。
• HashSet中的元素都存放在 HashMap的 key上面，而value中的值都是統(tǒng)一的一個 private static final Object PRESENT = new Object();

hashCode()與 equals()的相關(guān)規(guī)定：

如果兩個對象相等，則 hashcode 一定也是相同的

兩個對象相等，對兩個 equals 方法返回 true

兩個對象有相同的 hashcode 值，它們也不一定是相等的

綜上，equals 方法被覆蓋過，則 hashCode 方法也必須被覆蓋

hashCode()的默認(rèn)行為是對堆上的對象產(chǎn)生獨(dú)特值。如果沒有重寫 hashCode()，則該 class 的兩個對象無論如何都不會相等(即使這兩個對象指向相同的數(shù)據(jù))。

==與 equals 的區(qū)別

1. ==是判斷兩個變量或?qū)嵗遣皇侵赶蛲粋€內(nèi)存空間 equals 是判斷兩個變量或?qū)嵗赶虻膬?nèi)存空間的值是不是相同
2. == 是指對內(nèi)存地址進(jìn)行比較 equals() 是對字符串的內(nèi)容進(jìn)行比較
3. ==指引用是否相同， equals() 指的是值是否相同。

Queue

BlockingQueue 是什么?

Java.util.concurrent.BlockingQueue 是一個隊列，在進(jìn)行檢索或移除一個元素的時候，線程會等待隊列變?yōu)榉强?

當(dāng)在添加一個元素時，線程會等待隊列中的可用空間。

BlockingQueue 接口是 Java 集合框架的一部分，主要用于實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者模式。

Java 提供了幾種 BlockingQueue的實(shí)現(xiàn)，比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue、SynchronousQueue等。

在 Queue 中 poll()和 remove()有什么區(qū)別?

相同點(diǎn)：都是返回第一個元素，并在隊列中刪除返回的對象。

不同點(diǎn)：如果沒有元素 poll()會返回 null，而 remove()會直接拋出 NoSuchElementException 異常。

Map 接口

Map 整體結(jié)構(gòu)如下所示：

Hashtable 比較特別，作為類似 Vector、Stack 的早期集合相關(guān)類型，它是擴(kuò)展了 Dictionary 類的，類結(jié)構(gòu)上與 HashMap 之類明顯不同。

HashMap 等其他 Map 實(shí)現(xiàn)則是都擴(kuò)展了 AbstractMap，里面包含了通用方法抽象。

不同 Map 的用途，從類圖結(jié)構(gòu)就能體現(xiàn)出來，設(shè)計目的已經(jīng)體現(xiàn)在不同接口上。

HashMap 的實(shí)現(xiàn)原理?

在 JDK 1.7 中 HashMap 是以數(shù)組加鏈表的形式組成的，JDK 1.8 之后新增了紅黑樹的組成結(jié)構(gòu)，當(dāng)鏈表大于 8 并且容量大于 64 時，鏈表結(jié)構(gòu)會轉(zhuǎn)換成紅黑樹結(jié)構(gòu)。

HashMap 基于 Hash 算法實(shí)現(xiàn)的：

1.當(dāng)我們往 Hashmap 中 put 元素時，利用 key 的 hashCode 重新 hash 計算出當(dāng)前對象的元素在數(shù)組中的下標(biāo)。

2.存儲時，如果出現(xiàn) hash 值相同的 key，此時有兩種情況。

• 如果 key 相同，則覆蓋原始值;
• 如果 key 不同(出現(xiàn)沖突)，則將當(dāng)前的 key-value 放入鏈表中

3.獲取時，直接找到 hash 值對應(yīng)的下標(biāo)，在進(jìn)一步判斷 key 是否相同，從而找到對應(yīng)值。

4.理解了以上過程就不難明白 HashMap 是如何解決 hash 沖突的問題，核心就是使用了數(shù)組的存儲方式，然后將沖突的 key 的對象放入鏈表中，一旦發(fā)現(xiàn)沖突就在鏈表中做進(jìn)一步的對比。

JDK1.7 VS JDK1.8 比較

JDK1.8 主要解決或優(yōu)化了一下問題：

1. resize 擴(kuò)容優(yōu)化
2. 引入了紅黑樹，目的是避免單條鏈表過長而影響查詢效率，紅黑樹算法請參考
3. 解決了多線程死循環(huán)問題，但仍是非線程安全的，多線程時可能會造成數(shù)據(jù)丟失問題。

如何有效避免哈希碰撞

主要是因?yàn)槿绻褂?hashCode 取余，那么相當(dāng)于參與運(yùn)算的只有 hashCode 的低位，高位是沒有起到任何作用的。

所以我們的思路就是讓 hashCode 取值出的高位也參與運(yùn)算，進(jìn)一步降低 hash 碰撞的概率，使得數(shù)據(jù)分布更平均，我們把這樣的操作稱為擾動，在JDK 1.8中的 hash()函數(shù)如下：

static final int hash(Object key) { 
    int h; 
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 與自己右移16位進(jìn)行異或運(yùn)算（高低位異或） 
} 

HashMap 的 put 方法的具體流程?

當(dāng)我們 put 的時候，首先計算 key的hash值，這里調(diào)用了 hash方法，hash方法實(shí)際是讓key.hashCode()與key.hashCode()>>>16進(jìn)行異或操作，高 16bit 補(bǔ) 0，一個數(shù)和 0 異或不變，所以 hash 函數(shù)大概的作用就是：高 16bit 不變，低 16bit 和高 16bit 做了一個異或，目的是減少碰撞。 

①.判斷鍵值對數(shù)組 table[i]是否為空或?yàn)?null，否則執(zhí)行 resize()進(jìn)行擴(kuò)容;

②.根據(jù)鍵值 key 計算 hash 值得到插入的數(shù)組索引 i，如果 table[i]==null，直接新建節(jié)點(diǎn)添加，轉(zhuǎn)向 ⑥，如果 table[i]不為空，轉(zhuǎn)向 ③;

③.判斷 table[i]的首個元素是否和 key 一樣，如果相同直接覆蓋 value，否則轉(zhuǎn)向 ④，這里的相同指的是 hashCode 以及 equals;

④.判斷 table[i] 是否為 treeNode，即 table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對，否則轉(zhuǎn)向 ⑤;

⑤.遍歷 table[i]，判斷鏈表長度是否大于 8，大于 8 的話把鏈表轉(zhuǎn)換為紅黑樹，在紅黑樹中執(zhí)行插入操作，否則進(jìn)行鏈表的插入操作;遍歷過程中若發(fā)現(xiàn) key 已經(jīng)存在直接覆蓋 value 即可;

⑥.插入成功后，判斷實(shí)際存在的鍵值對數(shù)量 size 是否超多了最大容量 threshold，如果超過，進(jìn)行擴(kuò)容。

HashMap 的擴(kuò)容操作是怎么實(shí)現(xiàn)的?

①.在 jdk1.8 中，resize 方法是在 hashmap 中的鍵值對大于閥值時或者初始化時，就調(diào)用 resize 方法進(jìn)行擴(kuò)容;

②.每次擴(kuò)展的時候，都是擴(kuò)展 2 倍;

③.擴(kuò)展后 Node 對象的位置要么在原位置，要么移動到原偏移量兩倍的位置。

在 1.7 中，擴(kuò)容之后需要重新去計算其 Hash 值，根據(jù) Hash 值對其進(jìn)行分發(fā).

但在 1.8 版本中，則是根據(jù)在同一個桶的位置中進(jìn)行判斷(e.hash & oldCap)是否為 0，0 -表示還在原來位置，否則就移動到原數(shù)組位置 + oldCap。

重新進(jìn)行 hash 分配后，該元素的位置要么停留在原始位置，要么移動到原始位置+增加的數(shù)組大小這個位置上。

任何類都可以作為 Key 么?

可以使用任何類作為 Map 的 key，然而在使用之前，需要考慮以下幾點(diǎn)：

• 如果類重寫了 equals() 方法，也應(yīng)該重寫 hashCode() 方法。
• 類的所有實(shí)例需要遵循與 equals() 和 hashCode() 相關(guān)的規(guī)則。
• 如果一個類沒有使用 equals()，不應(yīng)該在 hashCode() 中使用它。
• 用戶自定義 Key 類最佳實(shí)踐是使之為不可變的，這樣 hashCode() 值可以被緩存起來，擁有更好的性能。

不可變的類也可以確保 hashCode() 和 equals() 在未來不會改變，這樣就會解決與可變相關(guān)的問題了。

為什么 HashMap 中 String、Integer 這樣的包裝類適合作為 K?

String、Integer 等包裝類的特性能夠保證 Hash 值的不可更改性和計算準(zhǔn)確性，能夠有效的減少 Hash 碰撞的幾率。

1. 都是 final 類型，即不可變性，保證 key 的不可更改性，不會存在獲取 hash 值不同的情況
2. 內(nèi)部已重寫了equals()、hashCode()等方法，遵守了 HashMap 內(nèi)部的規(guī)范(不清楚可以去上面看看 putValue 的過程)，不容易出現(xiàn) Hash 值計算錯誤的情況;

HashMap 為什么不直接使用 hashCode()處理后的哈希值直接作為 table 的下標(biāo)?

hashCode()方法返回的是 int 整數(shù)類型，其范圍為-(2 ^ 31)~(2 ^ 31 - 1)，約有 40 億個映射空間，而 HashMap 的容量范圍是在 16(初始化默認(rèn)值)~2 ^ 30，HashMap 通常情況下是取不到最大值的，并且設(shè)備上也難以提供這么多的存儲空間，從而導(dǎo)致通過hashCode()計算出的哈希值可能不在數(shù)組大小范圍內(nèi)，進(jìn)而無法匹配存儲位置;

HashMap 的長度為什么是 2 的冪次方

為了能讓 HashMap 存取高效，盡量較少碰撞，也就是要盡量把數(shù)據(jù)分配均勻，每個鏈表/紅黑樹長度大致相同。這個實(shí)現(xiàn)就是把數(shù)據(jù)存到哪個鏈表/紅黑樹中的算法。

這個算法應(yīng)該如何設(shè)計呢?

我們首先可能會想到采用 % 取余的操作來實(shí)現(xiàn)。

但是，重點(diǎn)來了：取余(%)操作中如果除數(shù)是 2 的冪次則等價于與其除數(shù)減一的與(&)操作(也就是說 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方;)。

并且采用二進(jìn)制位操作 &，相對于 % 能夠提高運(yùn)算效率，這就解釋了 HashMap 的長度為什么是 2 的冪次方。

那為什么是兩次擾動呢?

答：這樣就是加大哈希值低位的隨機(jī)性，使得分布更均勻，從而提高對應(yīng)數(shù)組存儲下標(biāo)位置的隨機(jī)性&均勻性，最終減少 Hash 沖突，兩次就夠了，已經(jīng)達(dá)到了高位低位同時參與運(yùn)算的目的;

HashMap 和 ConcurrentHashMap 的區(qū)別

1. ConcurrentHashMap 對整個桶數(shù)組進(jìn)行了分割分段(Segment)，每一個分段上都用 lock 鎖進(jìn)行保護(hù)，相對于 HashTable 的 synchronized 鎖的粒度更精細(xì)了一些，并發(fā)性能更好，而 HashMap 沒有鎖機(jī)制，不是線程安全的。(JDK1.8 之后 ConcurrentHashMap 啟用了一種全新的方式實(shí)現(xiàn),利用 synchronized + CAS 算法。)
2. HashMap 的鍵值對允許有 null，但是 ConCurrentHashMap 都不允許。

ConcurrentHashMap 實(shí)現(xiàn)原理

JDK1.7

首先將數(shù)據(jù)分為一段一段的存儲，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個線程占用鎖訪問其中一個段數(shù)據(jù)時，其他段的數(shù)據(jù)也能被其他線程訪問。

在 JDK1.7 中，ConcurrentHashMap 采用 Segment + HashEntry 的方式進(jìn)行實(shí)現(xiàn)，結(jié)構(gòu)如下：

一個 ConcurrentHashMap 里包含一個 Segment 數(shù)組。

Segment 的結(jié)構(gòu)和 HashMap 類似，是一種數(shù)組和鏈表結(jié)構(gòu)，一個 Segment 包含一個 HashEntry 數(shù)組，每個 HashEntry 是一個鏈表結(jié)構(gòu)的元素，每個 Segment 守護(hù)著一個 HashEntry 數(shù)組里的元素，當(dāng)對 HashEntry 數(shù)組的數(shù)據(jù)進(jìn)行修改時，必須首先獲得對應(yīng)的 Segment 的鎖。

1. 該類包含兩個靜態(tài)內(nèi)部類 HashEntry 和 Segment ;前者用來封裝映射表的鍵值對，后者用來充當(dāng)鎖的角色;
2. HashEntry 內(nèi)部使用 volatile 的 value 字段來保證可見性，get 操作需要保證的是可見性，所以并沒有什么同步邏輯。
3. Segment 是一種可重入的鎖 ReentrantLock，每個 Segment 守護(hù)一個 HashEntry 數(shù)組里得元素，當(dāng)對 HashEntry 數(shù)組的數(shù)據(jù)進(jìn)行修改時，必須首先獲得對應(yīng)的 Segment 鎖。

get 操作需要保證的是可見性，所以并沒有什么同步邏輯

public V get(Object key) { 
        Segment<K,V> s; // manually integrate access methods to reduce overhead 
        HashEntry<K,V>[] tab; 
        int h = hash(key.hashCode()); 
       //利用位操作替換普通數(shù)學(xué)運(yùn)算 
       long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; 
        // 以Segment為單位，進(jìn)行定位 
        // 利用Unsafe直接進(jìn)行volatile access 
        if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null && 
            (tab = s.table) != null) { 
           //省略 
          } 
        return null; 
    } 

而對于 put 操作，首先是通過二次哈希避免哈希沖突，然后以 Unsafe 調(diào)用方式，直接獲取相應(yīng)的 Segment，然后進(jìn)行線程安全的 put 操作：

public V put(K key, V value) { 
       Segment<K,V> s; 
       if (value == null) 
           throw new NullPointerException(); 
       // 二次哈希，以保證數(shù)據(jù)的分散性，避免哈希沖突 
       int hash = hash(key.hashCode()); 
       int j = (hash >>> segmentShift) & segmentMask; 
       if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck 
            (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment 
           s = ensureSegment(j); 
       return s.put(key, hash, value, false); 
   } 

其核心邏輯實(shí)現(xiàn)在下面的內(nèi)部方法中：

final V put(K key, int hash, V value, boolean onlyIfAbsent) { 
            // scanAndLockForPut會去查找是否有key相同Node 
            // 無論如何，確保獲取鎖 
            HashEntry<K,V> node = tryLock() ? null : 
                scanAndLockForPut(key, hash, value); 
            V oldValue; 
            try { 
                HashEntry<K,V>[] tab = table; 
                int index = (tab.length - 1) & hash; 
                HashEntry<K,V> first = entryAt(tab, index); 
                for (HashEntry<K,V> e = first;;) { 
                    if (e != null) { 
                        K k; 
                        // 更新已有value... 
                    } 
                    else { 
                        // 放置HashEntry到特定位置，如果超過閾值，進(jìn)行rehash 
                        // ... 
                    } 
                } 
            } finally { 
                unlock(); 
            } 
            return oldValue; 
        } 

JDK1.8

在JDK1.8 中，放棄了 Segment 臃腫的設(shè)計，取而代之的是采用 Node + CAS + Synchronized 來保證并發(fā)安全進(jìn)行實(shí)現(xiàn)。

synchronized 只鎖定當(dāng)前鏈表或紅黑二叉樹的首節(jié)點(diǎn)，這樣只要 hash 不沖突，就不會產(chǎn)生并發(fā)，效率又提升 N 倍。

• 總體結(jié)構(gòu)上，它的內(nèi)部存儲和 HashMap 結(jié)構(gòu)非常相似，同樣是大的桶(bucket)數(shù)組，然后內(nèi)部也是一個個所謂的鏈表結(jié)構(gòu)(bin)，同步的粒度要更細(xì)致一些。
• 其內(nèi)部仍然有 Segment 定義，但僅僅是為了保證序列化時的兼容性而已，不再有任何結(jié)構(gòu)上的用處。
• 因?yàn)椴辉偈褂?Segment，初始化操作大大簡化，修改為 lazy-load 形式，這樣可以有效避免初始開銷，解決了老版本很多人抱怨的這一點(diǎn)。
• 數(shù)據(jù)存儲利用 volatile 來保證可見性。
• 使用 CAS 等操作，在特定場景進(jìn)行無鎖并發(fā)操作。
• 使用 Unsafe、LongAdder 之類底層手段，進(jìn)行極端情況的優(yōu)化。

另外，需要注意的是，“線程安全”這四個字特別容易讓人誤解，因?yàn)镃oncurrentHashMap 只能保證提供的原子性讀寫操作是線程安全的。

誤區(qū)

我們來看一個使用 Map 來統(tǒng)計 Key 出現(xiàn)次數(shù)的場景吧，這個邏輯在業(yè)務(wù)代碼中非常常見。

開發(fā)人員誤以為使用了 ConcurrentHashMap 就不會有線程安全問題，于是不加思索地寫出了下面的代碼：

• 在每一個線程的代碼邏輯中先通過 containsKey 方法判斷可以 是否存在。
• key 存在則 + 1，否則初始化 1.

// 共享數(shù)據(jù) 
ConcurrentHashMap<String, Long> freqs = new ConcurrentHashMap<>(ITEM_COUNT); 
 
public void normaluse(String key) throws InterruptedException { 
 
      if (freqs.containsKey(key)) { 
        //Key存在則+1 
        freqs.put(key, freqs.get(key) + 1); 
      } else { 
        //Key不存在則初始化為1 
        freqs.put(key, 1L); 
      } 
} 

大錯特錯啊朋友們，需要注意 ConcurrentHashMap 對外提供的方法或能力的限制：

• 使用了 ConcurrentHashMap，不代表對它的多個操作之間的狀態(tài)是一致的，是沒有其他線程在操作它的，如果需要確保需要手動加鎖。
• 諸如 size、isEmpty 和 containsValue 等聚合方法，在并發(fā)情況下可能會反映 ConcurrentHashMap 的中間狀態(tài)。
• 因此在并發(fā)情況下，這些方法的返回值只能用作參考，而不能用于流程控制。
• 顯然，利用 size 方法計算差異值，是一個流程控制。
• 諸如 putAll 這樣的聚合方法也不能確保原子性，在 putAll 的過程中去獲取數(shù)據(jù)可能會獲取到部分?jǐn)?shù)據(jù)。

正確寫法：

//利用computeIfAbsent()方法來實(shí)例化LongAdder，然后利用LongAdder來進(jìn)行線程安全計數(shù) 
freqs.computeIfAbsent(key, k -> new LongAdder()).increment(); 

使用 ConcurrentHashMap 的原子性方法 computeIfAbsent 來做復(fù)合邏輯操作，判斷 Key 是否存在 Value，如果不存在則把 Lambda 表達(dá)式運(yùn)行后的結(jié)果放入 Map 作為 Value，也就是新創(chuàng)建一個 LongAdder 對象，最后返回 Value。

由于 computeIfAbsent 方法返回的 Value 是 LongAdder，是一個線程安全的累加器，因此可以直接調(diào)用其 increment 方法進(jìn)行累加。

本文轉(zhuǎn)載自微信公眾號「碼哥字節(jié)」

【編輯推薦】