原文：https://www.cnblogs.com/hexinwei1/p/10000779.html

一、小總結

1、HashMap 、HashTable、 ConcurrentHashMap

HashMap：線程不安全

HashTable：線程安全，每個方法都加了 synchronized 修飾。類似 Collections.synchronizedMap(hashMap)

對讀寫加鎖，獨占式，一個線程在讀時其他線程必須等待，吞吐量較低，性能較為低下。

ConcurrentHashMap：利用CAS+Synchronized來保證并發的安全性。數據結構同HashMap。

2、ConcurrentHashMap如何實現線程安全？

（1）get()方法使用tabAt(Node<k, v="">[], int)方法

調用Unsafe的native方法 getObjectVolatile(Object obj, long offset);
// 獲取obj對象中offset偏移地址對應的object型field的值，支持volatile load語義，即：讓緩存中的數據失效，重新從主內存加載數據

（2）put()方法

　　①需要獲取數組上的Node時同樣使用tabAt()方法

　　②設置數組上Node是使用casTabAt() 方法，casTabAt()調用Unsafe的native方法compareAndSwapObject()，CAS操作

　　③哈希沖突之后，需要操作改hash值對應的鏈表/紅黑樹，此時synchronized(該鏈表第一個Node)保證線程安全的基礎上，減小了鎖的粒度。

3、線程安全的容器只能保證自身的數據不被破壞，但無法保證業務的行為是否正確。

1 public static void demo1() { 2 final Map<String, Integer> count = new ConcurrentHashMap<>(); 3 final CountDownLatch endLatch = new CountDownLatch(2); 4 Runnable task = new Runnable() { 5 @Override 6 public void run() { 7 for (int i = 0; i < 5; i++) { 8 Integer value = count.get("a"); 9 if (null == value) { 10 count.put("a", 1); 11 } else { 12 count.put("a", value + 1); 13 } 14 } 15 endLatch.countDown(); 16 } 17 }; 18 new Thread(task).start(); 19 new Thread(task).start(); 20 21 try { 22 endLatch.await(); 23 System.out.println(count); 24 } catch (Exception e) { 25 e.printStackTrace(); 26 } 27 }

demo1是兩個線程操作ConcurrentHashMap，意圖將value變為10。但是，因為多個線程用相同的key調用時，很可能會覆蓋相互的結果，造成記錄的次數比實際出現的次數少。

當然可以用鎖解決這個問題，但是也可以使用ConcurrentMap定義的方法：

V putIfAbsent(K key, V value)如果key對應的value不存在，則put進去，返回null。否則不put，返回已存在的value。boolean remove(Object key, Object value)如果key對應的值是value，則移除K-V，返回true。否則不移除，返回false。boolean replace(K key, V oldValue, V newValue)如果key對應的當前值是oldValue，則替換為newValue，返回true。否則不替換，返回false。

修改：

1 public static void demo1() { 2 final Map<String, Integer> count = new ConcurrentHashMap<>(); 3 final CountDownLatch endLatch = new CountDownLatch(2); 4 Runnable task = new Runnable() { 5 @Override 6 public void run() { 7 Integer oldValue, newValue; 8 for (int i = 0; i < 5; i++) { 9 while (true) { 10 oldValue = count.get("a"); 11 if (null == oldValue) { 12 newValue = 1; 13 if (count.putIfAbsent("a", newValue) == null) { 14 break; 15 } 16 } else { 17 newValue = oldValue + 1; 18 if (count.replace("a", oldValue, newValue)) { 19 break; 20 } 21 } 22 } 23 } 24 endLatch.countDown(); 25 } 26 }; 27 new Thread(task).start(); 28 new Thread(task).start(); 29 30 try { 31 endLatch.await(); 32 System.out.println(count); 33 } catch (Exception e) { 34 e.printStackTrace(); 35 } 36 }

由于ConcurrentMap中不能保存value為null的值，所以需要處理不存在和已存在兩種情況，不過可以使用AtomicInteger來替代。

