面霸篇：Java 集合容器大滿貫（卷二）

面霸篇，從面試角度作為切入點提升大家的 Java 内功，所謂根基不牢，地動山搖。

碼哥在 《Redis 系列》的開篇 Redis 為什麼這麼快中說過：學習一個技術，通常隻接觸了零散的技術點，沒有在腦海裡建立一個完整的知識架構和架構體系，沒有系統觀。這樣會很吃力，而且會出現一看好像自己會，過後就忘記，一臉懵逼。

我們需要一個系統觀，清晰完整的去學習技術，在「面霸篇：Java 核心基礎大滿貫（卷一）」中，碼哥梳理了 Java 高頻核心知識點。

本篇将一舉攻破 Java 集合容器知識點，跟着「碼哥」一起來提綱挈領，梳理一個完整的 Java 容器開發技術能力圖譜，将基礎夯實。

點選下方卡片，關注「碼哥位元組」

集合容器概述

什麼是集合？

顧名思義，集合就是用于存儲資料的容器。

集合架構是為表示和操作集合而規定的一種統一的标準的體系結構。 任何集合架構都包含三大塊内容：對外的接口、接口的實作和對集合運算的算法。

碼老濕，可以說下集合架構的三大塊内容具體指的是什麼嗎？

接口

面向接口程式設計，抽象出集合類型，使得我們可以在操作集合的時候不必關心具體實作，達到「多态」。

就好比密碼箱，我們隻關心能打開箱子，存放東西，并且關閉箱子，至于怎麼加密咱們不關心。

接口實作

每種集合的具體實作，是重用性很高的資料結構。

算法

集合提供了資料存放以及查找、排序等功能，集合有很多種，也就是算法通常也是多态的，因為相同的方法可以在同一個接口被多個類實作時有不同的表現。

事實上，算法是可複用的函數。 它減少了程式設計的辛勞。

集合架構通過提供有用的資料結構和算法使你能集中注意力于你的程式的重要部分上，而不是為了讓程式能正常運轉而将注意力于低層設計上。

集合的特點

• 對象封裝資料，多個對象需要用集合存儲；
• 對象的個數可以确定使用數組更高效，不确定個數的情況下可以使用集合，因為集合是可變長度。

集合與數組的差別

• 數組是固定長度的；集合可變長度的。
• 數組可以存儲基本資料類型，也可以存儲引用資料類型；集合隻能存儲引用資料類型。
• 數組存儲的元素必須是同一個資料類型；集合存儲的對象可以是不同資料類型。

由于有多種集合容器，因為每一個容器的自身特點不同，其實原理在于每個容器的内部資料結構不同。

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

集合架構有哪些優勢

• 容量自動增長擴容；
• 提供高性能的資料結構和算法；
• 可以友善地擴充或改寫集合，提高代碼複用性和可操作性。
• 通過使用JDK自帶的集合類，可以降低代碼維護和學習新API成本。

有哪些常用的集合類

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

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

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

• List：一個有序（元素存入集合的順序和取出的順序一緻）容器，元素可以重複，可以插入多個null元素，元素都有索引。常用的實作類有 ArrayList、LinkedList 和 Vector。
• Set：一個無序（存入和取出順序有可能不一緻）容器，不可以存儲重複元素，隻允許存入一個null元素，必須保證元素唯一性。
• Set 接口常用實作類是 HashSet、LinkedHashSet 以及 TreeSet。

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

Map沒有繼承于 Collection 接口，從 Map 集合中檢索元素時，隻要給出鍵對象，就會傳回對應的值對象。

Map 的常用實作類：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap

集合的底層資料結構

Collection

1. List
   • ArrayList：Object 數組；
   • Vector：Object 數組；
   • LinkedList：雙向循環連結清單；
2. Set

   • HashSet：唯一，無序。基于 HashMap 實作，底層采用 HashMap 儲存資料。

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

     如果我們沒有重寫這兩個方法，将會使用這個方法的預設實作。

   • LinkedHashSet： LinkedHashSet 繼承與 HashSet，底層使用 LinkedHashMap 來儲存所有元素。
   • TreeSet（有序，唯一）： 紅黑樹(自平衡的排序二叉樹。)

Map

• HashMap：JDK1.8之前HashMap由數組+連結清單組成的，數組是HashMap的主體，連結清單則是主要為了解決哈希沖突而存在的（“拉鍊法”解決沖突）。

  JDK1.8以後在解決哈希沖突時有了較大的變化，當連結清單長度大于門檻值（預設為8）時，将連結清單轉化為紅黑樹，以減少搜尋時間。

