引言

相信大家在學習JavaSE時都曾接觸過容器這一內(nèi)容煎娇，一般Java中的容器可分為四類：Map二庵、List贪染、Queue以及Set容器，而在使用過程中催享，對于ArrayList抑进、HashMap等這類容器都是經(jīng)常使用的，但問題在于這些容器在并發(fā)環(huán)境下都會存在線程安全問題。所以當我們在多線程環(huán)境下使用容器時，一般會使用Vector历涝、HashTable來代替之前的ArrayList薪缆、HashMap，或者通過如下幾個Collections提供的方法來將容器轉(zhuǎn)換線程安全的：

// 將一個List轉(zhuǎn)換為線程安全的List
Collections.synchronizedList(new ArrayList<E>());
// 將一個Set轉(zhuǎn)換為線程安全的Set
Collections.synchronizedSet(new HashSet<E>());
// 將一個map轉(zhuǎn)換為線程安全的map
Collections.synchronizedMap(new HashMap<K,V>());

但是不管是如上的哪種方式炬称，其底層都是通過對所有方法添加synchronized關(guān)鍵字修飾保證的線程安全汁果。但問題就在于：雖然解決了線程安全問題，但因為都是通過synchronized的對象鎖保證的玲躯，所以當多條線程在同時操作容器時則需要阻塞排隊据德，性能堪憂！
舉個例子直觀感受一下：

Map map = new HashMap<String,Object>();  
Map syncMap = Collections.synchronizedMap(map);  
T1線程：syncMap.put("竹子","熊貓");  
T2線程：syncMap.get("xxx");  

ok~跷车，在這個案例中棘利，假設(shè)T1,T2兩條線程是在并發(fā)執(zhí)行的，那么T1,T2線程在這種情況下是不能同時執(zhí)行的朽缴，因為T2線程需要等到T1線程put完成釋放鎖資源后善玫，才能獲取鎖資源進行g(shù)et操作。為什么密强？如下：

// Collections類 → synchronizedMap方法
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
    // 將傳入的不安全map封裝成了SynchronizedMap對象
    return new SynchronizedMap<>(m);
}

// Collections類 → SynchronizedMap內(nèi)部類
private static class SynchronizedMap<K,V>
        implements Map<K,V>, Serializable {
    
    private final Map<K,V> m; // 傳入的線程不安全容器
    final Object      mutex; // 對象鎖
    
    // SynchronizedMap構(gòu)造方法
    SynchronizedMap(Map<K,V> m) {
        this.m = Objects.requireNonNull(m);
        mutex = this; // 對象鎖為this（當前實例對象鎖）
    }
    
    // 只是在外面使用synchronized包裹后再次調(diào)用了原有的get方法
    public V get(Object key) {
        synchronized (mutex) {return m.get(key);}
    }
    // 只是在外面使用synchronized包裹后再次調(diào)用了原有的put方法
    public V put(K key, V value) {
        synchronized (mutex) {return m.put(key, value);}
    }
    // ..........
}        

顯而易見茅郎。從如上源碼中觀察可以得知，當線程想操作容器時或渤，必須先獲取當前容器對象的實例鎖系冗。ok~，那么關(guān)于Vector薪鹦、HashTable就不再展開贅述了掌敬，原理大致相同，因為這兩個類中的所有方法都是使用synchronized關(guān)鍵字修飾距芬。

如果對于synchronized不太了解的小伙伴可以參考之前的文章：《Synchronized關(guān)鍵字實現(xiàn)原理剖析》

而在JDK1.5之后涝开，JUC并發(fā)包中，則推出了三個系列的并發(fā)容器：阻塞隊列容器框仔、寫時復制容器以及分段容器舀武。接下來我們逐步從三類容器的簡單使用到實現(xiàn)原理依次分析。

一离斩、阻塞隊列容器

阻塞隊列與普通隊列最大的不同點在于：支持隊列內(nèi)元素的阻塞添加與阻塞彈出银舱，也就是代表著當在往隊列中添加元素時瘪匿，如果隊列已經(jīng)滿了，那么當前添加元素的線程則會阻塞寻馏，直至隊列彈出一個元素后才會喚醒棋弥，并將元素添加至隊列中，阻塞彈出同理诚欠，如若隊列為空顽染，那么會阻塞至隊列中有元素為止。在JUC中主要提供了兩類阻塞隊列：單向阻塞隊列以及雙向阻塞隊列轰绵，在JUC包分別對應著BlockingQueue粉寞、BlockingDeque兩個接口，而在Java中的隊列總覽如下：

• 1左腔、BlockingQueue單向FIFO先進先出阻塞隊列：
  • ①ArrayBlockingQueue：由數(shù)組結(jié)構(gòu)支持的有界隊列
  • ②LinkedBlockingQueue：由鏈表結(jié)構(gòu)支持的可選有界隊列
  • ③PriorityBlockingQueue：由最小二叉堆(優(yōu)先級堆)結(jié)構(gòu)支持的無界優(yōu)先級隊列
  • ④DelayQueue：由最小二叉堆(優(yōu)先級堆)結(jié)構(gòu)支持且基于時間的調(diào)度隊列
  • ⑤SynchronousQueue：實現(xiàn)簡單聚集(rendezvous)機制的同步阻塞交換隊列(只存一個元素)
  • ⑥LinkedTransferQueue：由鏈表結(jié)構(gòu)支持的無界隊列(1-②唧垦、1-⑤與3-①優(yōu)點組成的超集)
  • ⑦DelayWorkQueue：由最小二叉堆(優(yōu)先級堆)結(jié)構(gòu)支持的定時線程池定制版無界優(yōu)先級隊列
• 2、BlockingDeque雙向阻塞隊列：
  • ①LinkedBlockingDeque：由鏈表結(jié)構(gòu)支持的可選雙向有界隊列
• 3液样、其他隊列（非阻塞隊列）：
  • ①ConcurrentLinkedQueue：由鏈表結(jié)構(gòu)支持的并發(fā)無界隊列
  • ②PriorityQueue：由最小二叉堆(優(yōu)先級堆)結(jié)構(gòu)支持無界隊列
  • ③ConcurrentLinkedDeque：由鏈表結(jié)構(gòu)支持的并發(fā)雙向無界隊列
  • ④ArrayDeque：由數(shù)組結(jié)構(gòu)支持的雙向有界隊列

如上便是Java中提供的隊列容器振亮，簡單解釋一下名詞：有界、無界鞭莽、單向坊秸、雙向：

• 有界：代表隊列可以設(shè)置固定長度，隊列中元素數(shù)量達到隊列最大長度時則不能入列
• 無界：代表隊列不需要設(shè)長度撮抓，在內(nèi)存允許的情況下可以一直添加元素直至溢出妇斤。默認是Integer.MAX_VALUE長度，只是對于使用者而言丹拯，相當于無限大
• 單向：遵循先進先出FIFO原則的隊列
• 雙向：兩端都可以插入/彈出元素的隊列站超，可以使用雙向隊列實現(xiàn)棧結(jié)構(gòu)

如上的不同類型隊列區(qū)別主要體現(xiàn)在存儲結(jié)構(gòu)以及對元素操作上不同，但是對于阻塞操作的原理都是類似的乖酬。而Java中的阻塞隊列都實現(xiàn)自BlockingQueue接口死相，也包括BlockingDeque接口也繼承自BlockingQueue接口，所以下面我們簡單看看BlockingQueue接口的定義：

public interface BlockingQueue<E> extends Queue<E> {
    // 如果隊列未滿則將元素e插入隊列尾部咬像，插入成功返回true算撮，
    // 如果隊列已滿，則拋IllegalStateException異常
    boolean add(E e); 
    
    // 如果隊列未滿則將元素e插入隊列尾部县昂，插入成功返回true
    boolean offer(E e);
    
    // 如果隊列未滿則將元素e插入隊列尾部肮柜，插入成功返回true，
    // 如果該隊列已滿倒彰，則在指定的等待時間之內(nèi)阻塞至可用空間出現(xiàn)
    // 如果超出指定時間還未將元素插入隊列則返回（可響應線程中斷）
    boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException; 
    
    // 將元素插入隊列的尾部审洞，如果該隊列已滿，則一直阻塞等待
    void put(E e) throws InterruptedException; 
    
    // 獲取并移除隊列的頭部元素待讳，如果沒有元素則阻塞等待芒澜， 
    // 直到有線程添加元素后再喚醒等待線程執(zhí)行該操作 
    E take() throws InterruptedException; 
    
    // 獲取并移除隊列的頭部元素仰剿，在指定的等待時間之內(nèi)阻塞等待獲取元素，
    // 如果超出指定時間還未獲取到元素則返回（可響應線程中斷）
    E poll(long timeout, TimeUnit unit) throws InterruptedException; 
    
    // 從隊列中移除某個指定元素痴晦，移除成功返回true南吮，沒有該元素則返回false
    boolean remove(Object o); 
    
    // 獲取隊列剩余的可用空位
    // 假設(shè)隊列長度為10，已有3個元素誊酌，調(diào)用該方法則返回7
    int remainingCapacity();
    
    // 檢查隊列中是否存在指定元素部凑，存在返回true，反之false
    public boolean contains(Object o);
    
    // 一次性從隊列中獲取所有可用元素
    int drainTo(Collection<? super E> c);
    
    // 一次性從隊列中獲取指定個數(shù)的可用元素
    int drainTo(Collection<? super E> c, int maxElements);
}

總的來說碧浊，阻塞隊列中的方法可分為三類：增刪查砚尽，在使用阻塞隊列時一般都是通過這三類方法操作隊列容器，當然put/take類型的操作在有些地方也被稱為：生產(chǎn)/消費辉词、新增/彈出、添加/獲取等猾骡，但是表達的意思都是一致的瑞躺。接下來看個阻塞隊列的簡單使用案例：

