ConcurreentHashMap的實現(xiàn)原理與使用

ConcurrentHashMap是線程安全且高效的HashMap锯茄。

為什么要使用ConcurrentHashMap

在并發(fā)編程中使用HashMap可能導(dǎo)致程序死循環(huán)。而使用線程安全的HashTable效率又非常低下茶没，基于以上兩個原因肌幽，便有了ConcurrentHashMap的登場機會。

1. 線程不安全的HashMap

   在多線程環(huán)境下抓半，使用HashMap進行put操作會引起死循環(huán)喂急，導(dǎo)致CPU利用率接近100%，所以在并發(fā)情況下不能使用HashMap笛求。

   HashMap在并發(fā)執(zhí)行put操作時會引起死循環(huán)廊移，是因為多線程會導(dǎo)致HashMap的Entry鏈表形成環(huán)形數(shù)據(jù)結(jié)構(gòu)，一旦形成環(huán)形數(shù)據(jù)結(jié)構(gòu)探入，Entry的next節(jié)點永遠不為空狡孔，，就會產(chǎn)生死循環(huán)獲取Entry蜂嗽。

2. 效率低下的HashTable

   HashTable容器使用了synchronized來保證線程安全步氏，但在線程競爭激烈的情況下HashTable的效率非常低下。因為當(dāng)一個線程訪問HashTable的同步方法徒爹，其他線程也訪問HashTable的同步方法時，會進入阻塞或輪詢狀態(tài)芋类。

3. ConcurrentHashMap的鎖分段技術(shù)可有效提升并發(fā)訪問率

   容器里有很多把鎖隆嗅，每一把鎖用于鎖容器中其中一部分數(shù)據(jù)，那么當(dāng)多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)時侯繁，線程間就不會存在鎖競爭胖喳，從而可以有效提高并發(fā)訪問效率，這就是ConcurrentHashMap所使用的鎖分段技術(shù)贮竟。

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

ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)據(jù)結(jié)構(gòu)組成丽焊。Segment是一種可重入鎖（ReentrantLock），在ConcurrentHashMap里扮演鎖的角色咕别；HashEntry則用于存儲鍵值對數(shù)據(jù)技健。

255.png

256.png

ConcurrentHashMap的操作

1. get操作

   Segment的get操作實現(xiàn)非常簡單和高效。先經(jīng)過一次再散列惰拱，然后使用這個散列值通過散列運算定位到Segment雌贱，再通過散列算法定位到元素：

    public V get(Object key) {
           Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
           int h = spread(key.hashCode());
           if ((tab = table) != null && (n = tab.length) > 0 &&
               (e = tabAt(tab, (n - 1) & h)) != null) {
               if ((eh = e.hash) == h) {
                   if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                       return e.val;
               }
               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;
       }
   

2. put操作

   由于put操作方法里需要對共享變量進行寫操作，所以為了線程安全，在操作共享變量時必須加鎖欣孤。

   public V put(K key, V value) {
           return putVal(key, value, false);
       }
   final V putVal(K key, V value, boolean onlyIfAbsent) {
           if (key == null || value == null) throw new NullPointerException();
           int hash = spread(key.hashCode());
           int binCount = 0;
           for (Node<K,V>[] tab = table;;) {
               Node<K,V> f; int n, i, fh;
               if (tab == null || (n = tab.length) == 0)
                   tab = initTable();
               else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                   if (casTabAt(tab, i, null,
                                new Node<K,V>(hash, key, value, null)))
                       break;                   // no lock when adding to empty bin
               }
               else if ((fh = f.hash) == MOVED)
                   tab = helpTransfer(tab, f);
               else {
                   V oldVal = null;
                   synchronized (f) {
                       if (tabAt(tab, i) == f) {
                           if (fh >= 0) {
                               binCount = 1;
                               for (Node<K,V> e = f;; ++binCount) {
                                   K ek;
                                   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;
                                   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;
                               if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                              value)) != null) {
                                   oldVal = p.val;
                                   if (!onlyIfAbsent)
                                       p.val = value;
                               }
                           }
                       }
                   }
                   if (binCount != 0) {
                       if (binCount >= TREEIFY_THRESHOLD)
                           treeifyBin(tab, i);
                       if (oldVal != null)
                           return oldVal;
                       break;
                   }
               }
           }
           addCount(1L, binCount);
           return null;
       }
   

(1)是否需要擴容

在插入元素前先會先判斷Segment里的HashEntry數(shù)組是否超過容量（threshold）馋没，如果超過閾值，則對數(shù)組進行擴容

(2)如何擴容

在擴容的時候降传，首先會創(chuàng)建一個容量是原來容量兩倍的數(shù)組篷朵，然后對原數(shù)組里的元素進行再散列后插入到新的數(shù)組里。為了高效婆排，ConcurrentHashMap不會對整個容器進行擴容声旺，而只對某個segment進行擴容。

3. size操作

   如果要統(tǒng)計整個ConcurrentHashMap里元素的大小泽论，就必須統(tǒng)計所有Segment里的元素的大小后求和艾少。

   public int size() {
           long n = sumCount();
           return ((n < 0L) ? 0 :
                   (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                   (int)n);
       }