1 public static void demo1() { 2 final Map<String, AtomicInteger> count = new ConcurrentHashMap<>(); 3 final CountDownLatch endLatch = new CountDownLatch(2); 4 Runnable task = new Runnable() { 5 @Override 6 public void run() { 7 AtomicInteger oldValue; 8 for (int i = 0; i < 5; i++) { 9 oldValue = count.get("a"); 10 if (null == oldValue) { 11 AtomicInteger zeroValue = new AtomicInteger(0); 12 oldValue = count.putIfAbsent("a", zeroValue); 13 if (null == oldValue) { 14 oldValue = zeroValue; 15 } 16 } 17 oldValue.incrementAndGet(); 18 } 19 endLatch.countDown(); 20 } 21 }; 22 new Thread(task).start(); 23 new Thread(task).start(); 24 25 try { 26 endLatch.await(); 27 System.out.println(count); 28 } catch (Exception e) { 29 e.printStackTrace(); 30 } 31 }

二、屬性

1 // 最大容量：2^30=1073741824 2 private static final int MAXIMUM_CAPACITY = 1 << 30; 3 4 // 默認初始值，必須是2的幕數 5 private static final int DEFAULT_CAPACITY = 16; 6 7 // 8 static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 9 10 // 11 private static final int DEFAULT_CONCURRENCY_LEVEL = 16; 12 13 // 14 private static final float LOAD_FACTOR = 0.75f; 15 16 // 鏈表轉紅黑樹閥值,> 8 鏈表轉換為紅黑樹 17 static final int TREEIFY_THRESHOLD = 8; 18 19 //樹轉鏈表閥值，小于等于6（tranfer時，lc、hc=0兩個計數器分別++記錄原bin、新binTreeNode數量，<=UNTREEIFY_THRESHOLD 則untreeify(lo)） 20 static final int UNTREEIFY_THRESHOLD = 6; 21 22 // 23 static final int MIN_TREEIFY_CAPACITY = 64; 24 25 // 26 private static final int MIN_TRANSFER_STRIDE = 16; 27 28 // 29 private static int RESIZE_STAMP_BITS = 16; 30 31 // 2^15-1，help resize的最大線程數 32 private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; 33 34 // 32-16=16，sizeCtl中記錄size大小的偏移量 35 private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; 36 37 // forwarding nodes的hash值 38 static final int MOVED = -1; 39 40 // 樹根節點的hash值 41 static final int TREEBIN = -2; 42 43 // ReservationNode的hash值 44 static final int RESERVED = -3; 45 46 // 可用處理器數量 47 static final int NCPU = Runtime.getRuntime().availableProcessors();

幾個很重要的概念：

（1）table：用來存放Node節點數據的，默認為null，默認大小為16的數組，每次擴容時大小總是2的冪次方；

（2）nextTable：擴容時新生成的數據，數組為table的兩倍；

（3）Node：節點，保存key-value的數據結構；

（4）ForwardingNode：一個特殊的Node節點，hash值為-1，其中存儲nextTable的引用。只有table發生擴容的時候，ForwardingNode才會發揮作用，作為一個占位符放在table中表示當前節點為null或則已經被移動

（5）sizeCtl：控制標識符，用來控制table初始化和擴容操作的，在不同的地方有不同的用途，其值也不同，所代表的含義也不同

負數代表正在進行初始化或擴容操作

-1代表正在初始化

-N 表示有N-1個線程正在進行擴容操作

正數或0代表hash表還沒有被初始化，這個數值表示初始化或下一次進行擴容的大小

三、構造

1 public ConcurrentHashMap() { 2 } 3 4 public ConcurrentHashMap(int initialCapacity) { 5 if (initialCapacity < 0) 6 throw new IllegalArgumentException(); 7 int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? 8 MAXIMUM_CAPACITY : 9 tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); 10 this.sizeCtl = cap; 11 } 12 13 public ConcurrentHashMap(Map<? extends K, ? extends V> m) { 14 this.sizeCtl = DEFAULT_CAPACITY; 15 putAll(m); 16 } 17 18 public ConcurrentHashMap(int initialCapacity, float loadFactor) { 19 this(initialCapacity, loadFactor, 1); 20 } 21 22 public ConcurrentHashMap(int initialCapacity, 23 float loadFactor, int concurrencyLevel) { 24 if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0) 25 throw new IllegalArgumentException(); 26 if (initialCapacity < concurrencyLevel) // Use at least as many bins 27 initialCapacity = concurrencyLevel; // as estimated threads 28 long size = (long)(1.0 + (long)initialCapacity / loadFactor); 29 int cap = (size >= (long)MAXIMUM_CAPACITY) ? 30 MAXIMUM_CAPACITY : tableSizeFor((int)size); 31 this.sizeCtl = cap; 32 }

四、put()

