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

正經(jīng)回答：

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

Vector:

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

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

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

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

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

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

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

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

深入追問：

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

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

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

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

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

• 重復(fù)對象

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

• null元素

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

• 容器是否有序

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

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

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

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

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

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

• 遍歷方式

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

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

Set：

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

List：

和數(shù)組類似，List可以動態(tài)增長，查找元素效率高，插入刪除元素效率低，因?yàn)闀鹌渌匚恢酶淖?/p>

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

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

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

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

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

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

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

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

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

正經(jīng)回答：

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

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

總結(jié)

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

最新評論