04 java 集合框架匯總及使用場景

首先了解下Java提供的集合類的頂級接口，主要存在兩個體系：Collection接口和Map接口

Collection接口

Collection

Collection是最基本的集合接口，Collection接口抽象的定義了集合的基本操作：

public interface Collection<E> extends Iterable<E> {
    // Query Operations

    int size();

    boolean isEmpty();

    boolean contains(Object o);

    Iterator<E> iterator();

    Object[] toArray();

    <T> T[] toArray(T[] a);

    // Modification Operations
    boolean add(E e);

    boolean remove(Object o);

    // Bulk Operations
    boolean containsAll(Collection<?> c);

    boolean addAll(Collection<? extends E> c);

    boolean removeAll(Collection<?> c);

    /**
     * @since 1.8
     */
    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }
    ...
}

Map接口

Map接口儲存一組成對的鍵-值對象,提供key(鍵)到value(值)的映射,Map中的key不要求有序,不允許重復(fù).value同樣不要求有序,但可以重復(fù)拓巧。

public interface Map<K,V> {
    // Query Operations

    int size();

    boolean isEmpty();

    boolean containsKey(Object key);

    boolean containsValue(Object value);

    V get(Object key);

    // Modification Operations
    V put(K key, V value);

    V remove(Object key);

    // Bulk Operations
    void putAll(Map<? extends K, ? extends V> m);

    void clear();

    // Views
    Set<K> keySet();

    Collection<V> values();

    Set<Map.Entry<K, V>> entrySet();

    ...

    boolean equals(Object o);

    int hashCode();

    ...
}

Collection接口衍生出來的常用集合類：

List類集合

List接口繼承自Collection，用于定義以列表形式存儲的集合一死，List接口為集合中的每個對象分配了一個索引(index)肛度，標(biāo)記該對象在List中的位置，并可以通過index定位到指定位置的對象投慈。

List在Collection基礎(chǔ)上增加的主要方法包括：

get(int) - 返回指定index位置上的對象
add(E)/add(int, E) - 在List末尾/指定index位置上插入一個對象
set(int, E) - 替換置于List指定index位置上的對象
indexOf(Object) - 返回指定對象在List中的index位置
subList(int,int) - 返回指定起始index到終止index的子List對象

List接口的常用實現(xiàn)類：

ArrayList

ArrayList基于數(shù)組來實現(xiàn)集合的功能承耿，其內(nèi)部維護了一個可變長的對象數(shù)組冠骄，集合內(nèi)所有對象存儲于這個數(shù)組中，并實現(xiàn)該數(shù)組長度的動態(tài)伸縮.

ArrayList使用數(shù)組拷貝來實現(xiàn)指定位置的插入和刪除：

插入

ArrayList-insert
刪除

ArrayList-del

LinkedList

LinkedList基于鏈表來實現(xiàn)集合的功能加袋，其實現(xiàn)了靜態(tài)類Node凛辣，集合中的每個對象都由一個Node保存，每個Node都擁有到自己的前一個和后一個Node的引用.

LinkedList追加元素的過程示例：

LinkedList-insert

ArrayList vs LinkedList

ArrayList的隨機訪問更高锁荔，基于數(shù)組實現(xiàn)的ArrayList可直接定位到目標(biāo)對象蟀给，而LinkedList需要從頭Node或尾Node開始向后/向前遍歷若干次才能定位到目標(biāo)對象
LinkedList在頭/尾節(jié)點執(zhí)行插入/刪除操作的效率比ArrayList要高
由于ArrayList每次擴容的容量是當(dāng)前的1.5倍，所以LinkedList所占的內(nèi)存空間要更小一些
二者的遍歷效率接近阳堕，但需要注意跋理，遍歷LinkedList時應(yīng)用iterator方式，不要用get(int)方式恬总，否則效率會很低

Vector

Vector和ArrayList很像前普，都是基于數(shù)組實現(xiàn)的集合，它和ArrayList的主要區(qū)別在于

