0. An overview

0.1 Synchronizing Containers

  • Vector thread safety
  • The ArrayList thread is not safe
    • Thread-safe Collections. SynchronizedList (ArrayList)
  • Hashtable thread safe
  • The HashMap thread is not safe
    • Thread-safety collections.synchronizedmap (HashMap)

0.2 Concurrent Container

  • CopyOnWriteArrayList works just like ArrayList. Each step requires a copy, so it consumes memory. You can use CopyOnWriteArrayList if you have lots of reads and writes, or synchronous containers if you have lots of reads and writes.
  • ConcurrentLinkedQueue
    • Offer into the queue
    • Poll the queue
  • ArrayBlockingQueue put(),take(),add(),remove(),size(),offer(); poll();
  • ConcurrentHashMap

0.3 Blocking Queue

  • BlockingQueue
    • put
    • take
    • add
    • remove
    • offer
    • poll
  • ArrayBlockingQueue
  • LinkedBlockingQueue

1. Synchronize containers

1.1 an overview of the

  • Vector’s thread-safe add method, synchronized, is also single-threaded in concurrent programming. When using multiple threads, however, performance deteriorates due to locking, so we do not use Vector in concurrent cases.
  • The ArrayList thread is not safe

The bottom layer uses arrays to store data, and when a certain amount of data is added, the current data is copied into a new, larger array.

    • Collections. SynchronizedList (ArrayList) such security, and ultimately with the synchronized code block, concurrent programming is single threaded.
  • Hashtable is thread-safe, using the synchronized put method, which is also single-threaded if used concurrently.
  • The HashMap thread is not safe
    • Collections.synchronizedmap (HashMap) thread safety, finally also synchronized code block, concurrent programming is single threaded.

1.2 the sample

1.2.1 Collections. The synchronize

public class CollectionThread { public static void main(String[] args) { ArrayList<String> s = new ArrayList<>(); / / to thread safe List < String > s1 = Collections. SynchronizedList (s); HashMap<String, Object> res = new HashMap<>(); / / into a thread-safe Collections. SynchronizedMap (res); }}Copy the code

1.3 Common apis for Synchronizing Containers

  • Vector thread safety
  • The ArrayList thread is not safe
    • Thread-safe Collections. SynchronizedList (ArrayList)
  • Hashtable thread safe
  • The HashMap thread is not safe
    • Thread-safety collections.synchronizedmap (HashMap)

1.4. The source code

1.4.1 Vector

  • Synchronized precedes Vector methods
package java.util; public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; }}Copy the code

1.4.2 Hashtable

  • Synchronized is synchronized before the put method of Hashtable
public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable { public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<? ,? > tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; for(; entry ! = null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index); return null; }}Copy the code

2. Concurrent containers

2.1 CopyOnWriteArrayList

Copy as you write.

2.1.1 CopyOnWriteArrayList overview

  • When the data is added, A copy of A’ is copied from the original array A, and the added data is added to A’. During this process, the read data is read from A. After the addition, the reference points to A’, and the read and write are from A’.
  • Copy-on-write, for short, is an optimization strategy used in program design. The basic idea is that everyone is sharing the same content from the beginning, and when someone wants to change the content, they will actually Copy the content to form a new content and then change it, which is a kind of delayed lazy strategy. Two concurrent containers that use the CopyOnWrite mechanism are available in Java since JDK1.5: CopyOnWriteArrayList and CopyOnWriteArraySet. It can be used in a wide variety of concurrent scenarios.
  • A CopyOnWrite container is a container for copying while writing. The common understanding is that when we add elements to a container, we do not directly add to the current container, but first Copy the current container, Copy the new container, then add elements to the new container, after adding elements, the original container reference to the new container. The advantage of this is that we can do concurrent reads to the CopyOnWrite container without locking, since no elements are being added to the current container. So the CopyOnWrite container is also an idea of read-write separation, reading and writing different containers.

2.1.2 CopyOnWriteArrayList Application Scenario

The CopyOnWrite concurrent container is used in concurrent scenarios where more reads and less writes are required. For example, whitelist, blacklist, commodity access and update scenarios, let’s say we have a search site, and the user enters keywords in the search box of the site to search for content, but certain keywords are not allowed to be searched. These unsearchable keywords are put on a blacklist, which is updated every night. When a user searches, the system checks whether the current keyword is in the blacklist. If so, the system prompts that the keyword cannot be searched. The implementation code is as follows:

