ArrayList source code analysis

ArrayList data structure

The ArrayList data structure is an array structure.

The figure shows an array of length 10, counting from 1, index representing the array’s subscript, counting from 0, and elementData representing the array itself

1.1 Important Variables

/ * *

* represents the initial size of the array, which defaults to 10;

* /

private static final int DEFAULT_CAPACITY = 10;



/ * *

* Count the number of changes to the current array. If the array structure is changed, +1 will be added.

* This variable is in AbstractList

* /

protected transient int modCount = 0;



/ * *

* Represents the size of the current array. The type is int. Volatile is not used, and is not thread-safe

* /

private int size;

Copy the code

Source code analysis

2.1 ArrayList class annotation parsing

  • If the put NULL value is allowed, the system automatically expands the capacity.
  • The time complexity of size, isEmpty, get, set and add methods is O (1).
  • Threadsafe; Collections#synchronizedList;
  • Enhance the for loop, or use iterators that will fail quickly if the array size changes, throwing an exception.

2.2 Initialization Implementation

Source code analysis:

ArrayList can be initialized with a specified size, or initialized with specified data.

/ * *

* Direct initialization without arguments, array size is empty

* /

public ArrayList(a) {

    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

  / * *

* Specifies parameter initialization

* /

    public ArrayList(Collection<? extends E> c) {

        //elementData is the container that holds the array. Default is NULL

        elementData = c.toArray();

        // If the given set has a value

        if((size = elementData.length) ! =0) {

            // If the collection element is not Object, it is converted to Object

            if(elementData.getClass() ! = Object[].class)

                elementData = Arrays.copyOf(elementData, size, Object[].class);

        } else {

            // If the set has no value, the array defaults to empty

            this.elementData = EMPTY_ELEMENTDATA;

        }

    }

Copy the code

Matters needing attention:

  • When the ArrayList no-argument constructor initializes, the default size is an empty array, not the usual 10, which is the value of the array expanded when we first add it.

2.3 Implementation of new and Capacity Expansion

Source code analysis:

To add an element to an array, do two steps:

  • Determine whether capacity expansion is required. If yes, perform capacity expansion.
  • Direct assignment.
Feature:
public boolean add(E e) {

   // Make sure that the array size is sufficient, but then expand the size of the current array

    ensureCapacityInternal(size + 1); 

    // It is not safe to copy threads directly

    elementData[size++] = e;

    return true;

}

Copy the code
Capacity:
private void ensureCapacityInternal(int minCapacity) {

  // If the size of the array is initialized with a given initial value, no if logic is used

    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

    }

    // Make sure the volume is sufficient

    ensureExplicitCapacity(minCapacity);

}



private void ensureExplicitCapacity(int minCapacity) {  

    // The record array is modified

    modCount++;

    // If the desired minimum capacity is greater than the current array size, expand it

    if (minCapacity - elementData.length > 0)

        grow(minCapacity);

}

// Expand the array and copy the existing data into the new array

private void grow(int minCapacity) {

     int oldCapacity = elementData.length;

    // oldCapacity >> 1

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

    // If the expanded value is less than our expected value, the expanded value is equal to our expected value

    if (newCapacity - minCapacity < 0)

            newCapacity = minCapacity;

    // If the expanded value is greater than the maximum number of arrays the JVM can allocate, then Integer's maximum value is used

    if (newCapacity - MAX_ARRAY_SIZE > 0)

            newCapacity = hugeCapacity(minCapacity);

     // Expand capacity by replication

     elementData = Arrays.copyOf(elementData, newCapacity);

    }

Copy the code
Nature of expansion:

CopyOf (elementData, newCapacity); This line of code is implemented, the nature of this line of code description is the copy between arrays, expansion is to first create a new array that meets our expected capacity, and then copy the data of the old array, we use the System. Arraycopy method to copy, this method is native method, the source code is as follows:

/ * *

*@paramSRC Specifies the array to be copied

*@paramSrcPos starts with an array

*@paramDest target array

*@paramDestPos is copied from the index position in the target array

*@paramLength Indicates the length of the copy

* This method does not return a value. The value is passed through a reference to dest

* /

public static native void arraycopy(Object src,  int  srcPos,

                                    Object dest, int destPos,

                                    int length);

Copy the code