public class BlockingQueueDemo {
    // 創(chuàng)建一個阻塞隊列容器
    private static ArrayBlockingQueue<String> arrayBlockingQueue
            = new ArrayBlockingQueue<String>(5);
//    LinkedBlockingQueue linkedBlockingQueue = new LinkedBlockingQueue();
//    PriorityBlockingQueue priorityBlockingQueue = new PriorityBlockingQueue();
//    DelayQueue delayQueue = new DelayQueue();
//    SynchronousQueue synchronousQueue = new SynchronousQueue();
//    LinkedTransferQueue linkedTransferQueue = new LinkedTransferQueue();
//    LinkedBlockingDeque linkedBlockingDeque = new LinkedBlockingDeque();

    public static void main(String[] args) {
        //創(chuàng)建生產(chǎn)者與消費者任務
        Producer producerTask = new Producer(arrayBlockingQueue);
        Consumer consumerTask = new Consumer(arrayBlockingQueue);
        
        // 生產(chǎn)者線程組
        Thread T1 = new Thread(producerTask, "T1");
        Thread T2 = new Thread(producerTask, "T2");

        // 消費者線程組
        Thread Ta = new Thread(consumerTask, "Ta");
        Thread Tb = new Thread(consumerTask, "Tb");

        T1.start();
        T2.start();
        Ta.start();
        Tb.start();
    }
    
    // 生產(chǎn)者
    static class Producer implements Runnable {
        private BlockingQueue<String> blockingQueue;

        private Producer(BlockingQueue<String> b) {
            this.blockingQueue = b;
        }

        @Override
        public void run() {
            for (; ; )
                producer();
        }
        