Vector是線程安全的壹堰，而ArrayList不是
由于Vector中的方法基本都是synchronized的拭卿，其性能低于ArrayList
Vector可以定義數(shù)組長度擴容的因子，ArrayList不能

CopyOnWriteArrayList

與 Vector一樣贱纠，CopyOnWriteArrayList也可以認(rèn)為是ArrayList的線程安全版峻厚，不同之處在于 CopyOnWriteArrayList在寫操作時會先復(fù)制出一個副本，在新副本上執(zhí)行寫操作谆焊，然后再修改引用惠桃。這種機制讓 CopyOnWriteArrayList可以對讀操作不加鎖，這就使CopyOnWriteArrayList的讀效率遠(yuǎn)高于Vector辖试。 CopyOnWriteArrayList的理念比較類似讀寫分離辜王，適合讀多寫少的多線程場景。但要注意罐孝，CopyOnWriteArrayList只能保證數(shù)據(jù)的最終一致性呐馆，并不能保證數(shù)據(jù)的實時一致性，如果一個寫操作正在進行中且并未完成莲兢，此時的讀操作無法保證能讀到這個寫操作的結(jié)果汹来。

二者均是線程安全的、基于數(shù)組實現(xiàn)的List
Vector是【絕對】線程安全的改艇，CopyOnWriteArrayList只能保證讀線程會讀到【已完成】的寫結(jié)果收班，但無法像Vector一樣實現(xiàn)讀操作的【等待寫操作完成后再讀最新值】的能力
CopyOnWriteArrayList讀性能遠(yuǎn)高于Vector，并發(fā)線程越多優(yōu)勢越明顯
CopyOnWriteArrayList占用更多的內(nèi)存空間

Map類集合

Map將key和value封裝至一個叫做Entry的對象中遣耍，Map中存儲的元素實際是Entry。只有在keySet()和values()方法被調(diào)用時炮车，Map才會將keySet和values對象實例化舵变。

HashMap

HashMap將Entry對象存儲在一個數(shù)組中酣溃，并通過哈希表來實現(xiàn)對Entry的快速訪問：

HashMap

由每個Entry中的key的哈希值決定該Entry在數(shù)組中的位置。以這種特性能夠?qū)崿F(xiàn)通過key快速查找到Entry纪隙，從而獲得該key對應(yīng)的value赊豌。在不發(fā)生哈希沖突的前提下，查找的時間復(fù)雜度是O(1)绵咱。
如果兩個不同的key計算出的index是一樣的碘饼，就會發(fā)生兩個不同的key都對應(yīng)到數(shù)組中同一個位置的情況，也就是所謂的哈希沖突悲伶。HashMap處理哈希沖突的方法是拉鏈法艾恼，也就是說數(shù)組中每個位置保存的實際是一個Entry鏈表，鏈表中每個Entry都擁有指向鏈表中后一個Entry的引用麸锉。在發(fā)生哈希沖突時钠绍，將沖突的Entry追加至鏈表的頭部。當(dāng)HashMap在尋址時發(fā)現(xiàn)某個key對應(yīng)的數(shù)組index上有多個Entry花沉，便會遍歷該位置上的 Entry鏈表柳爽，直到找到目標(biāo)的Entry。

Hashtable

Hashtable 可以說是HashMap的前身（Hashtable自JDK1.0就存在碱屁，而HashMap乃至整個Map接口都是JDK1.2引入的新特性）磷脯，其實現(xiàn)思路與HashMap幾乎完全一樣，都是通過數(shù)組存儲Entry娩脾，以key的哈希值計算Entry在數(shù)組中的index赵誓，用拉鏈法解決哈希沖突。二者最大的不同在于晦雨，Hashtable是線程安全的架曹，其提供的方法幾乎都是同步的。

ConcurrentHashMap

