Java集合框架 (Java Collections Framework, JCF) 也稱容器，這里可以類比 C++ 中的 STL，在市面上似乎還沒能找到一本詳細介紹的書籍。在這里主要對如下部分進行源碼分析，及在面試中常見的問題。

例如，在阿里面試常問到的 HashMap 和 ConcurrentHashMap 原理等等。深入源碼分析是面試中必備的技能，通過本文的閱讀會對集合框架有更深一步的了解。

一、概述

Java集合框架提供了數(shù)據(jù)持有對象的方式，提供了對數(shù)據(jù)集合的操作。Java 集合框架位于java.util包下，主要有三個大類：Collection(接口)、Map(接口)、集合工具類。

Collection

• ArrayList：線程不同步。默認(rèn)初始容量為 10，當(dāng)數(shù)組大小不足時容量擴大為 1.5 倍。為追求效率，ArrayList 沒有實現(xiàn)同步（synchronized），如果需要多個線程并發(fā)訪問，用戶可以手動同步，也可使用 Vector 替代。
• LinkedList：線程不同步。雙向鏈接實現(xiàn)。LinkedList 同時實現(xiàn)了 List 接口和 Deque 接口，也就是說它既可以看作一個順序容器，又可以看作一個隊列（Queue），同時又可以看作一個棧（Stack）。這樣看來，LinkedList 簡直就是個全能冠軍。當(dāng)你需要使用?；蛘哧犃袝r，可以考慮使用 LinkedList，一方面是因為 Java 官方已經(jīng)聲明不建議使用 Stack 類，更遺憾的是，Java 里根本沒有一個叫做 Queue 的類（它是個接口名字）。關(guān)于棧或隊列，現(xiàn)在的首選是 ArrayDeque，它有著比 LinkedList（當(dāng)作棧或隊列使用時）有著更好的性能。
• Stack and Queue：Java 里有一個叫做 Stack 的類，卻沒有叫做 Queue 的類（它是個接口名字）。當(dāng)需要使用棧時，Java 已不推薦使用 Stack，而是推薦使用更高效的 ArrayDeque；既然 Queue 只是一個接口，當(dāng)需要使用隊列時也就首選 ArrayDeque 了（次選是 LinkedList ）。
• Vector：線程同步。默認(rèn)初始容量為 10，當(dāng)數(shù)組大小不足時容量擴大為 2 倍。它的同步是通過Iterator方法加synchronized實現(xiàn)的。
• Stack：線程同步。繼承自 Vector，添加了幾個方法來完成棧的功能?，F(xiàn)在已經(jīng)不推薦使用 Stack，在棧和隊列中有限使用 ArrayDeque，其次是 LinkedList。
• TreeSet：線程不同步，內(nèi)部使用NavigableMap操作。默認(rèn)元素 “自然順序” 排列，可以通過Comparator改變排序。TreeSet 里面有一個 TreeMap（適配器模式）
• HashSet：線程不同步，內(nèi)部使用 HashMap 進行數(shù)據(jù)存儲，提供的方法基本都是調(diào)用 HashMap 的方法，所以兩者本質(zhì)是一樣的。集合元素可以為 NULL。
• Set：Set 是一種不包含重復(fù)元素的 Collection，Set 最多只有一個 null 元素。Set 集合通常可以通過 Map 集合通過適配器模式得到。
• PriorityQueue：Java 中 PriorityQueue 實現(xiàn)了 Queue 接口，不允許放入 null 元素；其通過堆實現(xiàn)，具體說是通過完全二叉樹（complete binary tree）實現(xiàn)的小頂堆（任意一個非葉子節(jié)點的權(quán)值，都不大于其左右子節(jié)點的權(quán)值），也就意味著可以通過數(shù)組來作為 PriorityQueue 的底層實現(xiàn)。
  • 優(yōu)先隊列的作用是能保證每次取出的元素都是隊列中權(quán)值最小的（Java 的優(yōu)先隊列每次取最小元素，C++ 的優(yōu)先隊列每次取最大元素）。這里牽涉到了大小關(guān)系，元素大小的評判可以通過元素本身的自然順序（natural ordering），也可以通過構(gòu)造時傳入的比較器（Comparator，類似于 C++ 的仿函數(shù)）。