        private void producer() {
            String task = "竹子-" + UUID.randomUUID().toString();
            try {
                blockingQueue.put(task);
                System.out.println(Thread.currentThread().getName()
                        + "生產(chǎn)任務：" + task);
                Thread.sleep(100);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
    
    //消費者
    static class Consumer implements Runnable {
        private BlockingQueue<String> blockingQueue;

        private Consumer(BlockingQueue<String> b) {
            this.blockingQueue = b;
        }

        @Override
        public void run() {
            for (; ; )
                consumer();
        }

        private void consumer() {
            try {
                Thread.sleep(200);
                String task = blockingQueue.take();
                System.out.println(Thread.currentThread().getName()
                        + "消費任務：" + task);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
/* *
 * 執(zhí)行結(jié)果：
 *    T1生產(chǎn)任務：竹子-f1ae18fc-de1c-49f2-b9c0-3b3c45ae2931
 *    Tb消費任務：竹子-46b45b67-4a1b-481a-80eb-3627d0c56a15
 *    T2生產(chǎn)任務：竹子-46b45b67-4a1b-481a-80eb-3627d0c56a15
 *    Ta消費任務：竹子-f1ae18fc-de1c-49f2-b9c0-3b3c45ae2931
 *    .........
 * */
}

上述代碼即是一個生產(chǎn)者-消費者案例，使用阻塞隊列來實現(xiàn)該案例會比之前的wait/notify兴想、condition簡單許多幢哨，通過put()方法將任務加入隊列完成生產(chǎn)任務，通過take()方法從隊列中獲取任務完成消費任務嫂便，而當隊列中元素已滿時生產(chǎn)者阻塞停止生產(chǎn)捞镰，而當隊列為空時，消費的線程則會阻塞等待毙替，直至新的任務到來岸售。

上述案例中，使用了ArrayBlockingQueue這個阻塞隊列完成了生產(chǎn)者-消費者案例厂画，而關(guān)于其他的阻塞隊列則不再演示凸丸，使用方式都近乎相似。ok~袱院，簡單了解了阻塞隊列的使用之后屎慢，接著繼續(xù)來看看它的實現(xiàn)。

1.1忽洛、ArrayBlockingQueue原理分析

先來看看ArrayBlockingQueue內(nèi)部的成員：

public class ArrayBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {
    // ArrayBlockingQueue構(gòu)造器：指定隊列長度
    public ArrayBlockingQueue(int capacity) {
        this(capacity, false);
    }
    // 構(gòu)造器：指定隊列長度與公平模式
    public ArrayBlockingQueue(int capacity, boolean fair) {
        if (capacity <= 0)
            throw new IllegalArgumentException();
        this.items = new Object[capacity];
        lock = new ReentrantLock(fair);
        notEmpty = lock.newCondition();
        notFull =  lock.newCondition();
    }
    
    // 內(nèi)部存儲元素的數(shù)組結(jié)構(gòu)
    final Object[] items;

    // 記錄獲取元素的下標（take腻惠、poll、peek欲虚、remove方法都會用到）
    int takeIndex;

    // 記錄添加元素的下標（put集灌、offer、add方法都會用到）
    int putIndex;

    // 當前隊列中元素的數(shù)量
    int count;

    // 控制并發(fā)的ReentrantLock鎖對象
    final ReentrantLock lock;

    // 用于控制獲取元素線程的condition對象
    private final Condition notEmpty;

    // 用于控制添加元素線程的condition對象
    private final Condition notFull;

    // 迭代器對象
    transient Itrs itrs = null;
}

ArrayBlockingQueue內(nèi)部使用一個數(shù)組成員items存儲所有的隊列元素苍在，分別使用三個數(shù)值：takeIndex绝页、putIndex以及count記錄添加與獲取元素的數(shù)組位置與隊列中的元素個數(shù)荠商，同時內(nèi)部使用ReentrantLock解決線程安全問題，用兩個Condition對象：notEmpty续誉、notFull控制“寫”線程與“讀”線程的阻塞莱没。同時還有一點需要額外注意：ArrayBlockingQueue的阻塞操作是基于ReentrantLock與Condition實現(xiàn)的，所以在創(chuàng)建ArrayBlockingQueue隊列對象時也可以指定為公平/非公平模式酷鸦，所以公平模式則是指：先阻塞的線程一定先操作隊列饰躲。ok~，接著先看看put()方法的實現(xiàn)：

// ArrayBlockingQueue類 → put()方法
public void put(E e) throws InterruptedException {
    // 檢查元素是否為空臼隔，為空則拋出空指針異常
    checkNotNull(e);
    // 獲取ReentrantLock成員鎖對象
    final ReentrantLock lock = this.lock;
    // 可響應中斷式獲取鎖
    lock.lockInterruptibly();
    try {
        // 如果隊列元素已滿
        while (count == items.length)
            // 阻塞當前添加元素的線程
            notFull.await();
        // 如果隊列元素未滿則執(zhí)行添加操作
        enqueue(e);
    } finally {
        // 釋放鎖
        lock.unlock();
    }
}

ArrayBlockingQueue.put()方法實現(xiàn)比較簡單嘹裂，總體執(zhí)行流程如下：

• ①判斷元素是否為空，為空拋出空指針異常
• ②獲取鎖資源（保證多線程情況下容器操作的安全問題）
• ③判斷隊列是否已滿摔握，如果滿了則阻塞當前執(zhí)行線程
• ④如果未滿則調(diào)用enqueue(e);方法進行添加操作

接著我們繼續(xù)看看ArrayBlockingQueue.enqueue()方法：

// ArrayBlockingQueue類 → enqueue()方法
private void enqueue(E x) {
    // 獲取存儲元素的items數(shù)組成員
    final Object[] items = this.items;
    // 將元素放在數(shù)組的putIndex下標位置
    items[putIndex] = x;
    // 對putIndex+1寄狼，+1后如果=數(shù)組長度了則重置為0
    if (++putIndex == items.length)
        putIndex = 0;
    // 記錄隊列元素的數(shù)值count+1
    count++;
    // 喚醒等待獲取隊列元素的線程
    notEmpty.signal();
}

總的來說邏輯并不算復雜，在ArrayBlockingQueue.enqueue()方法中氨淌，首先獲取了存儲隊列元素的數(shù)組成員items泊愧，然后通過成員putIndex記錄的隊列插入下標位置，將入?yún)⒅械脑胤旁诹嗽撐恢蒙鲜⒄o接著再對putIndex删咱、count成員進行了更新，同時喚醒了阻塞等待獲取元素的線程豪筝。不過值得注意的一點是：當記錄隊列插入下標的成員putIndex自增后等于數(shù)組長度時痰滋，會重置putIndex為0，道理也非常簡單续崖，因為如果不置為0敲街，下次插入元素時就會下標越界了。

ok~严望，接著再來看看take()方法的實現(xiàn)：

// ArrayBlockingQueue類 → take()方法
public E take() throws InterruptedException {
    // 獲取成員ReentrantLock鎖對象
    final ReentrantLock lock = this.lock;
    // 可響應中斷式獲取鎖
    lock.lockInterruptibly();
    try {
        // 如果隊列為空
        while (count == 0)
            // 通過condition對象阻塞當前獲取元素的線程
            notEmpty.await();
        // 如果隊列不為空則獲取元素
        return dequeue();
    } finally {
        // 釋放鎖
        lock.unlock();
    }
}

ArrayBlockingQueue.take()獲取隊列元素的方法與前面的ArrayBlockingQueue.put()
插入隊列元素的方法相比聪富，寫法大體來說是一致的，只不過前面的put()判斷的是隊列是否已滿著蟹，已滿則阻塞當前線程墩蔓，而現(xiàn)在的take()方法則是判斷的隊列是否為空，為空則阻塞當前獲取元素的線程萧豆。接下來再看看ArrayBlockingQueue.dequeue()方法：

// ArrayBlockingQueue類 → dequeue()方法
private E dequeue() {
    // 獲取存儲隊列元素的成員數(shù)組items
    final Object[] items = this.items;
    @SuppressWarnings("unchecked")
    // 獲取數(shù)組中下標為taseIndex位置上的元素
    E x = (E) items[takeIndex];
    // 獲取后清除該位置的元素
    items[takeIndex] = null;
    // 對takeIndex進行+1
    if (++takeIndex == items.length)
        // 如果takeIndex=數(shù)組長度時則將takeIndex置為0
        takeIndex = 0;
    // 記錄隊列元素數(shù)量的數(shù)值count-1
    count--;
    // 同時更新迭代器中的元素
    if (itrs != null)
        itrs.elementDequeued();
    // 當取出一個元素后喚醒添加操作的線程
    notFull.signal();
    // 返回
    return x;
}

ArrayBlockingQueue.dequeue()方法邏輯也比較簡單奸披，如下：

• ①獲取存儲隊列元素的數(shù)組成員
• ②根據(jù)takeIndex記錄的隊列下標獲取該位置上的元素
• ③清空數(shù)組下標為takeIndex上的元素數(shù)據(jù)
• ④更新成員takeIndex以及count的數(shù)值
• ⑤同步更新迭代器中的元素數(shù)據(jù)
• ⑥返回獲取到的隊列元素對象

至此整個ArrayBlockingQueue阻塞隊列的添加/獲取元素的原理分析完畢，因為ArrayBlockingQueue底層采用數(shù)組作為存儲結(jié)構(gòu)的原理涮雷，所以源碼分析起來實則并不難阵面。重點值得我們注意的是：ArrayBlockingQueue中的阻塞是基于ReentrantLock與Condition實現(xiàn)的，使用ReentrantLock保證線程安全，使用Condition來完成添加/獲取元素的阻塞操作样刷。ok~仑扑，接著再來分析一下另外一個阻塞隊列：LinkedBlockingQueue的實現(xiàn)原理。

對于Condition原理不太清楚的小伙伴可以參考之前的文章：《(五)深入剖析并發(fā)之AQS獨占鎖&重入鎖ReetrantLock及Condition實現(xiàn)原理》

1.2置鼻、LinkedBlockingQueue原理分析

關(guān)于阻塞隊列的阻塞實現(xiàn)原理實則比較簡單镇饮，明白了ReentrantLock的多條件等待Condition原理即可理解隊列的阻塞原理的實現(xiàn)過程。而關(guān)于Java中其他類型的阻塞隊列箕母，阻塞的實現(xiàn)幾乎大同小異储藐，區(qū)別就在于底層的存儲結(jié)構(gòu)不同以及操作方法有細微的差別。接下來再分析一個阻塞隊列：LinkedBlockingQueue的實現(xiàn)原理嘶是。LinkedBlockingQueue是一個比較有意思的隊列容器钙勃，因為其中采用了讀寫分離的思想提升了容器整體的吞吐量。先來簡單看看其內(nèi)部成員：

public class LinkedBlockingQueue<E> extends AbstractQueue<E>
        implements BlockingQueue<E>, java.io.Serializable {
    // 構(gòu)造器：可指定隊列長度
    public LinkedBlockingQueue(int capacity) {
       // 如果指定的隊列長度為0或小于0則拋出異常
       if (capacity <= 0) throw new IllegalArgumentException();
       // 將傳入的指定長度賦值給capacity成員
       this.capacity = capacity;
       // 初始化空的節(jié)點作為隊列頭節(jié)點
       last = head = new Node<E>(null);
   }
   // 構(gòu)造器：不指定長度默認則為Integer.MAX_VALUE
    public LinkedBlockingQueue() {
        this(Integer.MAX_VALUE);
    }
    
    // LinkedBlockingQueue類 → Node內(nèi)部類
    static class Node<E> {
        // 當前節(jié)點存儲的元素本身
        E item;
        // 當前節(jié)點的后繼節(jié)點
        Node<E> next;
        // 構(gòu)造器
        Node(E x) { item = x; }
    }
    
    // 隊列的長度（可以指定長度聂喇，默認為Integer.MAX_VALUE）
    private final int capacity;
    
    // 原子計數(shù)器：記錄隊列中元素的個數(shù)
    private final AtomicInteger count = new AtomicInteger();
    
    // 隊列(內(nèi)部鏈表)的頭節(jié)點
    transient Node<E> head;
    
    // 隊列(內(nèi)部鏈表)的尾節(jié)點
    private transient Node<E> last;
    
    // 讀鎖：線程從隊列中獲取元素時辖源，使用這把鎖
    private final ReentrantLock takeLock = new ReentrantLock();
    
    // 獲取元素時，隊列為空希太，線程加入該condition隊列等待
    private final Condition notEmpty = takeLock.newCondition();
    
    // 寫鎖：線程向隊列中添加元素時同木，使用這把鎖
    private final ReentrantLock putLock = new ReentrantLock();
    
    // 添加元素時，隊列已滿跛十，線程加入該condition隊列等待
    private final Condition notFull = putLock.newCondition();
}

如上，LinkedBlockingQueue因為是基于鏈表結(jié)構(gòu)實現(xiàn)的隊列容器秕硝，所以通過Node內(nèi)部類構(gòu)建了一個單向鏈表芥映，同時使用AtomicInteger原子類記錄隊列中元素數(shù)量，head远豺、last分別指向隊列的頭部以及尾部奈偏，同時使用takeLock、putLock兩個ReentrantLock控制隊列容器的讀寫并發(fā)訪問躯护。

OK~惊来，接下來看看put()方法：

// LinkedBlockingQueue類 → put()方法
public void put(E e) throws InterruptedException {
    // 如果元素為空則拋出空指針異常
    if (e == null) throw new NullPointerException();
    int c = -1;
    // 將要添加的元素封裝成node節(jié)點
    Node<E> node = new Node<E>(e);
    // 拿到寫鎖
    final ReentrantLock putLock = this.putLock;
    // 獲取當前隊列的元素數(shù)量
    final AtomicInteger count = this.count;
    // 可響應中斷式加鎖
    putLock.lockInterruptibly();
    try {
        // 如果隊列已滿
        while (count.get() == capacity) {
            // 掛起當前線程
            notFull.await();
        }
        // 如果隊列未滿，將封裝的node節(jié)點加入隊列
        enqueue(node);
        // 更新count計數(shù)器并獲取更新前的count值
        c = count.getAndIncrement();
        // 如果隊列還未滿
        if (c + 1 < capacity)
            // 喚醒下一個添加線程棺滞，執(zhí)行元素添加操作
            notFull.signal();
    } finally {
        // 釋放鎖
        putLock.unlock();
    }
    // 如果更新前隊列為空裁蚁，現(xiàn)在添加了一個元素
    // 代表著目前隊列中肯定有數(shù)據(jù)了
    // 那么則喚醒等待獲取元素的線程
    if (c == 0)
        // 如果存在元素則喚醒take線程
        signalNotEmpty();
}

// LinkedBlockingQueue類 → enqueue()方法
private void enqueue(Node<E> node) {
    // 將新來的節(jié)點添加到鏈表的尾部
    last = last.next = node;
}

如上源碼所示，不難發(fā)現(xiàn)LinkedBlockingQueue继准、ArrayBlockingQueue兩個隊列添加元素的原理大致相同枉证，不同點在于：LinkedBlockingQueue在添加元素完成后會喚醒等待隊列中的其他線程執(zhí)行添加操作，但之前的ArrayBlockingQueue卻不會移必。為什么呢室谚？

因為LinkedBlockingQueue添加和獲取元素使用的是兩把不同的鎖，而之前的ArrayBlockingQueue添加和獲取元素是公用同一把鎖，所以在ArrayBlockingQueue中同時只允許添加/獲取中一個操作執(zhí)行秒赤。所以ArrayBlockingQueue在添加完成后會喚醒take線程猪瞬，獲取完成后會喚醒put線程。在LinkedBlockingQueue中則不同入篮，使用的是兩把完全不同的鎖陈瘦，也就是說LinkedBlockingQueue的讀/寫完全是分離的，各自使用自己的鎖進行并發(fā)控制崎弃，添加元素與獲取元素的線程并不會產(chǎn)生互斥甘晤，所以這也是為什么一條線程添加元素后會繼續(xù)喚醒等待列隊中的其他線程的原因。同時這種做法也可以在很大程度上提升容器的吞吐量饲做。

ok~线婚，那么關(guān)于put()方法的整體工作流程大家可以參加源碼中的注釋，我們接下來再看看take()方法的實現(xiàn)：

// LinkedBlockingQueue類 → take()方法
public E take() throws InterruptedException {
    E x;
    int c = -1;
    // 獲取隊列中元素數(shù)量以及讀鎖
    final AtomicInteger count = this.count;
    final ReentrantLock takeLock = this.takeLock;
    // 可響應中斷式加鎖
    takeLock.lockInterruptibly();
    try {
        // 如果隊列為空則掛起當前線程
        while (count.get() == 0) {
            notEmpty.await();
        }
        // 如果隊列不為空則獲取元素
        x = dequeue();
        // 更新count成員并獲取更新前的count值
        c = count.getAndDecrement();
        // 如果隊列中還有元素
        if (c > 1)
            // 喚醒等待隊列的其他線程盆均，繼續(xù)執(zhí)行獲取操作
            notEmpty.signal();
    } finally {
        // 釋放鎖
        takeLock.unlock();
    }
    // 如果之前隊列是滿的塞弊，那么現(xiàn)在彈出了一個元素
    // 則代表著當前隊列出現(xiàn)了空位，那么喚醒添加線程
    if (c == capacity)
        signalNotFull();
    return x;
}
// LinkedBlockingQueue類 → dequeue()方法
private E dequeue() {
    // 獲取隊列頭節(jié)點
    // 因為頭節(jié)點是空節(jié)點
    // 所以隊列中的第一個帶數(shù)據(jù)的節(jié)點為：
    //      頭結(jié)點的后繼節(jié)點
    Node<E> h = head;
    // 獲取head節(jié)點的后繼節(jié)點
    Node<E> first = h.next;
    h.next = h; // 方便GC泪姨，置空引用信息
    // 將頭節(jié)點的后繼節(jié)點變?yōu)轭^節(jié)點
    head = first; 
    // 獲取后繼節(jié)點上存儲的元素數(shù)據(jù)
    E x = first.item;
    // 置空頭節(jié)點的后繼節(jié)點數(shù)據(jù)游沿，將后繼節(jié)點變?yōu)轭^節(jié)點
    first.item = null;
    // 返回獲取到的數(shù)據(jù)
    return x;
}

簡單闡述一下LinkedBlockingQueue.take()方法的實現(xiàn)過程：

• ①獲取take鎖并判斷隊列是否為空，為空則掛起當前線程
• ②如果不為空則移除并獲取隊列頭部節(jié)點中存儲的元素信息
• ③更新count并獲取更新之前的count值肮砾，判斷隊列是否還有元素诀黍，有則喚醒其他線程繼續(xù)執(zhí)行
• ④判斷之前的隊列是否是滿的，如果是滿的現(xiàn)在彈出了一個元素仗处，代表隊列有空位眯勾，那么喚醒添加線程

至此，LinkedBlockingQueue的put/take原理也分析完畢婆誓，與ArrayBlockingQueue最大的區(qū)別在于：LinkedBlockingQueue底層使用單向鏈表結(jié)構(gòu)以及雙鎖實現(xiàn)吃环，我為了簡單則將其稱呼為“讀鎖”、“寫鎖”洋幻，但是大家不要被誤導郁轻，該“讀鎖”并非真正意義上的讀，因為如果只是讀操作的話是不需要加鎖的文留，而隊列的take方法在讀取了元素之后還需移除該元素好唯，所以里面也涉及到了寫的操作，自然也需要加鎖保證線程安全燥翅。準確來說渠啊，我所謂的“讀/寫鎖”實際上是指“take/put”鎖。

OK~权旷，關(guān)于其他的阻塞隊列則不再繼續(xù)分析替蛉，因為內(nèi)部阻塞的原理實現(xiàn)都大致相同贯溅，區(qū)別則在于內(nèi)部的數(shù)據(jù)存儲結(jié)構(gòu)不同，大家有興趣可以自己閱讀其源碼實現(xiàn)躲查，隊列的源碼在理解數(shù)據(jù)結(jié)構(gòu)的前提下其實并不算復雜它浅。

二、寫時復制容器

在本文開始時的引言中镣煮，曾提到：對于常用的一些容器在多線程環(huán)境下都會存在線程安全問題姐霍。所以當需要保證線程安全時，一般會使用Vector典唇、HashTable或Collections.synchronizedXXX等來代替镊折。此類方式的確可以保證線程安全，但是在文章一開始我們也早已分析了這些方式存在的缺陷：性能有限介衔，并發(fā)吞吐量上不去恨胚。而為了解決這個問題，在JUC包提供了一類新的容器：寫時復制容器炎咖，其內(nèi)部采用讀寫分離的思想提升容器的并發(fā)吞吐量赃泡。

寫時復制容器(Copy-On-Write)： 寫時復制容器是計算機程序設(shè)計領(lǐng)域慣用的一種優(yōu)化思想，在很多系統(tǒng)設(shè)計中乘盼，比如Linux中的Fork父子進程數(shù)據(jù)同步等機制都采用了這種思想升熊，子進程在創(chuàng)建時并不會拷貝父進程的數(shù)據(jù)，對于需要用到的數(shù)據(jù)僅僅只是存在一個引用指向父進程中存儲的數(shù)據(jù)地址绸栅，每次讀取時都是通過引用地址從父進程中讀取數(shù)據(jù)级野，而當子進程中要修改數(shù)據(jù)時才發(fā)生真正的拷貝動作，將父進程中的數(shù)據(jù)拷貝一份粹胯，修改完成后再將指向父進程數(shù)據(jù)的指針改成指向拷貝數(shù)據(jù)蓖柔。當然，寫時復制實則也是懶加載矛双、惰性加載思想的產(chǎn)物。在JUC包中蟆豫，寫時復制容器主要提供了兩種：CopyOnWriteArrayList與CopyOnWriteArraySet议忽，在使用這兩個容器時，讀操作不會加鎖十减，寫操作時則會先獲取鎖栈幸，然后再復制一份原有數(shù)據(jù)進行修改，修改完成后再修改原有引用指向帮辟。

ok~速址，關(guān)于CopyOnWriteArrayList與CopyOnWriteArraySet的使用我們則不再闡述，因為這兩個容器是對應著ArrayList與HashSet的由驹，使用方法與之相同芍锚。接下來從源碼角度分析寫時復制容器的具體實現(xiàn)過程。

2.1、CopyOnWriteArrayList原理分析

CopyOnWriteArrayList內(nèi)部是基于數(shù)組結(jié)構(gòu)存儲的并炮，類結(jié)構(gòu)如下：

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

    // ReentrantLock獨占鎖：用于保證線程安全
    final transient ReentrantLock lock = new ReentrantLock();

    // volatile修飾的數(shù)組：用于存儲數(shù)據(jù)默刚，volatile保證讀取可見性
    private transient volatile Object[] array;
    
    // array的封裝方法
    final void setArray(Object[] a) {
        array = a;
    }
    
    // 構(gòu)造器1：初始化長度為0的數(shù)組
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }
    //構(gòu)造器2：入?yún)橐粋€Collection集合對象
    public CopyOnWriteArrayList(Collection<? extends E> c) {
        Object[] elements;
        // 如果傳入的Collection對象就是COWL對象則直接拷貝數(shù)據(jù)
        if (c.getClass() == CopyOnWriteArrayList.class)
            elements = ((CopyOnWriteArrayList<?>)c).getArray();
        // 如果不是
        else {
            // 將Collection集合對象轉(zhuǎn)換為Object數(shù)組
            elements = c.toArray();
            // 如果調(diào)用toArray()后沒返回數(shù)組
            if (elements.getClass() != Object[].class)
                // 再次自己copy集合的數(shù)據(jù)轉(zhuǎn)化為數(shù)組
                elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
        // 賦值給array成員
        setArray(elements);
    }
    // 構(gòu)造器3：入?yún)橐粋€數(shù)組對象
    public CopyOnWriteArrayList(E[] toCopyIn) {
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }
    
    // COWIterator內(nèi)部類：迭代器。該迭代器不是fail-fast的
    static final class COWIterator<E> implements ListIterator<E> {
        private final Object[] snapshot;
        // 省略其他代碼.......
    }
    // COWSubList內(nèi)部類：子列表逃魄。與ArrayList的子列表同樣的作用
    private static class COWSubList<E> extends AbstractList<E>
        implements RandomAccess{}
    // COWSubListIterator內(nèi)部類：子列表的迭代器荤西。
    private static class COWSubListIterator<E> implements ListIterator<E> {}
}

ok，簡單的看看CopyOnWriteArrayList內(nèi)部的成員伍俘，使用ReentrantLock獨占鎖保證容器整體寫操作的安全問題邪锌，其內(nèi)部使用一個volatile關(guān)鍵字修飾的Object類型數(shù)組存儲數(shù)據(jù)。同時CopyOnWriteArrayList存在三個內(nèi)部類癌瘾，分別為自身的迭代器觅丰、子列表以及子列表的迭代器類。值得注意的是：

CopyOnWriteArrayList的迭代器并不是fail-fast的柳弄，即代表著當有一條線程在通過迭代器遍歷一個CopyOnWriteArrayList對象時舀透，另外一條線程對該容器進行了寫操作切厘，不會對使用迭代器遍歷容器的線程產(chǎn)生影響。而我們經(jīng)常使用的ArrayList容器，迭代器則是fail-fast的竟痰，當一條線程使用迭代器遍歷數(shù)據(jù)，另外一條執(zhí)行修改操作時相叁，迭代器線程會拋ConcurrentModifyException的異常党涕。

接著再分析分析CopyOnWriteArrayList中的常用方法，先看看get(i)方法：

// CopyOnWriteArrayList類 → get()方法
public E get(int index) {
    return get(getArray(), index);
}

// CopyOnWriteArrayList類 → get()重載方法
private E get(Object[] a, int index) {
    return (E) a[index];
}

關(guān)于get()方法的實現(xiàn)一目了然逝变，沒啥好講的基茵，無非就是將數(shù)組指定下標的元素數(shù)據(jù)返回了而已。接著繼續(xù)看看修改(寫)操作的方法：

// CopyOnWriteArrayList類 → set()方法
public E set(int index, E element) {
    // 獲取鎖對象并加鎖
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        // 獲取內(nèi)部存儲數(shù)據(jù)的數(shù)組成員：array
        Object[] elements = getArray();
        // 獲取數(shù)組中指定下標原有的數(shù)據(jù)
        E oldValue = get(elements, index);
        // 如果指定下標位置原本存儲的數(shù)據(jù)與新的數(shù)據(jù)不同
        if (oldValue != element) {
            // 獲取數(shù)組的長度
            int len = elements.length;
            // 拷貝一個新的數(shù)組對象
            Object[] newElements = Arrays.copyOf(elements, len);
            // 將指定下標位置的元素修改為指定的數(shù)據(jù)
            newElements[index] = element;
            // 將成員array的引用從原本的數(shù)組改為新的數(shù)組
            setArray(newElements);
        } else {
            // 如果指定下標位置原本存儲的數(shù)據(jù)與新的數(shù)據(jù)相同
            // 不做任何更改
            setArray(elements);
        }
        // 返回原本下標位置的值
        return oldValue;
    } finally {
        // 釋放鎖/解鎖
        lock.unlock();
    }
}
// CopyOnWriteArrayList類 → add()方法
public void add(int index, E element) {
    // 獲取鎖/加鎖
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        // 獲取內(nèi)部存儲數(shù)據(jù)的數(shù)組成員：array
        Object[] elements = getArray();
        int len = elements.length;
        // 如果指定下標位置超出數(shù)組長度或小于0則拋出異常
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+len);
        // 創(chuàng)建一個新的數(shù)組對象
        Object[] newElements;
        // 計算插入的下標位置是在數(shù)組中間還在數(shù)組最后
        int numMoved = len - index;
        // 如果在數(shù)組最后壳影，那么拷貝原本的數(shù)組并長度+1拱层，留個空位
        if (numMoved == 0)
            newElements = Arrays.copyOf(elements, len + 1);
        // 如果要在數(shù)組中間插入數(shù)據(jù)
        else {
            // 先創(chuàng)建一個長度為len+1的新數(shù)組
            newElements = new Object[len + 1];
            // 然后將拷貝老數(shù)組中的所有數(shù)據(jù)拷貝過來
            // 但是將下標為index的位置空出來
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        // 將要添加的數(shù)據(jù)設(shè)置到數(shù)組的index下標位置
        newElements[index] = element;
        // 將成員array的引用從原本的數(shù)組改為新的數(shù)組
        setArray(newElements);
    } finally {
        // 釋放鎖/解鎖
        lock.unlock();
    }
}
// CopyOnWriteArrayList類 → remove()方法
public E remove(int index) {
    // 獲取鎖/加鎖
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        // 拷貝原本的數(shù)組
        Object[] elements = getArray();
        // 獲取數(shù)組長度與數(shù)組中要移除的值
        int len = elements.length;
        E oldValue = get(elements, index);
        // 計算要移除的位置是在數(shù)組的最后還是在數(shù)組的中間
        int numMoved = len - index - 1;
        // 如果在數(shù)組最后
        if (numMoved == 0)
            // 拷貝數(shù)組時，將最后一個元素不拷貝即可
            // 拷貝完成后重新更改引用指向
            setArray(Arrays.copyOf(elements, len - 1));
        // 如果要移除的位置是在數(shù)組中間
        else {
            // 創(chuàng)建一個長度為原本長度-1的新數(shù)組
            Object[] newElements = new Object[len - 1];
            // 在拷貝數(shù)據(jù)時宴咧，將指定位置的元素不拷貝即可
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            // 更改成員array的引用指向
            setArray(newElements);
        }
        // 返回被移除的值
        return oldValue;
    } finally {
        // 釋放鎖/解鎖
        lock.unlock();
    }
}

如上列出了CopyOnWriteArrayList常用的三個寫方法：set()根灯、add()、remove()掺栅，下面分別談談它們的執(zhí)行流程：

• set()方法是直接替換的方法烙肺，比如指定的下標位置已經(jīng)有數(shù)據(jù)的情況下會覆蓋之前的數(shù)據(jù)，該方法需要傳遞兩個參數(shù)氧卧，第一個參數(shù)為下標位置桃笙，第二個參數(shù)為要設(shè)置的數(shù)據(jù)本身，下面是set方法的執(zhí)行流程：
  • ①加鎖后獲取原本的數(shù)組沙绝，同時獲取指定下標原有的值
  • ②判斷原有值與新值是否相同搏明，相同則不做任何修改
  • ③老值與新值不同時鼠锈，先拷貝原有數(shù)組內(nèi)的元素數(shù)據(jù)，然后將指定下標位置的數(shù)據(jù)修改為新值熏瞄，最后將array成員的引用指向新數(shù)組并釋放鎖
  • ④返回指定下標被替換掉的老值
• add()方法與set()方法參數(shù)是相同的脚祟，但區(qū)別在于：add方法不會替換指定下標位置之前的老值，而是將新值插入到數(shù)組中强饮，執(zhí)行流程如下：
  • ①加鎖后獲取數(shù)組數(shù)據(jù)由桌、數(shù)組長度
  • ②判斷要插入數(shù)據(jù)的下標位置是否超出數(shù)組長度+1或小于0，如果是則拋出異常
  • ③判斷要插入數(shù)據(jù)的下標位置在數(shù)組中間還是在數(shù)組最后
  • ④如果是在最后位置插入邮丰，那么先創(chuàng)建一個長度+1的新數(shù)組行您，同時拷貝原有數(shù)組的所有數(shù)據(jù)，將要插入的數(shù)據(jù)添加到數(shù)組的最后位置剪廉，最后將array成員的引用指向新數(shù)組并釋放鎖
  • ⑤如果要插入的下標位置在數(shù)組中間娃循，也會先創(chuàng)建一個長度+1的新數(shù)組，同時拷貝原有數(shù)組的所有數(shù)據(jù)斗蒋，但是在拷貝時會將指定下標位置空出來捌斧，然后將要插入的數(shù)據(jù)添加到該位置，最后將array成員的引用指向新數(shù)組并釋放鎖
• remove()方法是移除容器中數(shù)據(jù)的方法泉沾，該方法需要傳入要移除的下標位置捞蚂，執(zhí)行流程如下：
  • ①加鎖后獲取原本的數(shù)組數(shù)據(jù)及其長度，同時獲取指定下標原有的值
  • ②判斷要刪除數(shù)據(jù)的下標位置在數(shù)組中間還是在數(shù)組最后
  • ③如果是在數(shù)組最后一個位置跷究，則在拷貝數(shù)組數(shù)據(jù)時姓迅，不拷貝最后一個元素，完成后將array成員的引用指向新數(shù)組并釋放鎖
  • ④如果要刪除的下標在數(shù)組中間位置俊马，那么則先創(chuàng)建一個長度-1的新數(shù)組丁存，同時在拷貝數(shù)據(jù)時，不拷貝指定下標位置的元素數(shù)據(jù)即可柴我，完成后將array成員的引用指向新數(shù)組并釋放鎖

OK~解寝，至此三個常用的修改方法原理分析完成，過程并不復雜艘儒，但是比較有意思的是：

在CopyOnWriteArrayList中的移除方法聋伦，如remove等方法，其實并不會去刪除指定下標的元素數(shù)據(jù)彤悔，或者說CopyOnWriteArrayList中的移除方法根本不會存在刪除的操作嘉抓，而僅僅只是在為新數(shù)組拷貝數(shù)據(jù)時索守，刻意“漏”掉指定下標的數(shù)據(jù)不拷貝即可晕窑。

同時因為寫操作都是使用的同一個鎖對象來進行的并發(fā)控制，所以也可以避免線程安全問題的出現(xiàn)卵佛。

2.2杨赤、CopyOnWriteArraySet原理分析

關(guān)于CopyOnWriteArraySet這個容器我們便不再分析其內(nèi)部實現(xiàn)了敞斋，至于為什么？我們看看其內(nèi)部成員就明白了疾牲。如下：

public class CopyOnWriteArraySet<E> extends AbstractSet<E>
        implements java.io.Serializable {
    // 內(nèi)部存儲數(shù)據(jù)的結(jié)構(gòu)
    private final CopyOnWriteArrayList<E> al;
    // 構(gòu)造器
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }
}    

