Java集合精選常見面試題( 二 ) _生活百科

Map 接口下的集合，需要排序時選擇 TreeMap，不需要排序時就選擇 HashMap，需要保證線程安全就選用 ConcurrentHashMap 。
當我們只需要存放元素值時，就選擇實現Collection 接口的集合，需要保證元素唯一時選擇實現 Set 接口的集合比如 TreeSet 或 HashSet ，不需要就選擇實現 List 接口的比如 ArrayList 或 LinkedList，然后再根據實現這些接口的集合的特點來選用。
5. 兩個對象的 hashCode相同，則 equals() 也一定為 true，對嗎不一定，元素調用hashCode()方法，計算出元素的哈希值，此哈希值接著通過某種散列函數計算出在HashSet底層數組中的存放位置（即索引位置)，并不能判斷兩個對象是否相同
Collection 子接口之 List1. Arraylist 和 Vector 的區別?

ArrayList 是 List 的主要實現類，底層使用 Object[ ]存儲，適用于頻繁的查找工作，線程不安全；
Vector 是 List 的古老實現類，底層使用Object[ ] 存儲，線程安全的。

2. Arraylist 與 LinkedList 區別?要求

能夠說清楚 LinkedList 對比 ArrayList 的區別，并重視糾正部分錯誤的認知

是否保證線程安全： ArrayList 和 LinkedList 都不保證線程安全；
底層數據結構： Arraylist 底層使用的是 Object 數組；LinkedList 底層使用的是雙向鏈表數據結構（JDK1.6 之前為循環鏈表，JDK1.7 取消了循環。注意雙向鏈表和雙向循環鏈表的區別，下面有介紹到?。?/li>
插入和刪除是否受元素位置的影響：
- ArrayList 采用數組存儲，所以插入和刪除元素的時間復雜度受元素位置的影響。比如：執行add(E e)方法的時候，ArrayList 會默認在將指定的元素追加到此列表的末尾，這種情況時間復雜度就是 O(1) 。但是如果要在指定位置 i 插入和刪除元素的話（add(int index，E element)）時間復雜度就為 O(n-i) 。因為在進行上述操作的時候集合中第 i 和第 i 個元素之后的(n-i)個元素都要執行向后位/向前移一位的操作。
- LinkedList 采用鏈表存儲，所以，如果是在頭尾插入或者刪除元素不受元素位置的影響（add(E e)、addFirst(E e)、addLast(E e)、removeFirst() 、 removeLast()），近似 O(1)，如果是要在指定位置 i 插入和刪除元素的話（add(int index，E element)，remove(Object o)）時間復雜度近似為 O(n)，因為需要先移動到指定位置再插入。
是否支持快速隨機訪問： LinkedList 不支持高效的隨機元素訪問，而 ArrayList 支持 ?？焖匐S機訪問就是通過元素的序號快速獲取元素對象(對應于get(int index)方法) 。
內存空間占用： ArrayList 的空間浪費主要體現在 list 列表的結尾會預留一定的容量空間，而 LinkedList 的空間花費則體現在它的每一個元素都需要消耗比 ArrayList 更多的空間（因為要存放直接后繼和直接前驅以及數據）

LinkedList

基于雙向鏈表，無需連續內存
隨機訪問慢（要沿著鏈表遍歷）
頭尾插入刪除性能高，中間元素慢
占用內存多

ArrayList

基于數組，需要連續內存
隨機訪問快（指根據下標訪問）
尾部插入、刪除性能可以，其它部分插入、刪除都會移動數據，因此性能會低
可以利用 cpu 緩存，局部性原理

補充內容:雙向鏈表和雙向循環鏈表雙向鏈表：包含兩個指針，一個 prev 指向前一個節點，一個 next 指向后一個節點。

另外推薦一篇把雙向鏈表講清楚的文章：https://juejin.cn/post/6844903648154271757(opens new window)

文章插圖
雙向循環鏈表：最后一個節點的 next 指向 head，而 head 的 prev 指向最后一個節點，構成一個環

文章插圖
補充內容:RandomAccess 接口public interface RandomAccess {}查看源碼我們發現實際上 RandomAccess 接口中什么都沒有定義。所以，在我看來 RandomAccess 接口不過是一個標識罷了。標識什么？標識實現這個接口的類具有隨機訪問功能。