Java - 集合框架完全解析

PhyllisMixo 8年前發布 | 230K 次閱讀 Java 鏈表 Java開發

數據結構是以某種形式將數據組織在一起的集合，它不僅存儲數據，還支持訪問和處理數據的操作。Java提供了幾個能有效地組織和操作數據的數據結構，這些數據結構通常稱為Java集合框架。在平常的學習開發中，靈活熟練地使用這些集合框架，可以很明顯地提高我們的開發效率，當然僅僅會用還是不夠的，理解其中的設計思想與原理才能更好地提高我們的開發水平。下面是自己對Java集合框架方面的學習總結。

一、概述
二、Collection接口
   1.List
   2.Set
   3.Queue
三、Map接口
   1.HashMap實現原理
   2.其它Map實現類
四、其它集合類
五、總結

一、概述

在Java 2之前，Java是沒有完整的集合框架的。它只有一些簡單的可以自擴展的容器類，比如Vector，Stack，Hashtable等。這些容器類在使用的過程中由于效率問題飽受詬病，因此在Java 2中，Java設計者們進行了大刀闊斧的整改，重新設計，于是就有了現在的集合框架。需要注意的是，之前的那些容器類庫并沒有被棄用而是進行了保留，主要是為了向下兼容的目的，但我們在平時使用中還是應該盡量少用。

Java集合框架

從上面的集合框架圖可以看到，Java集合框架主要包括兩種類型的容器，一種是集合（Collection），存儲一個元素集合，另一種是圖（Map），存儲鍵/值對映射。Collection接口又有3種子類型，List、Set和Queue，再下面是一些抽象類，最后是具體實現類，常用的有ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap等等。

二、Collection接口

Collection接口是處理對象集合的根接口，其中定義了很多對元素進行操作的方法，AbstractCollection是提供Collection部分實現的抽象類。下圖展示了Collection接口中的全部方法。

Collection接口結構

其中，有幾個比較常用的方法，比如方法add()添加一個元素到集合中，addAll()將指定集合中的所有元素添加到集合中，contains()方法檢測集合中是否包含指定的元素，toArray()方法返回一個表示集合的數組。Collection接口有三個子接口，下面詳細介紹。

1.List

List接口擴展自Collection，它可以定義一個允許重復的有序集合，從List接口中的方法來看，List接口主要是增加了面向位置的操作，允許在指定位置上操作元素，同時增加了一個能夠雙向遍歷線性表的新列表迭代器ListIterator。AbstractList類提供了List接口的部分實現，AbstractSequentialList擴展自AbstractList，主要是提供對鏈表的支持。下面介紹List接口的兩個重要的具體實現類，也是我們可能最常用的類，ArrayList和LinkedList。

ArrayList

通過閱讀ArrayList的源碼，我們可以很清楚地看到里面的邏輯，它是用數組存儲元素的，這個數組可以動態創建，如果元素個數超過了數組的容量，那么就創建一個更大的新數組，并將當前數組中的所有元素都復制到新數組中。假設第一次是集合沒有任何元素，下面以插入一個元素為例看看源碼的實現。

1、方法add(E e)向集合中添加指定元素。

   public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

2、此方法主要是確定將要創建的數組大小。

  private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

3、最后是創建數組，可以明顯的看到先是確定了添加元素后的大小之后將元素復制到新數組中。

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

LinkedList

同樣，我們打開LinkedList的源文件，不難看到LinkedList是在一個鏈表中存儲元素。

在學習數據結構的時候，我們知道鏈表和數組的最大區別在于它們對元素的存儲方式的不同導致它們在對數據進行不同操作時的效率不同，同樣，ArrayList與LinkedList也是如此，實際使用中我們需要根據特定的需求選用合適的類，如果除了在末尾外不能在其他位置插入或者刪除元素，那么ArrayList效率更高，如果需要經常插入或者刪除元素，就選擇LinkedList。

2.Set

Set接口擴展自Collection，它與List的不同之處在于，規定Set的實例不包含重復的元素。在一個規則集內，一定不存在兩個相等的元素。AbstractSet是一個實現Set接口的抽象類，Set接口有三個具體實現類，分別是散列集HashSet、鏈式散列集LinkedHashSet和樹形集TreeSet。

散列集HashSet

散列集HashSet是一個用于實現Set接口的具體類，可以使用它的無參構造方法來創建空的散列集，也可以由一個現有的集合創建散列集。在散列集中，有兩個名詞需要關注，初始容量和客座率。客座率是確定在增加規則集之前，該規則集的飽滿程度，當元素個數超過了容量與客座率的乘積時，容量就會自動翻倍。

下面看一個HashSet的例子。

/**
 * @author JackalTsc
 */
public class TestHashSet {

    public static void main(String[] args) {

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

        set.add("11111");
        set.add("22222");
        set.add("33333");
        set.add("44444");
        set.add("22222");

        System.out.println(set.size());

        for (String e : set) {
            System.out.println(e);
        }
    }
}

從輸出結果我們可以看到，規則集里最后有4個元素，而且在輸出時元素還是無序的。

鏈式散列集LinkedHashSet