顯而易見植捎，CopyOnWriteArraySet實際上是基于CopyOnWriteArrayList實現(xiàn)的，所以當我們明白了CopyOnWriteArrayList的原理實現(xiàn)后阳柔，自然也理解了CopyOnWriteArraySet這個容器焰枢。

2.3、CopyOnWrite寫時復制容器總結(jié)

關(guān)于寫時復制的容器舌剂，優(yōu)勢比較明顯济锄，其內(nèi)部充分運用了讀寫分離的思想提升了容器的整體并發(fā)吞吐量，以及避免了并發(fā)修改拋出的ConcurrentModificationException異常霍转。但是也存在兩個致命的缺陷：

• ①內(nèi)存占用問題荐绝。因為CopyOnWrite容器每次在發(fā)生修改時都會復制一個新的數(shù)組，所以當數(shù)組數(shù)據(jù)過大時對內(nèi)存消耗比較高避消。
• ②數(shù)據(jù)不一致性問題低滩。CopyOnWrite容器保證的是最終一致性，一條線程在執(zhí)行修改操作岩喷，另一條線程在執(zhí)行讀取操作恕沫，讀取的線程并不能看到最新的數(shù)據(jù)，就算修改操作執(zhí)行了setArray()方法將指向改成了新數(shù)組均驶，原本讀取的線程也不能看到最新的數(shù)據(jù)昏兆。因為讀取線程在執(zhí)行讀操作時并不是直接訪問成員array完成的，而是通過getArray()方法的形式獲取到的數(shù)組數(shù)據(jù)妇穴，在getArray()方法執(zhí)行完成之后爬虱，讀取數(shù)據(jù)的線程拿到的引用已經(jīng)是舊數(shù)組的地址了，之后就算修改成員array的指向也不會影響get的訪問腾它。

