The paper

The difference between HashMap and Hashtable is that the former is thread-safe while the latter is thread-safe. But when we need thread-safety, Hashtable is not a good choice, concurrentHashMap is.

Why use concurrentHashMap

There are three ways to get a thread-safe HashMap: ① Using Hashtable ② (3) use the Collections. SynchronizedMap () method. There are three ways to use concurrentHashMap. Why is the third recommended and not the other two? Answer: efficiency, let’s look at the source code of those two ways

  • Hashtable

  • Collections.synchronizedMap()
    • 
    public static  Map synchronizedMap(Map m) {
        return new SynchronizedMap<>(m);
    }

    private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable { private final Map<K,V> m; // Backing Map final Object mutex; // Object on which to synchronize SynchronizedMap(Map<K,V> m) { this.m = Objects.requireNonNull(m); mutex = this; } public int size() { synchronized (mutex) {return m.size(); } } public boolean isEmpty() { synchronized (mutex) {return m.isEmpty(); } } public boolean containsKey(Object key) { synchronized (mutex) {return m.containsKey(key); }}Copy the code
    

    Copy the code
    

    



    
   


    
   Segmented lock
    
   CAS + synchronized 
    

    ConcurrentHashMap(JDK 1.8) parsing
    

    attribute
    

    /** * TRANSIENT volatile node [] table; Private TRANSIENT volatile Node[] nextTable; Private TRANSIENT Volatile long baseCount; private transient volatile long baseCount; /** * Control flag * Negative: initializing or expanding the capacity. -1 indicates initializing and -n indicates that n-1 threads are expanding the capacity. * Positive or 0: This value is similar to the capacity expansion threshold *. Its value is always 0.75 times the capacity of the current ConcurrentHashMap, which corresponds to the loadfactor. */ private TRANSIENT int sizeCtl; /** * transfer index = 1 */ private transient int transferIndex; /** * CAS spunlock bit */ private TRANSIENT volatile int cellsBusy; Private transient volatile CounterCell[] counterCells; private transient volatile CounterCell[] counterCells;Copy the code
    

    Important inner class
    

  • The Node Node class
    • 

    static class Node implements Map.Entry { final int hash; final K key; volatile V val; volatile Node next; . }Copy the code
    


     
    

  • TreeNode tree node
    • 

       The hash value is fixed at -2 
    

    static final class TreeNode extends LinkedHashMap.Entry { TreeNode parent; // red-black tree links TreeNode left; TreeNode right; TreeNode prev; // needed to unlink next upon deletion boolean red; . }Copy the code
    


     
    

  • TreeBin
    • 

    
    static final class TreeBin extends Node {
        TreeNode root;
        volatile TreeNode first;
        volatile Thread waiter;
        volatile int lockState;
        // values for lockState
        static final int WRITER = 1; // set while holding write lock
        static final int WAITER = 2; // set when waiting for write lock
        static final int READER = 4; // increment value for setting read lock
        ...
    }
Copy the code
    


     
    

  • ForwardingNode
    • 

    static final class ForwardingNode extends Node { final Node[] nextTable; ForwardingNode(Node[] TAB) {super(MOVED, null, null, null); // The hash of the ForwardingNode Node is -1. this.nextTable = tab; }... }Copy the code
    

    A constructor
    

    Public ConcurrentHashMap() {} public ConcurrentHashMap(int initialCapacity) {// Exception if (initialCapacity < 0) throw new IllegalArgumentException(); Int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1))? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); this.sizeCtl = cap; } /** * Public ConcurrentHashMap(map m) {this.sizectl = DEFAULT_CAPACITY; putAll(m); } /** * Public ConcurrentHashMap(int initialCapacity, float loadFactor) {this(initialCapacity, float loadFactor) loadFactor, 1); } /** * Public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {if (! (loadFactor > 0.0 f) | | 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); // 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; }Copy the code
    

    The CAS operation
    

    ConcurrentHashMap calls a method in the Unsafe class to implement CAS. (The idea is to constantly compare the value of a variable in memory to the value you specify, and if it is equal, accept the value you specify; otherwise, reject it.) Most of its internal methods are native methods, which directly call the underlying resources of the operating system to perform corresponding tasks, providing some low-level operations that can directly control memory and threads.
    

    InitTable method
    

    The initTable method determines the sizeCtl value. If the sizeCtl value is -1, another Thread is initializing. Thread.yield() is called to yield the CPU time slices. The initializing thread uses the Unsafe.compareAndSwapInt method to change sizeCtl to -1, initialize the array, and expand the threshold.
    

    private final Node[] initTable() { Node[] tab; int sc; While (= (TAB table) = = null | | TAB. The length = = 0) {/ / if sizeCtl < 0, namely there are other threads are initialized, If ((sc = sizeCtl) < 0) thread.yield (); // lost initialization race; Sizectl = -1, CAS = -1 Else if (U.compareAndSwapInt(this, SIZECTL, sc, - 1)) {try {if ((TAB = table) = = null | | TAB. The length = = 0) {/ / for bucket capacity int n = > 0 (sc)? Sc: DEFAULT_CAPACITY; Node[] nt = (node [])new node [n]; table = tab = nt; // Calculate the capacity expansion threshold. 0.75 N sc = n - (n >>> 2); } } finally { sizeCtl = sc; } break; } } return tab; }Copy the code
    

    We can see from the source that the outermost flow control uses a while loop rather than an if conditional branch, because Thread.yield() gives up CPU time to ensure that the array is initialized successfully
    

    Put method
    

    ConcurrentHashMap’s PUT operation is similar to that of HashMap, but ConcurrentHashMap does not allow NULL as key and value, and to ensure thread-safety, there are two multithreading cases:
    

    1. If one or more threads are expanding ConcurrentHashMap, the current thread must also expand ConcurrentHashMap. The reason why this expansion operation can be detected is that the Transfer method will set the head node of the expansion bucket that has been operated as the ForwardingNode node. If the node is detected to occupy the position to be inserted, it will help expand the capacity.
    

    ② If it is detected that the node to be inserted is non-empty and not a ForwardingNode, the node is locked, thus ensuring thread safety.
    

    Final V putVal(K key, V value, Boolean onlyIfAbsent) {// Unlike HashMap, ConcurrentHashMap does not allow null as a key or value if (key = = null | | value = = null) throw new NullPointerException (); Int hash = spread(key.hashcode ()); int binCount = 0; for (Node[] tab = table;;) { Node f; int n, i, fh; / / if the table is empty, initialize the table if (TAB = = null | | (n = TAB. Length) = = 0) TAB = initTable (); Else if ((f = tabAt(TAB, I = (n-1) & hash)) == null) {//CAS inserts node (V: node at current array I; O: null; N: New Node object) if (casTabAt(TAB, I, null, new Node(hash, key, value, null)) break; Else if ((fh = f.hash) == MOVED) TAB = helpTransfer(TAB, f); // No lock when adding to empty bin} else { V oldVal = null; Synchronized (f) {synchronized (f) {synchronized (f) { If (tabAt(TAB, I) == f) {if (fh >= 0) {binCount = 1; For (Node e = f;; ++binCount) { K ek; / / if the hash value and the key values are the same, to replace the if (e.h ash = = hash && (= e.k (ek ey) = = key | | (ek! = null && key.equals(ek)))) { oldVal = e.val; if (! onlyIfAbsent) e.val = value; break; } Node pred = e; If ((e = e.next) == null) {next = new Node(hash, key, value, null); break; If (f instanceof TreeBin) {Node p; if (f instanceof TreeBin) {Node p; binCount = 2; If ((p = ((TreeBin)f).puttreeval (hash, key, value))! = null) { oldVal = p.val; if (! onlyIfAbsent) p.val = value; } } } } if (binCount ! If (binCount >= TREEIFY_THRESHOLD) treeifyBin(TAB, I); if (binCount >= TREEIFY_THRESHOLD) treeifyBin(TAB, I); if (oldVal ! = null) return oldVal; break; If the number of nodes exceeds the threshold, addCount(1L, binCount); return null; /** * hash algorithm */ static final int spread(int h) {return (h ^ (h >>> 16)) &hash_bits; }Copy the code
    

    Check whether the key and value are null. If they are null, exceptions are thrown. Unlike HashMap, ConcurrentHashMap does not allow NULL as key or value. Why is this designed?
    

    Because ConcurrentHashmap is concurrent, there’s a problem with that. When you get a value from get(k), if you get a null, you can’t tell if it’s put (k,v) and the value is null, or if the key has never been mapped. A HashMap is non-concurrent, and you can do this by contains(key). M may not be the same for concurrent maps that call M.corontains (key) and M.grid (key). reference
    

    ConcurrentHashMap uses a red-black tree to handle more hash collisions, which simplifies the hash algorithm. ConcurrentHashMap does not allow null keys. Instead of calculating the hash value of null as 0, there is an extra bit operation. The reason for this is to ensure that the result of the rehash must not be negative. I think if negative value is calculated, it may affect the subsequent judgment of node type
    

    Check whether the current table is empty, if empty, initialize the table, initialization method has been described no more mentioned ④. Based on the rehash value, the bucket index is obtained through and operation. Using the Unsafe class, the node in the memory is directly obtained. If there is no collision, ⑤ is directly added to the bucket. If a collision occurs, determine the type of the first node in the bucket. If it is a ForwardingNode, it indicates that other threads are expanding capacity. ⑥ Perform the expansion together. For the remaining scenarios, insert or update new nodes according to the linked list or red-black tree of corresponding structure of nodes. If the length of the linked list is larger than 8 after the new node is added, the linked list is converted into a red-black tree ⑧. Finally, the number of nodes is +1 to check whether the number exceeds the threshold
    

    AddCount method
    

    private final void addCount(long x, int check) { CounterCell[] as; long b, s; // Update baseCount if ((as = counterCells)! = null || ! U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { CounterCell a; long v; int m; boolean uncontended = true; if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null || ! (uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)) {fullAddCount(x, uncontended); return; } if (check <= 1) return; s = sumCount(); If (check >= 0) {Node[] TAB, nt; // if (check >= 0) {Node[] TAB, nt; int n, sc; while (s >= (long)(sc = sizeCtl) && (tab = table) ! = null && (n = tab.length) < MAXIMUM_CAPACITY) { int rs = resizeStamp(n); if (sc < 0) { if ((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); s = sumCount(); }}}Copy the code
    

    If the baseCount update fails, CELLVALUE will be updated. If the baseCount update fails, fullAddCount() will be called. This method keeps the value of the capacity change that failed the CAS due to multithreaded contention in an infinite loop in the CounterCell array in preparation for the size() method
    

    The size method
    

    For ConcurrentHashMap, the exact number of items in the table is an indeterminate number, because it is impossible to call size() and cause other threads to stop counting, like GC’s “stop the world” method, so the number is an estimate.
    

    public int size() { long n = sumCount(); return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n); } 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; }Copy the code
    

    To count the number of elements, ConcurrentHashMap accumulates the number of elements in baseCount and CounterCell arrays. The number of elements is stored in baseCount and the number of changes in some elements is stored in CounterCell arrays to obtain the total number of elements.
    

    Transfer method
    

    Supports multi-threaded capacity expansion without locking, not only to meet the requirements of concurrent, but also to reduce the time impact of capacity expansion by using concurrent processing. The capacity expansion mechanism may be triggered in the following two scenarios (same as 1.8HashMap): ①. When the length of the linked list in the bucket reaches the threshold 8, but the number of ConcurrentHashMap nodes is less than 64 (2). Description After a new node is added, the number of ConcurrentHashMap nodes exceeds the threshold
    

    private final void transfer(Node[] tab, Node[] nextTab) { int n = tab.length, stride; if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE; // nextTab == null) {// initiates the node array, Node[] nt = (Node[])new Node[n << 1]; nextTab = nt; } catch (Throwable ex) {// Try to cope with OOME // If an OOM exception occurs during capacity expansion, set the threshold to the maximum, indicating that capacity expansion is not supported. return; } nextTable = nextTab; transferIndex = n; } int nextn = nextTab.length; FWD = new ForwardingNode(nextTab); ForwardingNode FWD = new ForwardingNode(nextTab); boolean advance = true; boolean finishing = false; // to ensure sweep before committing nextTab for (int i = 0, bound = 0;;) { Node f; int fh; while (advance) { int nextIndex, nextBound; if (--i >= bound || finishing) advance = false; else if ((nextIndex = transferIndex) <= 0) { i = -1; advance = false; } // Use CAS to set the transferIndex attribute and initialize the I and bound values. // I indicates the number of the current slot, bound indicates the boundary of the slot to be processed. else if (U.compareAndSwapInt (this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) { bound = nextBound; i = nextIndex - 1; advance = false; }} / / the original node is copied to the new array in the array to the if (I < 0 | | I > = n | | I + n > = nextn) {int sc; // Assign nextTable to table if all nodes have been copied. Clear temporary objects nextTable if (finishing) {nextTable = null; table = nextTab; // Set the new capacity expansion threshold sizeCtl = (n << 1) - (n >>> 1); return; } // The CAS method is used to update the capacity expansion threshold, where the sizectl value is reduced by one, 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; Synchronized (f) {if (tabAt(TAB, I) == f) {Node ln, hn; If (fh >= 0) {int runBit = fh & n; Node lastRun = f; For (Node p = f.next; p ! = null; P = p) {// int b = p; 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); } // Insert a linked list setTabAt(nextTab, I, ln) in I of nextTable; // Insert another linked list setTabAt(nextTab, I +n, hn) at I +n of nextTable; // Insert forwardNode into table I to indicate that forwardNode has been processed setTabAt(TAB, I, FWD); // Set advance to true and return to the above while loop to execute I -- advance = true; 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; }} // If the tree structure is no longer needed after the expansion, switch to the linked list structure 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; } } } } } }Copy the code
    

  • The bucket is a chain structure
    • 

    As shown in the figure (blue :hash bit X 0, grey :hash bit X 1)
    

    

    
    
    



    
   One forward linked list, one reverse linked list
    
   


    
   

     
    

  • The bucket is a red-black tree structure
    • 



    
   


    
   Indicates that all nodes in the original bucket are still in this bucket after rehashing, that is, all original nodes are included in the LO list
    
   

     
    

    ConcurrentHashMap handles linked lists like the resize() method at the end of HashMap, and red-black trees like the split() method inside TreeNode in HashMap. The TreeBin constructor is similar to the Treeify () method of the TreeNode inner class, but is much more complex because ConcurrentHashMap needs to be thread-safe
    

    Question: Why build linked lists in reverse order? The following is a reference to the idea of 1.7HashMap header node. Since the data inserted after the insertion is used more frequently, the query cannot be randomly accessed and can only be iterated from the beginning, while ConcurrentHashMap uses built-in lock synchronized to lock the bucket header node because the data inserted after the insertion is used more frequently. Reverse order makes lock hold time shorter and wait time shorter.
    

    The get method
    

    When a key is given to determine a value, two conditions must be met: the keys are the same and the hash value is the same. If nodes may be in a linked list or tree, search for them separately.
    

    public V get(Object key) { Node[] tab; Node e, p; int n, eh; K ek; Int h = spread(key.hashcode ()); //// Determine node location based on hash value if ((TAB = table)! = null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) ! = null) {/ / barrels of the first node key and find the key of the same, is returned directly if (eh = e.h (ash) = = h) {if (= e.k (ek ey) = = key | | (ek! = null && key.equals(ek))) return e.val; Else if (eh < 0) return (p = e.type (h, key))! = null ? p.val : null; // List scenario while ((e = e.next)! = null) { if (e.hash == h && ((ek = e.key) == key || (ek ! = null && key.equals(ek)))) return e.val; } } return null; }Copy the code
    

    ConcurrentHashMap 1.7 is different from 1.8
    

    In JDK 7, ConcurrentHashMap uses a segment, and multiple threads will lock the segment first, and then locate the bucket in the segment. JDK 8 directly handles the bucket in Node array. Locking the head node of the bucket reduces the granularity of the lock. In addition, the segment inherits ReentrantLock, and ReentrantLock has more wait interruptability, fairness and binding conditions than synchronized keyword. However, in terms of performance, synchronized built-in lock is constantly optimized, and its performance is not bad.
    

    Thank you
    

    www.jianshu.com/p/e694f1e86… Blog.csdn.net/itachi85/ar…