• LinkedHashMap：LinkedHashMap 繼承自 HashMap，是以它的底層仍然是基于拉鍊式散列結構即由數組和連結清單或紅黑樹組成。

  内部還有一個雙向連結清單維護鍵值對的順序，每個鍵值對既位于哈希表中，也位于雙向連結清單中。

  LinkedHashMap支援兩種順序插入順序 、 通路順序。

  • 插入順序：先添加的在前面，後添加的在後面。修改操作不影響順序
  • 通路順序：所謂通路指的是get/put操作，對一個鍵執行get/put操作後，其對應的鍵值對會移動到連結清單末尾，是以最末尾的是最近通路的，最開始的是最久沒有被通路的，這就是通路順序。
• HashTable： 數組+連結清單組成的，數組是 HashMap 的主體，連結清單則是主要為了解決哈希沖突而存在的
• TreeMap： 紅黑樹（自平衡的排序二叉樹）

集合的 fail-fast 快速失敗機制

Java 集合的一種錯誤檢測機制，當多個線程對集合進行結構上的改變的操作時，有可能會産生 fail-fast 機制。

原因：疊代器在周遊時直接通路集合中的内容，并且在周遊過程中使用一個 modCount 變量。

集合在被周遊期間如果内容發生變化，就會改變modCount的值。

每當疊代器使用hashNext()/next()周遊下一個元素之前，都會檢測modCount變量是否為expectedmodCount值，是的話就傳回周遊；否則抛出異常，終止周遊。

解決辦法：

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

Collection 接口

List 接口

Itertator 是什麼

Iterator 接口提供周遊任何 Collection 的接口。我們可以從一個 Collection 中使用疊代器方法來擷取疊代器執行個體。

疊代器取代了 Java 集合架構中的 Enumeration，疊代器允許調用者在疊代過程中移除元素。

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)
}
           

運作以上錯誤代碼會報 ConcurrentModificationException 異常。

如何實作數組和 List 之間的轉換？

• 數組轉 List：使用 Arrays. asList(array) 進行轉換。
• List 轉數組：使用 List 自帶的 toArray() 方法。

ArrayList 和 LinkedList 的差別是什麼？

• 資料結構實作：ArrayList 是動态數組的資料結構實作，而 LinkedList 是雙向連結清單的資料結構實作。
• 随機通路效率：ArrayList 比 LinkedList 在随機通路的時候效率要高，因為 LinkedList 是線性的資料存儲方式，是以需要移動指針從前往後依次查找。
• 增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因為 ArrayList 增删操作要影響數組内的其他資料的下标。
• 記憶體空間占用：LinkedList 比 ArrayList 更占記憶體，因為 LinkedList 的節點除了存儲資料，還存儲了兩個引用，一個指向前一個元素，一個指向後一個元素。
• 線程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；

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

為什麼 ArrayList 的 elementData 加上 transient 修飾？

ArrayList 中的數組定義如下：

private transient Object[] elementData;
           

ArrayList 的定義：

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

ArrayList 實作了 Serializable 接口，這意味着 ArrayList 支援序列化。

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

每次序列化時，先調用

defaultWriteObject()

方法序列化

ArrayList

中的非

transient

元素，然後周遊

elementData

，隻序列化已存入的元素，這樣既加快了序列化的速度，又減小了序列化之後的檔案大小。

介紹下CopyOnWriteArrayList？

CopyOnWriteArrayList是ArrayList的線程安全版本，也是大名鼎鼎的copy-on-write（COW，寫時複制）的一種實作。

在讀操作時不加鎖，跟ArrayList類似；在寫操作時，複制出一個新的數組，在新數組上進行操作，操作完了，将底層數組指針指向新數組。

适合使用在讀多寫少的場景。例如add(Ee)方法的操作流程如下：使用ReentrantLock加鎖，拿到原數組的length，使用Arrays.copyOf方法從原數組複制一個新的數組（length+1），将要添加的元素放到新數組的下标length位置，最後将底層數組指針指向新數組。

List、Set、Map三者的差別?

• List（對付順序的好幫手）：存儲的對象是可重複的、有序的。
• Set（注重獨一無二的性質）：存儲的對象是不可重複的、無序的。
• Map（用Key來搜尋的專業戶）:存儲鍵值對（key-value），不能包含重複的鍵（key），每個鍵隻能映射到一個值。

Set 接口

說一下 HashSet 的實作原理？

• HashSet

  底層原理完全就是包裝了一下

  HashMap