還有一點值得注意：CopyOnWrite寫時復制容器提升的只是讀操作的吞吐量跑筝，而整個容器的寫操作還是基于同一把獨占鎖保證的線程安全，所以如果需要頻繁執(zhí)行寫操作的場景瞒滴，并不適合用CopyOnWrite容器曲梗，同時還會因為復制帶來的內(nèi)存、時間開銷導致性能下降妓忍。

三虏两、鎖分段容器

鎖分段容器的概念比較好理解，指的是將一個容器分為不同區(qū)域操作世剖，對不同區(qū)域操作時都是使用各自的鎖資源進行獲取/釋放鎖保障線程安全定罢。在引言中曾提及到，HashMap是線程不安全的旁瘫，如果要在多線程情況下使用祖凫，就要使用HashTable這類的容器操作琼蚯，但是這類容器因為是一把鎖控制并發(fā)，所以效率比較低下惠况。而在并發(fā)包中遭庶，則推出了一款新的容器：ConcurrentHashMap，其中就采用鎖分段技術(shù)提升了容器的整體并發(fā)吞吐性稠屠。不過在分析ConcurrentHashMap實現(xiàn)之前峦睡，我們先簡單的聊聊HashMap的原理。整體的闡述思路將分為三步：

• ①HashMap實現(xiàn)原理淺析
• ②JDK1.7中的ConcurrentHashMap原理淺談
• ③JDK1.8中的ConcurrentHashMap原理實現(xiàn)過程

