二.Java集合架構 · java核心知識整理

# 前言　　Java集合框架 (Java Collections Framework, JCF) 也稱容器，這里可以類比 C++ 中的 STL，在市面上似乎還沒能找到一本詳細介紹的書籍。在這里主要對如下部分進行源碼分析，及在面試中常見的問題。　　例如，在阿里面試常問到的 HashMap 和 ConcurrentHashMap 原理等等。深入源碼分析是面試中必備的技能，通過本文的閱讀會對集合框架有更深一步的了解。本文參考： * [CarpenterLee/JCFInternals: 深入理解Java集合框架](https://github.com/CarpenterLee/JCFInternals) * [crossoverJie/Java-Interview:?????Java related : basic, concurrent, algorithm](https://github.com/crossoverJie/Java-Interview) * [Interview-Notebook/Java 容器.md at master · CyC2018/Interview-Notebook](https://github.com/CyC2018/Interview-Notebook/blob/master/notes/Java%20%E5%AE%B9%E5%99%A8.md) # [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/02-Java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6.md#一概述)一、概述　　Java集合框架提供了數據持有對象的方式，提供了對數據集合的操作。Java 集合框架位于`java.util`包下，主要有三個大類：**Collection(接口)**、**Map(接口)**、**集合工具類**。 ## [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/02-Java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6.md#集合框架圖)集合框架圖 [![](https://github.com/frank-lam/fullstack-tutorial/raw/master/notes/JavaArchitecture/assets/1535785576589.png)](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/assets/1535785576589.png) ## [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/02-Java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6.md#collection)Collection * `ArrayList`：**線程不同步**。默認初始容量為 10，當數組大小不足時容量擴大為 1.5 倍。為追求效率，ArrayList 沒有實現同步（synchronized），如果需要多個線程并發訪問，用戶可以手動同步，也可使用 Vector 替代。 * `LinkedList`：**線程不同步**。**雙向鏈接實現**。LinkedList 同時實現了 List 接口和 Deque 接口，也就是說它既可以看作一個順序容器，又可以看作一個隊列（Queue），同時又可以看作一個棧（Stack）。這樣看來，LinkedList 簡直就是個全能冠軍。當你需要使用棧或者隊列時，可以考慮使用 LinkedList，一方面是因為 Java 官方已經聲明不建議使用 Stack 類，更遺憾的是，Java 里根本沒有一個叫做 Queue 的類（它是個接口名字）。關于棧或隊列，現在的首選是 ArrayDeque，它有著比 LinkedList（當作棧或隊列使用時）有著更好的性能。 * `Stack and Queue`：Java 里有一個叫做 Stack 的類，卻沒有叫做 Queue 的類（它是個接口名字）。當需要使用棧時，Java 已不推薦使用 Stack，而是推薦使用更高效的 ArrayDeque；既然 Queue 只是一個接口，當需要使用隊列時也就首選 ArrayDeque 了（次選是 LinkedList ）。 * `Vector`：**線程同步**。默認初始容量為 10，當數組大小不足時容量擴大為 2 倍。它的同步是通過`Iterator`方法加`synchronized`實現的。 * `Stack`：**線程同步**。繼承自 Vector，添加了幾個方法來完成棧的功能。現在已經不推薦使用 Stack，在棧和隊列中有限使用 ArrayDeque，其次是 LinkedList。 * `TreeSet`：**線程不同步**，內部使用`NavigableMap`操作。默認元素 “自然順序” 排列，可以通過`Comparator`改變排序。TreeSet 里面有一個 TreeMap（適配器模式） * `HashSet`：**線程不同步**，內部使用 HashMap 進行數據存儲，提供的方法基本都是調用 HashMap 的方法，所以兩者本質是一樣的。集合元素可以為 NULL。 * `Set`：Set 是一種不包含重復元素的 Collection，Set 最多只有一個 null 元素。Set 集合通常可以通過 Map 集合通過適配器模式得到。 * `PriorityQueue`：Java 中 PriorityQueue 實現了 Queue 接口，不允許放入 null 元素；其通過堆實現，具體說是通過完全二叉樹（complete binary tree）實現的**小頂堆**（任意一個非葉子節點的權值，都不大于其左右子節點的權值），也就意味著可以通過數組來作為 PriorityQueue 的底層實現。 * **優先隊列的作用是能保證每次取出的元素都是隊列中權值最小的**（Java 的優先隊列每次取最小元素，C++ 的優先隊列每次取最大元素）。這里牽涉到了大小關系，**元素大小的評判可以通過元素本身的自然順序（natural ordering），也可以通過構造時傳入的比較器**（*Comparator*，類似于 C++ 的仿函數）。 * `NavigableSet`：添加了搜索功能，可以對給定元素進行搜索：小于、小于等于、大于、大于等于，放回一個符合條件的最接近給定元素的 key。 * `EnumSet`：線程不同步。內部使用 Enum 數組實現，速度比`HashSet`快。**只能存儲在構造函數傳入的枚舉類的枚舉值**。　　 ## [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/02-Java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6.md#map)Map * `TreeMap`：線程不同步，基于**紅黑樹**（Red-Black tree）的 NavigableMap 實現，能夠把它保存的記錄根據鍵排序，默認是按鍵值的升序排序，也可以指定排序的比較器，當用 Iterator 遍歷 TreeMap 時，得到的記錄是排過序的。 * **TreeMap 底層通過紅黑樹（Red-Black tree）實現**，也就意味著`containsKey()`,`get()`,`put()`,`remove()`都有著`log(n)`的時間復雜度。其具體算法實現參照了《算法導論》。 * `HashTable`：**線程安全**，HashMap 的迭代器 (Iterator) 是`fail-fast`迭代器。**HashTable 不能存儲 NULL 的 key 和 value。** * `HashMap`：線程不同步。根據`key`的`hashcode`進行存儲，內部使用靜態內部類`Node`的數組進行存儲，默認初始大小為 16，每次擴大一倍。當發生 Hash 沖突時，采用拉鏈法（鏈表）。JDK 1.8中：**當單個桶中元素個數大于等于8時，鏈表實現改為紅黑樹實現；當元素個數小于6時，變回鏈表實現。由此來防止hashCode攻擊。** * Java?HashMap 采用的是沖突鏈表方式。 * HashMap 是 Hashtable 的輕量級實現，可以接受為 null 的鍵值 (key) 和值 (value)，而 Hashtable 不允許。 * `LinkedHashMap`：**保存了記錄的插入順序**，在用 Iterator 遍歷 LinkedHashMap 時，先得到的記錄肯定是先插入的。也可以在構造時用帶參數，按照應用次數排序。在遍歷的時候會比 HashMap 慢，不過有種情況例外，當 HashMap 容量很大，實際數據較少時，遍歷起來可能會比 LinkedHashMap 慢，因為 LinkedHashMap 的遍歷速度只和實際數據有關，和容量無關，而 HashMap 的遍歷速度和他的容量有關。 * `WeakHashMap`：從名字可以看出它是某種?Map。它的特殊之處在于?WeakHashMap?里的 entry 可能會被 GC 自動刪除，即使程序員沒有調用`remove()`或者`clear()`方法。 WeakHashMap 的存儲結構類似于HashMap * 既然有?WeekHashMap，是否有?WeekHashSet?呢？答案是沒有！不過 Java?Collections 工具類給出了解決方案，`Collections.newSetFromMap(Map<E,Boolean> map)`方法可以將任何?Map包裝成一個Set。 ## [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/02-Java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6.md#工具類)工具類 * `Collections`、`Arrays`：集合類的一個工具類幫助類，其中提供了一系列靜態方法，用于對集合中元素進行排序、搜索以及線程安全等各種操作。 * `Comparable`、`Comparator`：一般是用于對象的比較來實現排序，兩者略有區別。 > * 類設計者沒有考慮到比較問題而沒有實現 Comparable 接口。這是我們就可以通過使用 Comparator，這種情況下，我們是不需要改變對象的。 > * 一個集合中，我們可能需要有多重的排序標準，這時候如果使用 Comparable 就有些捉襟見肘了，可以自己繼承 Comparator 提供多種標準的比較器進行排序。 **說明**：線程不同步的時候可以通過，Collections.synchronizedList() 方法來包裝一個線程同步方法 ## [](https://github.com/frank-lam/fullstack-tutorial/blob/master/notes/JavaArchitecture/02-Java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6.md#通用實現)通用實現 :-: <table align="center"><tr><td colspan="2" rowspan="2" align="center" border="0"></td><th colspan="5" align="center">Implementations</th></tr><tr><th>Hash Table</th><th>Resizable Array</th><th>Balanced Tree</th><th>Linked List</th><th>Hash Table + Linked List</th></tr><tr><th rowspan="4">Interfaces</th><th>Set</th><td><tt>HashSet</tt></td><td></td><td><tt>TreeSet</tt></td><td></td><td><tt>LinkedHashSet</tt></td></tr><tr><th>List</th><td></td><td><tt>ArrayList</tt></td><td></td><td><tt>LinkedList</tt></td><td></td></tr><tr><th>Deque</th><td></td><td><tt>ArrayDeque</tt></td><td></td><td><tt>LinkedList</tt></td><td></td></tr><tr><th>Map</th><td><tt>HashMap</tt></td><td></td><td><tt>TreeMap</tt></td><td></td><td><tt>LinkedHashMap</tt></td></tr></table> **參考資料：** * [CarpenterLee/JCFInternals:深入理解Java集合框架](https://github.com/CarpenterLee/JCFInternals) * [Java基礎-集合框架 - 掘金](https://juejin.im/post/5af86ac8f265da0ba063410e)