ArrayList

ArrayList is one of the most commonly used data structures in Java collections, so it’s important to learn how it works.

The properties of ArrayList

//ArrayList Default capacity Private static final int DEFAULT_CAPACITY = 10; Private static final Object[] EMPTY_ELEMENTDATA = {}; // Use an empty constructor to instantiate a capacity expansion operation. // Use an empty constructor to instantiate a capacity expansion operation. Private Static Final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // Store real data transient Object[] elementData; Private int size; // Set the maximum capacity of the ArrarList to Integer.MAX_VALUE. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;Copy the code

ArrayList constructor

/ / initialCapacity: Public ArrayList(int initialCapacity) {if (initialCapacity > 0) {// if the initialCapacity is greater than 0, This. ElementData = new Object[initialCapacity]; } else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA; } else {throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); Public ArrayList() {ArrayList() {ArrayList(); This. ElementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //c: Collection class // This constructor is used to place the data of the Collection class into a new ArrayList. Extends E> c) {// Assign elementData = c.toarray (); if ((size = elementData.length) ! If (elementData.getClass()! = 0) {// If (elementData.getClass()! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else {// if the elementData of the collection class in the argument is null, set the elementData in its ArrayList to null this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

One of the most common methods used in ArrayList classes is to add, delete, modify, and review these operations, and then browse the source code for these methods

The add method

Public Boolean add(E E) {public Boolean add(E E) {public Boolean add(E E) {public Boolean add(E E) {public Boolean add(E E) {public Boolean add(E E) {public Boolean add(E E) { // assign the added element to the array elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) {//calculateCapacity(): Calculate the capacity of the element array //ensureExplicitCapacity(): ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, If (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {// If (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // If yes, return the maximum value of DEFAULT_CAPACITY and minCapacity. Return math. Max (DEFAULT_CAPACITY, minCapacity); } return minCapacity; return minCapacity; } private void ensureExplicitCapacity(int minCapacity) {//modCount: used to record the number of changes to the ArrayList modCount++; If (mincapacity-elementdata.length > 0) grow(minCapacity); if (minCapacity - elementData.length > 0) } private void grow(int minCapacity) {// overflow-conscious code Int newCapacity = oldCapacity + (oldCapacity >> 1); If (newCapacity -mincapacity < 0) // If (newCapacity -mincapacity < 0) // If (newCapacity -mincapacity < 0) // If (newCapacity -mincapacity < 0) // If (newCapacity -mincapacity < 0) newCapacity = minCapacity; If (newCapacity -max_array_size > 0) // If (newCapacity -max_array_size > 0) If it is larger, the newCapacity is set to integer. MAX_VALUE, otherwise it is set to MAX_ARRAY_SIZE newCapacity = hugeCapacity(minCapacity); ElementData = array.copyof (elementData, newCapacity); }Copy the code

Public void add(int index, E element) {// If the index to be inserted is greater than the number of elements in the current array rangeCheckForAdd(index); EnsureCapacityInternal (size + 1); ensureCapacityInternal(size + 1); // Move the size-index element to index+1. Arraycopy (elementData, index, elementData, index + 1, size-index); arrayCopy (elementData, index, elementData, index + 1, size-index); ElementData [index] = element; // element size+ 1 size++; }Copy the code

The remove method

Public E remove(int index) {rangeCheck(index) {if the index to be removed is greater than the number of elements; //modCount+1 modCount++; E oldValue = elementData(index); Int numMoved = size-index-1; int numMoved = size-index-1; If (numMoved > 0) system. arrayCopy (elementData, index+1, elementData, index, arrayCopy (elementData, index+1) numMoved); ElementData [--size] = null; // clear to let GC do its work return oldValue; }Copy the code

Public Boolean remove(Object o) {if (o == null) {if (o == null) { For (int index = 0; int index = 0; index < size; If (elementData[index] == null) {fastRemove(index); return true; } } else { for (int index = 0; index < size; If (o.quals (elementData[index])) {fastRemove(index); if (o.quals (elementData[index]); return true; }} // If not found, return false; }Copy the code

Set method

Public E set(int index, E element) {// Check whether the index position to be changed is greater than the current number of elements, rangeCheck(index); E oldValue = elementData(index); ElementData [index] = element; // return oldValue; }Copy the code

The get method

Public E get(int index) {// Check the index position rangeCheck(index); // Return elementData(index); }Copy the code

ArrayList summary:

1. ArrayList is a data structure that uses arrays as the underlying structure. It is very quick to modify and query data.

When creating an ArrayList, the default capacity of the ArrayList is 10 if the object is created using a constructor whose parameter is the initial capacity

The ArrayList expansion increases the size of the existing array by half.

4. The maximum size of an ArrayList is integer.max_value-8 in most cases, but integer.max_value in special cases

Arraylists are quick and convenient to use in a single-threaded environment, but can they be thread-safe in a multi-threaded environment? The answer is no

Reading the source code for the Add method, you can see that the size of the ArrayList is determined by its size. The system determines whether to expand the capacity based on the size+1 value. If the size is greater than the length of the array, the system needs to expand the capacity. Then size will be set to the value after size+1. Let’s take a look at an example of why ArrayList has thread safety issues.

If there are two threads that need to add elements to the ArrayList, the size of each thread is currently 0. When the two threads start adding elements to the ArrayList, thread A puts the elements at position 0, and the CPU scheduling thread A pauses and thread B starts executing, and the size is still 0. So thread B also puts the element at position 0. Then thread A and thread B both continue to execute, and the size increases, so there’s really only one element at this point, but the size is 2, so that’s A thread-safe issue. Next, verify with the code

public class Test { public static void main(String[] args) { ArrayList<String> list=new ArrayList<>(); for(int i=0; i<10; i++){ new Thread(()->{ list.add(UUID.randomUUID().toString()); System.out.println(list); }).start(); } } } /* Exception in thread "Thread-9" Exception in thread "Thread-6" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909) at java.util.ArrayList$Itr.next(ArrayList.java:859) at java.util.AbstractCollection.toString(AbstractCollection.java:461) at java.lang.String.valueOf(String.java:2994) at java.io.PrintStream.println(PrintStream.java:821) at com.itheima.test.Test5.lambda$main$0(Test.java:17) at java.lang.Thread.run(Thread.java:748) */Copy the code

So how do you make ArrayList thread-safe? There are three ways

1. Lock mechanism

2, CopyOnWriteArrayList class

3, the Collections. SynchronizedList ()

Let’s look at how the CopyOnWriteArrayList class implements thread-safety from a source code perspective.

CopyOnWriteArrayList class

attribute

Final TRANSIENT ReentrantLock LOCK = new ReentrantLock(); Private TRANSIENT volatile Object[]; private transient volatile Object[];Copy the code

methods

Public Boolean add(E E) {final ReentrantLock lock = this.lock; // Get lock lock.lock(); Elements = getArray(); // Get the array Object[] elements = getArray(); Int len = elements. Length; Object[] newElements = array.copyof (elements, len + 1); NewElements [len] = e; // Assign the new array to the array property setArray(newElements) that stores the elements in CopyOnWriteArrayList; return true; } finally {// unlock lock.unlock(); }} // Use final decorators to prevent the getArray method from being overwritten by CopyOnWriteArrayList and thus modifying array, which would violate the thread-safety of CopyOnWriteArrayList. final Object[] getArray() { return array; } final void setArray(Object[] a) {array = a; }Copy the code

Public E remove(int index) {final ReentrantLock lock = this.lock; // Add lock lock.lock(); Elements = getArray(); elements = getArray(); // count len = elements. Length; E oldValue = get(elements, index); Int numMoved = len-index-1; int numMoved = len-index-1; Arraysetarray (array.copyof (elements, len-1)); array.copyof (elements, len-1)); Else {// Create a new element array 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); // Assign the new array of elements to array setArray(newElements); } // return oldValue; } finally {// unlock lock.unlock(); }}Copy the code

Public E set(int index, E element) {final ReentrantLock lock = this.lock; The lock (); / / lock lock. Elements = getArray(); elements = getArray(); E oldValue = get(elements, index); If (oldValue! = element) {// Calculate the length of the element array. Object[] newElements = array.copyof (elements, len); NewElements [index] = element; // Assign the new array of elements to array setArray(newElements); } else { // Not quite a no-op; Volatile write semantics = volatile write semantics = volatile write semantics Ensure volatile write semantics setArray(elements); } // return oldValue; } finally {// unlock lock.unlock(); }}Copy the code

Since CopyOnWriteArrayList is thread-safe, is it always possible to iterate over the latest data?

Public Iterator<E> Iterator () {return new COWIterator<E>(getArray(), 0); } private COWIterator(Object[] elements, int initialCursor) {private COWIterator(Object[] elements, int initialCursor) { // Assign elements from CopyOnWriteArrayList to snapshot snapshot = elements; } public Boolean hasNext() {return cursor < snapshot.length; } public E next() {// if (! hasNext()) throw new NoSuchElementException(); Return (E) snapshot[cursor++]; }Copy the code

As you can see from the traverser above, the CopyOnWriteArrayList class does not guarantee that the latest data will be read. Because the iterator gets the contents of an array, and the CopyOnWriteArrayList class creates a new memory space to store new data every time it adds, subtracts or deletes, it cannot guarantee real-time consistency.

CopyOnWriteArrayList summary:

1, CopyOnWriteArrayList class is a Lock Lock to ensure the security of the class.

2. Unlike AarrayList, CopyOnWriteArrayList does not fix the timing and size of the expansion. CopyOnWriteArrayList copies a new array of +1 size for every element added

The CopyOnWriteArrayList class uses the same lock for all methods added, deleted, and modified. This ensures that in a multithreaded environment, methods added, deleted, and modified do not affect each other

4. Each add, delete, or change operation opens up a new memory space to store elements, which also ensures a certain amount of thread safety. But it also consumes memory space

5. When iterators are used to traverse data, the real-time performance of traversal data cannot be guaranteed.