ConcurrentHashMap是HashMap的線程安全版（自JDK1.5引入）闹瞧，提供比Hashtable更高效的并發(fā)性能绑雄。
JDK1.8版本的ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)已經(jīng)接近HashMap，相對而言奥邮，ConcurrentHashMap只是增加了同步的操作來控制并發(fā)万牺，

JDK1.7版本的ReentrantLock+Segment+HashEntry，
JDK1.8版本中synchronized+CAS+HashEntry+紅黑樹,相對而言洽腺，總結(jié)如下思考

1.JDK1.8的實現(xiàn)降低鎖的粒度脚粟，JDK1.7版本鎖的粒度是基于Segment的，包含多個HashEntry蘸朋，而JDK1.8鎖的粒度就是HashEntry（首節(jié)點）

2.JDK1.8版本的數(shù)據(jù)結(jié)構(gòu)變得更加簡單核无，使得操作也更加清晰流暢，因為已經(jīng)使用synchronized來進行同步藕坯，所以不需要分段鎖的概念团南，也就不需要Segment這種數(shù)據(jù)結(jié)構(gòu)了噪沙，由于粒度的降低，實現(xiàn)的復(fù)雜度也增加了 3.JDK1.8使用紅黑樹來優(yōu)化鏈表吐根，基于長度很長的鏈表的遍歷是一個很漫長的過程正歼，而紅黑樹的遍歷效率是很快的，代替一定閾值的鏈表拷橘，這樣形成一個最佳拍檔

4.JDK1.8為什么使用內(nèi)置鎖synchronized來代替重入鎖ReentrantLock局义，我覺得有以下幾點

1.因為粒度降低了，在相對而言的低粒度加鎖方式冗疮，synchronized并不比ReentrantLock差萄唇，在粗粒度加鎖中         ReentrantLock可能通過Condition來控制各個低粒度的邊界，更加的靈活赌厅，而在低粒度中穷绵，Condition的優(yōu)           勢就沒有了

2.JVM的開發(fā)團隊從來都沒有放棄synchronized，而且基于JVM的synchronized優(yōu)化空間更大特愿，使用內(nèi)嵌的           關(guān)鍵字比使用API更加自然

3.在大量的數(shù)據(jù)操作下仲墨，對于JVM的內(nèi)存壓力，基于API的ReentrantLock會開銷更多的內(nèi)存揍障，雖然不是瓶             頸目养，但是也是一個選擇依據(jù)

HashMap vs Hashtable vs ConcurrentHashMap

三者在數(shù)據(jù)存儲層面的機制原理基本一致
HashMap不是線程安全的，多線程環(huán)境下除了不能保證數(shù)據(jù)一致性之外毒嫡，還有可能在rehash階段引發(fā)Entry鏈表成環(huán)癌蚁，導(dǎo)致死循環(huán)
Hashtable是線程安全的，能保證絕對的數(shù)據(jù)一致性兜畸，但性能是問題努释，并發(fā)線程越多，性能越差
ConcurrentHashMap 也是線程安全的咬摇，使用分離鎖和volatile等方法極大地提升了讀寫性能伐蒂，同時也能保證在絕大部分情況下的數(shù)據(jù)一致性。但其不能保證絕對的數(shù)據(jù)一致性肛鹏，在一個線程向Map中加入Entry的操作沒有完全完成之前逸邦，其他線程有可能讀不到新加入的Entry

LinkedHashMap

LinkedHashMap與HashMap非常類似，唯一的不同在于前者的Entry在HashMap.Entry的基礎(chǔ)上增加了到前一個插入和后一個插入的Entry的引用在扰，以實現(xiàn)能夠按Entry的插入順序進行遍歷缕减。

TreeMap

TreeMap是基于紅黑樹實現(xiàn)的Map結(jié)構(gòu)，其Entry類擁有到左/右葉子節(jié)點和父節(jié)點的引用芒珠，同時還記錄了自己的顏色：


static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left = null;
        Entry<K,V> right = null;
        Entry<K,V> parent;
        boolean color = BLACK;
 
}

