從源碼看ConcurrentHashMap

簡介

ConcurrentHashMap是線程安全的HashMap實現，這里主要研究JDK8后的ConcurrentHashMap，下面是ConcurrentHashMap的簡單結構：在這里插入圖片描述
ConcurrentHashMap基于HashMap的基本邏輯，通過CAS + synchronized 來保證并發安全性。ConcurrentHashMap使用的數組及數組的每個節點都為volatile類型，通過CAS進行更新刪除操作，而所有的鏈表操作都需要通過synchronized鎖定鏈表的頭節點，然后進行操作。

    /*** The array of bins. Lazily initialized upon first insertion.* Size is always a power of two. Accessed directly by iterators.*/transient volatile Node<K,V>[] table;/*** Key-value entry.  This class is never exported out as a* user-mutable Map.Entry (i.e., one supporting setValue; see* MapEntry below), but can be used for read-only traversals used* in bulk tasks.  Subclasses of Node with a negative hash field* are special, and contain null keys and values (but are never* exported).  Otherwise, keys and vals are never null.*/static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;volatile V val;volatile Node<K,V> next;}

核心方法

1.put方法

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;}

我們可以看到put是通過一個死循環來實現，在循環邏輯內：

  1. 首先檢查核心的Node<K,V>[] table是否已經初始化，如果沒有初始化，則利用CAS將sizeCtl的值置為-1進行初始化。
  2. 通過CAS查詢key相應的槽位是否為 null，若為null直接通過CAS將鍵值對放入槽位。
  3. 如果相應的槽位已經有節點，并且其hash值為-1，則表示正在進行擴容，則當前線程幫忙進行擴容。
  4. 否則通過synchronized鎖住槽位內的節點即鏈表的頭結點，然后遍歷鏈表，尋找是否有hash值及key值相同的節點，若有則將value設置進去，否者創建新的節點加入鏈表。
  5. 通過addCount函數更新ConcurrentHashMap鍵值對的數量。

2.get方法

    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;}

get方法實現的邏輯比較簡單：

  1. 利用key通過cas的方式獲取其對應槽位的節點，若該節點就是想要查詢的節點，那就直接返回value。
  2. 如果槽位內節點的hash值小于0則說明正在進行擴容，則通過ForwardingNode的find函數去新的數組nextTable中進行查找。
  3. 以上都不符合的話，就直接遍歷節點，匹配就返回，否則最后就返回null。

