我們在日常的工作中,能夠高效地管理和操作數據是非常重要的。由于每個編程語言支持的數據結構不盡相同,比如我最早學習的 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 客戶的任務被優先處理,你可以利用哪些數據結構或者標準的集合類型呢?更進一步講,類似場景大多是基于什么數據結構呢?
- 前言
- 開篇詞
- 開篇詞 -以面試題為切入點,有效提升你的Java內功
- 模塊一 Java基礎
- 第1講 談談你對Java平臺的理解?
- 第2講 Exception和Error有什么區別?
- 第3講 談談final、finally、 finalize有什么不同?
- 第4講 強引用、軟引用、弱引用、幻象引用有什么區別?
- 第5講 String、StringBuffer、StringBuilder有什么區別?
- 第6講 動態代理是基于什么原理?
- 第7講 int和Integer有什么區別?
- 第8講 對比Vector、ArrayList、LinkedList有何區別?
- 第9講 對比Hashtable、HashMap、TreeMap有什么不同?
- 第10講 如何保證集合是線程安全的? ConcurrentHashMap如何實現高效地線程安全?
- 第11講 Java提供了哪些IO方式? NIO如何實現多路復用?
- 第12講 Java有幾種文件拷貝方式?哪一種最高效?
- 第13講 談談接口和抽象類有什么區別?
- 第14講 談談你知道的設計模式?
- 模塊二 Java進階
- 第15講 synchronized和ReentrantLock有什么區別呢?
- 第16講 synchronized底層如何實現?什么是鎖的升級、降級?
- 第17講 一個線程兩次調用start()方法會出現什么情況?
- 第18講 什么情況下Java程序會產生死鎖?如何定位、修復?
- 第19講 Java并發包提供了哪些并發工具類?
- 第20講 并發包中的ConcurrentLinkedQueue和LinkedBlockingQueue有什么區別?
- 第21講 Java并發類庫提供的線程池有哪幾種? 分別有什么特點?
- 第22講 AtomicInteger底層實現原理是什么?如何在自己的產品代碼中應用CAS操作?
- 第23講 請介紹類加載過程,什么是雙親委派模型?
- 第24講 有哪些方法可以在運行時動態生成一個Java類?
- 第25講 談談JVM內存區域的劃分,哪些區域可能發生OutOfMemoryError?
- 第26講 如何監控和診斷JVM堆內和堆外內存使用?
- 第27講 Java常見的垃圾收集器有哪些?
- 第28講 談談你的GC調優思路?
- 第29講 Java內存模型中的happen-before是什么?
- 第30講 Java程序運行在Docker等容器環境有哪些新問題?
- 模塊三 Java安全基礎
- 第31講 你了解Java應用開發中的注入攻擊嗎?
- 第32講 如何寫出安全的Java代碼?
- 模塊四 Java性能基礎
- 第33講 后臺服務出現明顯“變慢”,談談你的診斷思路?
- 第34講 有人說“Lambda能讓Java程序慢30倍”,你怎么看?
- 第35講 JVM優化Java代碼時都做了什么?
- 模塊五 Java應用開發擴展
- 第36講 談談MySQL支持的事務隔離級別,以及悲觀鎖和樂觀鎖的原理和應用場景?
- 第37講 談談Spring Bean的生命周期和作用域?
- 第38講 對比Java標準NIO類庫,你知道Netty是如何實現更高性能的嗎?
- 第39講 談談常用的分布式ID的設計方案?Snowflake是否受冬令時切換影響?
- 周末福利
- 周末福利 談談我對Java學習和面試的看法
- 周末福利 一份Java工程師必讀書單
- 結束語
- 結束語 技術沒有終點
- 結課測試 Java核心技術的這些知識,你真的掌握了嗎?