3.1权埠、HashMap實現(xiàn)原理淺析

HashMap是基于哈希表結(jié)構(gòu)實現(xiàn)的一個容器赐俗，底層是基于數(shù)組+單向鏈表結(jié)構(gòu)實現(xiàn)的，數(shù)組長度默認為16弊知，每個數(shù)組下標的位置用于存儲每個鏈表的頭節(jié)點阻逮。而鏈表的每個節(jié)點在JDK1.7中是Entity對象，Entity對象則由key秩彤、value以及next向下指針三個元素組成叔扼。結(jié)構(gòu)大致如下：

HashMap結(jié)構(gòu)

HashMap的put()原理實現(xiàn)：

• ①首先將key-value封裝成節(jié)點對象
• ②調(diào)用hashcode()方法計算出key的哈希值
• ③通過哈希算法將哈希值轉(zhuǎn)換為具體的下標值
• ④根據(jù)計算出的下標位置將key-value數(shù)據(jù)進行存儲。但在存儲前會先判斷該下標是否有數(shù)據(jù)：
  • 如果沒有：將該數(shù)據(jù)存儲在數(shù)組的該下標位置蓄坏，作為鏈表頭節(jié)點
  • 如果有：會用key值與鏈表每個節(jié)點的key值比較价捧，如果相同則覆蓋，如果全部不同則將數(shù)據(jù)使用頭插法添加到鏈表的頭部(jdk1.8之后是尾插法涡戳，追加到鏈表尾部)

HashMap的get()原理實現(xiàn)：

• ①調(diào)用hashcode()方法計算出key的哈希值并計算出具體的下標值
• ②通過下標值快速定位到數(shù)組的某個位置结蟋，首先會判斷該位置上是否有數(shù)據(jù)：
  • 如果沒有：代表該位置還不存在鏈表，直接返回null
  • 如果有：會用key值與鏈表每個節(jié)點的key值進行比較渔彰，相同則獲取該節(jié)點的數(shù)據(jù)返回嵌屎，如果遍歷完整個鏈表后，不存在key值相同的節(jié)點恍涂，同樣會返回null

注意：HashMap重寫了equals()方法宝惰，因為equals()默認是比較內(nèi)存地址，而重寫后再沧，在HashMap中是比較key值尼夺。

HashMap的resize()擴容原理實現(xiàn)：

• 前置條件：默認容量=16，負載因子=0.75，閾值=容量*負載因子
• 擴容條件：當數(shù)組容器中的元素數(shù)量達到閾值時汞斧，會發(fā)生擴容動作
• 擴容實現(xiàn)過程：
  • ①當容量達到閾值時，創(chuàng)建一個2倍長度的新數(shù)組什燕，調(diào)用transfer()方法遷移數(shù)據(jù)
  • ②遍歷原本老數(shù)組的所有元素(頭節(jié)點)粘勒，根據(jù)每個頭節(jié)點循環(huán)每個鏈表，使用頭插法將數(shù)據(jù)轉(zhuǎn)移到新的數(shù)組中

注意：1.7中因為使用的是頭插法屎即，所以在多線程環(huán)境下容易導致死循環(huán)庙睡、數(shù)據(jù)丟失的問題。

JDK1.7前后HashMap的區(qū)別：

JDK1.8中技俐，當鏈表長度大于8時乘陪，鏈表結(jié)構(gòu)會轉(zhuǎn)換為紅黑樹結(jié)構(gòu)。但前提是：當數(shù)組長度小于64時雕擂，如果有鏈表的長度大于8了啡邑，那么代表著當前數(shù)組中的數(shù)據(jù)哈希沖突比較嚴重，在這種情況下是不會直接發(fā)生紅黑樹轉(zhuǎn)換的井赌，而是會先對于數(shù)組進行擴容谤逼，擴容之后對數(shù)據(jù)重新進行哈希計算，重新散列分布仇穗。所以其實真正的鏈表轉(zhuǎn)紅黑樹的條件是：當數(shù)組長度已經(jīng)超過64并且鏈表中的元素數(shù)量超過默認設(shè)定（8個）時流部，才會將鏈表轉(zhuǎn)化為紅黑樹結(jié)構(gòu)。

3.2纹坐、JDK1.7前的ConcurrentHashMap原理淺談

在前面講過：在多線程環(huán)境下使用HashMap是線程不安全的枝冀，而使用線程安全的HashTable效率又非常低下，所以便誕生了ConcurrentHashMap耘子，ConcurrentHashMap中采用了鎖分段的技術(shù)實現(xiàn)了更細粒度的并發(fā)控制果漾，從而提升了容器吞吐。下面我們也可以先看看它的存儲結(jié)構(gòu)谷誓。

在JDK1.7中跨晴，ConcurrentHashMap使用Segment數(shù)組+HashEntry數(shù)組+單向鏈表的方式實現(xiàn)。而Segment繼承了ReentrantLock片林，所以Segment對象也可以作為ConcurrentHashMap中的鎖資源使用端盆。結(jié)構(gòu)如下：

ConcurrentHashMap結(jié)構(gòu)

在ConcurrentHashMap的每個段(Segment對象)中都存在一個計數(shù)器：volatile修飾的count變量，count表示每個段中的所有HashEntry數(shù)組中所有鏈表的數(shù)據(jù)總和數(shù)量璧针。除此之外嚷炉，在每個段中還有一個modCount計數(shù)器，記錄著當前這個段的寫入操作次數(shù)探橱，主要用于跨段操作時判斷段中是否發(fā)生了更改操作申屹。

JDK1.7前的ConcurrentHashMap.put()原理實現(xiàn)：

• ①根據(jù)數(shù)據(jù)的key值計算hash值，通過哈希值定位到具體的Segment(段)位置隧膏，查看段是否為空：
  • 為空：對段進行初始化
  • 不為空：定位到具體的段位置
• ②獲取段的鎖資源哗讥，然后再根據(jù)哈希值計算出段中HashEntry數(shù)組存儲數(shù)據(jù)的具體下標(桶)
• ③根據(jù)計算出的數(shù)組下標，將數(shù)據(jù)封裝成節(jié)點后存儲在該位置胞枕。但在存儲前會先判斷該下標是否有數(shù)據(jù)：
  • 沒有：將數(shù)據(jù)存儲在數(shù)組的該下標位置成為鏈表頭節(jié)點
  • 有：先判斷當前數(shù)據(jù)的key值與鏈表的每個節(jié)點的key值是否相同：
    • 相同：替換之前的數(shù)據(jù)
    • 不同：使用頭插法將節(jié)點插入到鏈表頭部(1.7后是尾插法)
• ④更新count值并釋放鎖

在前面曾提到ConcurrentHashMap的Segment數(shù)組長度默認是16(可自定義長度)杆煞，而且Segment繼承了ReentrantLock充當鎖的角色，那么這樣則可以推導出ConcurrentHashMap默認是16個段(可自定義更大長度)腐泻，代表著在最理想的狀態(tài)下索绪，同時允許16個線程對容器執(zhí)行寫操作。但是為什么說是最理想狀態(tài)呢贫悄？因為有可能會出現(xiàn)哈希沖突瑞驱，導致兩個線程要寫入的數(shù)據(jù)定位到了同一個段，所以往往在實際應用中是很難將該容器的最大吞吐發(fā)揮到極致的窄坦。
PS：ConcurrentHashMap中不允許key=null唤反，也不允許value=null。

JDK1.7前的ConcurrentHashMap.get()原理實現(xiàn)：

• ①根據(jù)數(shù)據(jù)的key值計算hash值鸭津，通過哈希值定位到具體的Segment(段)位置
• ②再次根據(jù)哈希值在段中定位具體的數(shù)組位置彤侍，獲取數(shù)組位置上存儲的頭節(jié)點
• ③根據(jù)頭節(jié)點遍歷整個鏈表，用傳入的key值和每個節(jié)點的key值進行判斷是否相同：
  • 相同：返回該節(jié)點中存儲的value值
  • 全部不同：返回null
• ④如果key值相同逆趋，但讀到的value依舊為null時會加鎖重讀一次

為什么key值相同value為null時需要加鎖重讀一次盏阶？因為ConcurrentHashMap中不允許value=null，所以當存在key闻书，但value為null時可能是出現(xiàn)了指令重排導致數(shù)據(jù)暫時為null名斟，所以需要加鎖重讀一次。

