我們在日常的工作中，能夠高效地管理和操作數據是非常重要的。由于每個編程語言支持的數據結構不盡相同，比如我最早學習的 C 語言，需要自己實現很多基礎數據結構，管理和操作會比較麻煩。相比之下，Java 則要方便的多，針對通用場景的需求，Java 提供了強大的集合框架，大大提高了開發者的生產力。 今天我要問你的是有關集合框架方面的問題，對比 Vector、ArrayList、LinkedList 有何區別？ ## 典型回答 這三者都是實現集合框架中的 List，也就是所謂的有序集合，因此具體功能也比較近似，比如都提供按照位置進行定位、添加或者刪除的操作，都提供迭代器以遍歷其內容等。但因為具體的設計區別，在行為、性能、線程安全等方面，表現又有很大不同。 Vector 是 Java 早期提供的**線程安全的動態數組**，如果不需要線程安全，并不建議選擇，畢竟同步是有額外開銷的。Vector 內部是使用對象數組來保存數據，可以根據需要自動的增加容量，當數組已滿時，會創建新的數組，并拷貝原有數組數據。 ArrayList 是應用更加廣泛的**動態數組**實現，它本身不是線程安全的，所以性能要好很多。與 Vector 近似，ArrayList 也是可以根據需要調整容量，不過兩者的調整邏輯有所區別，Vector 在擴容時會提高 1 倍，而 ArrayList 則是增加 50%。 LinkedList 顧名思義是 Java 提供的**雙向鏈表**，所以它不需要像上面兩種那樣調整容量，它也不是線程安全的。 ## 考點分析 似乎從我接觸 Java 開始，這個問題就一直是經典的面試題，前面我的回答覆蓋了三者的一些基本的設計和實現。 一般來說，也可以補充一下不同容器類型適合的場景 * Vector 和 ArrayList 作為動態數組，其內部元素以數組形式順序存儲的，所以非常適合隨機訪問的場合。除了尾部插入和刪除元素，往往性能會相對較差，比如我們在中間位置插入一個元素，需要移動后續所有元素。 * 而 LinkedList 進行節點插入、刪除卻要高效得多，但是隨機訪問性能則要比動態數組慢。 所以，在應用開發中，如果事先可以估計到，應用操作是偏向于插入、刪除，還是隨機訪問較多，就可以針對性的進行選擇。這也是面試最常見的一個考察角度，給定一個場景，選擇適合的數據結構，所以對于這種典型選擇一定要掌握清楚。 考察 Java 集合框架，我覺得有很多方面需要掌握： * Java 集合框架的設計結構，至少要有一個整體印象。 * Java 提供的主要容器（集合和 Map）類型，了解或掌握對應的**數據結構、算法**，思考具體技術選擇。 * 將問題擴展到性能、并發等領域。 * 集合框架的演進與發展。 作為 Java 專欄，我會在盡量圍繞 Java 相關進行擴展，否則光是羅列集合部分涉及的數據結構就要占用很大篇幅。這并不代表那些不重要，數據結構和算法是基本功，往往也是必考的點，有些公司甚至以考察這些方面而非常知名（甚至是“臭名昭著”）。我這里以需要掌握典型排序算法為例，你至少需要熟知： * 內部排序，至少掌握基礎算法如歸并排序、交換排序（冒泡、快排）、選擇排序、插入排序等。 * 外部排序，掌握利用內存和外部存儲處理超大數據集，至少要理解過程和思路。 考察算法不僅僅是如何簡單實現，面試官往往會刨根問底，比如哪些是排序是不穩定的呢（快排、堆排），或者思考穩定意味著什么；對不同數據集，各種排序的最好或最差情況；從某個角度如何進一步優化（比如空間占用，假設業務場景需要最小輔助空間，這個角度堆排序就比歸并優異）等，從簡單的了解，到進一步的思考，面試官通常還會觀察面試者處理問題和溝通時的思路。 以上只是一個方面的例子，建議學習相關書籍，如《算法導論》《編程珠璣》等，或相關[教程](https://www.coursera.org/learn/algorithms-part1)。對于特定領域，比如推薦系統，建議咨詢領域專家。單純從面試的角度，很多朋友推薦使用一些算法網站如 LeetCode 等，幫助復習和準備面試，但坦白說我并沒有刷過這些算法題，這也是仁者見仁智者見智的事情，招聘時我更傾向于考察面試者自身最擅長的東西，免得招到純面試高手。 ## 知識擴展 我們先一起來理解集合框架的整體設計，為了有個直觀的印象，我畫了一個簡要的類圖。注意，為了避免混淆，我這里沒有把 java.util.concurrent 下面的線程安全容器添加進來；也沒有列出 Map 容器，雖然通常概念上我們也會把 Map 作為集合框架的一部分，但是它本身并不是真正的集合（Collection）。 所以，我今天主要圍繞狹義的集合框架，其他都會在專欄后面的內容進行講解。  我們可以看到 Java 的集合框架，Collection 接口是所有集合的根，然后擴展開提供了三大類集合，分別是： * List，也就是我們前面介紹最多的有序集合，它提供了方便的訪問、插入、刪除等操作。 * Set，Set 是不允許重復元素的，這是和 List 最明顯的區別，也就是不存在兩個對象 equals 返回 true。我們在日常開發中有很多需要保證元素唯一性的場合。 * Queue/Deque，則是 Java 提供的標準隊列結構的實現，除了集合的基本功能，它還支持類似先入先出（FIFO， First-in-First-Out）或者后入先出（LIFO，Last-In-First-Out）等特定行為。這里不包括 BlockingQueue，因為通常是并發編程場合，所以被放置在并發包里。 每種集合的通用邏輯，都被抽象到相應的抽象類之中，比如 AbstractList 就集中了各種 List 操作的通用部分。這些集合不是完全孤立的，比如，LinkedList 本身，既是 List，也是 Deque 哦。 如果閱讀過更多[源碼](http://hg.openjdk.java.net/jdk/jdk/file/bf9177eac58d/src/java.base/share/classes/java/util/TreeSet.java)，你會發現，其實，TreeSet 代碼里實際默認是利用 TreeMap 實現的，Java 類庫創建了一個 Dummy 對象“PRESENT”作為 value，然后所有插入的元素其實是以鍵的形式放入了 TreeMap 里面；同理，HashSet 其實也是以 HashMap 為基礎實現的，原來他們只是 Map 類的馬甲！ 就像前面提到過的，我們需要對各種具體集合實現，至少了解基本特征和典型使用場景，以 Set 的幾個實現為例： * TreeSet 支持自然順序訪問，但是添加、刪除、包含等操作要相對低效（log(n) 時間）。 * HashSet 則是利用哈希算法，理想情況下，如果哈希散列正常，可以提供常數時間的添加、刪除、包含等操作，但是它不保證有序。 * LinkedHashSet，內部構建了一個記錄插入順序的雙向鏈表，因此提供了按照插入順序遍歷的能力，與此同時，也保證了常數時間的添加、刪除、包含等操作，這些操作性能略低于 HashSet，因為需要維護鏈表的開銷。 * 在遍歷元素時，HashSet 性能受自身容量影響，所以初始化時，除非有必要，不然不要將其背后的 HashMap 容量設置過大。而對于 LinkedHashSet，由于其內部鏈表提供的方便，遍歷性能只和元素多少有關系。 我今天介紹的這些集合類，都不是線程安全的，對于 java.util.concurrent 里面的線程安全容器，我在專欄后面會去介紹。但是，并不代表這些集合完全不能支持并發編程的場景，在 Collections 工具類中，提供了一系列的 synchronized 方法，比如 ~~~ static <T> List<T> synchronizedList(List<T> list) ~~~ 我們完全可以利用類似方法來實現基本的線程安全集合： ~~~ List list = Collections.synchronizedList(new ArrayList()); ~~~ 它的實現，基本就是將每個基本方法，比如 get、set、add 之類，都通過 synchronizd 添加基本的同步支持，非常簡單粗暴，但也非常實用。注意這些方法創建的線程安全集合，都符合迭代時 fail-fast 行為，當發生意外的并發修改時，盡早拋出 ConcurrentModificationException 異常，以避免不可預計的行為。 另外一個經常會被考察到的問題，就是理解 Java 提供的默認排序算法，具體是什么排序方式以及設計思路等。 這個問題本身就是有點陷阱的意味，因為需要區分是 Arrays.sort() 還是 Collections.sort() （底層是調用 Arrays.sort()）；什么數據類型；多大的數據集（太小的數據集，復雜排序是沒必要的，Java 會直接進行二分插入排序）等。 * 對于原始數據類型，目前使用的是所謂雙軸快速排序（Dual-Pivot QuickSort），是一種改進的快速排序算法，早期版本是相對傳統的快速排序，你可以閱讀[源碼](http://hg.openjdk.java.net/jdk/jdk/file/26ac622a4cab/src/java.base/share/classes/java/util/DualPivotQuicksort.java)。 * 而對于對象數據類型，目前則是使用[TimSort](http://hg.openjdk.java.net/jdk/jdk/file/26ac622a4cab/src/java.base/share/classes/java/util/TimSort.java)，思想上也是一種歸并和二分插入排序（binarySort）結合的優化排序算法。TimSort 并不是 Java 的獨創，簡單說它的思路是查找數據集中已經排好序的分區（這里叫 run），然后合并這些分區來達到排序的目的。 另外，Java 8 引入了并行排序算法（直接使用 parallelSort 方法），這是為了充分利用現代多核處理器的計算能力，底層實現基于 fork-join 框架（專欄后面會對 fork-join 進行相對詳細的介紹），當處理的數據集比較小的時候，差距不明顯，甚至還表現差一點；但是，當數據集增長到數萬或百萬以上時，提高就非常大了，具體還是取決于處理器和系統環境。 排序算法仍然在不斷改進，最近雙軸快速排序實現的作者提交了一個更進一步的改進，歷時多年的研究，目前正在審核和驗證階段。根據作者的性能測試對比，相比于基于歸并排序的實現，新改進可以提高隨機數據排序速度提高 10%～20%，甚至在其他特征的數據集上也有幾倍的提高，有興趣的話你可以參考具體代碼和介紹： [http://mail.openjdk.java.net/pipermail/core-libs-dev/2018-January/051000.html](http://mail.openjdk.java.net/pipermail/core-libs-dev/2018-January/051000.html)。 在 Java 8 之中，Java 平臺支持了 Lambda 和 Stream，相應的 Java 集合框架也進行了大范圍的增強，以支持類似為集合創建相應 stream 或者 parallelStream 的方法實現，我們可以非常方便的實現函數式代碼。 閱讀 Java 源代碼，你會發現，這些 API 的設計和實現比較獨特，它們并不是實現在抽象類里面，而是以**默認方法**的形式實現在 Collection 這樣的接口里！這是 Java 8 在語言層面的新特性，允許接口實現默認方法，理論上來說，我們原來實現在類似 Collections 這種工具類中的方法，大多可以轉換到相應的接口上。針對這一點，我在面向對象主題，會專門梳理 Java 語言面向對象基本機制的演進。 在 Java 9 中，Java 標準類庫提供了一系列的靜態工廠方法，比如，List.of()、Set.of()，大大簡化了構建小的容器實例的代碼量。根據業界實踐經驗，我們發現相當一部分集合實例都是容量非常有限的，而且在生命周期中并不會進行修改。但是，在原有的 Java 類庫中，我們可能不得不寫成： ~~~ ArrayList<String> list = new ArrayList<>();list.add("Hello");list.add("World"); ~~~ 而利用新的容器靜態工廠方法，一句代碼就夠了，并且保證了不可變性。 ~~~ List<String> simpleList = List.of("Hello","world"); ~~~ 更進一步，通過各種 of 靜態工廠方法創建的實例，還應用了一些我們所謂的最佳實踐，比如，它是不可變的，符合我們對線程安全的需求；它因為不需要考慮擴容，所以空間上更加緊湊等。 如果我們去看 of 方法的源碼，你還會發現一個特別有意思的地方：我們知道 Java 已經支持所謂的可變參數（varargs），但是官方類庫還是提供了一系列特定參數長度的方法，看起來似乎非常不優雅，為什么呢？這其實是為了最優的性能，JVM 在處理變長參數的時候會有明顯的額外開銷，如果你需要實現性能敏感的 API，也可以進行參考。 今天我從 Verctor、ArrayList、LinkedList 開始，逐步分析其設計實現區別、適合的應用場景等，并進一步對集合框架進行了簡單的歸納，介紹了集合框架從基礎算法到 API 設計實現的各種改進，希望能對你的日常開發和 API 設計能夠有幫助。 ## 一課一練 關于今天我們討論的題目你做到心中有數了嗎？留一道思考題給你，先思考一個應用場景，比如你需要實現一個云計算任務調度系統，希望可以保證 VIP 客戶的任務被優先處理，你可以利用哪些數據結構或者標準的集合類型呢？更進一步講，類似場景大多是基于什么數據結構呢？