「集合系列」- 初探 java 集合框架圖

實際開發中，經常用到 java 的集合框架，比如 ArrayList 、 LinkedList 、 HashMap 、 LinkedHashMap，幾乎經常接觸到，雖然用的多，但是對集合的整體框架，基礎知識還是不夠系統，今天想和大家一起來梳理一下！

01、集合類簡介

Java 集合就像一種容器，可以把多個對象（實際上是對象的引用，但習慣上都稱對象）“丟進”該容器中。從 Java 5 增加了泛型以後，Java 集合可以記住容器中對象的數據類型，使得編碼更加簡潔、健壯。

Java 集合大致可以分為兩大體系，一個是 Collection，另一個是 Map；

• Collection ：主要由List、Set、Queue接口組成，List代表有序、重複的集合；其中Set代表無序、不可重複的集合；Java 5 又增加了Queue體系集合，代表一種隊列集合實現。
• Map：則代表具有映射關係的鍵值對集合。

java.util.Collection 下的接口和繼承類關係簡易結構圖：

java.util.Map 下的接口和繼承類關係簡易結構圖：

其中，Java 集合框架中主要封裝的是典型的數據結構和算法，如動態數組、雙向鏈表、隊列、棧、Set、Map 等。

將集合框架挖掘處理，可以分為以下幾個部分

1) 數據結構

List列表、Queue隊列、Deque雙端隊列、Set集合、Map映射

2) 比較器

Comparator比較器、Comparable 排序接口

3) 算法

Collections常用算法類、Arrays靜態數組的排序、查找算法

4) 迭代器

Iterator通用迭代器、ListIterator針對 List 特化的迭代器

02、有序列表（List）

List集合的特點就是存取有序，可以存儲重複的元素，可以用下標進行元素的操作

List主要實現類：ArrayList、LinkedList、Vector、Stack。

2.1、ArrayList

ArrayList 是一個動態數組結構，支持隨機存取，尾部插入刪除方便，內部插入刪除效率低（因為要移動數組元素）；如果內部數組容量不足則自動擴容，因此當數組很大時，效率較低。

2.2、LinkedList

LinkedList 是一個雙向鏈表結構，在任意位置插入刪除都很方便，但是不支持隨機取值，每次都只能從一端開始遍歷，直到找到查詢的對象，然後返回；不過，它不像 ArrayList 那樣需要進行內存拷貝，因此相對來說效率較高，但是因為存在額外的前驅和後繼節點指針，因此佔用的內存比 ArrayList 多一些。

2.3、Vector

Vector 也是一個動態數組結構，一個元老級別的類，早在 jdk1.1 就引入進來類，之後在 jdk1.2 裡引進 ArrayList，ArrayList 大部分的方法和 Vector 比較相似，兩者是不同的，Vector 是允許同步訪問的，Vector 中的操作是線程安全的，但是效率低，而 ArrayList 所有的操作都是異步的，執行效率高，但不安全！

關於Vector，現在用的很少了，因為裡面的get、set、add等方法都加了synchronized，所以，執行效率會比較低，如果需要在多線程中使用，可以採用下面語句創建 ArrayList 對象

List

也可以考慮使用複製容器 java.util.concurrent.CopyOnWriteArrayList進行操作，例如：

final CopyOnWriteArrayList

2.4、Stack

Stack 是 Vector 的一個子類，本質也是一個動態數組結構，不同的是，它的數據結構是先進後出，取名叫棧！

關於Stack，現在用的也很少，因為有個ArrayDeque雙端隊列，可以替代Stack所有的功能，並且執行效率比它高！

03、集(Set)

Set集合的特點：元素不重複，存取無序，無下標；

Set主要實現類：HashSet、LinkedHashSet 和 TreeSet。

3.1、HashSet

HashSet底層是基於 HashMap 的k實現的，元素不可重複，特性同 HashMap。

3.2、LinkedHashSet

LinkedHashSet底層也是基於 LinkedHashMap 的k實現的，一樣元素不可重複，特性同 LinkedHashMap。

3.3、TreeSet