JDK1.7前的ConcurrentHashMap.size()原理實現(xiàn)：

在ConcurrentHashMap中的size()需要涉及到整個容器魄眉，需要統(tǒng)計所有段中的元素數(shù)量砰盐。那又該如何實現(xiàn)呢？

• ①先記錄所有段的modCount值且統(tǒng)計總和
• ②統(tǒng)計所有段中記錄元素個數(shù)的count成員總和
• ③統(tǒng)計完成后再將之前記錄的modCount與現(xiàn)在每個段中的modCount進行判斷是否相同：
  • 相同：代表統(tǒng)計前后沒有發(fā)生寫操作坑律，直接返回求和所有段count的總數(shù)
  • 不同：代表統(tǒng)計前后發(fā)生了寫操作岩梳，重新再執(zhí)行①②③步驟重新統(tǒng)計一次（最多執(zhí)行三次）
• ④如果統(tǒng)計三次后，每次統(tǒng)計總和前后都發(fā)生了寫入操作，則對容器所有段上鎖進行統(tǒng)計并返回

ok~冀值，至此JDK1.7前的ConcurrentHashMap原理分析結(jié)束也物，接下來再來看看1.7后的實現(xiàn)。

3.3列疗、JDK1.8中的ConcurrentHashMap源碼分析

ConcurrentHashMap在JDK1.8中滑蚯，棄用了之前Segment數(shù)組+HashEntry數(shù)組+單向鏈表這種臃腫的方式實現(xiàn)，而是采用了更輕量級的Node數(shù)組+鏈表+紅黑樹+CAS+Synchronized關(guān)鍵字實現(xiàn)作彤。下面我們先來看看ConcurrentHashMap的成員，如下：

// Node節(jié)點數(shù)組,該數(shù)組中每個位置要存儲的元素為每個鏈表的頭節(jié)點
transient volatile Node<K,V>[] table;
// 在擴容時過渡用的table表乌逐，擴容時節(jié)點會暫時轉(zhuǎn)遷到這個數(shù)組
private transient volatile Node<K,V>[] nextTable;
// 計數(shù)器值=baseCount+每個CounterCell[i].value竭讳。所以baseCount只是計數(shù)器的一部分
private transient volatile long baseCount;
// 這個值在不同情況時存放值都不同，主要有如下幾種情況：
//      1. 數(shù)組沒新建時浙踢，暫時存儲數(shù)組容量大小的數(shù)值
//      2. 數(shù)組正在新建時绢慢，該成員為-1
//      3. 數(shù)組正常情況時，存放閾值
//      4. 數(shù)組擴容時洛波，高16bit存放舊容量唯一對應的一個標簽值胰舆，低16bit存放進行擴容的線程數(shù)量
private transient volatile int sizeCtl;
//擴容時使用，正常情況時=0蹬挤，擴容剛開始時為容量缚窿，代表下一次領(lǐng)取的擴容任務的索引上界
private transient volatile int transferIndex;
//CounterCell相配套一個獨占鎖
private transient volatile int cellsBusy;
//counterCells也是計數(shù)器的一部分
private transient volatile CounterCell[] counterCells;

// 三種特殊的節(jié)點哈希值，一個節(jié)點正常的哈希值都為>=0的正數(shù)
// 此節(jié)點是擴容期間的轉(zhuǎn)發(fā)節(jié)點焰扳，這個節(jié)點持有新table的引用
static final int MOVED     = -1;
// 代表此節(jié)點是紅黑樹的節(jié)點
static final int TREEBIN   = -2;
// 代表此節(jié)點是一個占位節(jié)點倦零，不包含任何實際數(shù)據(jù)
static final int RESERVED  = -3; 

ok~，如上便是一些ConcurrentHashMap的成員吨悍，接下來再看看其節(jié)點類型扫茅，ConcurrentHashMap的節(jié)點稍微有些復雜，如下：

• Node：如果數(shù)組某個下標位置(桶)的結(jié)構(gòu)為單向鏈表育瓜，那所有數(shù)據(jù)會被封裝成Node節(jié)點加入鏈表中葫隙。Node類的value與next指針都為volatile修飾的，保證了寫操作的可見性
• TreeNode：如果數(shù)組某個下標位置(桶)的結(jié)構(gòu)為紅黑樹結(jié)構(gòu)躏仇，那么其桶內(nèi)存儲的節(jié)點則為TreeNode類型
• TreeBin：TreeNode的封裝體恋脚，用作放在數(shù)組下標上作為根節(jié)點使用，但TreeBin并不是真正的根節(jié)點焰手，根節(jié)點為其內(nèi)部封裝的root成員慧起。這樣包裝的好處在于：因為紅黑樹隨著平衡旋轉(zhuǎn)操作，根節(jié)點隨時可能發(fā)生變化册倒，所以如果直接使用TreeNode作為根節(jié)點蚓挤，數(shù)組上的成員會經(jīng)常變化，而用TreeBin進行封裝，可以讓數(shù)組成員不會發(fā)生變化
• ForwardingNode：擴容期間的轉(zhuǎn)發(fā)節(jié)點灿意，這個節(jié)點持有新table的引用
• ReservationNode：占位節(jié)點估灿，不包含任何實際數(shù)據(jù)

PS：1.8的ConcurrentHashMap和1.8的HashMap鏈表轉(zhuǎn)紅黑樹的時機是相同的，都為：當數(shù)組容量>=64且單個鏈表長度>=8缤剧，這個下標位置(桶)才會從鏈表結(jié)構(gòu)轉(zhuǎn)換為紅黑樹結(jié)構(gòu)

3.3.1馅袁、JDK1.8中的ConcurrentHashMap.put()源碼分析

put()方法為整個ConcurrentHashMap的核心，同時它涉及的方面也有很多：容器初始化荒辕、插入操作汗销、擴容、計數(shù)統(tǒng)計等抵窒，接下來從源碼的角度入手分析其實現(xiàn)原理：

// ConcurrentHashMap類 → put()方法
public V put(K key, V value) {
    // 調(diào)用其內(nèi)部的putVal()方法
    return putVal(key, value, false);
}

// ConcurrentHashMap類 → putVal()方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
    // 檢查key,value是否為空
    if (key == null || value == null) throw new NullPointerException();
    // 根據(jù)key的原始哈希值計算新的哈希值
    int hash = spread(key.hashCode());
    // 代表一個位置下(桶)的節(jié)點數(shù)量
    int binCount = 0;
    // 開始遍歷整個table數(shù)組(Node數(shù)組)
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        // 如果數(shù)組還未初始化
        if (tab == null || (n = tab.length) == 0)
            // 對數(shù)組進行初始化操作
            tab = initTable();
        // 如果通過哈希值計算出的下標位置為null
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 使用CAS機制將現(xiàn)有數(shù)據(jù)封裝成Node節(jié)點插入該位置成為頭節(jié)點
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                // 插入到空桶(空箱)時不需要上鎖弛针，也無法上鎖(稍后分析)
                break;                   
        }
        // 如果計算出的下標位置不為空，但節(jié)點的哈希值為MOVED
        // 代表當前位置的桶正在執(zhí)行擴容操作
        else if ((fh = f.hash) == MOVED)
            // 當前線程執(zhí)行幫忙擴容操作
            tab = helpTransfer(tab, f);
        // 如果計算出的下標位置不為空李皇，且哈希值不為MOVED
        else {
            V oldVal = null;
            // 以數(shù)組下標位置的元素(頭節(jié)點)作為鎖資源上鎖
            synchronized (f) {
                // 加鎖成功后要再次檢查f是否為頭節(jié)點
                if (tabAt(tab, i) == f) {
                    // 如果哈希值>=0代表是正常節(jié)點
                    if (fh >= 0) {
                        // 把binCount=1
                        binCount = 1;
                        // 根據(jù)頭節(jié)點遍歷整個鏈表削茁，每遍歷一次對binCount+1
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // 如果節(jié)點的key與傳入的key相同
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                // 用新值替換舊值
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                // 停止遍歷操作
                                break;
                            }
                            // 如果在整個鏈表中沒有找到key值相同的節(jié)點
                            Node<K,V> pred = e;
                            // 找到鏈表尾部
                            if ((e = e.next) == null) {
                                // 將傳入的數(shù)據(jù)封裝成Node節(jié)點插入到鏈表尾部
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                // 插入完成后停止鏈表遍歷操作
                                break;
                            }
                        }
                    }
                    // 如果頭節(jié)點是一個TreeBin類型
                    // 代表當前位置的結(jié)構(gòu)已經(jīng)變?yōu)榱思t黑樹結(jié)構(gòu)
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        // 把binCount=2，紅黑樹結(jié)構(gòu)時binCount固定為2
                        binCount = 2;
                        // 將傳入的k,v,hash值作為參數(shù)掉房，調(diào)用putTreeVal方法
                        // putTreeVal方法可能返回兩種結(jié)果：
                        //   ①在整棵樹中沒有找到key相同的節(jié)點茧跋，新建Node插入返回null
                        //   ②找到key相同的節(jié)點并返回原本的value值
                        // 如果找到了key值相同的節(jié)點
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            // 用新值替換舊值
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            // 如果binCount!=0，代表著當前線程肯定執(zhí)行了寫入操作
            if (binCount != 0) {
                // 如果鏈表節(jié)點數(shù)量達到了8
                if (binCount >= TREEIFY_THRESHOLD)
                    // 執(zhí)行擴容操作或鏈表轉(zhuǎn)紅黑樹的操作
                    treeifyBin(tab, i);
                // 如果這次put操作僅是新值換舊值卓囚，那么返回舊值
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // 如果本次put是插入操作瘾杭，那么size增加1
    addCount(1L, binCount);
    // 并且返回null
    return null;
}

ok，如上便是ConcurrentHashMap.put方法的源碼實現(xiàn)哪亿，執(zhí)行流程如下：

• ①判斷傳入的key,value值是否為空富寿，為空拋出空指針異常
• ②根據(jù)key的hashCode值計算出新的哈希值
• ③如果整個數(shù)組為空，那么代表容器還未初始化锣夹，執(zhí)行初始化操作
• ④通過計算出的哈希值定位到數(shù)組具體的下標位置页徐，同時判斷該位置是否為空
  • 為空：代表該桶還沒有頭節(jié)點，那么使用CAS機制將當前數(shù)據(jù)封裝成節(jié)點添加到該位置
  • 不為空：判斷當前位置(桶)的頭節(jié)點哈希值是否為MOVED
    • 是：代表當前位置(桶)處于擴容階段银萍，當前線程幫忙擴容
    • 不是：代表當前位置(桶)處于正常階段变勇，準備執(zhí)行put操作
• ⑤以頭節(jié)點作為鎖資源進行加鎖操作，加鎖成功后再次判斷頭節(jié)點是否被移除贴唇，沒有則執(zhí)行put操作
• ⑥判斷頭節(jié)點的哈希值是否>=0搀绣，如果成立則代表當前節(jié)點是普通的鏈表頭節(jié)點，將binCount=1
• ⑦根據(jù)頭節(jié)點指針開始遍歷整個鏈表戳气，判斷傳入的key值是否與鏈表中節(jié)點的key值相同：
  • 相同：代表是同一個key值链患，用新值替換舊值，返回舊值
  • 不同：將數(shù)據(jù)封裝成節(jié)點對象瓶您，使用尾插法插入到鏈表尾部麻捻，返回null
  • 注意：在遍歷鏈表時纲仍，每遍歷一個節(jié)點，binCount都會+1
• ⑧如果頭節(jié)點的類型為TreeBin類型贸毕，代表當前位置(桶)的結(jié)構(gòu)已經(jīng)變?yōu)榱思t黑樹郑叠，將binCount=2
• ⑨調(diào)用putTreeVal()方法查找整棵樹，查看是否有key值相同的節(jié)點：
  • 有：返回舊值明棍，在外部執(zhí)行新值換舊值的操作乡革，返回舊值
  • 沒有：將數(shù)據(jù)封裝成樹節(jié)點插入到紅黑樹中，返回null
