Java source code Learning Series: concurrent HashMap source code analysis of JDK1.8

itread01 2021-01-23 23:24:38
java source code learning series


[toc] Serial portal :- [Java And contract source code learning series :AbstractQueuedSynchronizer](https://blog.csdn.net/Sky_QiaoBa_Sum/article/details/112254373)- [Java And contract source code learning series :CLH Synchronization queue and synchronization resource acquisition and release ](https://blog.csdn.net/Sky_QiaoBa_Sum/article/details/112301359)- [Java And contract source code learning series :AQS The difference between sharing and exclusive resource acquisition and release ](https://blog.csdn.net/Sky_QiaoBa_Sum/article/details/112386838)- [Java And contract source code learning series :ReentrantLock Reentrant exclusive lock details ](https://blog.csdn.net/Sky_QiaoBa_Sum/article/details/112454874)- [Java And contract source code learning series :ReentrantReadWriteLock Analysis of read write lock ](https://blog.csdn.net/Sky_QiaoBa_Sum/article/details/112689635)- [Java And contract source code learning series : Detailed explanation Condition Condition queue 、signal and await](https://blog.csdn.net/Sky_QiaoBa_Sum/article/details/112727669)- [Java And contract source code learning series : Suspend and wake threads LockSupport Tool class ](https://blog.csdn.net/Sky_QiaoBa_Sum/article/details/112757098) notes : This article is based on JDK1.8.## Why use ConcurrentHashMap? Before thinking about it , We can think about : If not ConcurrentHashMap And then , What other containers are available for us to choose from ? And what are their flaws ? Hash table using hash algorithm can cost O(1) According to the time complexity of key find value value , The container that can meet this need is HashTable and HashMap.**HashTable**HashTable Use synchronized Keywords ensure security in multithreaded environments , But the implementation of locking is exclusive , All visits HashTable All threads must compete for the same lock , The efficiency is relatively low .```java public synchronized V put(K key, V value) { // ... }```**HashMap**JDK1.8 Version of HashMap Reading hash When the slot is opened, the object that the reference points to in the working memory is read , In a multithreaded environment , Values modified by other threads cannot be read in time .- About HashMap Source code analysis of :[【JDK1.8】Java Set source code learning series :HashMap Source code details ](https://blog.csdn.net/Sky_QiaoBa_Sum/article/details/104095675)> This leads to some possible problems :>> For example, during the insert operation ,** The first time will be based on key Of hash Value to determine whether the current slot is occupied , If not, it will be inserted value**. In a concurrent environment , If A The thread determines that the slot is not occupied , It happens that the time slice runs out while writing , Now B The thread happens to do the same thing , The first to insert B Of value, Now A By chance CPU Reschedule to continue writing , And then the thread B Of value Coverage .>> There's another situation where you're in the same hash In trough ,HashMap Always keep key only , At the time of insertion , If there is key, It will go on value Coverage . In the case of concurrency , If A The thread determines that the last node has not found a duplicate key, Then the insertion will be performed , If B Thread in A The same operation is performed between judgment and insertion , Data coverage also occurs , That is, the loss of data .>> Of course , There are still some concurrency problems like this , I won't go into details here , Just interested in small partners can check the following information .## ConcurrentHashMap The structural characteristics of ### Java8 Before that Java8 Before , The bottom layer adopts Segment+HashEntry How to achieve . Using the concept of segment lock , The bottom layer uses Segment Array ,Segment By inheritance ReentrantLock To lock , Each operation that needs to be locked will lock one segment, Segments ensure that each segment is thread safe .> Graph source :[Java7/8 Medium HashMap and ConcurrentHashMap Full resolution ](https://javadoop.com/post/hashmap)![](https://img2020.cnblogs.com/blog/1771072/202101/1771072-20210123181713661-756701711.png)### Java8 After that JDK1.8 And then we use `CAS + Synchronized` To ensure concurrency security . Adopt 【Node Array 】 Add 【 Link string 】 Add 【 Red and black trees 】 Structure of , And HashMap Similar .> Graph source :[Java7/8 Medium HashMap and ConcurrentHashMap Full resolution ](https://javadoop.com/post/hashmap)![](https://img2020.cnblogs.com/blog/1771072/202101/1771072-20210123181722181-597581021.png)## You can go through the basic constant , Don't worry too much , Some fields may be for compatibility Java8 Previous version .```java /* ---------------- Constants -------------- */ // Maximum capacity allowed private static final int MAXIMUM_CAPACITY = 1 << 30; // Default initial value 16, It has to be 2 Power private static final int DEFAULT_CAPACITY = 16; // toArray The amount that the relevant method may require static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // For and Java8 The previous section is compatible with the relevant content , Not used private static final int DEFAULT_CONCURRENCY_LEVEL = 16; // Load factor private static final float LOAD_FACTOR = 0.75f; // The threshold value of concatenation to red black tree > 8 Link string to red black tree static final int TREEIFY_THRESHOLD = 8; // Tree to link string threshold , Less than 6(tranfer When ,lc、hc=0 Two counters, respectively ++ Record the original bin、 new binTreeNode Quantity ,<=UNTREEIFY_THRESHOLD Then untreeify(lo)) static final int UNTREEIFY_THRESHOLD = 6; // The minimum capacity of concatenation treeing treeifyBin When , If the capacity is insufficient 64, Will choose to expand to 64 static final int MIN_TREEIFY_CAPACITY = 64; // Minimum number of knots per step private static final int MIN_TRANSFER_STRIDE = 16; // sizeCtl The number of bits used to generate tags in private static int RESIZE_STAMP_BITS = 16; // 2^15-1,help resize Maximum number of threads for private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; // 32-16=16,sizeCtl Recorded in size The offset of the size private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; // forwarding nodes Of hash value static final int MOVED = -1; // At the root of the tree hash value static final int TREEBIN = -2; // ReservationNode Of hash value static final int RESERVED = -3; // For ordinary node Node hash use static final int HASH_BITS = 0x7fffffff; // Number of processors available static final int NCPU = Runtime.getRuntime().availableProcessors();```## Important member variables ```java /* ---------------- Fields -------------- */ // It's what we call the bottom Node Array , Lazy , It's initialized the first time it's inserted , The size needs to be 2 Power transient volatile Node [] table; /** * Expansion resize Used when table */ private transient volatile Node [] nextTable; /** * Basic counter , Yes CAS To update */ private transient volatile long baseCount; /** * Table initialization and resizing control. * If it is a negative number : It means initializing or expanding , The details are as follows 、 * -1 Denotes initialization , * -N,N-1 Represents the number of threads being expanded * The default is 0, After initialization , Store the size of the next expansion */ private transient volatile int sizeCtl; /** * Split when expanding table The index of */ private transient volatile int transferIndex; /** * Spinlock (locked via CAS) used when resizing and/or creating CounterCells. */ private transient volatile int cellsBusy; /** * Table of counter cells. When non-null, size is a power of 2. */ private transient volatile CounterCell[] counterCells; // Look at private transient KeySetView keySet; private transient ValuesView values; private transient EntrySetView entrySet;```## Construction method and HashMap The same thing ,table The initialization of the array is done at the first insertion .```java /** * Build a new , Empty map, The default size is 16 */ public ConcurrentHashMap() { } /** * Specify initial capacity */ public ConcurrentHashMap(int initialCapacity) { if (initialCapacity < 0) throw new IllegalArgumentException(); int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : // hashmap I told you in , Is used to return the smallest... Greater than or equal to the value passed in 2 To the power of // https://blog.csdn.net/Sky_QiaoBa_Sum/article/details/104095675#tableSizeFor_105 tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); // sizeCtl Initialize to capacity this.sizeCtl = cap; } /** * Receive one map thing */ public ConcurrentHashMap(Map m) { this.sizeCtl = DEFAULT_CAPACITY; putAll(m); } /** * Specify initial capacity and load factor * @since 1.6 */ public ConcurrentHashMap(int initialCapacity, float loadFactor) { this(initialCapacity, loadFactor, 1); } /** * The most comprehensive : Capacity 、 Load factor 、 Concurrency level */ public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0) throw new IllegalArgumentException(); if (initialCapacity < concurrencyLevel) // Use at least as many bins initialCapacity = concurrencyLevel; // as estimated threads long size = (long)(1.0 + (long)initialCapacity / loadFactor); int cap = (size >= (long)MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)size); this.sizeCtl = cap; }``` Here tableSizeFor Method in HashMap It's been analyzed in :[https://blog.csdn.net/Sky_QiaoBa_Sum/article/details/104095675#tableSizeFor_105](https://blog.csdn.net/Sky_QiaoBa_Sum/article/details/104095675#tableSizeFor_105)### tableSizeFor We can know by annotation that , This method returns a value greater than or equal to the minimum value passed in 2 To the power of ( Incoming 1 When , For 1). How on earth did it come true , Let's take a look at the specific source code :```java static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }123456789``` To be honest , I'll see the implementation of this method , I sighed , Mathematics is good ! I put in the specific numbers , I read many articles and videos about this part , By a simple example , Let's summarize .- Let's try to think about , We want to get a ratio of n Large minimum 2 The power just needs to be ** In front of the highest position 1, All in the back 0** Just ok Is that right . Such as 0101 It stands for 5,1000 That's what we need 8.- Let's pass in a larger number , For the convenience of writing , This is where 8 For example :![](https://img2020.cnblogs.com/blog/1771072/202101/1771072-20210123181737808-614670333.png)- First step `int n = cap -1` This step is to prevent cap It is 2 The power of , If not for this step , After an operation , It's going to double . For example, the incoming is 8, It's going to be 16, So subtract... In advance 1, Guarantee the result .- Finally n<0 The judgment of the situation , Excluding the incoming capacity of 0 Situation of .- n>=MAXIMUM_CAPACITY The judgment of the situation , After excluding the shift sum or operation, all are 1 Situation of .## put Method store value ### putVal```java public V put(K key, V value) { return putVal(key, value, false); } /** Implementation for put and putIfAbsent */ final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); // Yes key Make a hash calculation : (h ^ (h >>> 16)) & HASH_BITS; int hash = spread(key.hashCode()); // Record the length of the link string int binCount = 0; for (Node [] tab = table;;) { Node f; int n, i, fh; // for the first time put, It's here to initialize if (tab == null || (n = tab.length) == 0) tab = initTable(); // Find this hash Array subscript corresponding to value , Get the first node f, // Here's the judgment f Is it empty , Is there any node in this position else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // If not , use CAS Try putting the value in , Insert the success , Then exit for Turn around // If CAS Failure , Indicates that there is concurrent competition , Enter the circle again if (casTabAt(tab, i, null, new Node (hash, key, value, null))) break; // no lock when adding to empty bin } // hash yes Node Node f An attribute of , Equal to MOVED Indicates that the node is in the migration state else if ((fh = f.hash) == MOVED) // Help with migration 【 The inside is actually calling transfer, Later analysis 】 tab = helpTransfer(tab, f); else { // Entering this branch means : According to key Calculated hash, The position we get is there Node Of , Then I'll go through the list of links V oldVal = null; // Lock it Node Node synchronized (f) { // The second check after locking , For tab Situations that may be modified by other threads if (tabAt(tab, i) == f) { if (fh >= 0) { // Of the head node hash Properties >= 0 binCount = 1; // Record the length of the link string // Traversal operation of concatenated columns , You'll see for (Node e = f;; ++binCount) { K ek; // Find the same key 了 if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; // onlyIfAbsent For false And then , This is going to cover , The default is overlay if (!onlyIfAbsent) e.val = value; // And then it's over break; } Node pred = e; // It's the end of the traversal , hold Node Insert the tail if ((e = e.next) == null) { pred.next = new Node (hash, key, value, null); break; } } } else if (f instanceof TreeBin) { // Red and black trees Node p; binCount = 2; // Red and black trees putTreeVal if ((p = ((TreeBin )f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { // Determine whether it is necessary to convert the link string to a red black tree Number of nodes >= 8 When if (binCount >= TREEIFY_THRESHOLD) // Treeing It will be analyzed separately later treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; }``` In fact, you will find that , If you have seen HashMap The original code of , understand ConcurrentHashMap In fact, the operation is relatively clear , I believe you have a basic understanding of . Next, we will analyze several key methods ### initTable Using delayed initialization , for the first time put When , call initTable() initialization Node Array .```java /** * Initializes table, using the size recorded in sizeCtl. */ private final Node [] initTable() { Node [] tab; int sc; while ((tab = table) == null || tab.length == 0) { // If less than 0, Indicates that there are other threads rushing to initialize if ((sc = sizeCtl) < 0) Thread.yield(); // lost initialization race; just spin // Here, try to cas Grab it , If you get it, you will sc Set to -1, Declare sovereignty , If you can't get it, go back to the circle again else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { if ((tab = table) == null || tab.length == 0) { // Set the initial capacity int n = (sc > 0) ? sc : DEFAULT_CAPACITY; // Build capacity for n Array of @SuppressWarnings("unchecked") Node [] nt = (Node [])new Node [n]; // Assign to volatile Variables table Bottom array table = tab = nt; // This is actually sc = n - n/4 = 0.75 * n sc = n - (n >>> 2); } } finally { // Just as 12 Well sizeCtl = sc; } break; } } return tab; }``` How to solve the concurrency problem of initialization ? Through volatile Of sizeCtl Variables , At the first initialization , If there are multiple threads initializing at the same time , They will judge sizeCtl Is it less than 0, Smaller than 0 Indicates that another thread is already initializing . Because the thread that gets the initialization right has passed cas The operation will sizeCtl The value of is changed to -1 了 , And volatile This feature ensures the visibility of variables between threads . Then , It's going to build an array of the right capacity , And will sizeCtl The value of is set to `cap*loadFactor`.### treeifyBin This part contains the logic of connecting a string to a red black tree , Of course , Some preconditions need to be met :1. First of all, of course, is the number of nodes that need to be connected to the string `>=TREEIFY_THRESHOLD` It's time to , The default is 8.```java if (binCount != 0) { // Determine whether it is necessary to convert the link string to a red black tree Number of nodes >= 8 When if (binCount >= TREEIFY_THRESHOLD) // Treeing treeifyBin(tab, i); if (oldVal != null) return oldVal; break; }```2. In fact, there is another condition , Namely : If the array length `< MIN_TREEIFY_CAPACITY` When , Call priority `tryPresize` Expansion of the array .```java private final void treeifyBin(Node [] tab, int index) { Node b; int n, sc; if (tab != null) { // If the array length is less than MIN_TREEIFY_CAPACITY Will give priority to expansion tryPresize if ((n = tab.length) < MIN_TREEIFY_CAPACITY) tryPresize(n << 1); else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { // Lock the head node synchronized (b) { if (tabAt(tab, index) == b) { // Traversal link sequence , Build a red black tree TreeNode hd = null, tl = null; for (Node e = b; e != null; e = e.next) { TreeNode p = new TreeNode (e.hash, e.key, e.val, null, null); if ((p.prev = tl) == null) hd = p; else tl.next = p; tl = p; } // Set the red black tree to the corresponding position setTabAt(tab, index, new TreeBin (hd)); } } } } }```### tryPresize The operation of array expansion is generally the core , Take a closer look at .```java private final void tryPresize(int size) { int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1);// tableSizeFor(1.5*size) int sc; while ((sc = sizeCtl) >= 0) { Node [] tab = table; int n; // This is what I said before initTable Part of the code if (tab == null || (n = tab.length) == 0) { n = (sc > c) ? sc : c; if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { if (table == tab) { @SuppressWarnings("unchecked") Node [] nt = (Node [])new Node [n]; table = nt; sc = n - (n >>> 2); } } finally { sizeCtl = sc; } } } else if (c <= sc || n >= MAXIMUM_CAPACITY) break; else if (tab == table) { //1 0000 | 0000 0000 0000 0000 1000 0000 0000 0000 int rs = resizeStamp(n); // sc Smaller than 0 Indicates that there are threads in the process of expansion if (sc < 0) { Node [] nt; if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; // cas Will sizeCtl Add 1, If it works , Then execute transfer operation if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } // No threads are expanding , Will sizeCtl The value of is changed to (rs << RESIZE_STAMP_SHIFT) + 2) else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); } } } static final int resizeStamp(int n) { // Integer.numberOfLeadingZeros(n) It's actually a return n The leading zeros of , Double the capacity every time , The number will be less 1 // If n = 16 , return 27 // 1 << (RESIZE_STAMP_BITS - 1) 1 Move left 15 Bit identification The first 16 Bit is 1, low 15 All the seats are 0 return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1)); }````resizeStamp(int n)` Methods can refer to [https://blog.csdn.net/tp7309/article/details/76532366](https://blog.csdn.net/tp7309/article/details/76532366) Parsing .### transfer This method involves the operation of data migration , Support concurrent execution , The first thread to initiate data migration ,nextTab Citation null, When you call this method later ,nextTab Not for null. Concurrent execution implementation : Use stride Split a migration task into small tasks , The first thread to initiate data migration will transferIndex Point to the last position of the original array , And then from the back to the front stride Subtasks belong to the first thread , And then transferIndex Point to a new location , Further on stride The first task belongs to the second thread , And so on .```java private final void transfer(Node [] tab, Node [] nextTab) { int n = tab.length, stride; // In the case of multicore , stride For (n >>> 3) / NCPU , In the case of a single core , It's the capacity of the array if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) // The minimum is 16 stride = MIN_TRANSFER_STRIDE; // subdivide range // The first thread to initiate data migration ,nextTab Citation null if (nextTab == null) { // initiating try { // n<<1 Double the capacity @SuppressWarnings("unchecked") Node [] nt = (Node [])new Node [n << 1]; nextTab = nt; } catch (Throwable ex) { // try to cope with OOME sizeCtl = Integer.MAX_VALUE; return; } // For nextTable and transferIndex Assignment ,transferIndex From the last one nextTable = nextTab; transferIndex = n; } int nextn = nextTab.length; // Construct a hash == MOVED The node of , Mark the location that has been migrated ForwardingNode fwd = new ForwardingNode (nextTab); // Here advance Indicates that a location has been migrated , Ready for the next position boolean advance = true; boolean finishing = false; // to ensure sweep before committing nextTab for (int i = 0, bound = 0;;) { Node f; int fh; // advance For true I'm ready for the next position while (advance) { int nextIndex, nextBound; if (--i >= bound || finishing) advance = false; // nextIndex Will wait for transferIndex // transferIndex Once less than or equal to 0, It shows that all positions of the original array have corresponding threads to handle else if ((nextIndex = transferIndex) <= 0) { i = -1; advance = false; } else if (U.compareAndSwapInt (this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) { // bound Yes transferIndex-stride bound = nextBound; // i Point to transferIndex - 1 // Perform the migration task from the back to the front i = nextIndex - 1; advance = false; } } if (i < 0 || i >= n || i + n >= nextn) { int sc; // All the migration operations are done if (finishing) { nextTable = null; table = nextTab; // Will nextTab Assign to table sizeCtl = (n << 1) - (n >>> 1); // Recalculate sizeCtl return; } // sizeCtl Set to before (rs << RESIZE_STAMP_SHIFT) + 2 // After that, every thread involved in the migration will Will sizeCtl Add 1 // This can be seen as a reverse operation , Every time -1, The representative completed his task if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) return; // Coming here means (sc - 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT // All the tasks are done , The next time we go to the top finish The branch finishing = advance = true; i = n; // recheck before commit } } // Here are the specific migration operations // If i Location is null, That will just initialize hash=MOVED The node of cas Put in else if ((f = tabAt(tab, i)) == null) advance = casTabAt(tab, i, null, fwd); // If it is already hash==MOVED , It means the location has been moved else if ((fh = f.hash) == MOVED) advance = true; // already processed else { // Lock this position separately , Handle the migration of the location synchronized (f) { if (tabAt(tab, i) == f) { Node ln, hn; // Connect serial nodes if (fh >= 0) { // Split the list of links in two int runBit = fh & n; Node lastRun = f; // The next few steps are looking for lastRun The location of , Express lastRun The following nodes need to be put together for (Node 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 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 (ph, pk, pv, ln); else hn = new Node (ph, pk, pv, hn); } // One of the link strings is placed in the i position setTabAt(nextTab, i, ln); // Another link string is placed in the new array i + n position setTabAt(nextTab, i + n, hn); // Put the original array of i The position is set to fwd It means that it has been processed // Here fwd It's something we built before ForwardingNode, // The next time you make a judgment , It will be advance Set to true 了 setTabAt(tab, i, fwd); // Announce that the location has been migrated advance = true; } // Here's the migration of the red black tree else if (f instanceof TreeBin) { TreeBin t = (TreeBin )f; TreeNode lo = null, loTail = null; TreeNode hi = null, hiTail = null; int lc = 0, hc = 0; for (Node e = t.first; e != null; e = e.next) { int h = e.hash; TreeNode p = new TreeNode (h, e.key, e.val, null, null); if ((h & n) == 0) { if ((p.prev = loTail) == null) lo = p; else loTail.next = p; loTail = p; ++lc; } else { if ((p.prev = hiTail) == null) hi = p; else hiTail.next = p; hiTail = p; ++hc; } } // The number of nodes is less than 6 Transform the red black tree into a concatenated string untreeify ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc != 0) ? new TreeBin (lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc != 0) ? new TreeBin (hi) : t; setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; } } } } } }```## get Methods the values ### getget The method is relatively simple , According to key Calculated hash value , Find the corresponding position , Determine whether the header node is the value you want , If not, look for it in the red black tree or link list .```java public V get(Object key) { Node [] tab; Node e, p; int n, eh; K ek; // Calculation hash value int h = spread(key.hashCode()); // Find the corresponding hash Location of barrel if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { // Right on the head node if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } // Tree structure else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null; // On the link string while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; }``` You can see get The method is unlocked , Through volatile Decorated next To get the latest value every time .> Again :>> volatile It can ensure the visibility between variables , Can be read by multiple threads at the same time, and ensure that the expired value will not be read , Because based on Java Memory model happen before Principles , Yes volatile The write operation of a field precedes the read operation , Even if two threads modify and get at the same time volatile Variables ,get The operation can also get the latest value .>> But it can only be written by sheet threads ,【 There is a case where multiple threads can write , The value written does not depend on the original value 】, Read operations do not require locking .## Summary - ConcurrentHashMap stay JDK1.7 and JDK1.8 Great changes have taken place in the realization of the idea : - JDK1.7 Adopt `Segment+HashEntry` And ` Segmented lock ` The realization of the concept of . - JDK1.8 The concept of lock segmentation is abandoned , Use `Node + CAS + Synchronized` To achieve concurrency , Use ` Array + Link string + Red and black trees ` Structure of .- put The operation will be judged as follows : - If not initialized , Initialization first [ Lazy initialization ], The default capacity is 16, At the same time, I set SizeCtl. - If tab The array corresponds to hash There are no nodes in the slot ,CAS Operation to assign a value to the position , Success is about jumping out of the loop . - If the current slot node is in the migration state, that is `f.hash == MOVED`, First, help the node complete the migration operation . - It happened hash Conflict , First to use `synchronized` Lock the first node , Next, determine whether to connect the tandem node or the red black tree node , Find the right place , Insert or override values . - ** If the number of nodes exceeds the tree threshold 8, And the array capacity also reaches the threshold of treeing 64, To tree **.- When the number of nodes at the location of a bucket exceeds 8, But the array capacity is not up to 64 When , We'll do it first ** Expansion operation n*2, Execute tryPresize**.- The expansion operation involves transfer** Data migration **, Support concurrency , By dividing data migration into stride A little task , Through transferIndex and nextBound Two indicators to assign tasks .- get Operation does not require locking , According to key Calculated hash value , Find the corresponding position , Determine whether the header node is the value you want , If not, look for it in the red black tree or link list .## Reference reading - [ Zhan Xiaolang : Talk about ConcurrentHashMap1.7 and 1.8 Different implementations of ](https://www.jianshu.com/p/e694f1e868ec)- [jianshu_xw: Analysis JDK1.8 Next HashMap Thread security ](https://www.jianshu.com/p/06e7e626dcad)- [javadoop:Java7/8 Medium HashMap and ConcurrentHashMap Full resolution ](https://javadoop.com/post/hashmap)- [Java3y ConcurrentHashMap Based on JDK1.8 Source code analysis ](https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484161&idx=1&sn=6f52fb1f714f3ffd2f96a5ee4ebab146&chksm=ebd74200dca0cb16288db11f566cb53cafc580e08fe1c570e0200058e78676f527c014ffef41&scene=21###wechat_r
版权声明
本文为[itread01]所创,转载请带上原文链接,感谢
https://javamana.com/2021/01/20210123232234565h.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云