LinkedHashSet是用一個鏈表實現來擴展HashSet類，它支持對規則集內的元素排序。HashSet中的元素是沒有被排序的，而LinkedHashSet中的元素可以按照它們插入規則集的順序提取。

樹形集TreeSet

TreeSet擴展自AbstractSet，并實現了NavigableSet，AbstractSet擴展自AbstractCollection，樹形集是一個有序的Set，其底層是一顆樹，這樣就能從Set里面提取一個有序序列了。在實例化TreeSet時，我們可以給TreeSet指定一個比較器Comparator來指定樹形集中的元素順序。樹形集中提供了很多便捷的方法。

下面是一個TreeSet的例子。

/**
 * @author JackalTsc
 */
public class TestSet {

    public static void main(String[] args) {

        TreeSet<Integer> set = new TreeSet<>();

        set.add(1111);
        set.add(2222);
        set.add(3333);
        set.add(4444);
        set.add(5555);

        System.out.println(set.first()); // 輸出第一個元素
        System.out.println(set.lower(3333)); //小于3333的最大元素
        System.out.println(set.higher(2222)); //大于2222的最大元素
        System.out.println(set.floor(3333)); //不大于3333的最大元素
        System.out.println(set.ceiling(3333)); //不小于3333的最大元素

        System.out.println(set.pollFirst()); //刪除第一個元素
        System.out.println(set.pollLast()); //刪除最后一個元素
        System.out.println(set);
    }
}

3.Queue

隊列是一種先進先出的數據結構，元素在隊列末尾添加，在隊列頭部刪除。Queue接口擴展自Collection，并提供插入、提取、檢驗等操作。

Queue接口結構

上圖中，方法offer表示向隊列添加一個元素，poll()與remove()方法都是移除隊列頭部的元素，兩者的區別在于如果隊列為空，那么poll()返回的是null，而remove()會拋出一個異常。方法element()與peek()主要是獲取頭部元素，不刪除。

接口Deque，是一個擴展自Queue的雙端隊列，它支持在兩端插入和刪除元素，因為LinkedList類實現了Deque接口，所以通常我們可以使用LinkedList來創建一個隊列。PriorityQueue類實現了一個優先隊列，優先隊列中元素被賦予優先級，擁有高優先級的先被刪除。

/**
 * @author JackalTsc
 */
public class TestQueue {

    public static void main(String[] args) {

        Queue<String> queue = new LinkedList<>();

        queue.offer("aaaa");
        queue.offer("bbbb");
        queue.offer("cccc");
        queue.offer("dddd");

        while (queue.size() > 0) {
            System.out.println(queue.remove() + "");
        }
    }
}

三、Map接口

Map，圖，是一種存儲鍵值對映射的容器類，在Map中鍵可以是任意類型的對象，但不能有重復的鍵，每個鍵都對應一個值，真正存儲在圖中的是鍵值構成的條目。下面是接口Map的類結構。

接口Map的結構

從上面這張圖中我們可以看到接口Map提供了很多查詢、更新和獲取存儲的鍵值對的方法，更新包括方法clear()、put()、putAll()、remove()等等，查詢方法包括containsKey、containsValue等等。Map接口常用的有三個具體實現類，分別是HashMap、LinkedHashMap、TreeMap。

1.HashMap

HashMap是基于哈希表的Map接口的非同步實現，繼承自AbstractMap，AbstractMap是部分實現Map接口的抽象類。在平時的開發中，HashMap的使用還是比較多的。我們知道ArrayList主要是用數組來存儲元素的，LinkedList是用鏈表來存儲的，那么HashMap的實現原理是什么呢？先看下面這張圖：

HashMap原理.jpg

在之前的版本中，HashMap采用數組+鏈表實現，即使用鏈表處理沖突，同一hash值的鏈表都存儲在一個鏈表里。但是當鏈表中的元素較多，即hash值相等的元素較多時，通過key值依次查找的效率較低。而JDK1.8中，HashMap采用數組+鏈表+紅黑樹實現，當鏈表長度超過閾值（8）時，將鏈表轉換為紅黑樹，這樣大大減少了查找時間。

下面主要通過源碼介紹一下它的實現原理。

HashMap存儲元素的數組

transient Node<K,V>[] table;

數組的元素類型是Node<K,V>，Node<K,V>繼承自Map.Entry<K,V>，表示鍵值對映射。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        //構造函數 ( Hash值鍵值下一個節點 )
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