• ⑩判斷binCount是否>=8摊腋，如果是則代表當前鏈表過長沸版，調(diào)用treeifBin方法擴容或樹化
• ?判斷本次put操作是否為新值換舊值：
  • 是：返回舊值
  • 不是：代表是插入操作，那么對size+1兴蒸，然后返回null

注意點：
①為什么當計算出的下標位置(桶)元素為空時视粮，不加鎖反而使用CAS機制添加元素？
因為1.8之后的ConcurrentHashMap是基于synchronized關(guān)鍵字實現(xiàn)鎖機制的类咧，而synchronized是基于對象上鎖的馒铃，如果下標位置元素為空則代表沒有頭節(jié)點蟹腾，那么無法基于頭節(jié)點進行上鎖痕惋，所以只能通過CAS機制進行添加，將第一個數(shù)據(jù)添加到下標位置變?yōu)轭^節(jié)點娃殖。
②binCount這個值值戳，在鏈表結(jié)構(gòu)的情況下，遍歷鏈表時炉爆，每遍歷一個節(jié)點則binCount自增1堕虹，而在紅黑樹結(jié)構(gòu)時，binCount保持為2芬首，這是為什么赴捞？
因為binCount最終的作用是：判斷當前位置是否發(fā)生擴容或者樹化的，而只有鏈表結(jié)構(gòu)的情況下需要擴容或樹化郁稍。
③調(diào)用treeifBin()方法后赦政，不會直接發(fā)生樹化，而是會先判斷當前ConcurrentHashMap的數(shù)組長度是否已經(jīng)>=64耀怜，如果小于這個長度恢着，發(fā)生的則是擴容操作而并不是鏈表轉(zhuǎn)紅黑樹操作。

至此财破，整個ConcurrentHashMap.put方法執(zhí)行結(jié)束掰派。

3.3.2、JDK1.8中的ConcurrentHashMap.get()源碼分析

廢話不多說左痢，先上源碼靡羡，如下：

public V get(Object key) {
    // 定義相關(guān)局部變量
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    // 通過key的hashcode計算新的哈希值
    int h = spread(key.hashCode());
    // 如果數(shù)組不為空系洛，并且數(shù)組已經(jīng)初始化，并且計算出的具體下標位置不為空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        // 判斷頭節(jié)點的key是否與傳入的key相同
        if ((eh = e.hash) == h) {
            // 相同則直接返回頭節(jié)點中存儲的value值
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        // 如果頭節(jié)點的哈希值小于0亿眠，代表當前位置（桶）處于特殊狀態(tài)碎罚，有如下三種：
        //  ①為ForwardingNode節(jié)點：當前在擴容中，需轉(zhuǎn)發(fā)到nextTable上查找
        //  ②為TreeBin節(jié)點：代表當前位置是紅黑樹結(jié)構(gòu)纳像，需要二叉查找
        //  ③為ReservationNode節(jié)點：代表當前槽位之前是null荆烈，是占位節(jié)點，所以直接返回null
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        // 如果頭節(jié)點為正常節(jié)點竟趾，那么根據(jù)next指針遍歷整個鏈表
        while ((e = e.next) != null) {
            // 比較每個節(jié)點中的key值是否相同憔购，相同則返回節(jié)點中的value值
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    // 在鏈表中沒有找到key值相同的節(jié)點則返回null
    return null;
}

ConcurrentHashMap.get方法的源碼執(zhí)行流程如下：

• ①通過傳入的key值計算出新的哈希值
• ②判斷map內(nèi)部的數(shù)組是否為空，是否已經(jīng)初始化岔帽，key所在的位置(桶)是否為空
• ③判斷計算后的桶位置玫鸟，頭節(jié)點是否為要查找的數(shù)據(jù)，如果是則直接返回頭節(jié)點的value
• ④判斷頭節(jié)點的哈希值是否小于0犀勒，如果小于0代表當前位置(桶)處于特殊狀態(tài)屎飘，有三種情況：
  • 為ForwardingNode節(jié)點：當前在擴容中，需轉(zhuǎn)發(fā)到nextTable上查找
  • 為TreeBin節(jié)點：代表當前位置是紅黑樹結(jié)構(gòu)贾费，需要二叉查找
  • 為ReservationNode節(jié)點：代表當前槽位之前是null钦购，是占位節(jié)點，所以直接返回null
• ⑤如果頭節(jié)點為普通的鏈表節(jié)點褂萧，那么根據(jù)頭節(jié)點遍歷整個鏈表押桃，判斷每個節(jié)點中的key是否相同：
  • 相同：返回對應節(jié)點中的value值
  • 遍歷完整個鏈表還找到key值相同的節(jié)點，代表沒有這個數(shù)據(jù)导犹，返回null

ok~唱凯，到這里get方法的執(zhí)行過程也分析結(jié)束。

3.3.3谎痢、JDK1.8中的ConcurrentHashMap總結(jié)

對比之前來說磕昼，1.8中棄用了之前Segment數(shù)組+HashEntry數(shù)組+單向鏈表這種臃腫的結(jié)構(gòu)來實現(xiàn)ConcurrentHashMap，在1.8中节猿，存儲結(jié)構(gòu)方面采用了數(shù)組+鏈表+紅黑樹的方式實現(xiàn)票从，同時鎖機制方面，在之前是依賴于Segment對象上鎖沐批，而在1.8中纫骑，使用synchronized關(guān)鍵字基于數(shù)組每個位置上的元素上鎖，理論上ConcurrentHashMap中數(shù)組長度為多大九孩，那么就會有多少把鎖對象先馆。而當某個key經(jīng)過hash計算后，定位到的數(shù)組下標位置為空時躺彬，無法基于頭節(jié)點上鎖，那么則通過CAS無鎖機制進行添加。但是ConcurrentHashMap因為還是采用分段的形式實現(xiàn)的高吞吐簸搞，所以當要涉及到跨段操作時，比如size()方法時铣减，數(shù)據(jù)也會存在一定的偏差。

ConcurrentHashMap是一個無序的容器脚作，那么當想要實現(xiàn)有序的存儲時葫哗，會不會有ConcurrentTreeMap這么一個容器呢？答案是沒有的球涛，如果需要實現(xiàn)排序劣针，則得使用ConcurrentSkipListMap，ConcurrentSkipListMap是基于跳躍表實現(xiàn)的一個容器亿扁，大家有興趣也可以研究研究它的實現(xiàn)原理捺典。除此之外還有一些其他的并發(fā)容器，比如：ConcurrentSkipListSet从祝、ConcurrentLinkedQueue襟己、ConcurrentLinkedDeque等(不是分段容器，只是并發(fā)容器)牍陌。

四擎浴、總結(jié)

在前面我們總共提到了三類并發(fā)容器：阻塞隊列容器、寫時復制容器以及鎖分段容器呐赡。每一類容器都有很多種實現(xiàn)退客，最大的不同在于其內(nèi)部的存儲結(jié)構(gòu)不同骏融。而每一類容器都有各自的優(yōu)缺點链嘀，如阻塞隊列的單一性、寫時復制的內(nèi)存開銷档玻、分段容器的數(shù)據(jù)不一致等怀泊，所以在實際開發(fā)中，更多的是需要根據(jù)業(yè)務場景選擇合適并發(fā)容器误趴。