紅黑樹實際是一種算法復(fù)雜但高效的平衡二叉樹桥狡，具備二叉樹的基本性質(zhì)，即任何節(jié)點的值大于其左葉子節(jié)點，小于其右葉子節(jié)點裹芝，利用這種特性呈宇，TreeMap能夠?qū)崿F(xiàn)Entry的排序和快速查找。
TreeMap的Entry是有序的局雄，所以提供了一系列方便的功能，比如獲取以升序或降序排列的KeySet(EntrySet)存炮、獲取在指定key(Entry)之前/之后的key(Entry)等等炬搭。適合需要對key進行有序操作的場景。

ConcurrentSkipListMap

ConcurrentSkipListMap同樣能夠提供有序的Entry排列穆桂，但其實現(xiàn)原理與TreeMap不同宫盔，是基于跳表(SkipList)的.
ConcurrentSkipListMap由一個多級鏈表實現(xiàn)，底層鏈上擁有所有元素享完，逐級上升的過程中每個鏈的元素數(shù)遞減灼芭。在查找時從頂層鏈出發(fā)，按先右后下的優(yōu)先級進行查找般又，從而實現(xiàn)快速尋址彼绷。

static class Index<K,V> {
        final Node<K,V> node;
        final Index<K,V> down;//下引用
        volatile Index<K,V> right;//右引用
}

與TreeMap不同，ConcurrentSkipListMap在進行插入茴迁、刪除等操作時寄悯，只需要修改影響到的節(jié)點的右引用，而右引用又是volatile的堕义，所以ConcurrentSkipListMap是線程安全的猜旬。但ConcurrentSkipListMap與ConcurrentHashMap一樣，不能保證數(shù)據(jù)的絕對一致性倦卖，在某些情況下有可能無法讀到正在被插入的數(shù)據(jù)洒擦。

TreeMap vs ConcurrentSkipListMap

二者都能夠提供有序的Entry集合
二者的性能相近，查找時間復(fù)雜度都是O(logN)
ConcurrentSkipListMap會占用更多的內(nèi)存空間
ConcurrentSkipListMap是線程安全的怕膛，TreeMap不是

Set類集合

Set 接口繼承Collection熟嫩，用于存儲不含重復(fù)元素的集合。幾乎所有的Set實現(xiàn)都是基于同類型Map的嘉竟，簡單地說邦危，Set是閹割版的Map。每一個Set內(nèi)都有一個同類型的Map實例（CopyOnWriteArraySet除外舍扰，它內(nèi)置的是CopyOnWriteArrayList實例）倦蚪，Set把元素作為key存儲在自己的Map實例中，value則是一個空的Object边苹。Set的常用實現(xiàn)也包括 HashSet陵且、TreeSet、ConcurrentSkipListSet等，原理和對應(yīng)的Map實現(xiàn)完全一致.

Queue/Deque類集合

Queue和Deque接口繼承Collection接口慕购，實現(xiàn)FIFO（先進先出）的集合聊疲。二者的區(qū)別在于，Queue只能在隊尾入隊沪悲，隊頭出隊获洲，而Deque接口則在隊頭和隊尾都可以執(zhí)行出/入隊操作

Queue接口常用方法：

add(E)/offer(E)：入隊，即向隊尾追加元素殿如，二者的區(qū)別在于如果隊列是有界的贡珊，add方法在隊列已滿的情況下會拋出IllegalStateException，而offer方法只會返回false
remove()/poll()：出隊涉馁，即從隊頭移除1個元素门岔，二者的區(qū)別在于如果隊列是空的，remove方法會拋出NoSuchElementException烤送，而poll只會返回null
element()/peek()：查看隊頭元素寒随，二者的區(qū)別在于如果隊列是空的，element方法會拋出NoSuchElementException帮坚，而peek只會返回null

Deque接口常用方法：