1 public V put(K key, V value) { 2 return putVal(key, value, false); 3 } 4 5 final V putVal(K key, V value, boolean onlyIfAbsent) { 6 if (key == null || value == null) throw new NullPointerException(); 7 // 得到 hash 值 8 int hash = spread(key.hashCode()); 9 // 用于記錄相應鏈表的長度 10 int binCount = 0; 11 for (Node<K,V>[] tab = table;;) { 12 Node<K,V> f; int n, i, fh; 13 // 如果數組"空"，進行數組初始化 14 if (tab == null || (n = tab.length) == 0) 15 // 初始化數組，后面會詳細介紹 16 tab = initTable(); 17 18 // 找該 hash 值對應的數組下標，得到第一個節點 f 19 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { 20 // 如果數組該位置為空， 21 // 用一次 CAS 操作將這個新值放入其中即可，這個 put 操作差不多就結束了，可以拉到最后面了 22 // 如果 CAS 失敗，那就是有并發操作，進到下一個循環就好了 23 if (casTabAt(tab, i, null, 24 new Node<K,V>(hash, key, value, null))) 25 break; // no lock when adding to empty bin 26 } 27 // hash 居然可以等于 MOVED，這個需要到后面才能看明白，不過從名字上也能猜到，肯定是因為在擴容 28 else if ((fh = f.hash) == MOVED) 29 // 幫助數據遷移，這個等到看完數據遷移部分的介紹后，再理解這個就很簡單了 30 tab = helpTransfer(tab, f); 31 32 else { // 到這里就是說，f 是該位置的頭結點，而且不為空 33 34 V oldVal = null; 35 // 獲取數組該位置的頭結點的監視器鎖 36 synchronized (f) { 37 if (tabAt(tab, i) == f) { 38 if (fh >= 0) { // 頭結點的 hash 值大于 0，說明是鏈表 39 // 用于累加，記錄鏈表的長度 40 binCount = 1; 41 // 遍歷鏈表 42 for (Node<K,V> e = f;; ++binCount) { 43 K ek; 44 // 如果發現了"相等"的 key，判斷是否要進行值覆蓋，然后也就可以 break 了 45 if (e.hash == hash && 46 ((ek = e.key) == key || 47 (ek != null && key.equals(ek)))) { 48 oldVal = e.val; 49 if (!onlyIfAbsent) 50 e.val = value; 51 break; 52 } 53 // 到了鏈表的最末端，將這個新值放到鏈表的最后面 54 Node<K,V> pred = e; 55 if ((e = e.next) == null) { 56 pred.next = new Node<K,V>(hash, key, 57 value, null); 58 break; 59 } 60 } 61 } 62 else if (f instanceof TreeBin) { // 紅黑樹 63 Node<K,V> p; 64 binCount = 2; 65 // 調用紅黑樹的插值方法插入新節點 66 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, 67 value)) != null) { 68 oldVal = p.val; 69 if (!onlyIfAbsent) 70 p.val = value; 71 } 72 } 73 } 74 } 75 76 if (binCount != 0) { 77 // 判斷是否要將鏈表轉換為紅黑樹，臨界值和 HashMap 一樣，也是 8 78 if (binCount >= TREEIFY_THRESHOLD) 79 // 這個方法和 HashMap 中稍微有一點點不同，那就是它不是一定會進行紅黑樹轉換， 80 // 如果當前數組的長度小于 64，那么會選擇進行數組擴容，而不是轉換為紅黑樹 81 // 具體源碼我們就不看了，擴容部分后面說 82 treeifyBin(tab, i); 83 if (oldVal != null) 84 return oldVal; 85 break; 86 } 87 } 88 } 89 // 90 addCount(1L, binCount); 91 return null; 92 }

按照上面的源碼，我們可以確定put整個流程如下：

• 判空；ConcurrentHashMap的key、value都不允許為null

• 計算hash。利用方法計算hash值。

• 遍歷table，進行節點插入操作，過程如下：

  • 如果table為空，則表示ConcurrentHashMap還沒有初始化，則進行初始化操作：initTable()

  • 根據hash值獲取節點的位置i，若該位置為空，則直接插入，這個過程是不需要加鎖的。計算f位置：i=(n – 1) & hash

  • 如果檢測到fh = f.hash == -1，則f是ForwardingNode節點，表示有其他線程正在進行擴容操作，則幫助線程一起進行擴容操作

  • 如果f.hash >= 0 表示是鏈表結構，則遍歷鏈表，如果存在當前key節點則替換value，否則插入到鏈表尾部。如果f是TreeBin類型節點，則按照紅黑樹的方法更新或者增加節點

  • 若鏈表長度 > TREEIFY_THRESHOLD(默認是8)，則將鏈表轉換為紅黑樹結構

• 調用addCount方法，ConcurrentHashMap的size + 1

這里整個put操作已經完成。

五、get()

1 public V get(Object key) { 2 Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; 3 // 計算hash 4 int h = spread(key.hashCode()); 5 if ((tab = table) != null && (n = tab.length) > 0 && 6 (e = tabAt(tab, (n - 1) & h)) != null) { 7 // 搜索到的節點key與傳入的key相同且不為null,直接返回這個節點 8 if ((eh = e.hash) == h) { 9 if ((ek = e.key) == key || (ek != null && key.equals(ek))) 10 return e.val; 11 } 12 // 樹 13 else if (eh < 0) 14 return (p = e.find(h, key)) != null ? p.val : null; 15 // 鏈表，遍歷 16 while ((e = e.next) != null) { 17 if (e.hash == h && 18 ((ek = e.key) == key || (ek != null && key.equals(ek)))) 19 return e.val; 20 } 21 } 22 return null; 23 }

get操作：
? ?- 計算hash值
? ?- 判斷table是否為空，如果為空，直接返回null
? ?- 根據hash值獲取table中的Node節點（tabAt(tab, (n – 1) & h)），然后根據鏈表或者樹形方式找到相對應的節點，返回其value值。

六、擴容

1 // 首先要說明的是，方法參數 size 傳進來的時候就已經翻了倍了 2 private final void tryPresize(int size) { 3 // c：size 的 1.5 倍，再加 1，再往上取最近的 2 的 n 次方。 4 int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : 5 tableSizeFor(size + (size >>> 1) + 1); 6 int sc; 7 while ((sc = sizeCtl) >= 0) { 8 Node<K,V>[] tab = table; int n; 9 10 // 這個 if 分支和之前說的初始化數組的代碼基本上是一樣的，在這里，我們可以不用管這塊代碼 11 if (tab == null || (n = tab.length) == 0) { 12 n = (sc > c) ? sc : c; 13 if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { 14 try { 15 if (table == tab) { 16 @SuppressWarnings("unchecked") 17 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; 18 table = nt; 19 sc = n - (n >>> 2); // 0.75 * n 20 } 21 } finally { 22 sizeCtl = sc; 23 } 24 } 25 } 26 else if (c <= sc || n >= MAXIMUM_CAPACITY) 27 break; 28 else if (tab == table) { 29 // 我沒看懂 rs 的真正含義是什么，不過也關系不大 30 int rs = resizeStamp(n); 31 32 if (sc < 0) { 33 Node<K,V>[] nt; 34 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || 35 sc == rs + MAX_RESIZERS || (nt = nextTable) == null || 36 transferIndex <= 0) 37 break; 38 // 2. 用 CAS 將 sizeCtl 加 1，然后執行 transfer 方法 39 // 此時 nextTab 不為 null 40 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) 41 transfer(tab, nt); 42 } 43 // 1. 將 sizeCtl 設置為 (rs << RESIZE_STAMP_SHIFT) + 2) 44 // 我是沒看懂這個值真正的意義是什么？不過可以計算出來的是，結果是一個比較大的負數 45 // 調用 transfer 方法，此時 nextTab 參數為 null 46 else if (U.compareAndSwapInt(this, SIZECTL, sc, 47 (rs << RESIZE_STAMP_SHIFT) + 2)) 48 transfer(tab, null); 49 } 50 } 51 }

這個方法的核心在于 sizeCtl 值的操作，首先將其設置為一個負數，然后執行 transfer(tab, null)，再下一個循環將 sizeCtl 加 1，并執行 transfer(tab, nt)，之后可能是繼續 sizeCtl 加 1，并執行 transfer(tab, nt)。

所以，可能的操作就是執行 1 次 transfer(tab, null) + 多次 transfer(tab, nt)，關于這個可以查看源碼，篇幅過長，這里不說了。

轉載于:https://www.cnblogs.com/chuanyueinlife/articles/10212385.html

總結

以上是生活随笔為你收集整理的HashMap,HashTable,ConcurrentHashMap面试总结！！！的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。