Part1HashMap、ConcurrentHashMap

HashMap常見的不安全問題及原因

• 非原子操作

++ modCount 等非原子操作存在且沒有任何加鎖機制會導(dǎo)致線程不安全問題；

• 擴容取值

擴容期間會創(chuàng)建新的table在數(shù)據(jù)轉(zhuǎn)儲期間，可能會有取到null的可能；

• 碰撞丟失

多線程情況下，若同時對一個bucket 進行put操作可能會出現(xiàn)覆蓋情況；

• 可見性問題

HashMap中沒有可見性volatile關(guān)鍵字修飾，多線程情況下不能保證可見性；

• 死循環(huán)

JDK1.7 擴容期間，頭插法也可能導(dǎo)致出現(xiàn)循環(huán)鏈表，即NodeA.next = NodeB ; NodeB.next = NodeA 在取值時則會發(fā)生死循環(huán)；

ConcurrentHashMap在JDK1.8中的升級

Java 7 版本的 ConcurrentHashMap

從圖中我們可以看出，在 ConcurrentHashMap 內(nèi)部進行了 Segment 分段，Segment 繼承了 ReentrantLock，可以理解為一把鎖，各個 Segment 之間都是相互獨立上鎖的，互不影響分段鎖。相比于之前的 Hashtable 每次操作都需要把整個對象鎖住而言，大大提高了并發(fā)效率。因為它的鎖與鎖之間是獨立的，而不是整個對象只有一把鎖。

每個 Segment 的底層數(shù)據(jù)結(jié)構(gòu)與 HashMap 類似的HashEntry（所以1.7中的put操作需要進行兩次Hash，先找到Segment再找到HashEntry，并使用 tryLock + 自旋的方式嘗試插入數(shù)據(jù)），仍然是數(shù)組和鏈表組成的拉鏈法結(jié)構(gòu)。默認有 0~15 共 16 個 Segment，所以最多可以同時支持 16 個線程并發(fā)操作（操作分別分布在不同的 Segment 上）。16 這個默認值可以在初始化的時候設(shè)置為其他值，但是一旦確認初始化以后，是不可以擴容的。

獲取Map的size時，依次執(zhí)行兩種方案，嘗試不加鎖獲取兩次，若不變則說明size準確；否則執(zhí)行方案二 加鎖情況下直接獲取size；

Java 8 版本的 ConcurrentHashMap

