## 17 [*]并發 List、Map源碼面試題 ## 引導語 并發 List 和 Map 是技術面時常問的問題，問的問題也都比較深入，有很多問題都是面試官自創的，市面上找不到，所以說通過背題的方式，這一關大部分是過不了的，只有我們真正理解了 API 內部的實現，閱讀過源碼，才能自如應對各種類型的面試題，接著我們來看一下并發 List、Map 源碼相關的面試題集。 ### 1 CopyOnWriteArrayList 相關 #### 1.1 和 ArrayList 相比有哪些相同點和不同點？ 答：相同點：底層的數據結構是相同的，都是數組的數據結構，提供出來的 API 都是對數組結構進行操作，讓我們更好的使用。 不同點：后者是線程安全的，在多線程環境下使用，無需加鎖，可直接使用。 #### 1.2 CopyOnWriteArrayList 通過哪些手段實現了線程安全？ 答：主要有：1. 數組容器被 volatile 關鍵字修飾，保證了數組內存地址被任意線程修改后，都會通知到其他線程； 1. 對數組的所有修改操作，都進行了加鎖，保證了同一時刻，只能有一個線程對數組進行修改，比如我在 add 時，就無法 remove； 2. 修改過程中對原數組進行了復制，是在新數組上進行修改的，修改過程中，不會對原數組產生任何影響。 通過以上三點保證了線程安全。 #### 1.3 在 add 方法中，對數組進行加鎖后，不是已經是線程安全了么，為什么還需要對老數組進行拷貝？ 答：的確，對數組進行加鎖后，能夠保證同一時刻，只有一個線程能對數組進行 add，在同單核 CPU 下的多線程環境下肯定沒有問題，但我們現在的機器都是多核 CPU，如果我們不通過復制拷貝新建數組，修改原數組容器的內存地址的話，是無法觸發 volatile 可見性效果的，那么其他 CPU 下的線程就無法感知數組原來已經被修改了，就會引發多核 CPU 下的線程安全問題。 假設我們不復制拷貝，而是在原來數組上直接修改值，數組的內存地址就不會變，而數組被 volatile 修飾時，必須當數組的內存地址變更時，才能及時的通知到其他線程，內存地址不變，僅僅是數組元素值發生變化時，是無法把數組元素值發生變動的事實，通知到其它線程的。 #### 1.4 對老數組進行拷貝，會有性能損耗，我們平時使用需要注意什么么？ 答：主要有： 1. 在批量操作時，盡量使用 addAll、removeAll 方法，而不要在循環里面使用 add、remove 方法，主要是因為 for 循環里面使用 add 、remove 的方式，在每次操作時，都會進行一次數組的拷貝(甚至多次)，非常耗性能，而 addAll、removeAll 方法底層做了優化，整個操作只會進行一次數組拷貝，由此可見，當批量操作的數據越多時，批量方法的高性能體現的越明顯。 #### 1.5 為什么 CopyOnWriteArrayList 迭代過程中，數組結構變動，不會拋出ConcurrentModificationException 了 答：主要是因為 CopyOnWriteArrayList 每次操作時，都會產生新的數組，而迭代時，持有的仍然是老數組的引用，所以我們說的數組結構變動，是用新數組替換了老數組，老數組的結構并沒有發生變化，所以不會拋出異常了。 #### 1.6 插入的數據正好在 List 的中間，請問兩種 List 分別拷貝數組幾次？為什么？ 答：ArrayList 只需拷貝一次，假設插入的位置是 2，只需要把位置 2 （包含 2）后面的數據都往后移動一位即可，所以拷貝一次。 CopyOnWriteArrayList 拷貝兩次，因為 CopyOnWriteArrayList 多了把老數組的數據拷貝到新數組上這一步，可能有的同學會想到這種方式：先把老數組拷貝到新數組，再把 2 后面的數據往后移動一位，這的確是一種拷貝的方式，但 CopyOnWriteArrayList 底層實現更加靈活，而是：把老數組 0 到 2 的數據拷貝到新數組上，預留出新數組 2 的位置，再把老數組 3～ 最后的數據拷貝到新數組上，這種拷貝方式可以減少我們拷貝的數據，雖然是兩次拷貝，但拷貝的數據卻仍然是老數組的大小，設計的非常巧妙。 ### 2 ConcurrentHashMap 相關 #### 2.1ConcurrentHashMap 和 HashMap 的相同點和不同點 答：相同點：1. 都是數組 + 鏈表 +紅黑樹的數據結構，所以基本操作的思想相同； 1. 都實現了 Map 接口，繼承了 AbstractMap 抽象類，所以兩者的方法大多都是相似的，可以互相切換。 不同點：1. ConcurrentHashMap 是線程安全的，在多線程環境下，無需加鎖，可直接使用； 1. 數據結構上，ConcurrentHashMap 多了轉移節點，主要用于保證擴容時的線程安全。 #### 2.2 ConcurrentHashMap 通過哪些手段保證了線程安全。 答：主要有以下幾點： 1. 儲存 Map 數據的數組被 volatile 關鍵字修飾，一旦被修改，立馬就能通知其他線程，因為是數組，所以需要改變其內存值，才能真正的發揮出 volatile 的可見特性； 2. put 時，如果計算出來的數組下標索引沒有值的話，采用無限 for 循環 + CAS 算法，來保證一定可以新增成功，又不會覆蓋其他線程 put 進去的值； 3. 如果 put 的節點正好在擴容，會等待擴容完成之后，再進行 put ，保證了在擴容時，老數組的值不會發生變化； 4. 對數組的槽點進行操作時，會先鎖住槽點，保證只有當前線程才能對槽點上的鏈表或紅黑樹進行操作； 5. 紅黑樹旋轉時，會鎖住根節點，保證旋轉時的線程安全。 #### 2.3 描述一下 CAS 算法在 ConcurrentHashMap 中的應用？ 答：CAS 其實是一種樂觀鎖，一般有三個值，分別為：賦值對象，原值，新值，在執行的時候，會先判斷內存中的值是否和原值相等，相等的話把新值賦值給對象，否則賦值失敗，整個過程都是原子性操作，沒有線程安全問題。 ConcurrentHashMap 的 put 方法中，有使用到 CAS ，是結合無限 for 循環一起使用的，步驟如下： 1. 計算出數組索引下標，拿出下標對應的原值； 2. CAS 覆蓋當前下標的值，賦值時，如果發現內存值和 1 拿出來的原值相等，執行賦值，退出循環，否則不賦值，轉到 3； 3. 進行下一次 for 循環，重復執行 1，2，直到成功為止。 可以看到這樣做的好處，第一是不會盲目的覆蓋原值，第二是一定可以賦值成功。 #### 2.4 ConcurrentHashMap 是如何發現當前槽點正在擴容的。 答：ConcurrentHashMap 新增了一個節點類型，叫做轉移節點，當我們發現當前槽點是轉移節點時（轉移節點的 hash 值是 -1），即表示 Map 正在進行擴容。 #### 2.5 發現槽點正在擴容時，put 操作會怎么辦？ 答：無限 for 循環，或者走到擴容方法中去，幫助擴容，一直等待擴容完成之后，再執行 put 操作。 #### 2.6 兩種 Map 擴容時，有啥區別？ 答：區別很大，HashMap 是直接在老數據上面進行擴容，多線程環境下，會有線程安全的問題，而 ConcurrentHashMap 就不太一樣，擴容過程是這樣的： 1. 從數組的隊尾開始拷貝； 2. 拷貝數組的槽點時，先把原數組槽點鎖住，拷貝成功到新數組時，把原數組槽點賦值為轉移節點； 3. 從數組的尾部拷貝到頭部，每拷貝成功一次，就把原數組的槽點設置成轉移節點； 4. 直到所有數組數據都拷貝到新數組時，直接把新數組整個賦值給數組容器，拷貝完成。 簡單來說，通過擴容時給槽點加鎖，和發現槽點正在擴容就等待的策略，保證了 ConcurrentHashMap 可以慢慢一個一個槽點的轉移，保證了擴容時的線程安全，轉移節點比較重要，平時問的人也比較多。 #### 2.7 ConcurrentHashMap 在 Java 7 和 8 中關于線程安全的做法有啥不同？ 答：非常不一樣，拿 put 方法為例，Java 7 的做法是： 1. 把數組進行分段，找到當前 key 對應的是那一段； 2. 將當前段鎖住，然后再根據 hash 尋找對應的值，進行賦值操作。 Java 7 的做法比較簡單，缺點也很明顯，就是當我們需要 put 數據時，我們會鎖住改該數據對應的某一段，這一段數據可能會有很多，比如我只想 put 一個值，鎖住的卻是一段數據，導致這一段的其他數據都不能進行寫入操作，大大的降低了并發性的效率。Java 8 解決了這個問題，從鎖住某一段，修改成鎖住某一個槽點，提高了并發效率。 不僅僅是 put，刪除也是，僅僅是鎖住當前槽點，縮小了鎖的范圍，增大了效率。 #### 3 總結 因為目前大多數公司都已經在使用 Java 8 了，所以大部分面試內容還是以 Java 8 的 API 為主，特別是 CopyOnWriteArrayList 和 ConcurrentHashMap 兩個 API，文章畢竟篇幅有限，建議大家多多閱讀剩余源碼。