卷妹帶你回顧Java基礎(一)每日更新Day5

👩‍💻部落格首頁：京與舊鋪的部落格首頁

✨歡迎關注🖱點贊🎀收藏⭐留言✒

🔮本文由京與舊鋪原創

😘系列專欄：java學習

👕參考網站：牛客網

💻首發時間：🎞2022年8月8日🎠

🎨你做三四月的事，八九月就會有答案，一起加油吧

🀄如果覺得部落客的文章還不錯的話，請三連支援一下部落客哦

🎧最後的話，作者是一個新人，在很多方面還做的不好，歡迎大佬指正，一起學習哦，沖沖沖

💬推薦一款模拟面試、刷題神器👉點選進入網站

🛒導航小助手🎪

文章目錄

卷妹帶你回顧Java基礎(一)每日更新Day5
🛒導航小助手🎪

@[toc]

2.2 Java中的容器，線程安全和線程不安全的分别有哪些？
2.3 Map接口有哪些實作類？
2.4 描述一下Map put的過程
2.5 如何得到一個線程安全的Map？
2.6 HashMap有什麼特點？
2.7 JDK7和JDK8中的HashMap有什麼差別？
2.8 介紹一下HashMap底層的實作原理
2.9 介紹一下HashMap的擴容機制
2.10 HashMap中的循環連結清單是如何産生的？
2.11 HashMap為什麼用紅黑樹而不用B樹？
2.12 HashMap為什麼線程不安全？
2.13 HashMap如何實作線程安全？
2.14 HashMap是如何解決哈希沖突的？
2.15 說一說HashMap和HashTable的差別
2.16 HashMap與ConcurrentHashMap有什麼差別？
2.17 介紹一下ConcurrentHashMap是怎麼實作的？
2.18 ConcurrentHashMap是怎麼分段分組的？

2.2 Java中的容器，線程安全和線程不安全的分别有哪些？

參考答案

java.util包下的集合類大部分都是線程不安全的，例如我們常用的HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap，這些都是線程不安全的集合類，但是它們的優點是性能好。如果需要使用線程安全的集合類，則可以使用Collections工具類提供的synchronizedXxx()方法，将這些集合類包裝成線程安全的集合類。

java.util包下也有線程安全的集合類，例如Vector、Hashtable。這些集合類都是比較古老的API，雖然實作了線程安全，但是性能很差。是以即便是需要使用線程安全的集合類，也建議将線程不安全的集合類包裝成線程安全集合類的方式，而不是直接使用這些古老的API。

從Java5開始，Java在java.util.concurrent包下提供了大量支援高效并發通路的集合類，它們既能包裝良好的通路性能，有能包裝線程安全。這些集合類可以分為兩部分，它們的特征如下：

以Concurrent開頭的集合類：

以Concurrent開頭的集合類代表了支援并發通路的集合，它們可以支援多個線程并發寫入通路，這些寫入線程的所有操作都是線程安全的，但讀取操作不必鎖定。以Concurrent開頭的集合類采用了更複雜的算法來保證永遠不會鎖住整個集合，是以在并發寫入時有較好的性能。
以CopyOnWrite開頭的集合類：

以CopyOnWrite開頭的集合類采用複制底層數組的方式來實作寫操作。當線程對此類集合執行讀取操作時，線程将會直接讀取集合本身，無須加鎖與阻塞。當線程對此類集合執行寫入操作時，集合會在底層複制一份新的數組，接下來對新的數組執行寫入操作。由于對集合的寫入操作都是對數組的副本執行操作，是以它是線程安全的。

2.3 Map接口有哪些實作類？

參考答案

Map接口有很多實作類，其中比較常用的有HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap。

對于不需要排序的場景，優先考慮使用HashMap，因為它是性能最好的Map實作。如果需要保證線程安全，則可以使用ConcurrentHashMap。它的性能好于Hashtable，因為它在put時采用分段鎖/CAS的加鎖機制，而不是像Hashtable那樣，無論是put還是get都做同步處理。

對于需要排序的場景，如果需要按插入順序排序則可以使用LinkedHashMap，如果需要将key按自然順序排列甚至是自定義順序排列，則可以選擇TreeMap。如果需要保證線程安全，則可以使用Collections工具類将上述實作類包裝成線程安全的Map。

2.4 描述一下Map put的過程

參考答案

HashMap是最經典的Map實作，下面以它的視角介紹put的過程：

首次擴容：

先判斷數組是否為空，若數組為空則進行第一次擴容（resize）；
計算索引：

通過hash算法，計算鍵值對在數組中的索引；
插入資料：