• HashSet

  的唯一性保證是依賴與

  hashCode()

  和

  equals()

  兩個方法，是以存入對象的時候一定要自己重寫這兩個方法來設定去重的規則。

• HashSet

  中的元素都存放在

  HashMap

  的

  key

  上面，而

  value

  中的值都是統一的一個 private static final Object PRESENT = new Object();

hashCode（）與equals（）的相關規定：

1. 如果兩個對象相等，則 hashcode 一定也是相同的
2. 兩個對象相等，對兩個 equals 方法傳回 true
3. 兩個對象有相同的 hashcode 值，它們也不一定是相等的
4. 綜上，equals方法被覆寫過，則hashCode方法也必須被覆寫
5. hashCode()的預設行為是對堆上的對象産生獨特值。如果沒有重寫hashCode()，則該class的兩個對象無論如何都不會相等（即使這兩個對象指向相同的資料）。

==與equals的差別

1. ==

   是判斷兩個變量或執行個體是不是指向同一個記憶體空間

   equals

   是判斷兩個變量或執行個體所指向的記憶體空間的值是不是相同

2. ==

   是指對記憶體位址進行比較

   equals()

   是對字元串的内容進行比較

3. ==

   指引用是否相同，

   equals()

   指的是值是否相同。

Queue

BlockingQueue是什麼？

Java.util.concurrent.BlockingQueue

是一個隊列，在進行檢索或移除一個元素的時候，線程會等待隊列變為非空；

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

BlockingQueue接口是Java集合架構的一部分，主要用于實作生産者-消費者模式。

Java提供了幾種

BlockingQueue

的實作，比如

ArrayBlockingQueue

、

LinkedBlockingQueue

、

PriorityBlockingQueue

、

SynchronousQueue

等。

在 Queue 中 poll()和 remove()有什麼差別？

• 相同點：都是傳回第一個元素，并在隊列中删除傳回的對象。
• 不同點：如果沒有元素 poll()會傳回 null，而 remove()會直接抛出 NoSuchElementException 異常。

Map 接口

Map 整體結構如下所示：

Hashtable 比較特别，作為類似 Vector、Stack 的早期集合相關類型，它是擴充了 Dictionary 類的，類結構上與 HashMap 之類明顯不同。

HashMap 等其他 Map 實作則是都擴充了 AbstractMap，裡面包含了通用方法抽象。

不同 Map 的用途，從類圖結構就能展現出來，設計目的已經展現在不同接口上。

HashMap 的實作原理？

在 JDK 1.7 中 HashMap 是以數組加連結清單的形式組成的，JDK 1.8 之後新增了紅黑樹的組成結構，當連結清單大于 8 并且容量大于 64 時，連結清單結構會轉換成紅黑樹結構。

HashMap 基于 Hash 算法實作的：

1. 當我們往Hashmap 中 put 元素時，利用 key 的 hashCode 重新 hash 計算出目前對象的元素在數組中的下标。
2. 存儲時，如果出現 hash 值相同的 key，此時有兩種情況。
   • 如果 key 相同，則覆寫原始值；
   • 如果 key 不同（出現沖突），則将目前的 key-value 放傳入連結表中
3. 擷取時，直接找到 hash 值對應的下标，在進一步判斷 key 是否相同，進而找到對應值。
4. 了解了以上過程就不難明白 HashMap 是如何解決 hash 沖突的問題，核心就是使用了數組的存儲方式，然後将沖突的key的對象放傳入連結表中，一旦發現沖突就在連結清單中做進一步的對比。

JDK1.7 VS JDK1.8 比較

JDK1.8主要解決或優化了一下問題：

1. resize 擴容優化
2. 引入了紅黑樹，目的是避免單條連結清單過長而影響查詢效率，紅黑樹算法請參考
3. 解決了多線程死循環問題，但仍是非線程安全的，多線程時可能會造成資料丢失問題。

不同	JDK 1.7	JDK 1.8
存儲結構	數組 + 連結清單	數組 + 連結清單 + 紅黑樹
初始化方式	單獨函數： inflateTable()	直接內建到了擴容函數 resize() 中
hash值計算方式	擾動處理 = 9次擾動 = 4次位運算 + 5次異或運算	擾動處理 = 2次擾動 = 1次位運算 + 1次異或運算
存放資料的規則	無沖突時，存放數組；沖突時，存放連結清單	無沖突時，存放數組；沖突 & 連結清單長度 < 8：存放單連結清單；沖突 & 連結清單長度 > 8：樹化并存放紅黑樹
插入資料方式	頭插法（先講原位置的資料移到後1位，再插入資料到該位置）	尾插法（直接插入到連結清單尾部/紅黑樹）
擴容後存儲位置的計算方式	全部按照原來方法進行計算（即hashCode ->> 擾動函數 ->> (h&length-1)）	按照擴容後的規律計算（即擴容後的位置=原位置 or 原位置 + 舊容量）

