So the finest | 21 picture with you appreciate collection thread unsafe

The main contents of this paper are as follows:

All of this sample code has been updated to my Github

This article is in my Java online documentation

Java Concurrency Must Know must be series:

1. Counter the interviewer | | 14 zhang diagram is no longer afraid of being asked a volatile!

2. Programmer was despised by his wife in the middle of the night because CAS principle was too simple?

3. The principle of with blocks on ABA | wife incredibly understand again!

4. Cut the finest | 21 picture with you appreciate collection thread unsafe

Thread unsafe ArrayList

There are two types of Collection framework: Map and Collection. Under Collection, there are List, Set and Queue. Below List are ArrayList, Vector, and LinkedList. As shown in the figure below:

Collections are Queue, CopyOnWriteArrayList, CopyOnWriteArraySet, and ConcurrentMap

So let’s look at ArrayList first.

1.1. Low-level initialization of ArrayList

First, let’s review the use of arrayLists. Let’s initialize an ArrayList that contains values of type Integer.

new ArrayList<Integer>();
Copy the code

So what’s being done at the bottom?

1.2. Underlying Principles of ArrayList

1.2.1 Initializing arrays

/** * Constructs an empty list with an initial capacity of ten. */
public ArrayList(a) {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

We created an empty array with a capacity of 0, which according to the official English comment should be 10, but it’s actually 0, and we’ll see why it’s not.

1.2.1 Add Operations for an ArrayList

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

The key is this step: elementData[size++] = e; Size++ and elementData[xx]=e, neither of which is atomic (an indivisible one or series of operations that either execute successfully or none at all).

1.2.2 ArrayList Expands source code parsing

(1) When performing the add operation, we will first confirm whether the size of the array is exceeded

ensureCapacityInternal(size + 1);
Copy the code

(2) Calculate the current capacity of the array: calculateCapacity

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
Copy the code

MinCapacity: The value is 1

ElementData: represents the current array

Let’s first look at the ensureCapacityInternal method called by ensureCapacityInternal

calculateCapacity(elementData, minCapacity)
Copy the code

The method of calculateCapacity is as follows:

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
Copy the code

ElementData: represents the current array. When the first element is added, elementData equals DEFAULTCAPACITY_EMPTY_ELEMENTDATA (empty array)

MinCapacity: equal to 1

DEFAULT_CAPACITY: equal to 10

Math.max(DEFAULT_CAPACITY, minCapacity) = 10

Summary: So the first time you add an element, calculate the size of the array to 10

(3) Determine the current capacity

minCapacity = 10

elementData.length=0

Summary: Since minCapacity > elementData.length, do the first expansion, call the grow() method to expand from 0 to 10.

(4) Call the grow method

OldCapacity = 0, newCapacity = 10.

ElementData = arrays.copyof (elementData, newCapacity);

The current array and the size of the array copy operation, assigned to elementData. The capacity of the array is set to 10

The value of elementData will be different from that of DEFAULTCAPACITY_EMPTY_ELEMENTDATA.

(5) The element is then assigned to the first element of the array, and the size increases by 1

elementData[size++] = e;
Copy the code

(6) When we add the second element, we pass 2 to ensureCapacityInternal

ensureCapacityInternal(size + 1)
Copy the code

Size = 1 + 1 = 2 size

(7) When adding elements for the second time, execute calculateCapacity

The value of elementData is not equal to the value of DEFAULTCAPACITY_EMPTY_ELEMENTDATA, so return 2 directly

(8) When adding an element the second time, execute ensureExplicitCapacity

Since minCapacity is equal to 2, which is less than the current array length of 10, no expansion is performed and the grow method is not executed.

(9) Add the second element to the array, incrementing the size by 1

elementData[size++] = e
Copy the code

(10) The grow method is called when the 11th element is added

MinCapacity =11, elementData.length=10, call the grow method.

(11) Expand by 1.5 times

int newCapacity = oldCapacity + (oldCapacity >> 1);
Copy the code

NewCapacity =10+5=15; newCapacity= 15; oldCapacity=10; newCapacity= 15;

(12) Summary

1. Initialize the ArrayList to aAn empty array
2. Add to ArrayList is not thread-safe
3. When the first element is added to the ArrayList, the array capacity is set to10
4. When the capacity of ArrayList exceeds the current capacity, expand the capacity to1.5 timesAfter the first expansion, the capacity is 15, and the second expansion is 22…
5.ArrayList will copy and call the array after the first and expansionArrays.copyOfMethods.

1.3. Is ArrayList single-threaded environment safe?

Scene:

We show that ArrayList is thread-safe under a single thread with an example of adding building blocks.

Add the building blocks triangle A, quadrilateral B, pentagonal C, hexagon D and pentagram E to A box in turn. There are 5 squares in the box, and each square can put A building block.

Code implementation:

(1) This time we use the new building block class BuildingBlockWithName

This block class can pass shape and name

/** * Building blocks *@author: Wukong chat structure *@create: the 2020-08-27 * /
class BuildingBlockWithName {
    String shape;
    String name;
    public BuildingBlockWithName(String shape, String name) {
        this.shape = shape;
        this.name = name;
    }
    @Override
    public String toString(a) {
        return "BuildingBlockWithName{" + "shape='" + shape + ",name=" + name +'} '; }}Copy the code

(2) Initialize an ArrayList

ArrayList<BuildingBlock> arrayList = new ArrayList<>();
Copy the code

(3) Add triangle A, quadrilateral B, pentagonal C, hexagon D, pentagram E

arrayList.add(new BuildingBlockWithName("Triangle"."A"));
arrayList.add(new BuildingBlockWithName(Quadrilateral."B"));
arrayList.add(new BuildingBlockWithName("Pentagon"."C"));
arrayList.add(new BuildingBlockWithName("Hexagon"."D"));
arrayList.add(new BuildingBlockWithName("Pentacle"."E"));
Copy the code

(4) Verify that the contents and order of the elements in the arrayList are consistent with the addition

BuildingBlockWithName{shape='triangle,name=A} BuildingBlockWithName{shape='Quadrilateral,name=B} BuildingBlockWithName{shape='pentagonal,name=C} BuildingBlockWithName{shape='Hexagon,name=D} BuildingBlockWithName{shape=Name =E}Copy the code

We see that the results do agree.

Summary: ArrayList is thread-safe in a single-threaded environment.

ArrayList is not safe under multiple threads

The scenario is as follows: 20 threads randomly add an arbitrarily shaped building block to the ArrayList.

(1) Code implementation: 20 threads to randomly store a building block in the array.

(2) Print results: after the program starts to run, each thread stores only one random building block.

Will continue to store in the array blocks, multiple threads will compete for an array of storage, in the process of storage, throws an exception: ConcurrentModificationException (parallel) modified

Exception in thread "10" Exception in thread "13" java.util.ConcurrentModificationException
Copy the code

This is common concurrency exception: Java. Util. ConcurrentModificationException

1.5 How to solve the problem of ArrayList thread insecurity?

There are the following plans:

1. Vector instead of ArrayList
2. Use the Collections. Synchronized (new ArrayList < > ())
3.CopyOnWriteArrayList

1.6 Is Vector Thread safe?

Let’s analyze the source code for Vector.

1.6.1 Initializing Vector

Initialize the capacity to 10

public Vector(a) {
    this(10);
}
Copy the code

1.6.2 The Add operation is thread safe

The Add method with a synchronized to ensure the Add operation is thread-safe (ensure visibility, atomicity, order), to this a few concepts have don’t understand the articles – may have a look before you counter the interviewer | | 14 zhang diagram is never afraid of being asked a volatile!

1.6.3 Vector doubled

int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
Copy the code

Note: capacityIncrement can be passed when initializing; if not, it defaults to 0. If yes, oldCapacity+capacityIncrement is set during the first capacity expansion and is doubled during the second capacity expansion.

Disadvantages: Although guaranteed thread safety, performance degrades due to blocking with the addition of synchronized.

1.6.4 Simulate the add operation of Vector with building blocks

When the elements are stored in the vector, a lock is added to the box, and only one person can store the blocks. After that, the lock is released, and when the second element is placed, the lock is added, and so on.

1.7 the use of the Collections. SynchronizedList ensure thread safety

We can use the Collections. SynchronizedList method is to encapsulate an ArrayList.

List<Object> arrayList = Collections.synchronizedList(new ArrayList<>());
Copy the code

Why is it thread-safe when it’s encapsulated?

Source code parsing: Because Collections. SynchronizedList encapsulation after the list, the list of all the operation method is with synchronized keyword (with the exception of the iterator ()), the equivalent of all operations are locked, So it is thread-safe to use it (except to iterate over arrays).

Note: Manual synchronization is required when iterating over arrays. The official example is as follows:

synchronized (list) {
     Iterator i = list.iterator(); // Must be in synchronized block
     while (i.hasNext())
         foo(i.next());
}
Copy the code

1.8 Use CopyOnWriteArrayList to ensure thread safety

, version 1.8.1 CopyOnWriteArrayList thought

Copy on write: An idea that separates read and write.
Write operation: When adding an element to the current array, it does not directly add the element to the current array. Instead, it copies the array first. After adding the element to the new array, it points the reference to the new array. Since arrays are modified with the volatile keyword, other threads can immediately know when the array is reassigned.
Read operation: when reading an array, read the old array without locking.
Read/write separation: a write operation copies a new array, and a read operation reads the old array, so it is read/write separation.

1.8.2 Usage Mode

CopyOnWriteArrayList<BuildingBlockWithName> arrayList = new CopyOnWriteArrayList<>();
Copy the code

1.8.3 Underlying source analysis

The process of ADD:

A reentrant lock is definedReentrantLock
Before adding an element, acquire the locklock.lock()
To add an element, copy the current arrayArrays.copyOf
When adding an element, expand by +1 (len + 1)
After the element is added, the array reference points to the array with the newly added elementsetArray(newElements)

Why do other threads immediately know when an array is reassigned?

Because the array here is volatile. Wow, volatile again. That’s a nice keyword

 private transient volatile Object[] array;
Copy the code

1.8.4 Differences between ReentrantLock and synchronized

To highlight

Similarities:

1. Both are used to coordinate multi-threaded access to shared objects and variables
2. Both locks are reentrant. The same thread can obtain the same lock multiple times
3. Both guarantee visibility and mutual exclusion

Difference:

1.ReentrantLock acquires and releases the lock, and synchronized implicitly acquires and releases the lock
2.ReentrantLock can respond to interrupts, synchronized can’t, providing more flexibility in dealing with lock unavailability
3.ReentrantLock is API level and synchronized is JVM level
4.ReentrantLock can implement fair and non-fair locking
5.ReentrantLock can bind multiple conditions through the Condition
6. The underlying implementation is different. Synchronized refers to synchronous blocking and uses a pessimistic concurrency policy, while lock refers to synchronous non-blocking and uses an optimistic concurrency policy

1.8.5 The difference between Lock and synchronized

1.Lock The Lock must be obtained and released manually. It’s like the difference between automatic and manual
Lock is an interface, synchronized is a keyword in Java, and synchronized is a built-in language implementation.
2. Synchronized releases locks held by the thread when an exception occurs, so deadlocks do not occur. UnLock () : unLock() : unLock() : unLock() : unLock() : unLock() : unLock() : unLock() : unLock() : unLock() : unLock() : unLock() : unLock() : unLock()
3. A Lock can interrupt a thread waiting for a Lock, but synchronized cannot. With synchronized, a thread waiting for a Lock can wait forever and cannot respond to an interrupt.
4. You can tell whether a Lock has been successfully acquired by locking, whereas synchronized cannot.
5.Lock Can improve the efficiency of read operations by multiple threads by implementing read/write locks.

Thread unsafe Hashsets

Now that we’ve spent a lot of time talking about arrayLists being thread-safe, and how we can use other ways to make them thread-safe, hashSets should be a little easier to understand.

2.1 Usage of HashSet

The usage is as follows:

Set<BuildingBlockWithName> Set = new HashSet<>();
set.add("a");
Copy the code

Initial capacity =10, load factor =0.75 (start expansion when the number of elements reaches 75% of capacity)

2.2 Underlying Principles of HashSet

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

The underlying use is again HashMap().

The add operation of a HashSet requires only one parameter (value) and the add operation of a HashMap requires two parameters (key and value).

2.3 Add operations for a HashSet

private static final Object PRESENT = new Object();

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

In the add operation of a HashSet, the key is equal to the value passed. The value is PRESENT, and the PRESENT is the new Object(). Key =e, value=new Object The Hash only cares about the key, not the value.

Why HashSets are unsafe: The underlying ADD operation does not guarantee visibility, atomicity. So it’s not thread safe.

2.4 How can I Ensure Thread Safety

1. The use of the Collections. SynchronizedSet

Set<BuildingBlockWithName> set = Collections.synchronizedSet(new HashSet<>());
Copy the code

2. Use CopyOnWriteArraySet

CopyOnWriteArraySet<BuildingBlockWithName> set = new CopyOnWriteArraySet<>();
Copy the code

2.5 The underlying CopyOnWriteArraySet is CopyOnWriteArrayList

public CopyOnWriteArraySet(a) {
    al = new CopyOnWriteArrayList<E>();
}
Copy the code

Thread unsafe HashMap

3.1 Use of HashMap

Similarly, a HashMap, like a HashSet, is thread unsafe in a multi-threaded environment.

Map<String, BuildingBlockWithName> map = new HashMap<>();
map.put("A".new BuildingBlockWithName("Triangle"."A"));
Copy the code

3.2 Solution to HashMap Thread Insecurity:

1.Collections.synchronizedMap

Map<String, BuildingBlockWithName> map2 = Collections.synchronizedMap(new HashMap<>());
Copy the code

2.ConcurrentHashMap

ConcurrentHashMap<String, BuildingBlockWithName> set3 = new ConcurrentHashMap<>();
Copy the code

3.3 ConcurrentHashMap principle

ConcurrentHashMap, which internally subdivides a number of small HashMaps, called segments. By default, a ConcurrentHashMap is further subdivided into 16 segments, which is the concurrency of the lock. If you need to add a new entry to ConcurrentHashMap, you do not lock the entire HashMap. Instead, you first find out which segment the entry should be stored in according to the Hashcode, then lock the segment, and complete the PUT operation. In a multi-threaded environment, if multiple threads perform the PUT operation at the same time, the threads can be truly parallel as long as the entries to be added are not stored in the same segment.

Other collection classes

LinkedList: Thread unsafe, same as ArrayList TreeSet: thread unsafe, same as HashSet LinkedHashSet: thread unsafe, same as HashSet TreeMap: HashMap: thread unsafe HashTable: thread safe

conclusion

The first part of this article detailed the underlying scaling principles of the ArrayList collection, demonstrating that ArrayList thread insecurity causes concurrent modification exceptions to be thrown. Then, through source code parsing, we explain three ways to ensure thread safety:

VectorThrough theaddAnd so onsynchronizedTo be thread safe
Collections.synchronized()By wrapping an array, we preappend the operation methods on the arraysynchronizedTo be thread safe
CopyOnWriteArrayListthroughWhen writing copyTo be thread safe.

Part 2 explained that hashsets are thread unsafe, and there are two ways to make them thread-safe:

Collections.synchronizedSet
CopyOnWriteArraySet

Part 3 explains that HashMap is thread unsafe. There are two ways to ensure thread safety:

Collections.synchronizedMap
ConcurrentHashMap

In addition, the differences between ReentrantLock and synchronized and between Lock and synchronized are compared in detail in the process of explanation.

Easter Egg: If you’re smart enough, there’s one more important thing missing from the set: the Queue. Looking forward to what happens next?

White go whoring? Forward -> look -> Like – favorites!!

I am Wukong, a code to become stronger! I’m gonna be a super Saiyan!

In addition, you can search wechat “Wukong chat architecture” or PassJava666, progress together! On my GitHub home page, follow my Spring Cloud practical project, Jibbi Pass.