如果目前位置元素為空，則直接插入資料；
如果目前位置元素非空，且key已存在，則直接覆寫其value；
如果目前位置元素非空，且key不存在，則将資料鍊到連結清單末端；
若連結清單長度達到8，則将連結清單轉換成紅黑樹，并将資料插入樹中；

再次擴容

如果數組中元素個數（size）超過threshold，則再次進行擴容操作。

2.5 如何得到一個線程安全的Map？

參考答案

使用Collections工具類，将線程不安全的Map包裝成線程安全的Map；
使用java.util.concurrent包下的Map，如ConcurrentHashMap；
不建議使用Hashtable，雖然Hashtable是線程安全的，但是性能較差。

2.6 HashMap有什麼特點？

參考答案

HashMap是線程不安全的實作；
HashMap可以使用null作為key或value。

2.7 JDK7和JDK8中的HashMap有什麼差別？

參考答案

JDK7中的HashMap，是基于數組+連結清單來實作的，它的底層維護一個Entry數組。它會根據計算的hashCode将對應的KV鍵值對存儲到該數組中，一旦發生hashCode沖突，那麼就會将該KV鍵值對放到對應的已有元素的後面，此時便形成了一個連結清單式的存儲結構。

JDK7中HashMap的實作方案有一個明顯的缺點，即當Hash沖突嚴重時，在桶上形成的連結清單會變得越來越長，這樣在查詢時的效率就會越來越低，其時間複雜度為O(N)。

JDK8中的HashMap，是基于數組+連結清單+紅黑樹來實作的，它的底層維護一個Node數組。當連結清單的存儲的資料個數大于等于8的時候，不再采用連結清單存儲，而采用了紅黑樹存儲結構。這麼做主要是在查詢的時間複雜度上進行優化，連結清單為O(N)，而紅黑樹一直是O(logN)，可以大大的提高查找性能。

2.8 介紹一下HashMap底層的實作原理

參考答案

它基于hash算法，通過put方法和get方法存儲和擷取對象。

存儲對象時，我們将K/V傳給put方法時，它調用K的hashCode計算hash進而得到bucket位置，進一步存儲，HashMap會根據目前bucket的占用情況自動調整容量(超過Load Facotr則resize為原來的2倍)。擷取對象時，我們将K傳給get，它調用hashCode計算hash進而得到bucket位置，并進一步調用equals()方法确定鍵值對。

如果發生碰撞的時候，HashMap通過連結清單将産生碰撞沖突的元素組織起來。在Java 8中，如果一個bucket中碰撞沖突的元素超過某個限制(預設是8)，則使用紅黑樹來替換連結清單，進而提高速度。

2.9 介紹一下HashMap的擴容機制

參考答案

數組的初始容量為16，而容量是以2的次方擴充的，一是為了提高性能使用足夠大的數組，二是為了能使用位運算代替取模預算(據說提升了5~8倍)。
數組是否需要擴充是通過負載因子判斷的，如果目前元素個數為數組容量的0.75時，就會擴充數組。這個0.75就是預設的負載因子，可由構造器傳入。我們也可以設定大于1的負載因子，這樣數組就不會擴充，犧牲性能，節省記憶體。
為了解決碰撞，數組中的元素是單向連結清單類型。當連結清單長度到達一個門檻值時（7或8），會将連結清單轉換成紅黑樹提高性能。而當連結清單長度縮小到另一個門檻值時（6），又會将紅黑樹轉換回單向連結清單提高性能。
對于第三點補充說明，檢查連結清單長度轉換成紅黑樹之前，還會先檢測目前數組數組是否到達一個門檻值（64），如果沒有到達這個容量，會放棄轉換，先去擴充數組。是以上面也說了連結清單長度的門檻值是7或8，因為會有一次放棄轉換的操作。

2.10 HashMap中的循環連結清單是如何産生的？

參考答案

在多線程的情況下，當重新調整HashMap大小的時候，就會存在條件競争，因為如果兩個線程都發現HashMap需要重新調整大小了，它們會同時試着調整大小。在調整大小的過程中，存儲在連結清單中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap并不會将元素放在連結清單的尾部，而是放在頭部，這是為了避免尾部周遊。如果條件競争發生了，那麼就會産生死循環了。

2.11 HashMap為什麼用紅黑樹而不用B樹？

參考答案

B/B+樹多用于外存上時，B/B+也被成為一個磁盤友好的資料結構。

HashMap本來是數組+連結清單的形式，連結清單由于其查找慢的特點，是以需要被查找效率更高的樹結構來替換。如果用B/B+樹的話，在資料量不是很多的情況下，資料都會“擠在”一個結點裡面，這個時候周遊效率就退化成了連結清單。

