Java中的List你真的會用嗎？
- 2019 年 10 月 6 日
- 筆記
最近來了一個實習生，小強問他關於java中list的用法，他很快答上來。然後問他arraylist、vector和linkedList的區別，他就有點懵了，其實小強也不能回答的非常完善，於是整理出來和大家一起進階學習。
典型回答
Vector、ArrayList和LinkedList三者都是實現集合框架中的List，也就是所謂有序集合，因此具體功能比較近似，比如都提供按照位置進行定位、添加或刪除的操作，都提供迭代器以遍歷其內容等。但因具體的設計區別，在性能、線程安全等方面，表現有很大不同。
- Vector是java早期提供線程安全的動態數組，如果不需要線程安全，並不建議選擇，畢竟同步有額外的開銷。Vector內部是使用自動增加的容量，當數組已滿時，會創建新的數組，並拷貝原有數組數據。
- ArrayList是應用更加廣泛的動態數組實現方式，它本身不是線程安全的，所以性能要好很多。與Vector近似，ArrayList也是 可以根據需要調整容量，不過兩者的調整邏輯有所區別，Vector在擴容時會提高一倍，而ArrayList則是增加50%
- LinkedList是java提供的雙向鏈表，它不需要上面兩種調整容量，它也不是線程安全的。
補充
- Vector和ArrayList作為動態數組，其內部元素以數組形式順序存儲，所以非常適合隨機訪問的場合。除了尾部插入和刪除元素，比如在中間位置插入一個元素，需要移動後續元素。
- LinkedList進行節點插入、刪除卻高效很多，但是隨機訪問的性能則要比動態數組慢很多。
排序算法
內部排序，至少掌握基礎算法如歸併排序、交換排序（冒泡、快排）、選擇排序、插入排序等。
外部排序，掌握利用內存和外部存儲處理超大數據集，至少要理解過程和思路。
比如哪些是排序是不穩定的呢（快排、堆排），或者思考穩定意味着什麼； 對不同數據集，各種排序的最好或最差情況； 從某個角度如何進一步優化（比如空間佔用，假設業務場景需要最小輔助空間，這個角度堆排序就比歸併優異）等
集合框架
Collection接口是所有集合的根，然後提供3大集合：
- List：提供方便的插入、刪除和訪問操作
- Set：不允許重複元素
- Queue、Deque：支持FIFO或LIFO
set的底層實現都是map，TreeSet 代碼里實際默認是利用 TreeMap 實現的，Java 類庫創建了一個 Dummy 對象「PRESENT」作為 value，然後所有插入的元素其實是以鍵的形式放入了 TreeMap 裏面；同理，HashSet 其實也是以 HashMap 為基礎實現的！
Set
- TreeSet：支持自然順序訪問，但是添加、刪除、包含等操作要相對低效(log(n))時間
- HashSet 則是利用哈希算法，理想情況下，如果哈希散列正常，可以提供常數時間的添加、刪除、包含等操作，但是它不保證有序
- LinkedHashSet，內部構建了一個記錄插入順序的雙向鏈表，因此提供了按照插入順序遍歷的能力，與此同時，也保證了常數時間的添加、刪除、包含等操作，這些操作性能略低於 HashSet，因為需要維護鏈表的開銷
線程安全
以上集合類非線程安全，在Collections工具類中，提供了一系列synchronized方法
static List synchronizedList(List list)
可以用類似方式實現線程安全集合：
List list = Collections.synchronizedList(new ArrayList());
它的實現，基本就是將每個基本方法，比如 get、set、add 之類，都通過 synchronizd 添加基本的同步支持，非常簡單粗暴，但也非常實用。注意這些方法創建的線程安全集合，都符合迭代時 fail-fast 行為，當發生意外的並發修改時，儘早拋出 ConcurrentModificationException 異常，以避免不可預計的行為。