在 Java 8 中，幾乎完全重寫了 ConcurrentHashMap，代碼量從原來 Java 7 中的 1000 多行，變成了現(xiàn)在的 6000 多行，取消了Segment，使用 Node [] + 鏈表 + 紅黑樹，放棄了ReentrantLock的使用采用了`Synchronized + CAS + volatile（Node 的 value屬性） 鎖機制能適應(yīng)更高的并發(fā)和更高效的鎖機制，也依賴于Java團隊對Synchronized鎖的優(yōu)化。

獲取Map的size時，sumCount函數(shù)在每次操作時已經(jīng)記錄好了，所以直接返回；但既然是高并發(fā)容器，size并沒有多大意義，瞬時值；

圖中的節(jié)點有三種類型。

第一種是最簡單的，空著的位置代表當前還沒有元素來填充。第二種就是和 HashMap 非常類似的拉鏈法結(jié)構(gòu)，在每一個槽中會首先填入第一個節(jié)點，但是后續(xù)如果計算出相同的 Hash 值，就用鏈表的形式往后進行延伸。第三種結(jié)構(gòu)就是紅黑樹結(jié)構(gòu)，這是 Java 7 的 ConcurrentHashMap 中所沒有的結(jié)構(gòu)，在此之前我們可能也很少接觸這樣的數(shù)據(jù)結(jié)構(gòu)。當?shù)诙N情況的鏈表長度大于某一個閾值（默認為 8），且同時滿足一定的容量要求的時候，ConcurrentHashMap 便會把這個鏈表從鏈表的形式轉(zhuǎn)化為紅黑樹的形式，目的是進一步提高它的查找性能。所以，Java 8 的一個重要變化就是引入了紅黑樹的設(shè)計，由于紅黑樹并不是一種常見的數(shù)據(jù)結(jié)構(gòu)，所以我們在此簡要介紹一下紅黑樹的特點。

紅黑樹是每個節(jié)點都帶有顏色屬性的自平衡的二叉查找樹，顏色為紅色或黑色，紅黑樹的本質(zhì)是對二叉查找樹 BST 的一種平衡策略，我們可以理解為是一種平衡二叉查找樹，查找效率高，會自動平衡，防止極端不平衡從而影響查找效率的情況發(fā)生。

由于自平衡的特點，即左右子樹高度幾乎一致，所以其查找性能近似于二分查找，時間復(fù)雜度是 O(log(n)) 級別；反觀鏈表，它的時間復(fù)雜度就不一樣了，如果發(fā)生了最壞的情況，可能需要遍歷整個鏈表才能找到目標元素，時間復(fù)雜度為 O(n)，遠遠大于紅黑樹的 O(log(n))，尤其是在節(jié)點越來越多的情況下，O(log(n)) 體現(xiàn)出的優(yōu)勢會更加明顯。

紅黑樹的一些其他特點：

• 每個節(jié)點要么是紅色，要么是黑色，但根節(jié)點永遠是黑色的。
• 紅色節(jié)點不能連續(xù)，也就是說，紅色節(jié)點的子和父都不能是紅色的。
• 從任一節(jié)點到其每個葉子節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點。

正是由于這些規(guī)則和要求的限制，紅黑樹保證了較高的查找效率，所以現(xiàn)在就可以理解為什么 Java 8 的 ConcurrentHashMap 要引入紅黑樹了。好處就是避免在極端的情況下沖突鏈表變得很長，在查詢的時候，效率會非常慢。而紅黑樹具有自平衡的特點，所以，即便是極端情況下，也可以保證查詢效率在 O(log(n))。

事實上，鏈表長度超過 8 就轉(zhuǎn)為紅黑樹的設(shè)計，更多的是為了防止用戶自己實現(xiàn)了不好的哈希算法時導(dǎo)致鏈表過長，從而導(dǎo)致查詢效率低，而此時轉(zhuǎn)為紅黑樹更多的是一種保底策略，用來保證極端情況下查詢的效率。

通常如果 hash 算法正常的話，那么鏈表的長度也不會很長，那么紅黑樹也不會帶來明顯的查詢時間上的優(yōu)勢，反而會增加空間負擔。所以通常情況下，并沒有必要轉(zhuǎn)為紅黑樹，所以就選擇了概率非常小，小于千萬分之一概率，也就是長度為 8 的概率，把長度 8 作為轉(zhuǎn)化的默認閾值。

所以如果平時開發(fā)中發(fā)現(xiàn) HashMap 或是 ConcurrentHashMap 內(nèi)部出現(xiàn)了紅黑樹的結(jié)構(gòu)，這個時候往往就說明我們的哈希算法出了問題，需要留意是不是我們實現(xiàn)了效果不好的 hashCode 方法，并對此進行改進，以便減少沖突。

源碼分析

• putVal方法，關(guān)鍵詞：CAS、helpTransfer、synchronized、addCount

final V putVal(K key, V value, boolean onlyIfAbsent) {
  if (key == null || value == null) {
      throw new NullPointerException();
  }
  //計算 hash 值
  int hash = spread(key.hashCode());
  int binCount = 0;
  for (Node<K, V>[] tab = table; ; ) {
      Node<K, V> f;
      int n, i, fh;
      //如果數(shù)組是空的，就進行初始化
      if (tab == null || (n = tab.length) == 0) {
          tab = initTable();
      }
      // 找該 hash 值對應(yīng)的數(shù)組下標
      else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
          //如果該位置是空的，就用 CAS 的方式放入新值
          if (casTabAt(tab, i, null,
                  new Node<K, V>(hash, key, value, null))) {
              break;
          }
      }
      //hash值等于 MOVED 代表在擴容
      else if ((fh = f.hash) == MOVED) {
          tab = helpTransfer(tab, f);
      }
      //槽點上是有值的情況
      else {
          V oldVal = null;
          //用 synchronized 鎖住當前槽點，保證并發(fā)安全
          synchronized (f) {
              if (tabAt(tab, i) == f) {
                  //如果是鏈表的形式
                  if (fh >= 0) {
                      binCount = 1;
                      //遍歷鏈表
                      for (Node<K, V> e = f; ; ++binCount) {
                          K ek;
                          //如果發(fā)現(xiàn)該 key 已存在，就判斷是否需要進行覆蓋，然后返回
                          if (e.hash == hash &&
                                  ((ek = e.key) == key ||
                                          (ek != null && key.equals(ek)))) {
                              oldVal = e.val;
                              if (!onlyIfAbsent) {
                                  e.val = value;
                              }
                              break;
                          }
                          Node<K, V> pred = e;
                          //到了鏈表的尾部也沒有發(fā)現(xiàn)該 key，說明之前不存在，就把新值添加到鏈表的最后
                          if ((e = e.next) == null) {
                              pred.next = new Node<K, V>(hash, key,
                                      value, null);
                              break;
                          }
                      }
                  }
                  //如果是紅黑樹的形式
                  else if (f instanceof TreeBin) {
                      Node<K, V> p;
                      binCount = 2;
                      //調(diào)用 putTreeVal 方法往紅黑樹里增加數(shù)據(jù)
                      if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key,
                              value)) != null) {
                          oldVal = p.val;
                          if (!onlyIfAbsent) {
                              p.val = value;
                          }
                      }
                  }
              }
          }
          if (binCount != 0) {
              //檢查是否滿足條件并把鏈表轉(zhuǎn)換為紅黑樹的形式，默認的 TREEIFY_THRESHOLD 閾值是 8
              if (binCount >= TREEIFY_THRESHOLD) {
                  treeifyBin(tab, i);
              }
              //putVal 的返回是添加前的舊值，所以返回 oldVal
              if (oldVal != null) {
                  return oldVal;
              }
              break;
          }
      }
  }
  addCount(1L, binCount);
  return null;
 }

putVal方法中會逐步根據(jù)當前槽點是未初始化、空、擴容、鏈表、紅黑樹等不同情況做出不同的處理。當?shù)谝淮蝡ut 會對數(shù)組進行初始化，bucket為空則CAS操作賦值，不為空則判斷是鏈表還是紅黑樹進行賦值操作，若此時數(shù)組正在擴容則調(diào)用helpTransfer進行多線程并發(fā)擴容操作，最后返回oldValue 并對操作調(diào)用addCount記錄（size相關(guān)）；

• getVal源碼分析

public V get(Object key) {
  Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
  //計算 hash 值
  int h = spread(key.hashCode());
  //如果整個數(shù)組是空的，或者當前槽點的數(shù)據(jù)是空的，說明 key 對應(yīng)的 value 不存在，直接返回 null
  if ((tab = table) != null && (n = tab.length) > 0 &&
          (e = tabAt(tab, (n - 1) & h)) != null) {
      //判斷頭結(jié)點是否就是我們需要的節(jié)點，如果是則直接返回
      if ((eh = e.hash) == h) {
          if ((ek = e.key) == key || (ek != null && key.equals(ek)))
              return e.val;
      }
      //如果頭結(jié)點 hash 值小于 0，說明是紅黑樹或者正在擴容，就用對應(yīng)的 find 方法來查找
      else if (eh < 0)
          return (p = e.find(h, key)) != null ? p.val : null;
      //遍歷鏈表來查找
      while ((e = e.next) != null) {
          if (e.hash == h &&
                  ((ek = e.key) == key || (ek != null && key.equals(ek))))
              return e.val;
      }
  }
  return null;
}

get過程：

1. 計算 Hash 值，并由此值找到對應(yīng)的bucket；
2. 如果數(shù)組是空的或者該位置為 null，那么直接返回 null 就可以了；
3. 如果該位置處的節(jié)點剛好就是我們需要的，直接返回該節(jié)點的值；
4. 如果該位置節(jié)點是紅黑樹或者正在擴容，就用 find 方法繼續(xù)查找；
5. 否則那就是鏈表，就進行遍歷鏈表查找。

總結(jié)

• 數(shù)據(jù)結(jié)構(gòu)：Java 7 采用 Segment 分段鎖來實現(xiàn)，而 Java 8 中的 ConcurrentHashMap 使用數(shù)組 + 鏈表 + 紅黑樹
• 并發(fā)度：Java 7 中，每個 Segment 獨立加鎖，最大并發(fā)個數(shù)就是 Segment 的個數(shù)，默認是 16。但是到了 Java 8 中，鎖粒度更細，理想情況下 table 數(shù)組元素的個數(shù)（也就是數(shù)組長度）就是其支持并發(fā)的最大個數(shù)，并發(fā)度比之前有提高。
• 并發(fā)原理：Java 7 采用 Segment 分段鎖來保證安全，而 Segment 是繼承自 ReentrantLock。Java 8 中放棄了 Segment 的設(shè)計，采用 Node + CAS + synchronized 保證線程安全。
• Hash碰撞：Java 7 在 Hash 沖突時，會使用拉鏈法，也就是鏈表的形式。Java 8 先使用拉鏈法，在鏈表長度超過一定閾值時，將鏈表轉(zhuǎn)換為紅黑樹，來提高查找效率。

1CopyOnWriteArrayList / Set

其實在 CopyOnWriteArrayList 出現(xiàn)之前，我們已經(jīng)有了 ArrayList 和 LinkedList 作為 List 的數(shù)組和鏈表的實現(xiàn)，而且也有了線程安全的 Vector 和 Collections.synchronizedList() 可以使用。

Vector和HashTable類似僅僅是對方法增加synchronized 上對象鎖，并發(fā)效率比較低；并且，前面這幾種 List 在迭代期間不允許編輯，如果在迭代期間進行添加或刪除元素等操作，則會拋出 ConcurrentModificationException 異常，這樣的特點也在很多情況下給使用者帶來了麻煩。所以從 JDK1.5 開始，Java 并發(fā)包里提供了使用 CopyOnWrite 機制實現(xiàn)的并發(fā)容器 CopyOnWriteArrayList 作為主要的并發(fā) List，CopyOnWrite 的并發(fā)集合還包括 CopyOnWriteArraySet，其底層正是利用 CopyOnWriteArrayList 實現(xiàn)的。所以今天我們以 CopyOnWriteArrayList 為突破口，來看一下 CopyOnWrite 容器的特點。

適用場景

• 讀快寫慢

在很多應(yīng)用場景中，讀操作可能會遠遠多于寫操作。比如，有些系統(tǒng)級別的信息，往往只需要加載或者修改很少的次數(shù)，但是會被系統(tǒng)內(nèi)所有模塊頻繁的訪問。對于這種場景，我們最希望看到的就是讀操作可以盡可能的快，而寫即使慢一些也沒關(guān)系。

• 讀多寫少

黑名單是最典型的場景，假如我們有一個搜索網(wǎng)站，用戶在這個網(wǎng)站的搜索框中，輸入關(guān)鍵字搜索內(nèi)容，但是某些關(guān)鍵字不允許被搜索。這些不能被搜索的關(guān)鍵字會被放在一個黑名單中，黑名單并不需要實時更新，可能每天晚上更新一次就可以了。當用戶搜索時，會檢查當前關(guān)鍵字在不在黑名單中，如果在，則提示不能搜索。這種讀多寫少的場景也很適合使用 CopyOnWrite 集合。

讀寫規(guī)則

• 讀寫鎖的規(guī)則

讀寫鎖的思想是：讀讀共享、其他都互斥（寫寫互斥、讀寫互斥、寫讀互斥），原因是由于讀操作不會修改原有的數(shù)據(jù)，因此并發(fā)讀并不會有安全問題；而寫操作是危險的，所以當寫操作發(fā)生時，不允許有讀操作加入，也不允許第二個寫線程加入。

• 對讀寫鎖規(guī)則的升級

CopyOnWriteArrayList 的思想比讀寫鎖的思想又更進一步。為了將讀取的性能發(fā)揮到極致，CopyOnWriteArrayList 讀取是完全不用加鎖的，更厲害的是，寫入也不會阻塞讀取操作，也就是說你可以在寫入的同時進行讀取，只有寫入和寫入之間需要進行同步，也就是不允許多個寫入同時發(fā)生，但是在寫入發(fā)生時允許讀取同時發(fā)生。這樣一來，讀操作的性能就會大幅度提升。

特點

• CopyOnWrite的含義

從 CopyOnWriteArrayList 的名字就能看出它是滿足 CopyOnWrite 的 ArrayList，CopyOnWrite 的意思是說，當容器需要被修改的時候，不直接修改當前容器，而是先將當前容器進行 Copy，復(fù)制出一個新的容器 （和MySQL中的快照讀機制類似），然后修改新的容器，完成修改之后，再將原容器的引用指向新的容器。這樣就完成了整個修改過程。

這樣做的好處是，CopyOnWriteArrayList 利用了“數(shù)組不變性”原理，因為容器每次修改都是創(chuàng)建新副本，所以對于舊容器來說，其實是不可變的，也是線程安全的，無需進一步的同步操作。我們可以對 CopyOnWrite 容器進行并發(fā)的讀，而不需要加鎖，因為當前容器不會添加任何元素，也不會有修改。

CopyOnWriteArrayList 的所有修改操作（add，set等）都是通過創(chuàng)建底層數(shù)組的新副本來實現(xiàn)的，所以 CopyOnWrite 容器也是一種讀寫分離的思想體現(xiàn)，讀和寫使用不同的容器。

• 迭代期間允許修改集合內(nèi)容

我們知道 ArrayList 在迭代期間如果修改集合的內(nèi)容，會拋出 ConcurrentModificationException 異常。讓我們來分析一下 ArrayList 會拋出異常的原因。

在 ArrayList 源碼里的 ListItr 的 next 方法中有一個 checkForComodification 方法，代碼如下：

final void checkForComodification() {
  if (modCount != expectedModCount)
      throw new ConcurrentModificationException();
}

這里會首先檢查 modCount 是否等于 expectedModCount。modCount 是保存修改次數(shù)，每次我們調(diào)用 add、remove 或 trimToSize 等方法時它會增加，expectedModCount 是迭代器的變量，當我們創(chuàng)建迭代器時會初始化并記錄當時的 modCount。后面迭代期間如果發(fā)現(xiàn) modCount 和 expectedModCount 不一致，就說明有人修改了集合的內(nèi)容，就會拋出異常。而CopyOnWriteArrayList不會拋異常，參見源碼分析COWIterator；

缺點

這些缺點不僅是針對 CopyOnWriteArrayList，其實同樣也適用于其他的 CopyOnWrite 容器：

• 內(nèi)存占用問題

因為 CopyOnWrite 的寫時復(fù)制機制，所以在進行寫操作的時候，內(nèi)存里會同時駐扎兩個對象的內(nèi)存，這一點會占用額外的內(nèi)存空間。

• 在元素較多或者復(fù)雜的情況下，復(fù)制的開銷很大

復(fù)制過程不僅會占用雙倍內(nèi)存，還需要消耗 CPU 等資源，會降低整體性能。

• 臟讀問題

由于 CopyOnWrite 容器的修改是先修改副本，所以這次修改對于其他線程來說，并不是實時能看到的，只有在修改完之后才能體現(xiàn)出來。如果你希望寫入的的數(shù)據(jù)馬上能被其他線程看到，CopyOnWrite 容器是不適用的。

源碼分析

• 數(shù)據(jù)結(jié)構(gòu)

/** 可重入鎖對象 */
final transient ReentrantLock lock = new ReentrantLock();
 
/** CopyOnWriteArrayList底層由數(shù)組實現(xiàn)，volatile修飾，保證數(shù)組的可見性 */
private transient volatile Object[] array;
 
/**
* 得到數(shù)組
*/
final Object[] getArray() {
    return array;
}
 
/**
* 設(shè)置數(shù)組
*/
final void setArray(Object[] a) {
    array = a;
}
 
/**
* 初始化CopyOnWriteArrayList相當于初始化數(shù)組
*/
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}
`
(javascript:void(0); "復(fù)制代碼")[](https://common.cnblogs.com/images/copycode.gif)
這個類中首先會有一個 ReentrantLock 鎖，用來保證修改操作的線程安全。下面被命名為 array 的 Object[] 數(shù)組是被 volatile 修飾的，可以保證數(shù)組的可見性，這正是存儲元素的數(shù)組，同樣，我們可以從 getArray()、setArray 以及它的構(gòu)造方法看出，CopyOnWriteArrayList 的底層正是利用數(shù)組實現(xiàn)的，這也符合它的名字。
add方法
(javascript:void(0); "復(fù)制代碼")[](https://common.cnblogs.com/images/copycode.gif)
`
public boolean add(E e) {
  
    // 加鎖
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
 
        // 得到原數(shù)組的長度和元素
        Object[] elements = getArray();
        int len = elements.length;
 
        // 復(fù)制出一個新數(shù)組
        Object[] newElements = Arrays.copyOf(elements, len + 1);
 
        // 添加時，將新元素添加到新數(shù)組中
        newElements[len] = e;
 
        // 將volatile Object[] array 的指向替換成新數(shù)組
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

上面的步驟實現(xiàn)了 CopyOnWrite 的思想：寫操作是在原來容器的拷貝上進行的，并且在讀取數(shù)據(jù)的時候不會鎖住 list。而且可以看到，如果對容器拷貝操作的過程中有新的讀線程進來，那么讀到的還是舊的數(shù)據(jù)，因為在那個時候?qū)ο蟮囊眠€沒有被更改。

• get方法

public E get(int index) {
    return get(getArray(), index);
}
final Object[] getArray() {
    return array;
}
private E get(Object[] a, int index) {
    return (E) a[index];
}

get方法十分普通，沒有任何鎖相關(guān)內(nèi)容，主要是保證讀取效率；

• 迭代器 COWIterator 類

這個迭代器有兩個重要的屬性，分別是 Object[] snapshot 和 int cursor。其中 snapshot 代表數(shù)組的快照，也就是創(chuàng)建迭代器那個時刻的數(shù)組情況，而 cursor 則是迭代器的游標。迭代器的構(gòu)造方法如下：

private COWIterator(Object[] elements, int initialCursor) {
    cursor = initialCursor;
    snapshot = elements;
}

可以看出，迭代器在被構(gòu)建的時候，會把當時的 elements 賦值給 snapshot，而之后的迭代器所有的操作都基于 snapshot 數(shù)組進行的，比如：

public E next() {
    if (! hasNext())
        throw new NoSuchElementException();
    return (E) snapshot[cursor++];
}

在 next 方法中可以看到，返回的內(nèi)容是 snapshot 對象，所以，后續(xù)就算原數(shù)組被修改，這個 snapshot 既不會感知到，也不會影響執(zhí)行；