2.12 HashMap為什麼線程不安全？

參考答案

HashMap在并發執行put操作時，可能會導緻形成循環連結清單，進而引起死循環。

2.13 HashMap如何實作線程安全？

參考答案

直接使用Hashtable類；
直接使用ConcurrentHashMap；
使用Collections将HashMap包裝成線程安全的Map。

2.14 HashMap是如何解決哈希沖突的？

參考答案

為了解決碰撞，數組中的元素是單向連結清單類型。當連結清單長度到達一個門檻值時，會将連結清單轉換成紅黑樹提高性能。而當連結清單長度縮小到另一個門檻值時，又會将紅黑樹轉換回單向連結清單提高性能。

2.15 說一說HashMap和HashTable的差別

參考答案

Hashtable是一個線程安全的Map實作，但HashMap是線程不安全的實作，是以HashMap比Hashtable的性能高一點。
Hashtable不允許使用null作為key和value，如果試圖把null值放進Hashtable中，将會引發空指針異常，但HashMap可以使用null作為key或value。

擴充閱讀

從Hashtable的類名上就可以看出它是一個古老的類，它的命名甚至沒有遵守Java的命名規範：每個單詞的首字母都應該大寫。也許當初開發Hashtable的工程師也沒有注意到這一點，後來大量Java程式中使用了Hashtable類，是以這個類名也就不能改為HashTable了，否則将導緻大量程式需要改寫。

與Vector類似的是，盡量少用Hashtable實作類，即使需要建立線程安全的Map實作類，也無須使用Hashtable實作類，可以通過Collections工具類把HashMap變成線程安全的Map。

2.16 HashMap與ConcurrentHashMap有什麼差別？

參考答案

HashMap是非線程安全的，這意味着不應該在多線程中對這些Map進行修改操作，否則會産生資料不一緻的問題，甚至還會因為并發插入元素而導緻連結清單成環，這樣在查找時就會發生死循環，影響到整個應用程式。

Collections工具類可以将一個Map轉換成線程安全的實作，其實也就是通過一個包裝類，然後把所有功能都委托給傳入的Map，而包裝類是基于synchronized關鍵字來保證線程安全的（Hashtable也是基于synchronized關鍵字），底層使用的是互斥鎖，性能與吞吐量比較低。

ConcurrentHashMap的實作細節遠沒有這麼簡單，是以性能也要高上許多。它沒有使用一個全局鎖來鎖住自己，而是采用了減少鎖粒度的方法，盡量減少因為競争鎖而導緻的阻塞與沖突，而且ConcurrentHashMap的檢索操作是不需要鎖的。

2.17 介紹一下ConcurrentHashMap是怎麼實作的？

參考答案

JDK 1.7中的實作：

在 jdk 1.7 中，ConcurrentHashMap 是由 Segment 資料結構和 HashEntry 數組結構構成，采取分段鎖來保證安全性。Segment 是 ReentrantLock 重入鎖，在 ConcurrentHashMap 中扮演鎖的角色，HashEntry 則用于存儲鍵值對資料。一個 ConcurrentHashMap 裡包含一個 Segment 數組，一個 Segment 裡包含一個 HashEntry 數組，Segment 的結構和 HashMap 類似，是一個數組和連結清單結構。

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-SeYa3VPC-1660798666217)(https://uploadfiles.nowcoder.com/images/20220224/4107856_1645689003626/A064CF0DD49D1B3694548913C28728DB)]

JDK 1.8中的實作：

JDK1.8 的實作已經摒棄了 Segment 的概念，而是直接用 Node 數組+連結清單+紅黑樹的資料結構來實作，并發控制使用 Synchronized 和 CAS 來操作，整個看起來就像是優化過且線程安全的 HashMap，雖然在 JDK1.8 中還能看到 Segment 的資料結構，但是已經簡化了屬性，隻是為了相容舊版本。

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-j8I9TOuF-1660798666218)(https://uploadfiles.nowcoder.com/images/20220224/4107856_1645689024609/9C8ABF1CD3475339A49DE3B9E1696FE7)]

2.18 ConcurrentHashMap是怎麼分段分組的？

參考答案

get操作：

Segment的get操作實作非常簡單和高效，先經過一次再散列，然後使用這個散列值通過散列運算定位到 Segment，再通過雜湊演算法定位到元素。get操作的高效之處在于整個get過程都不需要加鎖，除非讀到空的值才會加鎖重讀。原因就是将使用的共享變量定義成 volatile 類型。

put操作：

判斷是否需要擴容；
定位到添加元素的位置，将其放入 HashEntry 數組中。

卷妹帶你回顧Java基礎(一)每日更新Day5