Java集合源碼分析之開篇

初衷

Java集合是我們使用最頻繁的工具，也是面試的熱點，但我們對它的了解僅限于使用上，而且大多數情況沒有考慮過其使用規範。本系列文章将跟随源碼的思路，分析實作的每個細節，以期在使用時避免各種不規範的坑。在這裡，我們會驚豔于開發者優秀的設計，也會感激先輩們付出的艱辛努力，更重要的是知其是以然，少犯錯誤，寫出優秀的代碼。

許多人對集合類的了解是暴力的，當需要儲存對象時就使用

ArrayList

，當需要儲存鍵值對時就使用

HashMap

，當需要不可重複時就使用

HashSet

，等等。而且使用方式也比較單一：

List<String> list = new ArrayList<>();

Map<String, String> map = new HashMap<>();

Set<String> set = new HashSet<>();

// ...
           

這裡我們先不考慮多線程安全問題，這個問題通常有專門的類實作，或者可以通過

Collections.synchronizedXXX

方法解決。除此之外，我們真的可以如此簡單的使用集合嗎？

假如資料隻有幾百、幾千個，那麼使用何種方式實作差别并不大。但當我們需要處理大數量級的資料時，采用不同的方式效率可能相差百倍甚至更多，這種情況下性能将變得格外重要。例如分别存儲于

ArrayList

和

LinkedList

的100萬條資料，要擷取位于位置 i 的元素，前者可以瞬間完成，後者則可能需要數秒。這時，使用哪個集合類，怎樣合理使用就是我們必須掌握的技能了。

為什麼要讀本系列文章

如果你也像以上這般使用集合，或者不知道如何優化集合的使用，你都應該讀本系列文章。如果你僅有一些點不清晰，也可以在這裡找到答案。或者你隻是不想閱讀枯燥的源碼，卻對原理很好奇，你也可以閱讀本系列文章。如果你隻是想應付面試，我想當你堅持把這些文章讀完後，你會覺得面試好像也不那麼重要了。

本系列文章立足于深刻了解Java集合的原理與實作，讀完這些文章後你将獲得以下知識：

• 大量的資料結構知識。
• ArrayList有那麼多構造函數，使用不同的構造函數會有差別嗎？
• ArrayList是如何擴容的？
• LinkedList如何提供通過位置擷取資料的功能的，它的查詢效率真的非常低嗎？
• 用數組可以實作隊列嗎？
• 影響HashMap性能的因素有哪些？
• 複雜的紅黑樹是如何實作的？
• LRUCache的底層原理是什麼？
• ……

基礎知識概述

對資料的操作，大抵就是增、删、改、查，以及在某些時候根據位置擷取資料，有時可能還需要進行排序。改和查又可以了解為一緻的操作，因為要修改一條資料需要先找到它，然後替換即可。接下來我們就從增、删、查這三點簡要分析下目前使用比較廣泛的幾種資料結構。

數組

數組在記憶體中占據一段連續的記憶體，所有的資料在記憶體中連續排列。它的大小是固定的，這一特性使得數組對于插入操作并不友好，我們分析

ArrayList

時就會看到這種操作的複雜。但數組對于位置的通路是極其友好的，它支援所謂

RandomAccess

特性，這使得基于位置的操作可以迅速完成，其時間複雜度為O(1)。數組的資料順序與插入順序一緻，是以查詢操作需要周遊，其時間複雜度為O(n)。

是以數組最大的優勢在于基于位置的通路，在擴充性方面表現無力。

連結清單

不同于數組，連結清單是通過指針域來表示資料與資料之間的位置關系的，是以連結清單在頭部或尾部插入資料的複雜度僅為O(1)。連結清單不具備

RandomAccess

特性，是以無法提供基于位置的通路。其查詢操作也必須從從到尾周遊，複雜度為O(n)。

是以連結清單最大的優勢在于插入，而查詢的表現很一般。

那有沒有一種結構能夠結合數組和連結清單的優點，使得查詢和插入都具有優秀的表現呢？答案是肯定的，這就是散清單。

散清單

散清單就是Hash Table，這種結構使用

key-value

形式存儲資料，我們經常使用的

HashMap

、

HashTable

就基于它。

數組和連結清單在查詢時表現一般的原因在于它們并不記得資料的位置，是以隻能用待查詢的資料和存儲的資料依次比對。散清單使用一種巧妙的方式來減少甚至避免這種依次比對，它的原理是通過一個函數把任何的key轉為int，每次查找時隻需要執行一次這個函數便可以迅速定位。這個過程是不是像查字典呢？

散清單并不像上述那般完美，因為并不會有一個函數，能夠保證所有的key轉換結果都不同，也就是會發生所謂的

哈希碰撞

，而且它必須依賴于其他的資料結構，這部分知識會在後續文章中詳細介紹。