Matters needing attention:

  • The capacity expansion rule does not double the original capacity. The capacity is half of the original capacity plus half of the original capacity. The capacity after expansion is 1.5 times of the original capacity.

  • The maximum value of an array in an ArrayList is integer.max_value, beyond which no memory is allocated by the JVM. When added, values are not strictly validated, so ArrayList allows null values.

  • The lower bound of the size of the array cannot be less than 0, and the upper bound cannot be greater than the maximum Integer.

  • Once the expansion is complete, the assignment is very simple, simply adding elements to the array: elementData [size++] = e. This simple assignment does not have any lock control, so the operation here is thread-unsafe:

2.4 Deleting implementation

Source code analysis:

ArrayList can delete elements in many ways, such as by array index delete, delete by value or batch delete, etc. We select by value delete method to carry out source code:

public boolean remove(Object o) {

    // If the value to be deleted is null, find the delete whose first value is null

    if (o == null) {

        for (int index = 0; index < size; index++)

            if (elementData[index] == null) {

                fastRemove(index);

                return true;

            }

    } else {

      // If the value to be deleted is not null, find the first delete equal to the value to be deleted

        for (int index = 0; index < size; index++)

        // Check the value equals, then delete the value according to the index position

            if (o.equals(elementData[index])) {

                fastRemove(index);

                return true;

            }

    }

    return false;

}

Copy the code

The index position of the element to be deleted is found in the following code:

private void fastRemove(int index) {

    // The structure of the record array has changed

    modCount++;

    // numMoved Indicates how many elements to move from the index position to the front after the index position is removed

    // The reason for the reduction is that size starts at 1 and index starts at 0

    int numMoved = size - index - 1;

    if (numMoved > 0)

    // The copy will start at index +1 and the length will be numMoved

        System.arraycopy(elementData, index+1, elementData, index,

                         numMoved);

   // Assign the last position of the array to null to help the GC

    elementData[--size] = null; 

}

Copy the code

Matters needing attention:

  • Nulls are not checked when they are added, so nulls can be deleted when they are deleted.
  • Finding the index position of the value in the array is determined by equals. If the array element is of non-primitive type, we need to pay attention to the implementation of equals.
  • When an element is deleted, we always move the element behind the array forward to maintain the array structure

Time complexity

After the source code analysis of the new or delete method, the operation of array elements, only according to the array index, directly add and delete, so the time complexity is O (1).

Four. Thread safety

4.1 Thread safety Causes Occur

Thread-safety is only a problem when ArrayList is a shared variable, and not when ArrayList is a local variable within a method.

ArrayList is thread-safe because none of its elementData, size, and modConut operations are locked, and none of these variables are volatile. So if multiple threads operate on these variables, the values may be overwritten.

The method synchronizedList (Collections#synchronizedList) is thread safe. The method synchronizedList (Collections#synchronizedList) is thread safe.

public boolean add(E e) {

    synchronized (mutex) {returnc.add(e); }

}

Copy the code

We can also use CopyOnWriteArrayList to keep our threads safe for comparison in the following table

4.2 Comparison of Thread Safety Methods:

CopyOnWriteArrayList (JDK 1.5 introduced) SynchronizedList
create List list = new CopyOnWriteArrayList(); List list = new ArrayList(); List syncList = Collections.synchronizedList(list);
Thread safety Security CopyOnWriteArrayList is a thread-safe variant of ArrayList. It is designed for concurrent access from multiple threads. CopyOnWriteArrayList provides a thread-safe alternative to ArrayList. security
How to implement thread safety? Thread-safe is achieved by making a fresh copy of the original array with each mutable operation (add, set, etc.). As you can also see from the name, whenever the value changes, it can be copied at write time. Locks the SynchronizedList for all operations on the original list, essentially adding a synchronization block for all operations
performance CopyOnWriteArrayList implements all mutable operations (add, set, etc.) by creating a new copy of the original array. Therefore, there is no additional overhead during a read operation, but there is significant overhead during a write operation. Because the entire list is locked and only one thread can access it at any given time, performance is very poor.
Memory overhead You need to create a new copy of the original array for mutable operations like add, set, and so on. There is no
When to use When the number of reads exceeds the number of writes, select CopyOnWriteArrayList. When read write more than the number of times, should choose the Collections. SynchronizedList ().

In live.

The underlying structure of An ArrayList is an array structure, and the apis encapsulate the operations of an array, so that users don’t need to be aware of the underlying implementation, but can only focus on how to use it.

If you feel helpful, I hope you can pay attention to it, click a “like” and then go, thank you!!