同樣的，TreeSet 也是基於 TreeMap 的k實現的，同樣元素不可重複，特性同 TreeMap；

Set 集合的實現，基本都是基於 Map 中的鍵做文章，使用 Map 中鍵不能重複、無序的特性；所以，我們只需要重點關注 Map 的實現即可！

04、隊列(Queue)

Queue是一個隊列集合，隊列通常是指“先進先出”（FIFO）的容器。新元素插入（offer）到隊列的尾部，訪問元素（poll）操作會返回隊列頭部的元素。通常，隊列不允許隨機訪問隊列中的元素。

Queue主要實現類：ArrayDeque、LinkedList、PriorityQueue。

4.1、ArrayDeque

ArrayQueue是一個基於數組實現的雙端隊列，可以想象，在隊列中存在兩個指針，一個指向頭部，一個指向尾部，因此它具有“FIFO隊列”及“棧”的方法特性。

既然是雙端隊列，那麼既可以先進先出，也可以先進後出，以下是測試例子！

先進先出

public static void main(String[] args) {                ArrayDeque queue = new ArrayDeque<>();        //入隊        queue.offer("AAA");        queue.offer("BBB");        queue.offer("CCC");        System.out.println(queue);        //獲取但不出隊        System.out.println(queue.peek());        System.out.println(queue);        //出隊        System.out.println(queue.poll());        System.out.println(queue);}

輸出結果：

[AAA, BBB, CCC]AAA[AAA, BBB, CCC]AAA[BBB, CCC]

先進後出

public static void main(String[] args) {                ArrayDeque stack = new ArrayDeque<>();        //壓棧,此時AAA在最下,CCC在最外        stack.push("AAA");        stack.push("BBB");        stack.push("CCC");        System.out.println(stack);        //獲取最後添加的元素,但不刪除        System.out.println(stack.peek());        System.out.println(stack);        //彈出最後添加的元素        System.out.println(stack.pop());        System.out.println(stack);}

輸出結果：

[CCC, BBB, AAA]CCC[CCC, BBB, AAA]CCC[BBB, AAA]

4.2、LinkedList

LinkedList是List接口的實現類，也是Deque的實現類，底層是一種雙向鏈表的數據結構，在上面咱們也有所介紹，LinkedList可以根據索引來獲取元素，增加或刪除元素的效率較高，如果查找的話需要遍歷整合集合，效率較低，LinkedList同時實現了stack、Queue、PriorityQueue的所有功能。

例子

public static void main(String[] args) {                LinkedList ll = new LinkedList<>();        //入隊        ll.offer("AAA");        //壓棧        ll.push("BBB");        //雙端的另一端入隊        ll.addFirst("NNN");        ll.forEach(str -> System.out.println("遍歷中:" + str));        //獲取隊頭        System.out.println(ll.peekFirst());        //獲取隊尾        System.out.println(ll.peekLast());        //彈棧        System.out.println(ll.pop());        System.out.println(ll);        //雙端的後端出列        System.out.println(ll.pollLast());        System.out.println(ll);}

輸出結果：

遍歷中:NNN遍歷中:BBB遍歷中:AAANNNAAANNN[BBB, AAA]AAA[BBB]

4.3、PriorityQueue

PriorityQueue也是一個隊列的實現類，此實現類中存儲的元素排列並不是按照元素添加的順序進行排列，而是內部會按元素的大小順序進行排列，是一種能夠自動排序的隊列。

例子

public static void main(String[] args) {        PriorityQueue queue1 = new PriorityQueue<>(10);        System.out.println("處理前的數據");        Random rand = new Random();        for (int i = 0; i < 10; i++) {                Integer num = rand.nextInt(90) + 10;                System.out.print(num + ", ");            queue1.offer(num); // 隨機兩位數        }        System.out.println("\\n處理後的數據");        for (int i = 0; i < 10; i++) { // 默認是自然排序 [升序]            System.out.print(queue1.poll() + ", ");        }}

輸出結果：

處理前的數據36, 23, 24, 11, 12, 26, 79, 96, 14, 73, 處理後的數據11, 12, 14, 23, 24, 26, 36, 73, 79, 96,  

05、映射表(Map)

Map是一個雙列集合，其中保存的是鍵值對，鍵要求保持唯一性，值可以重複。

Map 主要實現類：HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties。

5.1、HashMap

關於HashMap，相信大家都不陌生，繼承自AbstractMap，key 不可重複，因為使用的是哈希表存儲元素，所以輸入的數據與輸出的數據，順序基本不一致，另外，HashMap最多隻允許一條記錄的 key 為 null。

5.2、LinkedHashMap

HashMap 的子類，內部使用鏈表數據結構來記錄插入的順序，使得輸入的記錄順序和輸出的記錄順序是相同的。LinkedHashMap與HashMap最大的不同處在於，LinkedHashMap輸入的記錄和輸出的記錄順序是相同的！

5.3、TreeMap

能夠把它保存的記錄根據鍵排序，默認是按鍵值的升序排序，也可以指定排序的比較器，當用 Iterator 遍歷時，得到的記錄是排過序的；如需使用排序的映射，建議使用 TreeMap。TreeMap實際使用的比較少！

5.4、IdentityHashMap

繼承自AbstractMap，與HashMap有些不同，在獲取元素的時候，通過==代替equals ()來進行判斷，比較的是內存地址。

get方法源碼部分

public V get(Object key) {        Object k = maskNull(key);        Object[] tab = table;        int len = tab.length;        int i = hash(k, len);        while (true) {            Object item = tab[i];//用==比較k和元素是否相等            if (item == k)                return (V) tab[i + 1];            if (item == null)                return null;            i = nextKeyIndex(i, len);        }}

5.5、WeakHashMap

WeakHashMap繼承自AbstractMap，被稱為緩存Map，向WeakHashMap中添加元素，再次通過鍵調用方法獲取元素方法時，不一定獲取到元素值，因為WeakHashMap 中的 Entry 可能隨時被 GC 回收。

5.6、Hashtable

Hashtable，一個元老級的類，鍵值不能為空，與HashMap不同的是，方法都加了synchronized同步鎖，是線程安全的，但是效率上，沒有HashMap快！

同時，HashMap 是 HashTable 的輕量級實現，他們都完成了Map 接口，區別在於 HashMap 允許K和V為空，而HashTable不允許K和V為空，由於非線程安全，效率上可能高於 Hashtable。

如果需要在多線程環境下使用HashMap，可以使用如下的同步器來實現或者使用併發工具包中的ConcurrentHashMap類

Map map =Collections.synchronizedMap(new HashMap<>());

5.7、Properties

Properties繼承自HashTable，Properties新增了load()和和store()方法，可以直接導入或者將映射寫入文件，另外，Properties的鍵和值都是String類型。

06、比較器

Comparable和Comparator接口都是用來比較大小的，一般在TreeSet、TreeMap接口中使用的比較多，主要用於解決排序問題。

6.1、Comparable

Comparable：對實現它的每個類的對象進行整體排序

package java.lang;import java.util.*;public interface Comparable {public int compareTo(T o);}

若一個類實現了Comparable 接口，實現 Comparable 接口的類的對象的 List 列表 ( 或數組)可以通過 Collections.sort（或 Arrays.sort）進行排序。

此外，實現 Comparable 接口的類的對象 可以用作 “有序映射 ( 如 TreeMap)” 中的鍵或 “有序集合 (TreeSet)” 中的元素，而不需要指定比較器。

使用例子：

 
/**  * 實體類Person實現Comparable接口  */public class Person implements Comparable{    private int age;    private String name;    public Person(String name, int age){        this.name = name;        this.age = age;    }    @Override    public int compareTo(Person o){        return this.age-o.age;    }    @Override    public String toString(){        return name+":"+age;    }}

測試

public static void main(String[] args) {Person person1 = new Person("張三",18);Person person2 = new Person("李四",17);Person person3 = new Person("王五",19);List list = new ArrayList<>();list.add(person1);list.add(person2);list.add(person3);System.out.println(list);Collections.sort(list);System.out.println(list);}

輸出：

[張三:18, 李四:17, 王五:19][李四:17, 張三:18, 王五:19]

6.2、Comparator

Comparator：也是對實現它的每個類的對象進行排序

package java.util;import ***;public interface Comparator {int compare(T o1, T o2);......}

如果我們的這個類Person無法修改或者沒有繼承Comparable接口，我們又要對其進行排序，Comparator就可以派上用場了。

將類Person實現的Comparable接口去掉

/**  * 實體類Person  */public class Person {    private int age;    private String name;public int getAge() {        return age;    }    public void setAge(int age) {        this.age = age;    }    public Person(String name, int age){        this.name = name;        this.age = age;    }    @Override    public String toString(){        return name+":"+age;    }}

測試類：

 
public static void main(String[] args) {Person person1 = new Person("張三",18);Person person2 = new Person("李四",17);Person person3 = new Person("王五",19);List list = new ArrayList<>();list.add(person1);list.add(person2);list.add(person3);System.out.println(list);Collections.sort(list, new Comparator() {@Overridepublic int compare(Person o1, Person o2) {if(o1 == null || o2 == null){return 0;}//o1比o2小,返回負數//o1等於o2,等於0//o1大於o2,返回正數return o1.getAge()-o2.getAge();}});System.out.println(list);}

輸出：

[張三:18, 李四:17, 王五:19][李四:17, 張三:18, 王五:19]

07、常用工具類

7.1、Collections類

java.util.Collections工具類為集合框架提供了很多有用的方法，這些方法都是靜態的，在編程中可以直接調用。整個Collections工具類源碼差不多有4000行，這裡只針對一些典型的方法進行闡述。

7.1.1、addAll

addAll：向指定的集合c中加入特定的一些元素elements

public static  boolean addAll(Collection super T> c, T… elements)

7.1.2、binarySearch

binarySearch：利用二分法在指定的集合中查找元素

#集合元素T實現Comparable接口的方式，進行查詢public static  int binarySearch(List extends Comparable super T>> list, T key)#元素以外部實現Comparator接口的方式，進行查詢public static  int binarySearch(List extends T> list, T key, Comparator super T> c)

7.1.3、sort

#集合元素T實現Comparable接口的方式，進行排序public static > void sort(List list)#元素以外部實現Comparator接口的方式，進行排序public static  void sort(List list, Comparator super T> c)

7.1.4、shuffle

shuffle：混排，隨機打亂原來的順序，它打亂在一個List中可能有的任何排列的蹤跡。

#方法一public static void shuffle(List> list)#方法二，指定隨機數訪問public static void shuffle(List> list, Random rnd)

7.1.5、reverse

reverse：集合排列反轉

#直接反轉集合的元素public static void reverse(List> list)#返回可以使集合反轉的比較器Comparatorpublic static  
 Comparator reverseOrder()#集合的反轉的反轉，如果cmp不為null，返回cmp的反轉的比較器，如果cmp為null，效果等同於第二個方法.public static  Comparator reverseOrder(Comparator cmp)

7.1.6、synchronized系列

synchronized系列：確保所封裝的集合線程安全（強同步）

#同步Collection接口下的實現類public static  Collection synchronizedCollection(Collection c)#同步SortedSet接口下的實現類public static  SortedSet synchronizedSortedSet(SortedSet s)#同步List接口下的實現類public static  List synchronizedList(List list)#同步Map接口下的實現類public static  Map synchronizedMap(Map m)#同步SortedMap接口下的實現類public static  SortedMap synchronizedSortedMap(SortedMap m) 

7.2、Arrays類

java.util.Arrays工具類也為集合框架提供了很多有用的方法，這些方法都是靜態的，在編程中可以直接調用。整個Arrays工具類源碼有3000多行，這裡只針對一些典型的方法進行闡述。

7.2.1、asList

asList：將一個數組轉變成一個List，準確來說是ArrayList

public static  List asList(T... a) {        return new ArrayList<>(a);}

注意：這個List是定長的，企圖添加或者刪除數據都會報錯java.lang.UnsupportedOperationException

7.2.2、sort

sort：對數組進行排序，適合byte,char,double,float,int,long,short等基本類型，還有Object類型

#基本數據類型，例子int類型數組public static void sort(int[] a)#Object類型數組#如果使用Comparable進行排序，Object需要實現Comparable#如果使用Comparator進行排序，可以使用外部比較方法實現public static void sort(Object[] a) 

7.2.3、binarySearch

binarySearch：通過二分查找法對已排序的數組進行查找。如果數組沒有經過Arrays.sort排序，那麼檢索結果未知。

適合byte,char,double,float,int,long,short等基本類型，還有Object類型和泛型。

#基本數據類型，例子int類型數組，key為要查詢的參數public static int binarySearch(int[] a, int key)#Object類型數組，key為要查詢的參數#如果使用Comparable進行排序，Object需要實現Comparable#如果使用Comparator進行排序，可以使用外部比較方法實現public static int binarySearch(Object[] a, Object key)

7.2.4、copyOf

copyOf：數組拷貝，底層採用System.arrayCopy（native方法）實現。

適合byte,char,double,float,int,long,short等基本類型，還有泛型數組。

#基本數據類型，例子int類型數組，newLength新數組長度public static int[] copyOf(int[] original, int newLength)#T為泛型數組，newLength新數組長度public static  T[] copyOf(T[] original, int newLength)

7.2.5、copyOfRange

copyOfRange：數組拷貝，指定一定的範圍，底層採用System.arrayCopy（native方法）實現。

適合byte,char,double,float,int,long,short等基本類型，還有泛型數組。

#基本數據類型，例子int類型數組，from：開始位置，to：結束位置public static int[] copyOfRange(int[] original, int from, int to)#T為泛型數組，from：開始位置，to：結束位置public static  T[] copyOfRange(T[] original, int from, int to)

7.2.6、equals和deepEquals

equals：判斷兩個數組的每一個對應的元素是否相等（equals, 對於兩個數組的元素a和a2有a==null ? a2==null : a.equals(a2)）

#基本數據類型，例子int類型數組，a為原數組，a2為目標數組public static boolean equals(int[] a, int[] a2)#Object數組，a為原數組，a2為目標數組public static boolean equals(Object[] a, Object[] a2)

deepEquals：主要針對一個數組中的元素還是數組的情況(多維數組比較)

#Object數組，a1為原數組，a2為目標數組public static boolean deepEquals(Object[] a1, Object[] a2)

7.2.7、toString和deepToString

toString：將數組轉換成字符串，中間用逗號隔開

#基本數據類型，例子int類型數組，a為數組public static String toString(int[] a)#Object數組，a為數組public static String toString(Object[] a)

deepToString：當數組中又包含數組，就不能單純的利用Arrays.toString()了，使用此方法將數組轉換成字符串

#Object數組，a為數組public static String deepToString(Object[] a)

08、迭代器

JCF的迭代器（Iterator）為我們提供了遍歷容器中元素的方法。只有容器本身清楚容器裡元素的組織方式，因此迭代器只能通過容器本身得到。每個容器都會通過內部類的形式實現自己的迭代器。

ArrayList list = new ArrayList();list.add(new String("a1"));list.add(new String("a2"));list.add(new String("a3"));Iterator it = list.iterator();//得到迭代器while(it.hasNext()){    String obj = it.next();//訪問元素    System.out.println(obj);}

JDK 1.5 引入了增強的for循環，簡化了迭代容器時的寫法

//使用增強for迭代ArrayList list = new ArrayList();list.add(new String("a1"));list.add(new String("a2"));list.add(new String("a3"));for(String obj : list){//enhanced for statement    System.out.println(obj);}

09、總結

以上，主要是對java集合的整體架構進行簡單的介紹，如果有理解不當之處，歡迎指正。

10、參考

1、JDK1.7&JDK1.8 源碼

2、Otokaze’s Blog - Java Collection框架

3、CSDN - 朱小廝 - Comparable與Comparator淺析

閱讀更多 科技伍小黑 的文章

關鍵字: 算法 數據結構 框架圖