3.擴容方法

    /*** Helps transfer if a resize is in progress.*/final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {Node<K,V>[] nextTab; int sc;if (tab != null && (f instanceof ForwardingNode) &&(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {int rs = resizeStamp(tab.length);while (nextTab == nextTable && table == tab &&(sc = sizeCtl) < 0) {if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||sc == rs + MAX_RESIZERS || transferIndex <= 0)break;if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {transfer(tab, nextTab);break;}}return nextTab;}return table;}/*** Moves and/or copies the nodes in each bin to new table. See* above for explanation.*/private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {int n = tab.length, stride;if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)stride = MIN_TRANSFER_STRIDE; // subdivide rangeif (nextTab == null) {            // initiatingtry {@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];nextTab = nt;} catch (Throwable ex) {      // try to cope with OOMEsizeCtl = Integer.MAX_VALUE;return;}nextTable = nextTab;transferIndex = n;}int nextn = nextTab.length;ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);boolean advance = true;boolean finishing = false; // to ensure sweep before committing nextTabfor (int i = 0, bound = 0;;) {Node<K,V> f; int fh;while (advance) {int nextIndex, nextBound;if (--i >= bound || finishing)advance = false;else if ((nextIndex = transferIndex) <= 0) {i = -1;advance = false;}else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,nextBound = (nextIndex > stride ?nextIndex - stride : 0))) {bound = nextBound;i = nextIndex - 1;advance = false;}}if (i < 0 || i >= n || i + n >= nextn) {int sc;if (finishing) {nextTable = null;table = nextTab;sizeCtl = (n << 1) - (n >>> 1);return;}if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)return;finishing = advance = true;i = n; // recheck before commit}}else if ((f = tabAt(tab, i)) == null)advance = casTabAt(tab, i, null, fwd);else if ((fh = f.hash) == MOVED)advance = true; // already processedelse {synchronized (f) {if (tabAt(tab, i) == f) {Node<K,V> ln, hn;if (fh >= 0) {int runBit = fh & n;Node<K,V> lastRun = f;for (Node<K,V> p = f.next; p != null; p = p.next) {int b = p.hash & n;if (b != runBit) {runBit = b;lastRun = p;}}if (runBit == 0) {ln = lastRun;hn = null;}else {hn = lastRun;ln = null;}for (Node<K,V> p = f; p != lastRun; p = p.next) {int ph = p.hash; K pk = p.key; V pv = p.val;if ((ph & n) == 0)ln = new Node<K,V>(ph, pk, pv, ln);elsehn = new Node<K,V>(ph, pk, pv, hn);}setTabAt(nextTab, i, ln);setTabAt(nextTab, i + n, hn);setTabAt(tab, i, fwd);advance = true;}else if (f instanceof TreeBin) {TreeBin<K,V> t = (TreeBin<K,V>)f;TreeNode<K,V> lo = null, loTail = null;TreeNode<K,V> hi = null, hiTail = null;int lc = 0, hc = 0;for (Node<K,V> e = t.first; e != null; e = e.next) {int h = e.hash;TreeNode<K,V> p = new TreeNode<K,V>(h, e.key, e.val, null, null);if ((h & n) == 0) {if ((p.prev = loTail) == null)lo = p;elseloTail.next = p;loTail = p;++lc;}else {if ((p.prev = hiTail) == null)hi = p;elsehiTail.next = p;hiTail = p;++hc;}}ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :(hc != 0) ? new TreeBin<K,V>(lo) : t;hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :(lc != 0) ? new TreeBin<K,V>(hi) : t;setTabAt(nextTab, i, ln);setTabAt(nextTab, i + n, hn);setTabAt(tab, i, fwd);advance = true;}}}}}}

擴容的邏輯比較復雜，如果擴容時有多個線程，那么每個線程都可以通過helpTransfer函數幫忙進行擴容：

  1. 首先新建一個兩倍長度的數組nextTable。
  2. 初始化ForwardingNode節點，其中保存了新數組nextTable的引用，在處理完每個槽位節點后當做占位節點，表示該槽位已經處理過了。
  3. 通過for循環處理每個槽位中的鏈表元素，處理完后在這個槽位內通過CAS插入初始化的ForwardingNode節點，用于告訴其它線程該槽位已經處理過了。
  4. 如果某個槽位已經被線程A處理了，那么線程B處理到這個節點時，取到該節點的hash值應該為MOVED，值為-1，則直接跳過，繼續處理下一個槽位內的節點。

4.計數方法

    /*** {@inheritDoc}*/public int size() {long n = sumCount();return ((n < 0L) ? 0 :(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :(int)n);}/*** A padded cell for distributing counts.  Adapted from LongAdder* and Striped64.  See their internal docs for explanation.*/@sun.misc.Contended static final class CounterCell {volatile long value;CounterCell(long x) { value = x; }}final long sumCount() {CounterCell[] as = counterCells; CounterCell a;long sum = baseCount;if (as != null) {for (int i = 0; i < as.length; ++i) {if ((a = as[i]) != null)sum += a.value;}}return sum;}

代碼里的變量baseCount用于在無競爭環境下記錄元素的個數，每當插入元素或刪除元素時都會利用CAS更新鍵值對個數。
當有線程競爭時，會使用CounterCell數組來計數，每個ConuterCell都是一個獨立的計數單元。線程可以通過ThreadLocalRandom.getProbe() & m找到屬于它的CounterCell進行計數。這種方法能夠降低線程的競爭，相比所有線程對一個共享變量不停進行CAS操作性能上要好很多。這里的CounterCell數組初始容量為2，最大容量是機器的CPU數。
注意這里有個@sun.misc.Contended，這個注解用于解決偽共享問題。所謂偽共享，就是在同一緩存行cache line（CPU緩存的基本單位）中連續存儲了多個變量，當其中一個變量被修改時，會導致其他變量也失效，會降低計算機cache的緩存命中率并且導致內存總線流量大增。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/450929.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/450929.shtml
英文地址，請注明出處：http://en.pswp.cn/news/450929.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

代碼重構的方法

代碼重構的方法

見&#xff1a;http://blog.csdn.net/u011889786/article/details/51865344 見&#xff1a;http://blog.csdn.net/weiky626/article/details/1602691 一.提取子函數 說白了就是一個大函數里&#xff0c;可以根據不同功能分成幾個小函數&#xff0c;因為說不定&#xff0c;其他…
閱讀更多...
android 去掉標題欄、狀態欄、橫屏

android 去掉標題欄、狀態欄、橫屏

// 去掉標題欄supportRequestWindowFeature(Window.FEATURE_NO_TITLE);// 全屏、隱藏狀態欄getWindow().setFlags(WindowManager.LayoutParams.FLAG_FULLSCREEN, WindowManager.LayoutParams.FLAG_FULLSCREEN);// 橫屏setRequestedOrientation(ActivityInfo.SCREEN_ORIENTATION…
閱讀更多...
Spring Boot 整合Mybatis (一)

Spring Boot 整合Mybatis (一)

2019獨角獸企業重金招聘Python工程師標準>>> 新建spring-boot項目&#xff0c;相關依賴 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-jpa</artifactId></dependency><de…
閱讀更多...
x264 的 cache詳解

x264 的 cache詳解

在這里和下一級別的分析中有必要先講一下這個h->mb.cache&#xff08;沒法講&#xff0c;就是cache!&#xff09;。 x264_macroblock_cache_load將參考幀中某位置的&#xff08;重建后&#xff09;數據保存進cache&#xff0c;供參考和反復使用。 x264_macroblock_cache_s…
閱讀更多...
同步/異步阻塞/非阻塞

同步/異步阻塞/非阻塞

平時開發中經常會聽大家說到什么同步阻塞、異步非阻塞等等名詞&#xff0c;這里我談下自己對這兩個名詞的理解&#xff0c;僅僅是個人觀點&#xff0c;并不一定正確。 1.阻塞/非阻塞 我認為判定阻塞還是非阻塞&#xff0c;取決于線程所做的操作是否需要將線程掛起等待。 舉個…
閱讀更多...
Repeater的使用

Repeater的使用

1.頁面代碼 如果要分頁&#xff0c;那么頁面開頭必須寫&#xff08;<% Register Src"~/Controls/Page.ascx" TagName"Page" TagPrefix"uc1" %>&#xff09; 并且分頁&#xff0c;頁腳<uc1:Page ID"Page2" runat"server&…
閱讀更多...
springboot 整合 mongodb實現 批量更新數據

springboot 整合 mongodb實現 批量更新數據

現需求&#xff1a;需要批量將1000個數據先查詢在更新到mongodb&#xff08;如果查詢不到數據&#xff0c;則添加數據&#xff09; 1&#xff1a;工具類BathUpdateOptions 1 import org.springframework.data.mongodb.core.query.Query;2 import org.springframework.data.mong…
閱讀更多...
【開題報告】基于微信小程序的校園資訊平臺的設計與實現

【開題報告】基于微信小程序的校園資訊平臺的設計與實現

1.選題背景與意義 隨著移動互聯網的快速發展&#xff0c;微信成為了人們日常生活中不可或缺的工具之一。在校園生活中&#xff0c;學生們對于校園資訊的獲取和交流需求也越來越高。然而&#xff0c;傳統的校園資訊發布方式存在信息不及時、傳播范圍有限等問題&#xff0c;無法…
閱讀更多...
三種Cache寫入方式原理簡介

三種Cache寫入方式原理簡介

三種Cache寫入方式原理簡介 在386以上檔次的微機中&#xff0c;為了提高系統效率&#xff0c;普遍采用Cache&#xff08;高速緩沖存儲器&#xff09;&#xff0c;現在的系統甚至可以擁有多級Cache。Cache實際上是位于CPU與DRAM主存儲器之間少量超高速的靜態存儲器&#xff08;S…
閱讀更多...
Minor GC和Full GC

Minor GC和Full GC

我們在日常開發中可能經常會聽大家談論GC&#xff0c;但是其實很多人對GC的種類其實并不是很了解&#xff0c;接下來我們簡單介紹下Minor GC和Full GC及他們的區別。 MinorGC&#xff1a; 也可以叫作新生代GC&#xff0c;指的是發生在新生代的垃圾收集動作。因為新生代中對象大…
閱讀更多...
linux安裝軟件的幾種方法

linux安裝軟件的幾種方法

見&#xff1a;http://blog.csdn.net/u010509774/article/details/50593231 一、rpm包安裝方式步驟&#xff1a; 1、找到相應的軟件包&#xff0c;比如soft.version.rpm&#xff0c;下載到本機某個目錄&#xff1b; 2、打開一個終端&#xff0c;su -成root用戶&#xff1b; …
閱讀更多...
Android NDK MediaCodec在ijkplayer中的實踐

Android NDK MediaCodec在ijkplayer中的實踐

https://www.jianshu.com/p/41d3147a5e07 從API 21&#xff08;Android 5.0&#xff09;開始Android提供C層的NDK MediaCodec的接口。 Java MediaCodec是對NDK MediaCodec的封裝&#xff0c;ijkplayer硬解通路一直使用的是Java MediaCodec接Surface的方式。 本文的主要內容是&a…
閱讀更多...
leetcode-49-字母異位詞分組（神奇的哈希）

leetcode-49-字母異位詞分組（神奇的哈希）

題目描述&#xff1a; 給定一個字符串數組&#xff0c;將字母異位詞組合在一起。字母異位詞指字母相同&#xff0c;但排列不同的字符串。 示例: 輸入: ["eat", "tea", "tan", "ate", "nat", "bat"], 輸出: [[&quo…
閱讀更多...
【精心總結】java內存模型和多線程必會知識

【精心總結】java內存模型和多線程必會知識

內存模型 &#xff08;1&#xff09;java內存模型到底是個啥子東西&#xff1f; java內存模型是java虛擬機規范定義的一種特定模型&#xff0c;用以屏蔽不同硬件和操作系統的內存訪問差異&#xff0c;讓java在不同平臺中能達到一致的內存訪問效果&#xff0c;是在特定的協議下…
閱讀更多...
工作流 activity 視頻教程 + redis 視頻教程 百度網盤分享地址

工作流 activity 視頻教程 + redis 視頻教程 百度網盤分享地址

前些天發現了一個巨牛的人工智能學習網站&#xff0c;通俗易懂&#xff0c;風趣幽默&#xff0c;忍不住分享一下給大家。點擊跳轉到教程。 云盤下載都沒有密碼&#xff0c;直接下載&#xff0c;解壓有密碼&#xff1a;chongxiangmengxiangjiaoyu&#xff0c; 解壓完成后就可以…
閱讀更多...
快速解決 GRADLE 項目下載 gradle-*-all.zip 慢的問題

快速解決 GRADLE 項目下載 gradle-*-all.zip 慢的問題

1、首先根據項目中 gradle\wrapper\gradle-wrapper.properties 文件的 distributionUrl 屬性的值 #Tue Feb 06 12:27:20 CET 2018 distributionBaseGRADLE_USER_HOME distributionPathwrapper/dists zipStoreBaseGRADLE_USER_HOME zipStorePathwrapper/dists distributionUrlht…
閱讀更多...
[Python] 程序結構與控制流

[Python] 程序結構與控制流

1. 條件語句 if、else與elif語句用于控制條件代碼的執行。條件語句的一般格式如下&#xff1a; if expression:statements elif expression:statements elif expression:statements ... else:statements 如果不需要執行任何操作&#xff0c;可以省略條件語句的else和elif子句。…
閱讀更多...
webrtc 源碼結構

webrtc 源碼結構

apiWebRTC 接口層。包括 DataChannel, MediaStream, SDP相關的接口。各瀏覽器都是通過該接口層調用的 WebRTC。call存放的是 WebRTC “呼叫&#xff08;Call&#xff09;” 相關邏輯層的代碼。audio存放音頻網絡邏輯層相關的代碼。音頻數據邏輯上的發送&#xff0c;接收等代碼。…
閱讀更多...
mysql查詢流程解析及重要知識總結

mysql查詢流程解析及重要知識總結

時光荏苒啊&#xff01;在過兩個月我就工作滿三年了&#xff0c;大學畢業的情景還歷歷在目&#xff0c;而我已經默默的向油膩中年大叔進發了。作為一名苦逼的后端工程師&#xff0c;我搞過一段時間python&#xff0c;現在靠java糊口&#xff0c;但后來才發現&#xff0c;始終不…
閱讀更多...
界面無小事(八):RecyclerView增刪item

界面無小事(八):RecyclerView增刪item

界面無小事(一): RecyclerViewCardView了解一下 界面無小事(二): 讓RecyclerView展示更多不同視圖 界面無小事(三):用RecyclerView Toolbar做個文件選擇器 界面無小事(四):來寫個滾動選擇器吧! 界面無小事(五):自定義TextView 界面無小事(六):來做個好看得側拉菜單! 界面無小事…
閱讀更多...
最新文章

Copyright @ 2022~2023