如何有效避免哈希碰撞

主要是因為如果使用hashCode取餘，那麼相當于參與運算的隻有hashCode的低位，高位是沒有起到任何作用的。

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

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

HashMap的put方法的具體流程？

當我們put的時候，首先計算

key

的

hash

值，這裡調用了

hash

方法，

hash

方法實際是讓

key.hashCode()

與

key.hashCode()>>>16

進行異或操作，高16bit補0，一個數和0異或不變，是以 hash 函數大概的作用就是：高16bit不變，低16bit和高16bit做了一個異或，目的是減少碰撞。

①.判斷鍵值對數組table[i]是否為空或為null，否則執行resize()進行擴容；

②.根據鍵值key計算hash值得到插入的數組索引i，如果table[i]==null，直接建立節點添加，轉向⑥，如果table[i]不為空，轉向③；

③.判斷table[i]的首個元素是否和key一樣，如果相同直接覆寫value，否則轉向④，這裡的相同指的是hashCode以及equals；

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

⑤.周遊table[i]，判斷連結清單長度是否大于8，大于8的話把連結清單轉換為紅黑樹，在紅黑樹中執行插入操作，否則進行連結清單的插入操作；周遊過程中若發現key已經存在直接覆寫value即可；

⑥.插入成功後，判斷實際存在的鍵值對數量size是否超多了最大容量threshold，如果超過，進行擴容。

HashMap的擴容操作是怎麼實作的？

①.在jdk1.8中，resize方法是在hashmap中的鍵值對大于閥值時或者初始化時，就調用resize方法進行擴容；

②.每次擴充的時候，都是擴充2倍；

③.擴充後Node對象的位置要麼在原位置，要麼移動到原偏移量兩倍的位置。

在1.7中，擴容之後需要重新去計算其Hash值，根據Hash值對其進行分發.

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

重新進行 hash 配置設定後，該元素的位置要麼停留在原始位置，要麼移動到原始位置+增加的數組大小這個位置上。

任何類都可以作為 Key 麼？

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

• 如果類重寫了 equals() 方法，也應該重寫 hashCode() 方法。
• 類的所有執行個體需要遵循與 equals() 和 hashCode() 相關的規則。
• 如果一個類沒有使用 equals()，不應該在 hashCode() 中使用它。

• 使用者自定義 Key 類最佳實踐是使之為不可變的，這樣 hashCode() 值可以被緩存起來，擁有更好的性能。

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

為什麼HashMap中String、Integer這樣的包裝類适合作為K？

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

1. 都是final類型，即不可變性，保證key的不可更改性，不會存在擷取hash值不同的情況
2. 内部已重寫了

   equals()

   、

   hashCode()

   等方法，遵守了HashMap内部的規範（不清楚可以去上面看看putValue的過程），不容易出現Hash值計算錯誤的情況；

HashMap為什麼不直接使用hashCode()處理後的哈希值直接作為table的下标？

hashCode()

方法傳回的是int整數類型，其範圍為-(2 ^ 31)~(2 ^ 31 - 1)，約有40億個映射空間，而HashMap的容量範圍是在16（初始化預設值）~2 ^ 30，HashMap通常情況下是取不到最大值的，并且裝置上也難以提供這麼多的存儲空間，進而導緻通過

hashCode()

計算出的哈希值可能不在數組大小範圍内，進而無法比對存儲位置；

HashMap 的長度為什麼是2的幂次方

為了能讓 HashMap 存取高效，盡量較少碰撞，也就是要盡量把資料配置設定均勻，每個連結清單/紅黑樹長度大緻相同。這個實作就是把資料存到哪個連結清單/紅黑樹中的算法。

這個算法應該如何設計呢？

我們首先可能會想到采用 % 取餘的操作來實作。

但是，重點來了：取餘(%)操作中如果除數是2的幂次則等價于與其除數減一的與(&)操作（也就是說 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。

并且采用二進制位操作 &，相對于 % 能夠提高運算效率，這就解釋了 HashMap 的長度為什麼是2的幂次方。

那為什麼是兩次擾動呢？

