面試題1：對比 Vector、ArrayList、LinkedList 有何區(qū)別？適合在什么場景下使用

正經回答：

這三者都是實現(xiàn)了集合框架中的 List，也就是有序集合，因此具體功能也比較近似，比如都提供按照位置進行定位、添加或者刪除的操作，都提供迭代器以遍歷其內容等。但因為具體的設計區(qū)別，在行為、性能、線程安全等方面，表現(xiàn)又有很大不同。

Vector:

是 Java 早期提供的線程安全的動態(tài)數組，如果不需要線程安全，并不建議選擇，畢竟同步是有額外開銷的。

Vector 內部是使用對象數組來保存數據，可以根據需要自動的增加容量。當數組已滿，開始擴容時，會先創(chuàng)建新的擴容后數組，并拷貝原有數組數據，最后刪除原數組。

ArrayList（擅長 "查詢" 和 "更新" 場景）:

是應用更加廣泛的動態(tài)數組實現(xiàn)，它本身不是線程安全的，所以性能要好很多。與 Vector 近似，ArrayList 也是可以根據需要調整容量，不過兩者的調整邏輯有所區(qū)別，Vector 在擴容時會提高 1 倍，而 ArrayList 則是增加 50%。

• 數據結構:ArrayList 是動態(tài)數組的數據結構實現(xiàn)；
• 隨機查詢效率：（優(yōu)勢），ArrayList 比 LinkedList 在隨機訪問的時候效率要高，因為 LinkedList 是線性的數據存儲方式，所以需要移動指針從前往后依次查找，而ArrayList根據角標index直接鎖定位置。
• 插入和刪除效率：在List中間插入和刪除數據時，ArrayList 要比 LinkedList 效率低很多，因為 ArrayList 增刪操作要影響數組內的其他數據的下標（整體移動），而如果是正常的末尾追加方式，效率大體相同。
• 內存空間占用：LinkedList 比 ArrayList 更占內存，因為 LinkedList 的節(jié)點除了存儲數據，還存儲了兩個引用，一個指向前一個元素，一個指向后一個元素。

LinkedList（擅長 "插入" 和 "刪除" 場景）:

顧名思義是 Java 提供的雙向鏈表，所以它不需要像上面兩種那樣調整容量，它也不是線程安全的。

• 數據結構:LinkedList 是雙向鏈表的數據結構實現(xiàn)。
• 隨機查詢效率：相比ArrayList （劣勢）
• 插入和刪除效率：LinkedList按序號查詢數據時需要進行前向或后向遍歷，但插入數據時只需要記錄當前項的前后項即可，增刪時也只需修改鏈表指向即可，所以 LinkedList 插入和刪除速度較快。（優(yōu)勢）
• 內存空間占用：相比ArrayList （劣勢）

深入追問：

追問1：多線程場景下就不能使用ArrayList么？

我們知道ArrayList 不是線程安全的，如果遇到多線程場景，可以通過 Collections 的 synchronizedList 方法將其轉換成線程安全的容器后再使用。例如像下面這樣：

List<String> syncList = Collections.synchronizedList(arraylist);

面試題2：List 和 Set 有哪些區(qū)別？ 正經回答：

List、Set 都是繼承自Collection 接口，區(qū)別主要有以下幾點：

• 重復對象

list方法可以允許重復的對象，而set方法不允許重復對象；

• null元素

list可以插入多個null元素，而set只允許插入一個null元素；

• 容器是否有序

list是一個有序的容器，保持了每個元素的插入順序。即輸出順序就是輸入順序，而set方法是無序容器，無法保證每個元素的存儲順序，TreeSet通過 Comparator 或者 Comparable 維護了一個排序順序

• 常用的實現(xiàn)類

list方法常用的實現(xiàn)類有：

ArrayList、LinkedList 和 Vector。ArrayList最常用，提供使用索引（index）訪問，定位、查詢效率高；而LinkedList 則對于經常需要從 List 中添加或刪除元素的場合更為合適，Vector 表示底層數組，線程安全，效率低被邊緣化~

Set方法中常用的實現(xiàn)類有:

HashSet、LinkedHashSet 以及 TreeSet。最常用的是基于 HashMap 實現(xiàn)的 HashSet；另外TreeSet 還實現(xiàn)了 SortedSet 接口（支持排序），因此 TreeSet 是一個可根據 compare() 和compareTo()方法進行排序的有序容器。

• 遍歷方式

List 支持for循環(huán)，也就是通過下標來遍歷，也可以用迭代器（Iterator），但是set只能用迭代，因為他無序，無法用下標來取得想要的值。

深入追問： 追問1：Set 和 List 效率上對比怎么樣呢？

Set：

刪除和插入效率高，插入和刪除不會引起元素位置改變。檢索元素的話，效率低下；當然，在理想情況下，不考慮哈希沖突的情況，且僅需一次定位即可完成，時間復雜度為O(1)，但是不現(xiàn)實。

List：

和數組類似，List可以動態(tài)增長，查找元素效率高，插入刪除元素效率低，因為會引起其他元素位置改變

曾測試過1000萬元素情況下，Set查詢第9999999個元素用時0.203秒，List查詢第9999999個元素用時0.01秒；

追問2：說一下 HashSet 的實現(xiàn)原理？

HashSet 底層是基于 HashMap 實現(xiàn)的，能夠繼承 HashMap 的所有特性，因此 HashSet 結構也是數組+鏈表+紅黑樹，同樣也不能使用get方法，HashSet 的操作，基本上都是直接調用底層 HashMap 的相關方法來完成，不允許key重復，但支持null對象作為key。

追問3：HashSet是如何保證Key不重復的？

HashSet 的值是不能重復的，在業(yè)務上經常被用來做數據去重的工作，那么，他是怎么保證元素不重復的呢？

當我們對一個HashSet 的實例添加一個值時，使用到的是它的 add 方法，源碼如下：

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

由代碼中的 add 方法實現(xiàn)可知，其維護了一個 HashMap 來實現(xiàn)元素的添加；我們知道，HashMap 作為雙列集合，它的鍵是不能夠重復的，HashMap 針對 hashCode 相同且 equals 比較值相同的時候執(zhí)行的是更新操作，所以Hashmap中的key是唯一的，也決定了hashset元素值也是唯一的。

面試題3：Array 和 ArrayList 有何區(qū)別？

正經回答：

• Array 可以存儲基本數據類型和對象，ArrayList 只能存儲對象。
• Array 是指定固定大小的，而 ArrayList 大小是自動擴展的。
• Array 內置方法沒有 ArrayList 多，比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。

Array 和 ArrayList可以互相轉換，Array 轉 List有： Arrays.asList(array)；而List 轉 Array有：List.toArray()方法。

總結

本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關注腳本之家的更多內容！

最新評論