package com.ifeve.book; import java.util.Map; import com.ifeve.book.forkjoin.CopyOnWriteMap; Public class BlackListServiceImpl {private static CopyOnWriteMap<String, Boolean> blackListMap = new CopyOnWriteMap<String, Boolean>( 1000); public static boolean isBlackList(String id) { return blackListMap.get(id) == null ? false : true; } public static void addBlackList(String id) { blackListMap.put(id, Boolean.TRUE); } /** * @param ids */ public static void addBlackList(Map<String,Boolean> ids) {blackListmap.putall (ids); }}Copy the code

The code is simple, but there are two things to be aware of when using CopyOnWriteMap:

1. Reduce capacity expansion costs. Initialize the size of CopyOnWriteMap as required to avoid the cost of CopyOnWriteMap expansion.

2. Use batch add. Because the container is copied every time you add, reducing the number of times you add reduces the number of times the container is copied. For example, use the addBlackList method in the code above.

2.1.3 CopyOnWriteCopyOnWriteArrayList

The CopyOnWrite container has many advantages, but it also has two problems: memory footprint and data consistency. So you need to pay attention to it during development.

  • Memory usage is abnormal. Because CopyOnWrite write replication mechanism, so at the time of writing, in the memory will be stationed at the same time two objects of memory, the old and new writing object (note: just copy the reference in the container when copy, just at the time of writing will create a new object is added to the new container, the old container object is still in use, So there are two pieces of object memory. If these objects take up a lot of memory, say 200 MB, then writing another 100 MB of data will take up 300 MB of memory, which is likely to result in frequent Yong and Full GC. We used a service on our system that had 15 seconds of Full GC per night due to updating large objects using CopyOnWrite every night, resulting in longer application response times.

You can reduce the memory consumption of large objects by compressing the elements in the container. For example, if the elements are all base 10 numbers, consider compressing them to base 36 or 64. Or instead of using the CopyOnWrite container, use another concurrent container, such as ConcurrentHashMap.

  • Data consistency issues. The CopyOnWrite container only guarantees final data consistency, not real-time data consistency. So if you want to write data that is immediately readable, don’t use the CopyOnWrite container.

2.1.4 CopyOnWriteArrayList source

  • CopyOnWriteArrayList copies the new storage array space.
  • The following code is an implementation of the add method to CopyOnWriteArrayList (adding elements to CopyOnWriteArrayList). It can be found that the lock is needed to add elements to CopyOnWriteArrayList, otherwise multi-threaded writing will Copy N copies.
  • If multiple threads are adding data to CopyOnWriteArrayList while reading, the old data will still be read because the old CopyOnWriteArrayList will not be locked while writing.
package java.util.concurrent; public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private transient volatile Object[] array; Public Boolean add(E E) {// Final ReentrantLock lock = this.lock; // Final ReentrantLock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len + 1); NewElements [len] = e; setArray(newElements); return true; } finally { lock.unlock(); Public E get(int index) {return get(getArray(), index); } final Object[] getArray() { return array; } final void setArray(Object[] a) { array = a; } private E get(Object[] a, int index) { return (E) a[index]; } public E remove(int index) {final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; E oldValue = get(elements, index); Int numMoved = len-index - 1; If (numMoved == 0)// Delete the last data (Len 3,index 2) setArray(Array.copyof (Elements, Len-1)); Else {// if not the last data, form the data before and after the node into a new array // example :(len 10[0~9],index 3[4],numMoved=10-3-1=6) Object[] newElements = new Object[len - 1]; Arraycopy (elements, 0, newElements, 0, index); arrayCopy (elements, 0, newElements, 0, index); Arraycopy (elements, index + 1, newElements, index,numMoved); arrayCopy (elements, index + 1, newElements, index,numMoved); setArray(newElements); } return oldValue; } finally { lock.unlock(); }} public E set(int index, E element) {final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); E oldValue = get(elements, index); if (oldValue ! = element) { int len = elements.length; [] newElements = array.copyof (elements, len); NewElements [index] = Element; newElements[index] = element; newElements[index] = element; setArray(newElements); } else { // Not quite a no-op; ensures volatile write semantics setArray(elements); } return oldValue; } finally { lock.unlock(); }}}Copy the code
package java.util; public class Arrays { public static <T> T[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass()); }}Copy the code
  • CopyOnWriteMap
import java.util.Collection; import java.util.Map; import java.util.Set; public class CopyOnWriteMap<K, V> implements Map<K, V>, Cloneable { private volatile Map<K, V> internalMap; public CopyOnWriteMap() { internalMap = new HashMap<K, V>(); } public V put(K key, V value) { synchronized (this) { Map<K, V> newMap = new HashMap<K, V>(internalMap); V val = newMap.put(key, value); internalMap = newMap; return val; } } public V get(Object key) { return internalMap.get(key); } public void putAll(Map<? extends K, ? extends V> newData) { synchronized (this) { Map<K, V> newMap = new HashMap<K, V>(internalMap); newMap.putAll(newData); internalMap = newMap; }}}Copy the code

　　

2.2 ConcurrentLinkedQueue Unbounded non-blocking queue, concurrent linked list structure

2.2.1 ConcurrentLinkedQueue overview

Common concurrent queues are blocking queues and non-blocking queues, the former using locks, the latter using CAS non-blocking algorithm, The ConcurrentLinkedQueue is implemented using the CAS non-blocking algorithm. CAS solves the security link between the current node and the next node and the assignment of the current node value. Since CAS does not use locks, it is possible to perform offer, poll or remove operations when acquiring size, resulting in an inaccurate number of acquired elements. Therefore, the size function is not very useful in the case of concurrency. In addition, the first peek or FIRST will point the head to the first actual queue element.

2.2.2 ConcurrentLinkedQueue Class diagram structure

  • In ConcurrentLinkedQueue, two volatile nodes are used to store the first and last nodes of the list. Head is used to store nodes whose first item is null, and tail is not always used to point to the last Node. Inside the Node Node, a variable item is maintained to store the value of the Node, and next is used to store the next Node, thus linking into a one-way unbounded list.
public ConcurrentLinkedQueue() {
    head = tail = new Node<E>(null);
}
Copy the code

The code above initializes and builds an empty node with a NULL item as the first and last node of the list.

2.2.3 Offer Action – Add an element to the end of the list

Public Boolean offer(E E) {// if E is null checkNotNull(E); PutObject final Node<E> newNode = newNode <E>(E); final Node<E> newNode = newNode <E>(E); For (Node<E> t = tail, p = t;;) { Node<E> q = p.next; If (q == null) {//cas insert (1) if (p.casnext (null, newNode)) {//cas succeeds if the newNode has been added to the list, then set the current tail node (including head, One, three, five. If (p! = t) // hop two nodes at a time casTail(t, newNode); // Failure is OK. return true; } // Lost CAS race to another thread; Re-read next} else if (p == q)//(2) // if (p == q)// if (p == q)// if (p == q)/ Because the node after the new head is the active node. = (t = tail)) ? t : head; Else // Find the last node (3) p = (p! = t && t ! = (t = tail)) ? t : q; }}Copy the code

2.2.4 Add operation – Add an element to the end of the list

In fact, the internal call is still offer

 public boolean add(E e) {
        return offer(e);
    }
Copy the code

2.2.5 poll operation – Retrieves and removes an element from the head of the list

Public E poll() {restartFromHead: // for (;;) {// for (Node<E> h = head, p = h, q;;) {// save the current item value E item = p.item; // Cas becomes null (1) if (item! = null &&p.casItem (item, null)) {//cas successfully flags the current node and removes it from the list. (2) updateHead(h, ((q = p.ext)! = null) ? q : p); return item; Else if ((q = p.ext) == null) {updateHead(h, p); return null; Else if (p == q) continue restartFromHead; else//(5) p = q; } } } final void updateHead(Node<E> h, Node<E> p) { if (h ! = p && casHead(h, p)) h.lazySetNext(h); }Copy the code

2.2.6 Operation peek – Obtain one element in the head of the linked list (read but not remove)

The code is similar to poll, but without castitem. and the peek operation changes the head pointing to the sentinel node after the offer, and the head pointing to the first real node element after the first peek.

public E peek() { restartFromHead: for (;;) { for (Node<E> h = head, p = h, q;;) { E item = p.item; if (item ! = null || (q = p.next) == null) { updateHead(h, p); return item; } else if (p == q) continue restartFromHead; else p = q; }}}Copy the code

2.2.7 SIZE operation – Obtain the number of current queue elements

The number of elements in the current queue is not very useful in a concurrent environment. The number of elements may be added or deleted between the call to size and the return of the result, resulting in an inaccurate number of elements.

public int size() { int count = 0; for (Node<E> p = first(); p ! = null; p = succ(p)) if (p.item ! MAX_VALUE if (++count == integer.max_value) break; return count; } Node<E> first() {restartFromHead: for (;); { for (Node<E> h = head, p = h, q;;) { boolean hasItem = (p.item ! = null); if (hasItem || (q = p.next) == null) { updateHead(h, p); return hasItem ? p : null; } else if (p == q) continue restartFromHead; else p = q; Final Node<E> succ(Node<E> p) {Node<E> next = p.ext; return (p == next) ? head : next; }Copy the code

2.2.8 Remove operation – If the element exists in the queue, remove it to the element; if there are more than one, remove the first element and return true; otherwise return false

Public Boolean remove(Object o) {return false if (o == null) return false; Node<E> pred = null; for (Node<E> p = first(); p ! = null; p = succ(p)) { E item = p.item; // The cas value null is used for equality, and one thread succeeds. The failed thread loops to see if any other elements in the queue match. if (item ! = null &&o.quals (item) &&p.casitem (item, null) {// Get the next element Node<E> next = succ(p); // If there is a precursor node and next is not empty, link the precursor node to next, if (pred! = null && next ! = null) pred.casNext(p, next); return true; } pred = p; } return false; }Copy the code

2.2.9 Contains operation – Checks whether the queue contains a specified object

If the size of an element in the queue is not specified, the size of an element in the queue is not specified. If the size of an element is not specified, the size of an element in the queue is not specified.

public boolean contains(Object o) { if (o == null) return false; for (Node<E> p = first(); p ! = null; p = succ(p)) { E item = p.item; if (item ! = null && o.equals(item)) return true; } return false; }Copy the code

2.2.10 Summary of implementation principle

// This principle is quite difficult. Package java.util.concurrent; public class ConcurrentLinkedQueue<E> extends AbstractQueue<E> implements Queue<E>, Java.io.Serializable {//tail Node private TRANSIENT volatile Node<E> tail; Public ConcurrentLinkedQueue() {head = tail = new Node<E>(null); ** * Inserts the specified elements at the tail of this queue. * As the queue is unbounded, this method will never return {@code false}. */ public boolean offer(E e) { checkNotNull(e); final Node<E> newNode = new Node<E>(e); ConcurrentLinkedQueue for (Node<E> t = tail, p = t;) {//q is next of p, the first time next is empty //q is next of P, the second time next points to the first value added. Node<E> q = p.next; If (q == null) {// p is last node, add the new node to next (check next is empty) if (p.casnext (null, // Successful CAS is the linearization point // for e to become an element of this queue, // And for newNode to become "live". // If (p! // Hop two nodes at a time. CasTail (t, newNode); // Failure is OK. return true; } // Lost CAS race to another thread; Re-read next} // Not the first time // else if (p == q) // We have fallen off list. it // will also be off-list, in which case we need to // jump to head, from which all live nodes are always // reachable. Else the new tail is a better bet. p = (t ! = (t = tail)) ? t : head; // The second time q is not empty, nor is p==q, then p! Else // Check for tail updates after two hops. p= (p! = t && t ! = (t = tail)) ? t : q; Public E poll() {} private static class Node<E> {volatile E item; // Store data, volatile Node<E> next; // Next pointer. PutObject (this, itemOffset, item); // Unsafe. putObject(this, itemOffset, item); // unsafe. putObject(this, itemOffset, item); } private static final sun.misc.Unsafe UNSAFE; private static final long itemOffset; private static final long nextOffset; static { try { UNSAFE = sun.misc.Unsafe.getUnsafe(); Class<? > k = Node.class; itemOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("item")); nextOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("next")); } catch (Exception e) { throw new Error(e); }}}}Copy the code

2.2.11 Refer to the article

ConcurrentLinkedQueue (ConcurrentLinkedQueue) ConcurrentLinkedQueue (ConcurrentLinkedQueue

2.3 ConcurrentHashMap

2.3.1 overview

  • Partition the map into chunks (hash), and then write to only the corresponding block.

ConcurrentHashMap has the same idea as HashMap, but is more complex because it supports concurrent operations.

  • The entire ConcurrentHashMap consists of segments that stand for “part” or “Segment”, and are often described as segmented locks. Notice how many places I used “slots” to represent a segment.

  • ConcurrentHashMap is an array of segments. A Segment is locked by inheritingReentrantLock. As long as each Segment is thread-safe, global thread-safe is achieved.

2.3.2 Implementation Principles of JDK8

The implementation of JDK8 has abandoned the Segment Segment locking mechanism, using CAS+Synchronized to ensure the security of concurrent updates, the bottom still uses array + linked list + red-black tree storage structure.

2.3.3 Explanation of variables

  1. Table: default null, initialization occurs on the first insert operation, default size 16 array, used to store Node data, expansion is always a power of 2.

  2. NextTable: the default value is null. A new array is twice the size of the original one.

  3. SizeCtl: The default value is 0. It is used to control table initialization and capacity expansion operations. Specific applications will be described later.

    • -1 indicates that the table is being initialized
    • -n Indicates that N-1 threads are performing capacity expansion
    • The rest:
      • 1. If the table is not initialized, it indicates the size of the table to be initialized.
      • (n – (n >>> 2)); (n – (n >>> 2)); (n – (n >> 2)); (n – (n >> 2));

  4. Node: data structure that stores keys, values, and hash values for keys.

  5. ForwardingNode: a special Node Node with a hash value of -1 that stores references to nextTable. The ForwardingNode takes effect only when the table is expanded. It is placed in the table as a placeholder to indicate that the current node is null or has been moved.

2.3.4 initialization

When instantiating ConcurrentHashMap with parameters, the size of the table will be adjusted based on the parameters. Assume that the parameter is 100, and eventually it will be adjusted to 256, ensuring that the table size is always a power of 2.

private static final int tableSizeFor(int c) {  
    int n = c - 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;  
}  
Copy the code

2.3.5 Initializing a Table

    private final Node<K,V>[] initTable() {  
        Node<K,V>[] tab; int sc;  
        while ((tab = table) == null || tab.length == 0) {  
        // If one thread finds sizeCtl<0, the CAS operation of another thread is successful, the current thread only needs to give up the CPU slice
            if ((sc = sizeCtl) < 0)   
                Thread.yield(); // lost initialization race; just spin  
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {  
                try {  
                    if ((tab = table) == null || tab.length == 0) {  
                        int n = (sc > 0)? sc : DEFAULT_CAPACITY;@SuppressWarnings("unchecked")  
                        Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n]; table = tab = nt; sc = n - (n >>>2); }}finally {  
                    sizeCtl = sc;  
                }  
                break; }}return tab;  
    }  
Copy the code

2.3.6 put operation

    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();  
            // Locate the index in the table. N is the size of the table
            / / if f is null, indicating the position in the table insert element, for the first time using Unsafe.com pareAndSwapObject insert Node Node method.
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {  
                
                // If the CAS succeeds, the Node Node is inserted. Then the addCount(1L,binCout) method checks whether the current capacity needs to be expanded. If CAS fails, another thread inserted the node early, and the spin tries to insert the node at that location again.
                if (casTabAt(tab, i, null.new Node<K,V>(hash, key, value, null)))  
                    break; // no lock when adding to empty bin  
            }  
            // If the hash value of f is -1, it indicates that f is a ForwardingNode node, which means that other threads are expanding capacity. Expand capacity together.
            else if ((fh = f.hash) == MOVED)  
                tab = helpTransfer(tab, f);  
            // Omit some code
        }  
        addCount(1L, binCount);  
        return null;  
    }  
Copy the code

2.3.7 hash algorithm

static final int spread(int h) {return (h ^ (h >>> 16)) & HASH_BITS; }Copy the code

2.3.8 Obtaining the corresponding element F in table

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
Copy the code

Doug Lea uses Unsafe. GetObjectVolatile to retrieve items, such as table[index]. In the Java memory model, we already know that each thread has a working memory that stores a copy of the table. Although the table is volatile, there is no guarantee that the thread will get the latest element in the table every time. Unsafe.getObjectVolatile accesses specified memory data directly, ensuring that data is up-to-date every time.

2.3.9 Linked list or red-black tree operation

In other cases, new nodes are inserted into the appropriate location in a linked list or red-black tree, using synchronous built-in locks for concurrency.

synchronized (f) {
    TabAt (TAB, I) == f before the node is inserted to prevent other threads from modifying it.
    if (tabAt(tab, i) == f) {
        // if f hash >= 0, f is the first node of the linked list. If f hash >= 0, f is the first node of the linked list.
        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; }}}// If f is a TreeBin node, then f is a red and black root node.
        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 the number of nodes in the list is binCount >= TREEIFY_THRESHOLD(default: 8), the list is converted to a red-black tree structure.
if(binCount ! =0) {
    if (binCount >= TREEIFY_THRESHOLD)
        treeifyBin(tab, i);
    if(oldVal ! =null)
        return oldVal;
    break;
}
Copy the code

2.3.10 table capacity

When the capacity of a table is insufficient, that is, the number of table elements reaches sizeCtl, you need to expand the table.

The expansion is divided into two parts:

  1. Build a nextTable twice the size of Table.
  2. Copy table data to nextTable.

ConcurrentHashMap supports concurrent insertions. In this case, the second step can support concurrent replication of nodes, which improves performance and complexity.

The first step is to build nextTable. This process, of course, can only be done by a single thread.

    private final void addCount(long x, int check) {  
        // Omit some code
        if (check >= 0) {  
            Node<K,V>[] 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

2.3.11 get operation

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) / / tree
            return(p = e.find(h, key)) ! =null ? p.val : null;
        while((e = e.next) ! =null) { / / list
            if(e.hash == h && ((ek = e.key) == key || (ek ! =null && key.equals(ek))))
                returne.val; }}return null;
}
Copy the code

2.3.12 Reference article

ConcurrentHashMap; ConcurrentHashMap; ConcurrentHashMap; Implementation principles of ConcurrentHashMap (JDK1.7 and JDK1.8)

3. Block the queue

3.1 BlockingQueue

3.1.1 BlockingQueue overview

BlockingQueue is an interface that inherits from Queue, which inherits from Collection, FIFO.

3.1.2 BlockingQueue

  • put
  • take
  • add
  • remove
  • offer
  • poll

3.1.3 BlockingQueue source

public interface BlockingQueue<E> extends Queue<E> { } public class ArrayBlockingQueue<E> extends AbstractQueue<E> implements BlockingQueue<E>, java.io.Serializable { public ArrayBlockingQueue(int capacity) { this(capacity, false); }}Copy the code

3.2 ArrayBlockingQueue

3.2.1 ArrayBlockingQueue overview

  • At the end of the queue where the producer inserts data, the consumer always takes data from the head of the queue. When the queue is full, inserting data into the queue will block the queue, as will fetching data from an empty queue.

As a fairness policy, if we wanted to always fetch the data in the queue in the same order that the producers produced the data, we could have set fair to true in the constructor, but this would reduce throughput.

java.lang.Object
---java.util.AbstractCollection<E>
----java.util.AbstractQueue<E>
------java.util.concurrent.ArrayBlockingQueue<E>
Copy the code

3.2.2 ArrayBlockingQueue source

package java.util.concurrent; public class ArrayBlockingQueue<E> extends AbstractQueue<E> implements BlockingQueue<E>, java.io.Serializable { ** Condition for waiting takes */ private final Condition notEmpty; /** Condition for waiting puts */ private final Condition notFull; public void put(E e) throws InterruptedException { checkNotNull(e); final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { while (count == items.length) notFull.await(); enqueue(e); } finally { lock.unlock(); } } public E take() throws InterruptedException { final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { while (count == 0) notEmpty.await(); return dequeue(); } finally { lock.unlock(); }}}Copy the code

3.3 LinkedBlockingQueue

3.3.1 LinkedBlockingQueue overview

  • A new class under the java.util.Concurrent package. One of these is LinkedBlockingQueue, which is a blocking thread-safe queue with the underlying implementation of a linked list. If the LinkedBlockingQueue is constructed without a size, the default size is integer.max_value, which can also be specified as an argument to the constructor. LinkedBlockingQueue does not accept NUL

  • A blocking queue of linked lists

Refer to the article

Java collection – the ArrayList implementation principle of www.cnblogs.com/ITtangtang/… HashMap implementation principle of www.importnew.com/16301.html