This is the sixth day of my participation in the August More text Challenge. For details, see:August is more challenging

Thread-safe collections

WangScaler: an author who works with his heart.

Statement: talent and learning shallow, if there is a mistake, kindly correct.

An unsafe set

For everyday coding, do we often use collections like ArrayList, HashSet, and HashMap? Did you know that these collections are not safe in multithreading, for example.

package com.wangscaler.securecollection;
​
import java.util.*;
​
/ * * *@author WangScaler
 * @date2021/8/5 arieh * /
​
public class NotSafeCollection {
    public static void main(String[] args) {
​
        List<Integer> list = new ArrayList<>();
        int number = 3;
        Random random = new Random();
        for (int i = 0; i < number; i++) {
            new Thread(() -> {
                int randomNumber = random.nextInt(10) % 11;
                list.add(randomNumber);
            }, String.valueOf(i)).start();
        }
        while (Thread.activeCount() > 2) { Thread.yield(); } list.forEach(System.out::println); }}Copy the code

You might want to use three threads to populate the ArrayList, but the result might be null; null; 3 May also be null; 2; 3, of course, it is possible to achieve your desired effect 1,2,3.

Why does this happen? Let’s open up the source code

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
Copy the code

But three lines of code are executed with bytecode as follows

 0 aload_0
 1 aload_0
 2 getfield #284 <java/util/ArrayList.size : I>
 5 iconst_1
 6 iadd
 7 invokespecial #309 <java/util/ArrayList.ensureCapacityInternal : (I)V>
10 aload_0
11 getfield #287 <java/util/ArrayList.elementData : [Ljava/lang/Object;>
14 aload_0
15 dup
16 getfield #284 <java/util/ArrayList.size : I>
19 dup_x1
20 iconst_1
21 iadd
22 putfield #284 <java/util/ArrayList.size : I>
25 aload_1
26 aastore
27 iconst_1
28 ireturn
Copy the code

Threads are executed alternately while the program is executing. Our example above has three threads, thread 1, thread 2, and thread 3.

Putfield #284 < Java /util/ arrayList. size: I> is written before aastore, that is, size is written back to main memory before array is written back. It is possible that thread 2 will execute the array before thread 1 has written it in, and the size will be incrementing by one, so thread 2 will save the new value to the array, and null will appear. 2; In the case of 3.

A HashMap is also thread-unsafe, as is a HashSet, because the underlying HashSet is a HashMap

public HashSet(a) {
    map = new HashMap<>();
}
Copy the code

So what’s the difference between a HashMap and a HashSet? We know that a HashMap is in the form of a key-value pair, while a HashSet has a fixed value.

private static final Object PRESENT = new Object();
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
Copy the code

In addition to being thread unsafe, a HashMap can also cause dead chains when it is expanded before JDK8.

How to solve it?

1. Legacy security collections

  • The Vector used in the ArrayList

  • HashTable for HashMap

    For example: Set the above List

    List = new ArrayList<>(); List

    List = new Vector<>(); Can. Why does this solve the problem? Open source

    public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}
Copy the code

    Is a synchronous method that solves the problem with mutex, but has been deprecated because it is extremely inefficient in multithreading. HashTable is also deprecated due to synchronization issues.

2, the Collections

Make insecure Collections secure through the collection decoration.

  • SynchronizedList for ArrayList
  • SynchronizedMap to HashMap
  • SynchronizedSet for HashSet

Wrapping a thread-safe class over an already unsafe set achieves the desired effect. For example: Set the above List

List = new ArrayList<>(); Modified to List < Integer > List = Collections. SynchronizedList (new ArrayList < > ()); Can be solved. How does that work? Again, look at the source code

SynchronizedList(List<E> list) {
    super(list);
    this.list = list;
}
 public E get(int index) {
            synchronized (mutex) {return list.get(index);}
        }
        public E set(int index, E element) {
            synchronized (mutex) {return list.set(index, element);}
        }
        public void add(int index, E element) {
            synchronized (mutex) {list.add(index, element);}
        }
        public E remove(int index) {
            synchronized (mutex) {return list.remove(index);}
        }
Copy the code

Synchronized = synchronized = synchronized = synchronized = synchronized = synchronized

3, JUC

  • Bloacking

    • ArrayBlockingQueue
    • LinkedBlockingQueue
    • LinkedBlockingDeque
    • .

  • CopyOnWrite

    • CopyOnWriteArrayList corresponding ArrayList
    • CopyOnWriteArraySet is used for HashSet, and the underlying layer is still CopyOnWriteArrayList

  • Concurrent (recommended, weak consistency.)

    • ConcurrentHashMap used HashMap

      Only one operation can be guaranteed to be atomic, such as checking whether the key is present first (get) and not adding (put). Two operations cannot be guaranteed to be atomic, so you should use computeIfAbsent().

    • ConcurrentSkipListMap

    • ConcurrentSkipListSet

    • .

For example: Set the above List

List = new ArrayList<>(); Change to List

List = new CopyOnWriteArrayList<>();

Good for scenarios where you read more than you write. Look at the source

public boolean add(E e) {
    final ReentrantLock lock = 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(); }}Copy the code

When writing, lock the data, make a copy, write the new array to the new array, and finally write the new array back to the original resource, thus ensuring the atomicity of the data. This process only adds the lock to the method, does not affect the read operation.

conclusion

In multi-threaded synchronization method greatly affects the efficiency of work, so ConcurrentHashMap through volatile combined with spin lock, widely popular, also is one of the interviewers often asked questions, it is worth everyone to read the source code.