面試題002-Java-Java集合

題目自測

• 1. 說說 List,Set,Map 三者的區別？三者底層的數據結構？
• 2. 有哪些集合是線程不安全的？怎么解決呢？
• 3. 比較 HashSet 、LinkedHashSet 和 TreeSet 三者的異同？
• 4. HashMap 和 Hashtable 的區別？HashMap 和 HashSet 區別？ HashMap 和 TreeMap 區別？
• 5. HashMap 的底層實現？
• 6. HashMap 的長度為什么是 2 的冪次方？
• 7. ConcurrentHashMap 和 Hashtable 的區別？
• 8. ConcurrentHashMap 線程安全的具體實現方式/底層具體實現？

題目答案

1. 說說 List,Set,Map 三者的區別？三者底層的數據結構？

答：List 有序、可以包含重復元素。主要實現類為 ArrayList 底層數據結構為動態數組。
Set 無序，不可以包含重復元素。主要實現類為 HashSet 底層數據結構為哈希表。
Map 存儲鍵值對，鍵不能重復，值可以重復。主要實現類為 HashMap 底層數據結構為數組+鏈表/紅黑樹。

2. 有哪些集合是線程不安全的？怎么解決呢？

答：常見的線程不安全的集合類有 ArrayList，LinkedList，HashSet，TreeSet， HashMap，TreeMap等。
解決辦法有：1.使用concurrent包中的并發集合類，如ConcurrentHashMap等。
2.使用Collections類的靜態方法返回線程安全的集合。
3.使用synchroniza關鍵字對需要同步的代碼塊加鎖。

3. 比較 HashSet 、LinkedHashSet 和 TreeSet 三者的異同？

答：相同點是這三個類都實現了Set接口，都提供了集合的基本操作，都是線程不安全的。
HashSet 底層數據結構為哈希表，元素無序。
LinkedHashSet 底層數據結構為鏈表和哈希表，元素按照插入順序排序，先進先出。
TreeSet 底層數據結構為紅黑樹，按照自然排序或者通過Comparator自定義排序。

4. HashMap 和 Hashtable 的區別？HashMap 和 HashSet 區別？ HashMap 和 TreeMap 區別？

答：
HashMap 和 Hashtable ：

• HashMap 線程不安全。可以存儲一個null鍵，和多個null值。初始容量為16，擴容時容量翻倍。
• Hashtable 線程安全，其中的大部分方法使用synchronized關鍵字修飾。不可以存儲null鍵和值。初始容量為11，擴容時容量變為原來的2n+1。

HashMap 和 HashSet：

• HashMap 存儲鍵值對，基于哈希表實現。
• HashSet 僅存儲不重復的元素，基于HashMap實現。

HashMap 和 TreeMap：

• HashMap 基于哈希表實現，不保證順序，操作時間復雜度為O(1)。
• TreeMap 基于紅黑樹實現，按照自然排序或者通過Comparator自定義排序，操作時間復雜度為O(log n)。

5. HashMap 的底層實現？

答：它的底層是基于數組+鏈表、JDK8之后還包括紅黑樹來存儲鍵值對。
在存儲數據時，使用鍵的hashCode方法計算哈希值，通過哈希值確定元素在數組中的位置。HashMap會根據數組的占用情況自動的調整容量，當超過閾值時，會進行擴容，大小為原來的兩倍，并將舊數組的所有元素重新計算哈值后放入新數組。如果該位置為空就直接插入，否則就檢查鏈表或者紅黑樹，如果鏈表中已經存在相同的鍵，就更新對應的值，如果不存在相同的鍵，則插入新節點，JDK8以后當鏈表長度超過閾值8時，就將鏈表轉為紅黑樹。

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

答：HashMap的長度為2的冪次方，主要是為了簡化索引計算、減少哈希沖突和提高性能。通過位運算代替取模運算，可以更高效地計算數組索引，并確保哈希值的均勻分布。

7. ConcurrentHashMap 和 Hashtable 的區別？

答：兩者的區別主要體現在實現線程安全的方式上不同
Hashtable 使用單一鎖機制，使用synchronized關鍵字來實現，適用于低并發場景。
ConcurrentHashMap 采用了一種更復雜的機制，包括CAS操作、分段鎖和sychronized相結合的方式來實現線程安全，提供更高的并發性能。

8. ConcurrentHashMap 線程安全的具體實現方式/底層具體實現？

答：在JDK1.7及之前，采用分段鎖機制，它通過將整個Map分成多個Segment，每個Segment都有自己的鎖，從而允許多線程同時訪問不同的Segment。
在JDK8及以后取消了Segment，采用synchronized和CAS操作直接對哈希表中的節點進行操作，通過更加細粒度的鎖，保證了高效的并發訪問。

參考資料

• JavaGuide
• 牛客網-Java面試寶典