良好設計的散清單可以使增、删、查等操作的時間複雜度均為O(1)。

二叉排序樹

二叉排序樹是解決查詢問題的另一方案，如果資料在插入時是有序的，在查詢時就可以使用二分法。二分法的原理很簡單，比如猜一個在0-100之間的數，第一次猜50就可以直接排除一半的資料，每次按照這個規則就可以很快的擷取正确答案。二分法的時間複雜度為O(lg n)。

樹的結構對二分法有天然的支援（但這不是樹最重要的用途）。二叉排序樹犧牲了一部分插入的時間，但提高了查詢的速度，同時有序的資料也可以做些其他的操作。如果查詢的操作重要性超過了插入，我們應該考慮這種結構。二叉排序樹也存在一些不平衡導緻效率下降的問題，是以有了AVL樹、紅黑樹，以及用于資料庫索引的B樹、B+樹等概念，關于二叉排序樹的知識也會在後續文章中介紹。

分析過程

以上介紹的資料結構的知識是我們了解Java集合類的基礎，掌握這些核心原理，我們分析集合類源碼時才不會吃力，我們會先對這些資料結構進行簡要介紹，其他和本系列文章無關的概念不會涉及，大家可以查閱相關專業書籍進行系統學習。

由于集合類的源碼十分龐大，從接口抽象設計到具體實作涉及到數十個類，我們不可能每行代碼都進行分析，一些在前面分析過的點在後續部分也會略過，但對于我們應該注意的點都會詳細解讀。有一些過于複雜的代碼，還會用圖示進行直覺的示範，以幫助了解整個運作機制。

文章中會不可避免地粘貼大量源碼，但所有部分都會加上詳細的中文注釋。另外，粘貼的代碼不會截取（某些沒必要的會删除），這樣便于了解，而不用想看哪行代碼再去源碼中尋找了。

學習源碼的實作僅是我們的目的之一，我們更應該掌握作者優秀的程式設計思想，了解這樣做的初衷，站在更高的角度思考問題。

本系列文章的源碼全部基于JDK1.8，不同版本的實作代碼可能稍有差别，但核心思想是一緻的，希望大家不要被具體的實作帶偏了路。

Java集合類分為兩大部分：Collection和Map。Collection又主要由List、Queue和Set三大子產品組成。本系列文章也會基于這樣的結構進行，我們會先了解一些用到的資料結構，然後按照從接口抽象到具體實作的順序來一步步揭開集合的神秘面紗。

由于Set的結構與Map完全一緻，且Set的内部都是基于對應的Map實作的，是以隻需要知道Set是什麼即可，其具體實作如果感興趣可以自行閱讀源碼。

本系列文章不考慮多線程安全問題，與多線程相關的問題十分複雜，以後會對它專門研究。

本系列文章長達20多篇，全部讀完需要一定的耐心，但是我相信讀完對資料結構和集合一定會有更深的了解，在使用時需要注意哪些點也一定會胸有成竹。

另外由于個人能力有限，文章中若有表達不清晰或解釋錯誤的部分，希望各位看官能夠給予批評指正。

目錄結構

本系列文章會按照下述結構搭建：

• 資料結構
• Iterable概述
• Collection概述
• List系列分析
• Queue系列分析
• Map概述與系列分析
• Set簡介

以下是全部文章連結：

Java集合源碼分析之基礎（一）：數組與連結清單

Java集合源碼分析之基礎（二）：哈希表

Java集合源碼分析之基礎（三）：樹與二叉樹

Java集合源碼分析之基礎（四）：二叉排序樹

Java集合源碼分析之基礎（五）：平衡二叉樹（AVL Tree）

Java集合源碼分析之基礎（六）：紅黑樹（RB Tree）

Java集合源碼分析之Iterable概述

Java集合源碼分析之超級接口：Collection

Java集合源碼分析之List（一）：超級接口List

Java集合源碼分析之List（二）：ArrayList

Java集合源碼分析之Queue（一）：超級接口Queue

Java集合源碼分析之Queue（二）：接口Deque

Java集合源碼分析之Queue（三）：ArrayDeque

Java集合源碼分析之LinkedList

Java集合源碼分析之Map（一）：超級接口Map

Java集合源碼分析之Map（二）：接口SortedMap

Java集合源碼分析之Map（三）：接口NavigableMap

Java集合源碼分析之Map（四）：TreeMap

Java集合源碼分析之Map（五）：HashMap

Java集合源碼分析之Map（六）：LinkedHashMap

Java集合源碼分析之Set概述

本系列文章全部更新完畢，感謝您的關注~

本文到此就結束了，如果您喜歡我的文章，可以關注我的微信公衆号： 大大紙飛機

或者掃描下方二維碼直接添加：

您也可以關注我的github：https://github.com/LtLei/articles

程式設計之路，道阻且長。唯，路漫漫其修遠兮，吾将上下而求索。