addFirst(E) / addLast(E) / offerFirst(E) / offerLast(E)
removeFirst() / removeLast() / pollFirst() / pollLast()
getFirst() / getLast() / peekFirst() / peekLast()
removeFirstOccurrence(Object) / removeLastOccurrence(Object)

Queue接口的常用實現(xiàn)類：

ConcurrentLinkedQueue

ConcurrentLinkedQueue是基于鏈表實現(xiàn)的隊列妻往，隊列中每個Node擁有到下一個Node的引用：

private static class Node<E> {
        volatile E item;
        volatile Node<E> next;
}

由于Node類的成員都是volatile的，所以ConcurrentLinkedQueue自然是線程安全的试和。能夠保證入隊和出隊操作的原子性和一致性蒲讯，但在遍歷和size()操作時只能保證數(shù)據(jù)的弱一致性。

LinkedBlockingQueue

與ConcurrentLinkedQueue不同灰署，LinkedBlocklingQueue是一種無界的阻塞隊列判帮。所謂阻塞隊列，就是在入隊時如果隊列已滿溉箕，線程會被阻塞晦墙，直到隊列有空間供入隊再返回；同時在出隊時肴茄，如果隊列已空晌畅，線程也會被阻塞，直到隊列中有元素供出隊時再返回寡痰。LinkedBlocklingQueue同樣基于鏈表實現(xiàn)抗楔，其出隊和入隊操作都會使用ReentrantLock進行加鎖。所以本身是線程安全的拦坠，但同樣的连躏，只能保證入隊和出隊操作的原子性和一致性，在遍歷時只能保證數(shù)據(jù)的弱一致性贞滨。

ArrayBlockingQueue
ArrayBlockingQueue是一種有界的阻塞隊列入热，基于數(shù)組實現(xiàn)。其同步阻塞機制的實現(xiàn)與LinkedBlocklingQueue基本一致，區(qū)別僅在于前者的生產(chǎn)和消費使用同一個鎖勺良，后者的生產(chǎn)和消費使用分離的兩個鎖绰播。

ConcurrentLinkedQueue vsLinkedBlocklingQueue vs ArrayBlockingQueue

ConcurrentLinkedQueue是非阻塞隊列，其他兩者為阻塞隊列
三者都是線程安全的
LinkedBlocklingQueue是無界的尚困，適合實現(xiàn)不限長度的隊列蠢箩， ArrayBlockingQueue適合實現(xiàn)定長的隊列

SynchronousQueue

SynchronousQueue算是JDK實現(xiàn)的隊列中比較奇葩的一個，它不能保存任何元素事甜，size永遠(yuǎn)是0忙芒，peek()永遠(yuǎn)返回null。向其中插入元素的線程會阻塞讳侨，直到有另一個線程將這個元素取走，反之從其中取元素的線程也會阻塞奏属，直到有另一個線程插入元素跨跨。

這種實現(xiàn)機制非常適合傳遞性的場景。也就是說如果生產(chǎn)者線程需要及時確認(rèn)到自己生產(chǎn)的任務(wù)已經(jīng)被消費者線程取走后才能執(zhí)行后續(xù)邏輯的場景下囱皿，適合使用SynchronousQueue勇婴。

PriorityQueue & PriorityBlockingQueue

這兩種Queue并不是FIFO隊列，而是根據(jù)元素的優(yōu)先級進行排序嘱腥，保證最小的元素最先出隊耕渴，也可以在構(gòu)造隊列時傳入Comparator實例，這樣PriorityQueue就會按照Comparator實例的要求對元素進行排序齿兔。
PriorityQueue是非阻塞隊列橱脸，也不是線程安全的，PriorityBlockingQueue是阻塞隊列分苇，同時也是線程安全的添诉。
Deque 的實現(xiàn)類包括LinkedList（前文已描述過）、ConcurrentLinkedDeque医寿、LinkedBlockingDeque栏赴，其實現(xiàn)機制與前文所述的ConcurrentLinkedQueue和LinkedBlockingQueue非常類似