• NavigableSet：添加了搜索功能，可以對給定元素進行搜索：小于、小于等于、大于、大于等于，放回一個符合條件的最接近給定元素的 key。
• EnumSet：線程不同步。內(nèi)部使用 Enum 數(shù)組實現(xiàn)，速度比HashSet快。只能存儲在構(gòu)造函數(shù)傳入的枚舉類的枚舉值。

Map

• TreeMap：線程不同步，基于紅黑樹（Red-Black tree）的 NavigableMap 實現(xiàn)，能夠把它保存的記錄根據(jù)鍵排序，默認(rèn)是按鍵值的升序排序，也可以指定排序的比較器，當(dāng)用 Iterator 遍歷 TreeMap 時，得到的記錄是排過序的。
  • TreeMap 底層通過紅黑樹（Red-Black tree）實現(xiàn)，也就意味著containsKey(),get(),put(),remove()都有著log(n)的時間復(fù)雜度。其具體算法實現(xiàn)參照了《算法導(dǎo)論》。
• HashTable：線程安全，HashMap 的迭代器 (Iterator) 是fail-fast迭代器。HashTable 不能存儲 NULL 的 key 和 value。
• HashMap：線程不同步。根據(jù)key的hashcode進行存儲，內(nèi)部使用靜態(tài)內(nèi)部類Node的數(shù)組進行存儲，默認(rèn)初始大小為 16，每次擴大一倍。當(dāng)發(fā)生 Hash 沖突時，采用拉鏈法（鏈表）。JDK 1.8中：當(dāng)單個桶中元素個數(shù)大于等于8時，鏈表實現(xiàn)改為紅黑樹實現(xiàn)；當(dāng)元素個數(shù)小于6時，變回鏈表實現(xiàn)。由此來防止hashCode攻擊。
  • Java HashMap 采用的是沖突鏈表方式。
  • HashMap 是 Hashtable 的輕量級實現(xiàn)，可以接受為 null 的鍵值 (key) 和值 (value)，而 Hashtable 不允許。
• LinkedHashMap：保存了記錄的插入順序，在用 Iterator 遍歷 LinkedHashMap 時，先得到的記錄肯定是先插入的。也可以在構(gòu)造時用帶參數(shù)，按照應(yīng)用次數(shù)排序。在遍歷的時候會比 HashMap 慢，不過有種情況例外，當(dāng) HashMap 容量很大，實際數(shù)據(jù)較少時，遍歷起來可能會比 LinkedHashMap 慢，因為 LinkedHashMap 的遍歷速度只和實際數(shù)據(jù)有關(guān)，和容量無關(guān)，而 HashMap 的遍歷速度和他的容量有關(guān)。
• WeakHashMap：從名字可以看出它是某種 Map。它的特殊之處在于 WeakHashMap 里的 entry 可能會被 GC 自動刪除，即使程序員沒有調(diào)用remove()或者clear()方法。 WeakHashMap 的存儲結(jié)構(gòu)類似于HashMap
  • 既然有 WeekHashMap，是否有 WeekHashSet 呢？答案是沒有！不過 Java Collections 工具類給出了解決方案，Collections.newSetFromMap(Map<E,Boolean> map)方法可以將任何 Map包裝成一個Set。

集合工具類

• Collections、Arrays：集合類的一個工具類幫助類，其中提供了一系列靜態(tài)方法，用于對集合中元素進行排序、搜索以及線程安全等各種操作。

• Comparable、Comparator：一般是用于對象的比較來實現(xiàn)排序，兩者略有區(qū)別。

  • 類設(shè)計者沒有考慮到比較問題而沒有實現(xiàn) Comparable 接口。這是我們就可以通過使用 Comparator，這種情況下，我們是不需要改變對象的。
  • 一個集合中，我們可能需要有多重的排序標(biāo)準(zhǔn)，這時候如果使用 Comparable 就有些捉襟見肘了，可以自己繼承 Comparator 提供多種標(biāo)準(zhǔn)的比較器進行排序。

說明：線程不同步的時候可以通過，Collections.synchronizedList() 方法來包裝一個線程同步方法

通用實現(xiàn)

到此這篇關(guān)于深入理解Java基礎(chǔ)中的集合框架的文章就介紹到這了,更多相關(guān)Java集合框架內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論