面試題002-Java-Java集合

題目自測

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

題目答案

1. 說說 List,Set,Map 三者的區(qū)別？三者底層的數(shù)據(jù)結(jié)構(gòu)？

答：List 有序、可以包含重復元素。主要實現(xiàn)類為 ArrayList 底層數(shù)據(jù)結(jié)構(gòu)為動態(tài)數(shù)組。
Set 無序，不可以包含重復元素。主要實現(xiàn)類為 HashSet 底層數(shù)據(jù)結(jié)構(gòu)為哈希表。
Map 存儲鍵值對，鍵不能重復，值可以重復。主要實現(xiàn)類為 HashMap 底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組+鏈表/紅黑樹。

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

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

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

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

4. HashMap 和 Hashtable 的區(qū)別？HashMap 和 HashSet 區(qū)別？ HashMap 和 TreeMap 區(qū)別？

答：
HashMap 和 Hashtable ：

• HashMap 線程不安全?？梢源鎯σ粋€null鍵，和多個null值。初始容量為16，擴容時容量翻倍。
• Hashtable 線程安全，其中的大部分方法使用synchronized關(guān)鍵字修飾。不可以存儲null鍵和值。初始容量為11，擴容時容量變?yōu)樵瓉淼?n+1。

HashMap 和 HashSet：

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

HashMap 和 TreeMap：

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

5. HashMap 的底層實現(xiàn)？

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

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

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

7. ConcurrentHashMap 和 Hashtable 的區(qū)別？

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

8. ConcurrentHashMap 線程安全的具體實現(xiàn)方式/底層具體實現(xiàn)？

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

參考資料

• JavaGuide
• 牛客網(wǎng)-Java面試寶典