ArrayList capacity expansion mechanism and thread safety

Hello everyone , I meet you again , I'm your friend, Quan Jun .

List Implementation steps of capacity expansion

Generally speaking, there are two steps ：

1、 Capacity expansion

​ Copy the original array to another array with larger memory space

2、 Additive elements

​ Add new elements to the expanded array

Performance analysis

ArrayList As a dynamic array , Its internal elements are stored sequentially in the form of an array , So it is very suitable for random access . In addition to the tail, insert and delete elements , Performance tends to be relatively poor , For example, we insert an element in the middle , All subsequent elements need to be moved .

Source code analysis

The first ArrayList Some attributes defined in are posted for the following source code analysis

ArrayList Two construction methods of

1.ArrayList() 2.ArrayList(int initialCapacity)

 No arguments structure ：
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
 Belt structure ：
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

Copy

In nonparametric construction , Created an empty array , The length is 0

In parametric construction , If the passed in parameter is a positive integer, the size of the created array will be determined according to the passed in parameter , Otherwise abnormal

The way to expand capacity

Insert element function (boolean add(E e))

ArrayList When the insert element exceeds the predefined maximum value of the current array , The array needs to be expanded , The expansion process needs to call the underlying layer System.arraycopy() Method to perform a large number of array copy operations .

Paste the source code

public boolean add(E e) { 

	ensureCapacityInternal(size + 1); // Increments modCount!! 

	elementData[size++] = e; 

	return true;

}

Copy

see , Actually add The method is two steps ,

First step ： Increase length

The second step ： Add elements to the array

ensureCapacityInternal(int minCapacity) This method of increasing length

We saw this place , If the far array is empty when adding , Just give one 10 The length of , Otherwise, add one

ensureExplicitCapacity(int minCapacity)

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

Copy

Passing through this place is really increasing the length , When the required length is greater than the original array length, it needs to be expanded , On the contrary, there is no need to expand

This is where the attention is

int newCapacity = oldCapacity + (oldCapacity >> 1);

oldCapacity >> 1 Shift right operator Half the original length Plus the original length, that is, each expansion is the original 1.5 times

All the previous work is to determine the length of the new array , After confirmation, the old array copy Go to the new array , In this way, the expansion of the array is over

Everything above is ArrayList The first step of capacity expansion , There is nothing to say in the second step , Is to add the element to be added to the last bit of the array

ArrayList Security

Non-thread safety

1. stay add There will be thread safety problems during the capacity expansion of , ensureCapacityInternal(int minCapacity) There is a thread safety problem in this step

2. stay add Of elementData[size++] = e This code will also have thread safety problems when multithreading ,

There are two steps here ：

elementData[size] = e;

size = size + 1;

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/131442.html Link to the original text ：https://javaforall.cn