Part1HashMap、ConcurrentHashMap

HashMap常見(jiàn)的不安全問(wèn)題及原因

• 非原子操作

++ modCount 等非原子操作存在且沒(méi)有任何加鎖機(jī)制會(huì)導(dǎo)致線程不安全問(wèn)題；

• 擴(kuò)容取值

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

• 碰撞丟失

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

• 可見(jiàn)性問(wèn)題

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

• 死循環(huán)

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

ConcurrentHashMap在JDK1.8中的升級(jí)

Java 7 版本的 ConcurrentHashMap

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

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

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

Java 8 版本的 ConcurrentHashMap

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

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

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

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

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

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

紅黑樹(shù)的一些其他特點(diǎn)：

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

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

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

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

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

源碼分析

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

final V putVal(K key, V value, boolean onlyIfAbsent) {
  if (key == null || value == null) {
      throw new NullPointerException();
  }
  //計(jì)算 hash 值
  int hash = spread(key.hashCode());
  int binCount = 0;
  for (Node<K, V>[] tab = table; ; ) {
      Node<K, V> f;
      int n, i, fh;
      //如果數(shù)組是空的，就進(jìn)行初始化
      if (tab == null || (n = tab.length) == 0) {
          tab = initTable();
      }
      // 找該 hash 值對(duì)應(yīng)的數(shù)組下標(biāo)
      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 代表在擴(kuò)容
      else if ((fh = f.hash) == MOVED) {
          tab = helpTransfer(tab, f);
      }
      //槽點(diǎn)上是有值的情況
      else {
          V oldVal = null;
          //用 synchronized 鎖住當(dāng)前槽點(diǎn)，保證并發(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 已存在，就判斷是否需要進(jìn)行覆蓋，然后返回
                          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;
                          //到了鏈表的尾部也沒(méi)有發(fā)現(xiàn)該 key，說(shuō)明之前不存在，就把新值添加到鏈表的最后
                          if ((e = e.next) == null) {
                              pred.next = new Node<K, V>(hash, key,
                                      value, null);
                              break;
                          }
                      }
                  }
                  //如果是紅黑樹(shù)的形式
                  else if (f instanceof TreeBin) {
                      Node<K, V> p;
                      binCount = 2;
                      //調(diào)用 putTreeVal 方法往紅黑樹(shù)里增加數(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)換為紅黑樹(shù)的形式，默認(rè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方法中會(huì)逐步根據(jù)當(dāng)前槽點(diǎn)是未初始化、空、擴(kuò)容、鏈表、紅黑樹(shù)等不同情況做出不同的處理。當(dāng)?shù)谝淮蝡ut 會(huì)對(duì)數(shù)組進(jìn)行初始化，bucket為空則CAS操作賦值，不為空則判斷是鏈表還是紅黑樹(shù)進(jìn)行賦值操作，若此時(shí)數(shù)組正在擴(kuò)容則調(diào)用helpTransfer進(jìn)行多線程并發(fā)擴(kuò)容操作，最后返回oldValue 并對(duì)操作調(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;
  //計(jì)算 hash 值
  int h = spread(key.hashCode());
  //如果整個(gè)數(shù)組是空的，或者當(dāng)前槽點(diǎn)的數(shù)據(jù)是空的，說(shuō)明 key 對(duì)應(yīng)的 value 不存在，直接返回 null
  if ((tab = table) != null && (n = tab.length) > 0 &&
          (e = tabAt(tab, (n - 1) & h)) != null) {
      //判斷頭結(jié)點(diǎn)是否就是我們需要的節(jié)點(diǎn)，如果是則直接返回
      if ((eh = e.hash) == h) {
          if ((ek = e.key) == key || (ek != null && key.equals(ek)))
              return e.val;
      }
      //如果頭結(jié)點(diǎn) hash 值小于 0，說(shuō)明是紅黑樹(shù)或者正在擴(kuò)容，就用對(duì)應(yīng)的 find 方法來(lái)查找
      else if (eh < 0)
          return (p = e.find(h, key)) != null ? p.val : null;
      //遍歷鏈表來(lái)查找
      while ((e = e.next) != null) {
          if (e.hash == h &&
                  ((ek = e.key) == key || (ek != null && key.equals(ek))))
              return e.val;
      }
  }
  return null;
}

get過(guò)程：

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

總結(jié)

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

1CopyOnWriteArrayList / Set

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

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

適用場(chǎng)景

• 讀快寫(xiě)慢

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

• 讀多寫(xiě)少

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

讀寫(xiě)規(guī)則

• 讀寫(xiě)鎖的規(guī)則

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

• 對(duì)讀寫(xiě)鎖規(guī)則的升級(jí)

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

特點(diǎn)

• CopyOnWrite的含義

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

這樣做的好處是，CopyOnWriteArrayList 利用了“數(shù)組不變性”原理，因?yàn)槿萜髅看涡薷亩际莿?chuàng)建新副本，所以對(duì)于舊容器來(lái)說(shuō)，其實(shí)是不可變的，也是線程安全的，無(wú)需進(jìn)一步的同步操作。我們可以對(duì) CopyOnWrite 容器進(jìn)行并發(fā)的讀，而不需要加鎖，因?yàn)楫?dāng)前容器不會(huì)添加任何元素，也不會(huì)有修改。

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

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

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

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

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

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

缺點(diǎn)

這些缺點(diǎn)不僅是針對(duì) CopyOnWriteArrayList，其實(shí)同樣也適用于其他的 CopyOnWrite 容器：

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

因?yàn)?CopyOnWrite 的寫(xiě)時(shí)復(fù)制機(jī)制，所以在進(jìn)行寫(xiě)操作的時(shí)候，內(nèi)存里會(huì)同時(shí)駐扎兩個(gè)對(duì)象的內(nèi)存，這一點(diǎn)會(huì)占用額外的內(nèi)存空間。

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

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

• 臟讀問(wèn)題

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

源碼分析

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

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

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

• 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方法十分普通，沒(méi)有任何鎖相關(guān)內(nèi)容，主要是保證讀取效率；

• 迭代器 COWIterator 類

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

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

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

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

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

最近給大家找了  Vue進(jìn)階

資源，怎么領(lǐng)取？

掃二維碼，加我微信，回復(fù)：Vue進(jìn)階
 注意，不要亂回復(fù) 

沒(méi)錯(cuò)，不是機(jī)器人
記得一定要等待，等待才有好東西