答：這樣就是加大哈希值低位的随機性，使得分布更均勻，進而提高對應數組存儲下标位置的随機性&均勻性，最終減少Hash沖突，兩次就夠了，已經達到了高位低位同時參與運算的目的；

HashMap 和 ConcurrentHashMap 的差別

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

ConcurrentHashMap 實作原理

JDK1.7

首先将資料分為一段一段的存儲，然後給每一段資料配一把鎖，當一個線程占用鎖通路其中一個段資料時，其他段的資料也能被其他線程通路。

在JDK1.7中，ConcurrentHashMap采用Segment + HashEntry的方式進行實作，結構如下：

一個 ConcurrentHashMap 裡包含一個 Segment 數組。

Segment 的結構和HashMap類似，是一種數組和連結清單結構，一個 Segment 包含一個 HashEntry 數組，每個 HashEntry 是一個連結清單結構的元素，每個 Segment 守護着一個HashEntry數組裡的元素，當對 HashEntry 數組的資料進行修改時，必須首先獲得對應的 Segment的鎖。

1. 該類包含兩個靜态内部類 HashEntry 和 Segment ；前者用來封裝映射表的鍵值對，後者用來充當鎖的角色；
2. HashEntry 内部使用 volatile 的 value 字段來保證可見性，get 操作需要保證的是可見性，是以并沒有什麼同步邏輯。
3. Segment 是一種可重入的鎖 ReentrantLock，每個 Segment 守護一個HashEntry 數組裡得元素，當對 HashEntry 數組的資料進行修改時，必須首先獲得對應的 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());
       //利用位操作替換普通數學運算
       long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
        // 以Segment為機關，進行定位
        // 利用Unsafe直接進行volatile access
        if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
            (tab = s.table) != null) {
           //省略
          }
        return null;
    }
           

而對于 put 操作，首先是通過二次哈希避免哈希沖突，然後以 Unsafe 調用方式，直接擷取相應的 Segment，然後進行線程安全的 put 操作：

public V put(K key, V value) {
        Segment<K,V> s;
        if (value == null)
            throw new NullPointerException();
        // 二次哈希，以保證資料的分散性，避免哈希沖突
        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);
    }

           

其核心邏輯實作在下面的内部方法中：

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到特定位置，如果超過門檻值，進行rehash
                        // ...
                    }
                }
            } finally {
                unlock();
            }
            return oldValue;
        }

           

JDK1.8

在JDK1.8中，放棄了Segment臃腫的設計，取而代之的是采用Node + CAS + Synchronized來保證并發安全進行實作。

synchronized隻鎖定目前連結清單或紅黑二叉樹的首節點，這樣隻要hash不沖突，就不會産生并發，效率又提升N倍。

• 總體結構上，它的内部存儲和 HashMap 結構非常相似，同樣是大的桶（bucket）數組，然後内部也是一個個所謂的連結清單結構（bin），同步的粒度要更細緻一些。
• 其内部仍然有 Segment 定義，但僅僅是為了保證序列化時的相容性而已，不再有任何結構上的用處。
• 因為不再使用 Segment，初始化操作大大簡化，修改為 lazy-load 形式，這樣可以有效避免初始開銷，解決了老版本很多人抱怨的這一點。
• 資料存儲利用 volatile 來保證可見性。
• 使用 CAS 等操作，在特定場景進行無鎖并發操作。
• 使用 Unsafe、LongAdder 之類底層手段，進行極端情況的優化。

另外，需要注意的是，“線程安全”這四個字特别容易讓人誤解，因為ConcurrentHashMap 隻能保證提供的原子性讀寫操作是線程安全的。

誤區

我們來看一個使用 Map 來統計 Key 出現次數的場景吧，這個邏輯在業務代碼中非常常見。

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

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

// 共享資料
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，不代表對它的多個操作之間的狀态是一緻的，是沒有其他線程在操作它的，如果需要確定需要手動加鎖。

• 諸如 size、isEmpty 和 containsValue 等聚合方法，在并發情況下可能會反映 ConcurrentHashMap 的中間狀态。

  是以在并發情況下，這些方法的傳回值隻能用作參考，而不能用于流程控制。

  顯然，利用 size 方法計算差異值，是一個流程控制。

• 諸如 putAll 這樣的聚合方法也不能確定原子性，在 putAll 的過程中去擷取資料可能會擷取到部分資料。

//利用computeIfAbsent()方法來執行個體化LongAdder，然後利用LongAdder來進行線程安全計數 
freqs.computeIfAbsent(key, k -> new LongAdder()).increment();