接下來我們看下HashMap的put操作。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
        boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;  //如果沒有初始化則初始化table
        if ((p = tab[i = (n - 1) & hash]) == null)
            //這里 (n-1)&hash 是根據hash值得到這個元素在數組中的位置（即下標）
            tab[i] = newNode(hash, key, value, null);
        //如果數組該位置上沒有元素，就直接將該元素放到此數組中的該位置上
        else {
            Node<K,V> e; K k;
            //第一節節點hash值同，且key值與插入key相同
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                //屬于紅黑樹處理沖突
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                /鏈表處理沖突
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //新增節點后如果節點個數到達閾值，則將鏈表轉換為紅黑樹
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //更新hash值和key值均相同的節點Value值
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

接下來我們看下HashMap的get操作。

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                //如果第一個節點是TreeNode,說明采用的是數組+紅黑樹結構處理沖突
    //遍歷紅黑樹，得到節點值
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && 
                                                       key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

到這里HashMap的大致實現原理應該很清楚了，有幾個需要關注的重點是：HashMap存儲元素的方式以及根據Hash值確定映射在數組中的位置還有JDK 1.8之后加入的紅黑樹的。

在HashMap中要找到某個元素，需要根據key的hash值來求得對應數組中的位置。對于任意給定的對象，只要它的hashCode()返回值相同，那么程序調用hash(int h)方法所計算得到的hash碼值總是相同的。我們首先想到的就是把hash值對數組長度取模運算，這樣一來，元素的分布相對來說是比較均勻的。但是，“模”運算的消耗還是比較大的，在HashMap中，(n - 1) & hash 用于計算對象應該保存在table數組的哪個索引處。HashMap底層數組的長度總是2的n次方，當數組長度為2的n次冪的時候，(n - 1) & hash 算得的index相同的幾率較小，數據在數組上分布就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用遍歷某個位置上的鏈表，這樣查詢效率也就較高了。

2.LinkedHashMap

LinkedHashMap繼承自HashMap，它主要是用鏈表實現來擴展HashMap類，HashMap中條目是沒有順序的，但是在LinkedHashMap中元素既可以按照它們插入圖的順序排序，也可以按它們最后一次被訪問的順序排序。

3.TreeMap

TreeMap基于紅黑樹數據結構的實現，鍵值可以使用Comparable或Comparator接口來排序。TreeMap繼承自AbstractMap，同時實現了接口NavigableMap，而接口NavigableMap則繼承自SortedMap。SortedMap是Map的子接口，使用它可以確保圖中的條目是排好序的。

在實際使用中，如果更新圖時不需要保持圖中元素的順序，就使用HashMap，如果需要保持圖中元素的插入順序或者訪問順序，就使用LinkedHashMap，如果需要使圖按照鍵值排序，就使用TreeMap。

四、其它集合類

上面主要對Java集合框架作了詳細的介紹，包括Collection和Map兩個接口及它們的抽象類和常用的具體實現類，下面主要介紹一下其它幾個特殊的集合類，Vector、Stack、HashTable、ConcurrentHashMap以及CopyOnWriteArrayList。

1.Vector

前面我們已經提到，Java設計者們在對之前的容器類進行重新設計時保留了一些數據結構，其中就有Vector。用法上，Vector與ArrayList基本一致，不同之處在于Vector使用了關鍵字synchronized將訪問和修改向量的方法都變成同步的了，所以對于不需要同步的應用程序來說，類ArrayList比類Vector更高效。

2.Stack

Stack，棧類，是Java2之前引入的，繼承自類Vector。

3.HashTable

HashTable和前面介紹的HashMap很類似，它也是一個散列表，存儲的內容是鍵值對映射，不同之處在于，HashTable是繼承自Dictionary的，HashTable中的函數都是同步的，這意味著它也是線程安全的，另外，HashTable中key和value都不可以為null。

上面的三個集合類都是在Java2之前推出的容器類，可以看到，盡管在使用中效率比較低，但是它們都是線程安全的。下面介紹兩個特殊的集合類。

4.ConcurrentHashMap

Concurrent，并發，從名字就可以看出來ConcurrentHashMap是HashMap的線程安全版。同HashMap相比，ConcurrentHashMap不僅保證了訪問的線程安全性，而且在效率上與HashTable相比，也有較大的提高。關于ConcurrentHashMap的設計，我將會在下一篇關于并發編程的博客中介紹，敬請關注。

5.CopyOnWriteArrayList

CopyOnWriteArrayList，是一個線程安全的List接口的實現，它使用了ReentrantLock鎖來保證在并發情況下提供高性能的并發讀取。

五、總結

到這里，對于Java集合框架的總結就結束了，還有很多集合類沒有在這里提到，更多的還是需要大家自己去查去用。通過閱讀源碼，查閱資料，收獲很大。

Java集合框架主要包括Collection和Map兩種類型。其中Collection又有3種子類型，分別是List、Set、Queue。Map中存儲的主要是鍵值對映射。
規則集Set中存儲的是不重復的元素，線性表中存儲可以包括重復的元素，Queue隊列描述的是先進先出的數據結構，可以用LinkedList來實現隊列。
效率上，規則集比線性表更高效。
ArrayList主要是用數組來存儲元素，LinkedList主要是用鏈表來存儲元素，HashMap的底層實現主要是借助數組+鏈表+紅黑樹來實現。
Vector、HashTable等集合類效率比較低但都是線程安全的。包java.util.concurrent下包含了大量線程安全的集合類，效率上有較大提升。

來自：http://www.jianshu.com/p/63e76826e852

本文由用戶 PhyllisMixo 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1474167415464.html

Java 鏈表 Java開發

Java - 集合框架完全解析

一、概述

二、Collection接口

三、Map接口

四、其它集合類

五、總結

相關經驗

相關資訊

相關文檔

目錄