ArrayList,LinkedList,Vector差別？

title : 每日深耕，勤練不綴之ArrayList,LinkedList,Vector的差別?

ArrayList,LinkedList,Vector的差別?

高效的管理和操作資料

• 三者都是集合架構裡的list，即所謂的有序集合。
• 按照位置進行定位，添加和删除的操作
• 都提供疊代器以周遊其内容

Vector是Java早期的線程安全動态數組，通過我們不斷地積累學習（StringBuffer ,StringBuilder,String）,都會知道線程安全有額外開銷。

Vector内部是使用對象數組來儲存資料，根據需要自動增加容量，當數組已滿時，會建立新的數組，并拷貝原有數組資料

ArrayList是應用更廣泛的動态數組實作，它本身不是線程安全的，性能相對好很多，也可以根據需要調整容量，不過Vector調整一倍，ArrayList增加50%

LinkedList 顧名思義，就是java提供的雙向連結清單，他不需要調整容量，也不是線程安全的

考點分析

面試官會考察不同容器類型适合的場景？

Vector 和ArrayList作為動态數組，其内部元素以數組形式順序存儲的，是以非常适合随機通路，增删的話除非在尾部插入或者删除，其餘性能很慢。

而LinkedList作為雙向連結清單，雖然有順序，但是随機通路性能卻是很差，因為其一個資料節點中不僅得存現有節點的資料資訊，還得存下一節點的位置資訊。

但是增加或删除節點很快，因為不需将其餘元素移位，隻需将其相關聯的位置資訊修改就ok

是以在應用開發中，我們就得提前預估到，應用操作是偏向于通路操作，還是偏向于增删操作，可以有針對性的進行選擇

關于java集合架構？

這方面如果展開問，有四個大問題：

• java集合架構的設計結構，至少要有一個整體印象
• java提供的隻要容器（集合和Map）類型，了解或掌握對應的資料結構，算法，思考具體技術選擇
• 将問題擴充到性能、并發等領域
• 集合架構的演進和發展

1.狹義的集合架構

大家可以看到cellection是集合的根，然後展開提供了三大類集合：

• List ，也就是咱們今天學的有序集合，它提供了友善的通路，插入，删除等操作
• set ，set是不允許重複元素且無序的，這是和List最明顯的差別，我們日常開發中很多需要保證元素唯一性的場合都可以用set。在這裡說一下，很多set的實作完全依賴于Map的實作，也就是相當于HashMap的馬甲

• Queue/Deque,則是java提供的标準隊列結構的實作。除了集合的基本功能，它還支援先進先出，後進先出等行為。

  除了前面提到的，我們還是以現實為例，了解基本特征和典型使用場景

• TreeSet支援自然順序通路，但是添加、删除、包含等操作相對低效（log(n)時間）
• HashSet則是利用雜湊演算法，如果哈希散列正常，可以提供常數時間級别的添加、删除、包含等操作，但它不保證有序。
• LinkedHashSet,内部建構了一個記錄插入順序的雙向連結清單，是以提供了按照插入順序周遊的能力，與此同時，也保證了常數時間的添加、删除、包含等操作，這些操作略低于HashSet，需要維護連結清單的開銷。
• 在周遊元素時，HashSet性能受自身容量影響，是以初始化時，不要把初始容量設定太大。而LinkedHashSet周遊性能隻和元素多少有關

2.典型排序算法：内部排序（歸并排序，交換排序（冒泡，快排），選擇排序，插入排序）

外部排序：掌握利用記憶體和外部存儲處理超大資料集，至少要了解過程和思路

考察算法不一定如何簡單，比如：哪些算法是不穩定的（快排，堆排），思考穩定意味着什麼？

對不同資料集，各種排序的最好和最差情況？

從某個角度進一步優化（比如空間占用，假設業務場景需要最小輔助空間，這個角度堆排序就比歸并排序優異）

我們今天介紹的都不是線程安全的，對于java.util.concurrent裡面的線程安全容器，後面會介紹

并不代表這些集合不能支援并發程式設計的場景，在Collections工具類裡，提供了一系列synchronized方法

我們完全可以利用類似方法實作基本的線程安全集合：

它的實作，基本上就是将每個基本方法，比如

get,set,add之類，都通過synchronized添加基本的同步支援。

注意：這些方法建立的線程安全集合，都符合疊代時fail-fast行為，當發生意外的并發修改時，盡早抛出ConcurrentModificationException異常，以避免不可預計的損失

Java集合預設的排序算法是什麼？具體呢？能否解釋一下排序方式和設計思路？

其實說出這句話的面試官都是大佬！！！

他想讓你解釋一下多種情況

因為你需要區分是Arrays.sort()還是Collections.sort()

(底層是調用Array.sort());具體什麼資料類型；多大的資料集？（太小的資料集，複雜排序是沒必要的，Java會直接進行二分插入排序）

• 對于原始資料類型，目前使用的雙軸快速排序，是一種改進快速排序
• 對于對象資料類型，目前使用TimSort，思想上也是一種歸并和二分插入排序結合的優化排序算法
• 另外 java8直接引入了并行排序算法（parallelSort），為了充分利用現代多核處理器的計算能力，底層實作fork-join架構，當處理的資料集比較小的時候，差距不明顯。但是，當資料增長到數萬到百萬以上，提升就是一個量級
• 在 java9中，java标準類庫提供一系列靜态工廠方法，比如 list.of(),set.of(),大大簡化了建構曉得容器執行個體的代碼量，采用新的容器靜态工廠方法

并且保證了不可變性

讨論一個問題？

今天你需要實作一個雲計算任務排程系統，希望可以保證VIP客戶的任務被優先處理，你可以利用那些資料結構或者标準的集合類型？

我首先會使用ArrayList來存儲對象的姓名（自動開辟新記憶體），而後采用

HashMap來對接對象的任務及處理資料（可以接受NULL值），接下來如果他是VIP，我會考慮到優先級隊列，還要額外考慮一下vip再分級，即同等級vip的平權問題，即優先級規則問題，還得考慮同等級多個客戶互相不被單一客戶大量任務阻塞的問題，排程資料放入redis裡面