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

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

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

🔮本文由京與舊鋪原創

😘系列專欄：java學習

👕參考網站：牛客網

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

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

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

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

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

🛒導航小助手🎪

文章目錄

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

2.21 請介紹TreeMap的底層原理
2.24 ArrayList和LinkedList有什麼差別？
2.25 有哪些線程安全的List？
2.26 介紹一下ArrayList的資料結構？
2.27 談談CopyOnWriteArrayList的原理
2.28 說一說TreeSet和HashSet的差別
2.29 說一說HashSet的底層結構

2.21 請介紹TreeMap的底層原理

參考答案

TreeMap基于紅黑樹（Red-Black tree）實作。映射根據其鍵的自然順序進行排序，或者根據建立映射時提供的 Comparator 進行排序，具體取決于使用的構造方法。TreeMap的基本操作containsKey、get、put、remove方法，它的時間複雜度是log(N)。

TreeMap包含幾個重要的成員變量：root、size、comparator。其中root是紅黑樹的根節點。它是Entry類型，Entry是紅黑樹的節點，它包含了紅黑樹的6個基本組成：key、value、left、right、parent和color。Entry節點根據根據Key排序，包含的内容是value。Entry中key比較大小是根據比較器comparator來進行判斷的。size是紅黑樹的節點個數。

2.24 ArrayList和LinkedList有什麼差別？

參考答案

ArrayList的實作是基于數組，LinkedList的實作是基于雙向連結清單；
對于随機通路ArrayList要優于LinkedList，ArrayList可以根據下标以O(1)時間複雜度對元素進行随機通路，而LinkedList的每一個元素都依靠位址指針和它後一個元素連接配接在一起，查找某個元素的時間複雜度是O(N)；
對于插入和删除操作，LinkedList要優于ArrayList，因為當元素被添加到LinkedList任意位置的時候，不需要像ArrayList那樣重新計算大小或者是更新索引；
LinkedList比ArrayList更占記憶體，因為LinkedList的節點除了存儲資料，還存儲了兩個引用，一個指向前一個元素，一個指向後一個元素。

2.25 有哪些線程安全的List？

參考答案

Vector

Vector是比較古老的API，雖然保證了線程安全，但是由于效率低一般不建議使用。
Collections.SynchronizedList

SynchronizedList是Collections的内部類，Collections提供了synchronizedList方法，可以将一個線程不安全的List包裝成線程安全的List，即SynchronizedList。它比Vector有更好的擴充性和相容性，但是它所有的方法都帶有同步鎖，也不是性能最優的List。
CopyOnWriteArrayList

CopyOnWriteArrayList是Java 1.5在java.util.concurrent包下增加的類，它采用複制底層數組的方式來實作寫操作。當線程對此類集合執行讀取操作時，線程将會直接讀取集合本身，無須加鎖與阻塞。當線程對此類集合執行寫入操作時，集合會在底層複制一份新的數組，接下來對新的數組執行寫入操作。由于對集合的寫入操作都是對數組的副本執行操作，是以它是線程安全的。在所有線程安全的List中，它是性能最優的方案。

2.26 介紹一下ArrayList的資料結構？

參考答案

ArrayList的底層是用數組來實作的，預設第一次插入元素時建立大小為10的數組，超出限制時會增加50%的容量，并且資料以 System.arraycopy() 複制到新的數組，是以最好能給出數組大小的預估值。

按數組下标通路元素的性能很高，這是數組的基本優勢。直接在數組末尾加入元素的性能也高，但如果按下标插入、删除元素，則要用 System.arraycopy() 來移動部分受影響的元素，性能就變差了，這是基本劣勢。

2.27 談談CopyOnWriteArrayList的原理

參考答案

CopyOnWriteArrayList是Java并發包裡提供的并發類，簡單來說它就是一個線程安全且讀操作無鎖的ArrayList。正如其名字一樣，在寫操作時會複制一份新的List，在新的List上完成寫操作，然後再将原引用指向新的List。這樣就保證了寫操作的線程安全。

CopyOnWriteArrayList允許線程并發通路讀操作，這個時候是沒有加鎖限制的，性能較高。而寫操作的時候，則首先将容器複制一份，然後在新的副本上執行寫操作，這個時候寫操作是上鎖的。結束之後再将原容器的引用指向新容器。注意，在上鎖執行寫操作的過程中，如果有需要讀操作，會作用在原容器上。是以上鎖的寫操作不會影響到并發通路的讀操作。

優點：讀操作性能很高，因為無需任何同步措施，比較适用于讀多寫少的并發場景。在周遊傳統的List時，若中途有别的線程對其進行修改，則會抛出ConcurrentModificationException異常。而CopyOnWriteArrayList由于其"讀寫分離"的思想，周遊和修改操作分别作用在不同的List容器，是以在使用疊代器進行周遊時候，也就不會抛出ConcurrentModificationException異常了。
缺點：一是記憶體占用問題，畢竟每次執行寫操作都要将原容器拷貝一份，資料量大時，對記憶體壓力較大，可能會引起頻繁GC。二是無法保證明時性，Vector對于讀寫操作均加鎖同步，可以保證讀和寫的強一緻性。而CopyOnWriteArrayList由于其實作政策的原因，寫和讀分别作用在新老不同容器上，在寫操作執行過程中，讀不會阻塞但讀取到的卻是老容器的資料。

2.28 說一說TreeSet和HashSet的差別

參考答案

HashSet、TreeSet中的元素都是不能重複的，并且它們都是線程不安全的，二者的差別是：

HashSet中的元素可以是null，但TreeSet中的元素不能是null；
HashSet不能保證元素的排列順序，而TreeSet支援自然排序、定制排序兩種排序的方式；
HashSet底層是采用哈希表實作的，而TreeSet底層是采用紅黑樹實作的。

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