JDK source code analysis - collection array ArrayList

catalogue

1. General
2. Class diagram
3. Properties
4. Construction method
5. Add a single element
6. Array expansion
7. Add multiple elements
8. Remove individual elements
9. Remove multiple elements
10. Find a single element
11. Get the element at the specified position
12. Set the element of the specified position
13. Convert to array
14. Hash value
15. Judge equality
16. Empty array
17. Serialize array
18. Deserialize array
19. Cloning
20. Create subarray
21. Create Iterator iterator
22. Create ListIterator iterator
summary

1. General

ArrayList is a dynamic array based on [] array and supports automatic capacity expansion. Compared with array, because it supports automatic capacity expansion, it has become one of the most commonly used collection classes in our daily development.

In previous years, in the interview of internship or junior engineer, the most popular question may be the difference and use scenario between ArrayList and LinkedList. However, it seems that there are not many questions to ask now, because now the information is very developed, this kind of conventional interview questions can no longer distinguish ability. Of course, even so, it doesn't prevent us from cutting it. After all, it's our "old friend".

2. Class diagram

The interfaces and inherited abstract classes implemented by ArrayList are shown in the following figure:

Four interfaces are implemented:

java.util.List Interface, which provides operations such as adding, deleting, modifying, iterating and traversing arrays.
java.util.RandomAccess Interface, indicating that ArrayList supports fast random access.
java.io.Serializable Interface, indicating that ArrayList supports serialization.
java.lang.Cloneable Interface, indicating that ArrayList supports cloning.

Inherited java.util.AbstractList Abstract class, and AbstractList provides the skeleton implementation of the List interface, which greatly reduces the code for iterative traversal. Maybe this expression is a little abstract, you can click it java.util.AbstractList Take a look at abstract classes, such as #iterator(), #indexOf(Object o) and other methods.

😈 In fact, however, as we will see below, ArrayList largely rewrites the method implementation provided by AbstractList. Therefore, AbstractList is of little significance to ArrayList, and other subclasses of AbstractList enjoy this benefit.

3. Properties

ArrayList has few attributes, only 2. As shown in the figure below:

elementData attribute: array of elements. Among them, the red space in the figure represents that we have added elements, and the white space represents that we have not used them.
Size attribute: array size.

Note that size represents the number of elements in the ArrayList that have used elementData, and it is also the size of #size() seen by the developer. Moreover, when we add a new element, it happens to be the location (subscript) where the element is added to elementData. Of course, we know that the real size of ArrayList is the size of elementData.

The corresponding codes are as follows:

// ArrayList.java

/**
 * Element array.
 *
 * When adding new elements, if the array is not enough, a new array will be created and the elements of the original array will be copied to the new array. After that, point the variable to the new array.
 *
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 * An array buffer that stores array list elements. The capacity of ArrayList is the length of the array buffer.
 * When adding the first element, any with elementdata = = defaultcapability_ EMPTY_ ELEMENTDATA
 * The list of empty arrays will be extended to DEFAULT_CAPACITY. 
 */
transient Object[] elementData; // Non private to simplify nested class access does not use private repair to facilitate the access of embedded classes.

/**
 * Used array size
 *
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

4. Construction method

ArrayList has three construction methods. Let's take a look at them respectively.

① #ArrayList(int initialCapacity)

#The ArrayList(int initialCapacity) construction method creates an ArrayList array according to the incoming initialization capacity. If we specify the array size in advance, we must use this construction method to avoid array expansion and improve performance. At the same time, it is also a reasonable use of memory. The code is as follows:

// ArrayList.java

/**
 * Shared empty array object.
 *
 * In the {@ link #ArrayList(int)} or {@ link #ArrayList(Collection)} construction method,
 * If the incoming initialization size or collection size is 0, point {@ link #elementData} to it.
 *
 * Shared empty array instance used for empty instances.
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

public ArrayList(int initialCapacity) {
    // When the initialization capacity is greater than 0, an Object array is created
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    // When the initialization capacity is equal to 0, empty is used_ Elementdata object
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    // Throw an IllegalArgumentException when the initialization capacity is less than 0
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

In particular, if the initialization capacity is 0, empty is used_ Elementdata is an empty array. When adding elements, the capacity will be expanded to create the required array.

② #ArrayList(Collection c)

#The ArrayList(Collection c) construction method uses the incoming c collection as the elementData of ArrayList. The code is as follows:

// ArrayList.java

public ArrayList(Collection<? extends E> c) {
    // Convert c to Object array
    elementData = c.toArray();
    // If the array size is greater than 0
    if ((size = elementData.length) != 0) {
        // defend against c.toArray (incorrectly) not returning Object[]
        // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
        // <x> If the collection element is not of Object [] type, a new Object [] array will be created,
        // And assign elementData to it, and finally assign it to elementData.
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    // If the array size is equal to 0, empty is used_ ELEMENTDATA . 
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

What is more puzzling is the code at <x>. It is used to solve JDK-6260652 Bug. It is solved in JDK9, 😈 In other words, this problem will still exist in JDK8.

Let's look at a passage that can trigger JDK-6260652 The test code is then executed under JDK8 and JDK13 respectively. The code is as follows:

// ArrayListTest.java

public static void test02() {
    List<Integer> list = Arrays.asList(1, 2, 3);
    Object[] array = list.toArray(); // JDK8 returns Integer [] array, and JDK9 + returns Object [] array.
    System.out.println("array className : " + array.getClass().getSimpleName());

    // Here, JDK8 and JDK9 + behave differently. The former will report an ArrayStoreException exception, while the latter will not.
    array[0] = new Object();
}

The execution of JDK8 is shown in the following figure:
The execution of JDK13 is shown in the following figure:
In JDK8, the returned array is actually an Integer [] array. If we set the Object object into it, we will certainly report an error. How to fix it? Let's see JDK-6260652 The last paragraph of.

③ #ArrayList()

The parameterless construction method #ArrayList() construction method is also the construction method we use most. The code is as follows:

// ArrayList.java

/**
 * Default initialization capacity
 *
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array object for {@ link #ArrayList()} constructor.
 *
 * By using this static variable, it is distinguished from {@ link #EMPTY_ELEMENTDATA} when adding an element for the first time.
 *
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 * Shared empty array instances for empty instances of default size.
 * We compare it with EMPTY_ELEMENTDATA is distinguished so that you know how much to inflate when adding the first element.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

When we learn ArrayList, we have been instilled with a concept. When the initialization capacity is not set, the default size of ArrayList is 10. But here, we can see that it is initialized to defaultcapability_ EMPTY_ Elementdata is an empty array. Why? In consideration of memory saving, ArrayList objects are only created in some usage scenarios and are not actually used. Therefore, ArrayList is optimized to be an empty array, and it is really initialized to an array with a capacity of 10 when adding elements for the first time.
So why is defaultcapability declared separately_ EMPTY_ELEMENTDATA is an empty array instead of using empty directly_ What about elementdata? In the following, we will see the default capability_ EMPTY_ELEMENTDATA is expanded to 10 for the first time, while EMPTY_ELEMENTDATA is expanded by 1.5x, starting from 0 instead of 10. 😈 Hey, hey, the starting point is different.

5. Add a single element

#Add (E) method to sequentially add individual elements to the array. The code is as follows:

// ArrayList.java

@Override
public boolean add(E e) {
    // <1> Increase the number of array modifications
    modCount++;
    // Add element
    add(e, elementData, size);
    // Return to add successfully
    return true;
}

private void add(E e, Object[] elementData, int s) {
    // <2> If the capacity is insufficient, expand it
    if (s == elementData.length)
        elementData = grow();
    // <3> Set to end
    elementData[s] = e;
    // <4> Quantity and size plus one
    size = s + 1;
}

<1> At, increase the number of array modifications modCount. On the parent class AbstractList, the modCount attribute is defined to record the number of array modifications.
<2> If the position where the element is added exceeds the end (the array subscript starts from 0, and the array size is 1 larger than the maximum subscript), it indicates that the capacity of the array is insufficient and needs to be expanded, then you need to call #grow() method to expand the capacity.
<3> At, set to the end.
<4> Place, quantity and size plus one.

In terms of the overall process, regardless of the capacity expansion function, it is the same as adding elements to the [] array.

After understanding this method, take a look at the #add(int index, E element) method and insert a single element to the specified position. The code is as follows:

// ArrayList.java

public void add(int index, E element) {
    // Check whether the position is within the range of the array
    rangeCheckForAdd(index);
    // Increase the number of array modifications
    modCount++;
    // If the array size is not enough, expand it
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    // Move the element starting at index + 1 back
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    // Set to the specified location
    elementData[index] = element;
    // Array size plus one
    size = s + 1;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

6. Array expansion

#grow() method, expand the array and return it. In the whole expansion process, first create a new and larger array, which is generally 1.5 times the size (why is it general? We will see some small details later), then copy the original array to the new array, and finally return the new array. The code is as follows:

// ArrayList.java

private Object[] grow() {
    // <1>
    return grow(size + 1);
}

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // <2> If the original capacity is greater than 0 or the array is not defaultcapability_ EMPTY_ When elementdata, calculate the size of the new array and create expansion
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity >> 1           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    // <3> If it is defaultcapability_ EMPTY_ Elementdata array, you can directly create a new array.
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

<1> At, call #grow(int minCapacity) method, and it is required to be at least 1 larger than the original after capacity expansion. Because it is the minimum expansion requirement, it is actually allowed to be larger than it.
<2> If the original capacity is greater than 0, or the array is not defaultcapability_ EMPTY_ When elementdata, calculate the new array size and create expansion.
- ArraysSupport#newLength(int oldLength, int minGrowth, int prefGrowth) method to calculate the new array size. In short, the result is math Max (minGrowth, prefGrowth) + oldlength, whichever is greater according to minGrowth and prefGrowth.
- In general, from oldcapacity > > 1, it is 1.5 times the capacity expansion. But there are two special cases:
  
  1) When the initialization array requires a size of 0, when 0 > > 1 (> > 1 is a right shift operation, equivalent to dividing by 2) or 0, the 1 passed in by minCapacity is used.
  
  2) In the following, we will see that multiple elements are added. At this time, the incoming minCapacity is no longer only increased by 1, but expanded to the elementData array. Just a few elements can be added, and the number may exceed the capacity of the current ArrayList by 0.5 times.
<3> If it is defaultcapability_ EMPTY_ELEMENTDATA array, you can directly create a new array. Think about it. If the nonparametric construction method uses empty_ This effect cannot be achieved with elementdata.

Since there is an array capacity expansion method, is there a capacity reduction method? In the #trimToSize() method, a new array of just enough size is created and the original array is copied into it. The code is as follows:

// ArrayList.java

public void trimToSize() {
    // Increase the number of modifications
    modCount++;
    // If there is extra space, shrink the volume
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA // When the size is 0, empty is used directly_ ELEMENTDATA
          : Arrays.copyOf(elementData, size); // If the size is greater than 0, create a new array with size and copy the original array into it.
    }
}

At the same time, provide #ensureCapacity(int minCapacity) method to ensure that the elementData array has at least minCapacity. The code is as follows:

// ArrayList.java

public void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length // If minCapacity is greater than the capacity of the array
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) { 
        // If elementData is defaultcapability_ EMPTY_ When elementData,
        // The minimum minCapacity capacity required is greater than default_ Capability, because the actual capacity is DEFAULT_CAPACITY . 
        // Number of array modifications plus one
        modCount++;
        // Capacity expansion
        grow(minCapacity);
    }
}

Relatively simple, we can understand this method as active capacity expansion.

7. Add multiple elements

#addAll(Collection c) method to batch add multiple elements. When we clearly know that multiple elements will be added, we recommend using this method instead of adding a single element to avoid multiple expansion. The code is as follows:

// ArrayList.java

public boolean addAll(Collection<? extends E> c) {
    // Convert to a array
    Object[] a = c.toArray();
    // Increase the number of modifications
    modCount++;
    // If the a array size is 0, the ArrayList array returned is unchanged
    int numNew = a.length;
    if (numNew == 0)
        return false;
    // <1> If the remaining space of elementData is not enough, expand the capacity. The size of the expansion is required. As for the a array that can be installed.
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);
    // <2> Copy a to elementData starting from s
    System.arraycopy(a, 0, elementData, s, numNew);
    // Array size plus numNew
    size = s + numNew;
    return true;
}

<1> If the remaining space of elementData is insufficient, the capacity will be expanded. The size of the expansion is required. As for the a array that can be installed. Of course, in the section "6. Array expansion", we have seen that if the required expansion space is too small, the expansion will be 1.5 times.
<2> At, copy a to the starting position of elementData from s.

Generally speaking, it is the batch version of #add (E) method. As we said at the beginning of this section, the advantage is to avoid multiple capacity expansion.

After understanding this method, take a look at the #addAll(int index, Collection c) method and insert multiple elements from the specified position. The code is as follows:

// ArrayList.java

public boolean addAll(int index, Collection<? extends E> c) {
    // Check whether the position is within the range of the array
    rangeCheckForAdd(index);

    // Convert to a array
    Object[] a = c.toArray();
    // Increase the number of array modifications
    modCount++;
    // If the a array size is 0, the ArrayList array returned is unchanged
    int numNew = a.length;
    if (numNew == 0)
        return false;
    // If the remaining space of elementData is not enough, expand the capacity. The size of the expansion is required. As for the a array that can be installed.
    Object[] elementData;
    final int s;
    if (numNew > (elementData = this.elementData).length - (s = size))
        elementData = grow(s + numNew);

    // [difference point] if the starting position of index has been occupied, move them back
    int numMoved = s - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index,
                         elementData, index + numNew,
                         numMoved);

    // Copy a to elementData starting from s
    System.arraycopy(a, 0, elementData, index, numNew);
    // Array size plus numNew
    size = s + numNew;
    return true;
}

Focus on [differences].

8. Remove individual elements

#remove(int index) method to remove the element at the specified position and return the original element at that position. The code is as follows:

// ArrayList.java

public E remove(int index) {
    // Verify that the index does not exceed size
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    // Record the original value of this position
    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    // <10> Quick remove
    fastRemove(es, index);

    // Returns the original value of the location
    return oldValue;
}

The key point is to call #fastRemove(Object[] es, int i) method at < x > to remove quickly. The code is as follows

// ArrayList.java

private void fastRemove(Object[] es, int i) {
    // Increase the number of array modifications
    modCount++;
    // <Y> If i does not remove the last element, move the array at i + 1 forward
    final int newSize;
    if ((newSize = size - 1) > i) // -The reason for 1 is that size starts from 1 and the array subscript starts from 0.
        System.arraycopy(es, i + 1, es, i, newSize - i);
    // Set the new end to null to help GC
    es[size = newSize] = null;
}

<Y> It looks complex. It's easy to understand according to "if i doesn't remove the last element, move the array at i + 1 forward".

#The remove(Object o) method removes the first element with O and returns whether to remove it to. The code is as follows:

// ArrayList.java

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    // <Z> Find the first location with o
    int i = 0;
    found: {
        if (o == null) { // o is null
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else { // o non null cases
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        // If not found, return false
        return false;
    }
    // Quick remove
    fastRemove(es, i);
    // Found, return true
    return true;
}

It's similar to #remove(int index), that is, at < z >, change to get the first position with o, and then call the #fastRemove(Object[] es, int i) method to remove it quickly.

9. Remove multiple elements

Let's first look at #removeRange(int fromIndex, int toIndex) method. Remove multiple elements of [fromIndex, toIndex) in batch. Note that toIndex elements are not included. The code is as follows:

// ArrayList.java

protected void removeRange(int fromIndex, int toIndex) {
    // The range is incorrect. An IndexOutOfBoundsException exception is thrown
    if (fromIndex > toIndex) {
        throw new IndexOutOfBoundsException(
                outOfBoundsMsg(fromIndex, toIndex));
    }
    // Increase the number of array modifications
    modCount++;
    // <10> Remove multiple elements of [fromindex, toindex])
    shiftTailOverGap(elementData, fromIndex, toIndex);
}

private static String outOfBoundsMsg(int fromIndex, int toIndex) {
    return "From Index: " + fromIndex + " > To Index: " + toIndex;
}

<10> At, call #shifttailoverap (object [] es, int lo, int HI) method to remove multiple elements of [fromindex, toindex]. The code is as follows:
```
// ArrayList.java

private void shiftTailOverGap(Object[] es, int lo, int hi) {
    // Move the es element from the hi position to the lo position.
    System.arraycopy(es, hi, es, lo, size - hi);
    // Empty the element from [size - hi + lo, size) because it has been moved to the front.
    for (int to = size, i = (size -= hi - lo); i < to; i++)
        es[i] = null;
}
```
- The same routine as #fastRemove(Object[] es, int i) method, move first and then set null.
- One thing to note is that ArrayList particularly likes to write multiple lines of code into one line. Therefore, you may have doubts. It seems that the size of the array has not been modified here? The answer is i = (size -= hi - lo), which is too concise to understand.

#The removeAll(Collection c) method removes the specified multiple elements in batch. The implementation logic is relatively simple, but it seems to be around. Simply put, the array (elementData) is traversed in r order through two variables w (write position) and R (read position). If it does not exist in the specified multiple elements, it is written to the w position of elementData, and then the w position + 1 jumps to the next write position. In this way, the implementation writes the nonexistent elementData overwrite to the w position. It may be a little windy to understand. Of course, it will be a little windy to look at the code. Hey hey. The code is as follows:

// ArrayList.java

public boolean removeAll(Collection<?> c) {
    return batchRemove(c, false, 0, size);
}

Call #batchremove (collection C, Boolean complex, final int from, final int end) method to remove multiple specified elements in batch. The code is as follows:
```
// ArrayList.java

boolean batchRemove(Collection<?> c, boolean complement, final int from, final int end) {
    // Check that c is not null.
    Objects.requireNonNull(c);
    final Object[] es = elementData;
    int r;
    // Optimize for initial run of survivors
    // <1> Optimize, traverse the elementData array in sequence, find the first one that does not conform to the complexity, and then end the traversal.
    for (r = from;; r++) {
        // < 1.1 > after traversing to the end, if there is no unqualified, it will directly return false.
        if (r == end)
            return false;
        // < 1.2 > if the inclusion result does not conform to the complexity, it ends
        if (c.contains(es[r]) != complement)
            break;
    }
    // <2> Set the start write w to r. note that it is not r + +.
    // After R + +, it is used to read the element of the next position. Because we have es[r] failed to meet the conditions through the optimization cycle on.
    int w = r++;
    try {
        // <3> Continue to traverse the elementData array. If the conditions are met, remove it
        for (Object e; r < end; r++)
            if (c.contains(e = es[r]) == complement) // Judge whether it meets the conditions
                es[w++] = e; // The method of removal is to write the current value e to the w position, and then w jumps to the next position.
    } catch (Throwable ex) {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        // <4> If an exception occurs in the contains method, the data of es from r is written to the position where es starts from w
        System.arraycopy(es, r, es, w, end - r);
        w += end - r;
        // Continue throwing exceptions
        throw ex;
    } finally { // <5>
        // Increase the number of array modifications
        modCount += end - w;
        // Assign the position of array [w, end) to null.
        shiftTailOverGap(es, w, end);
    }
    return true;
}
```
- Don't panic. Let's look at the logic of each piece first. Then, fat friends debug it by themselves and understand it properly.
- The "complement" parameter translates to "complement". How to understand? Indicates whether to keep the elementData element if it is in the c set.
  - If the complexity is false, it means that it is not retained in the collection, which is obviously in line with #removeAll(Collection c) method's intention to remove.
  - If the completion is true, it means that it is exposed in the collection, which is in line with the intention of the #retainAll(Collection c) method to require intersection.
- <1> First of all, we need to know that this is a purpose based on Optimize optimization. We want to judge whether none of elementData conforms to c first, so there is no need to execute the corresponding removal logic. However, we hope to avoid repeated traversal, so we have such a piece of logic. In general, the purpose of this logic is to Optimize and sequentially traverse the elementData array, find the first one that does not conform to the complexity, and then end the traversal.
  - < 1.1 >, traverse to the end, and if there is no unqualified, return false directly. In other words, Ya Gen does not need the logic of removal.
  - At < 1.2 >, if the inclusion result does not comply with the complexity, end the cycle. It may be a little difficult to understand. Let's give an example. If elementData is [1, 2, 3, 1] and c is [2], then when traversing the 0th element 1, c. contains (ES [R])= complement => false != False does not match, so continue caching; Then, when traversing the first element 2, c. contains (ES [R])= complement => true != False matches, so the loop ends. At this point, we find the location of the first element to be removed. Of course, removal is not performed here. Let's move on. 😈 Calm down~
- <2> At, set the start writing w to R. note that it is not R + +. In this way, we will write the elementData array from W. At this time, r also jumps to the next position, so we can indirectly find that the element at W position has been "skipped".
- <3> Continue to traverse the elementData array. If the conditions are met, remove it. It may be a little difficult to understand. Let's continue with the above example. When traversing the second element 3, C. contains (ES [R]) = = complexity = > false = = false conforms, so write 3 to the w position and W points to the next position; When traversing the third element 1, C. contains (ES [R]) = = complexity = > true = = false does not match, so no operation is performed.
- <4> If an exception occurs in the contains method, the data of es from r is written to the position where es starts from w. In this way, we can ensure that the remaining elements that we haven't traversed can be moved to the position starting from w, so as to avoid some more elements.
- <5> Is it familiar to assign the position of array [w, end) to null.
- In the same sentence, if you feel around and debug more, you can draw a point diagram by hand to assist in understanding.

#retainAll(Collection c) method to find the intersection of the elementData array and the specified multiple elements. Simply put, just as #removeAll(Collection c) is the opposite, remove elements that are not in c. The code is as follows:

// ArrayList.java

public boolean retainAll(Collection<?> c) {
    return batchRemove(c, true, 0, size);
}

10. Find a single element

#indexOf(Object o) method to find the position of the first specified element. The code is as follows:

// ArrayList.java

public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    // o is null
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    // o non null cases
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    // Cannot find, return - 1
    return -1;
}

The #contains(Object o) method is implemented based on this method. The code is as follows:

// ArrayList.java

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

Sometimes we need to find the position of the last specified element, so we use the #lastIndexOf(Object o) method. The code is as follows:

// ArrayList.java

public int lastIndexOf(Object o) {
    return lastIndexOfRange(o, 0, size);
}

int lastIndexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    // o is null
    if (o == null) {
        for (int i = end - 1; i >= start; i--) { // Reverse order
            if (es[i] == null) {
                return i;
            }
        }
    // o non null cases
    } else {
        for (int i = end - 1; i >= start; i--) { // Reverse order
            if (o.equals(es[i])) {
                return i;
            }
        }
    }

    // Cannot find, return - 1
    return -1;
}

11. Get the element at the specified position

#get(int index) method to obtain the element at the specified position. The code is as follows:

// ArrayList.java

public E get(int index) {
    // Verify that the index does not exceed size
    Objects.checkIndex(index, size);
    // Get the element of index position
    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}

Random access to the elements at the index location, with a time complexity of O(1).

12. Set the element of the specified position

#set(int index, E element) method to set the element at the specified position. The code is as follows:

// ArrayList.java

public E set(int index, E element) {
    // Verify that the index does not exceed size
    Objects.checkIndex(index, size);
    // Get the original element of index position
    E oldValue = elementData(index);
    // Change the index position to a new element
    elementData[index] = element;
    // Returns the original element of the index position
    return oldValue;
}

13. Convert to array

#toArray() method to convert ArrayList into [] array. The code is as follows:

// ArrayList.java

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

// Arrays.java

public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

Note that the type returned is Object [].

In the actual scenario, we may want to specify the array of T generic type, so we need to use the #toArray(T[] a) method. The code is as follows:

// ArrayList.java

public <T> T[] toArray(T[] a) {
    // <1> If the passed in array is smaller than size, a new array will be copied directly and returned
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    // <2> Copy elementData to a
    System.arraycopy(elementData, 0, a, 0, size);
    // < 2.1 > if the passed in array is larger than the size, the size will be assigned null
    if (a.length > size)
        a[size] = null;
    // < 2.2 > return a
    return a;
}

It can be divided into two cases according to whether the passed in a array is large enough.
<1> If the passed in array is smaller than size, a new array will be copied directly and returned. Normally, we don't do that.
<2> At, copy elementData to a.
- At < 2.1 >, if the passed in array is larger than the size, the size position is assigned null. Well, I'm a little confused about the purpose of this.
- At < 2.2 >, return the incoming a. Very stable.
Considering that a new array may be returned at < 1 >, even if < 2 > returns an array of a, it is best to use a = list toArray(a) .

14. Hash value

#hashCode() method to find the hash value of ArrayList. The code is as follows:

// ArrayList.java

public int hashCode() {
    // Gets the current number of array modifications
    int expectedModCount = modCount;
    // DP Hash 
    int hash = hashCodeRange(0, size);
    // If the modification times change, a ConcurrentModificationException is thrown
    checkForComodification(expectedModCount);
    return hash;
}

int hashCodeRange(int from, int to) {
    final Object[] es = elementData;
    // If to exceeds the size, a ConcurrentModificationException is thrown
    if (to > es.length) {
        throw new ConcurrentModificationException();
    }
    // Traverse each element, * 31 hash.
    int hashCode = 1;
    for (int i = from; i < to; i++) {
        Object e = es[i];
        hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode());
    }
    return hashCode;
}

15. Judge equality

#equals(Object o) method to judge whether it is equal. The code is as follows:

// ArrayList.java

public boolean equals(Object o) {
    // If it's self, return equality directly
    if (o == this) {
        return true;
    }

    // If it is not a List type, it is not equal directly
    if (!(o instanceof List)) {
        return false;
    }

    // Gets the current number of array modifications
    final int expectedModCount = modCount;
    // ArrayList can be subclassed and given arbitrary behavior, but we can
    // still deal with the common case where o is ArrayList precisely
    // <10> Call different comparison methods according to different types. The main consideration is that ArrayList can directly use its elementData attribute, which has better performance.
    boolean equal = (o.getClass() == ArrayList.class)
        ? equalsArrayList((ArrayList<?>) o)
        : equalsRange((List<?>) o, 0, size);

    // If the modification times change, a ConcurrentModificationException is thrown
    checkForComodification(expectedModCount);
    return equal;
}

What may be puzzling at first glance is why two different methods are called to compare according to whether the type is ArrayList or not? Because of the ordinary List, we can only use Iterator to iterate. Compared with the elementData attribute traversal of ArrayList, the performance will be slightly lower. 😈 There are details everywhere.

The codes of these two methods are as follows, and detailed comments have been added. The code is as follows:

// ArrayList.java

boolean equalsRange(List<?> other, int from, int to) {
    // If the size of to is larger than es, it indicates a change and throws a ConcurrentModificationException
    final Object[] es = elementData;
    if (to > es.length) {
        throw new ConcurrentModificationException();
    }
    // Traverse other through iterators, and then compare elements one by one
    var oit = other.iterator();
    for (; from < to; from++) {
        // If oit does not have a next one, or the elements are not equal, false is returned for mismatch
        if (!oit.hasNext() || !Objects.equals(es[from], oit.next())) {
            return false;
        }
    }
    // Whether the traversal is completed through oit. Achieve the effect of equal size.
    return !oit.hasNext();
}

private boolean equalsArrayList(ArrayList<?> other) {
    // Get the modification times of other array
    final int otherModCount = other.modCount;
    final int s = size;
    boolean equal;
    // Determine whether the array size is equal
    if (equal = (s == other.size)) {
        final Object[] otherEs = other.elementData;
        final Object[] es = elementData;
        // If s is greater than the length of es or others, it indicates a change, and a ConcurrentModificationException is thrown
        if (s > es.length || s > otherEs.length) {
            throw new ConcurrentModificationException();
        }
        // Traverse and compare whether each element is equal one by one
        for (int i = 0; i < s; i++) {
            if (!Objects.equals(es[i], otherEs[i])) {
                equal = false;
                break; // If not, break
            }
        }
    }
    // If the number of other modifications changes, a ConcurrentModificationException is thrown
    other.checkForComodification(otherModCount);
    return equal;
}

16. Empty array

#clear() method, empty the array. The code is as follows:

// ArrayList.java

public void clear() {
    // Gets the current number of array modifications
    modCount++;
    // Traverse the array and set it to null in reverse order
    final Object[] es = elementData;
    for (int to = size, i = size = 0; i < to; i++)
        es[i] = null;
}

17. Serialize array

#writeObject(java.io.ObjectOutputStream s) method to realize the serialization of ArrayList. The code is as follows:

// ArrayList.java

@java.io.Serial
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out element count, and any hidden stuff
    // Gets the current number of array modifications
    int expectedModCount = modCount;

    // <1> Write non static attribute and non transient attribute
    s.defaultWriteObject();

    // Write out size as capacity for behavioral compatibility with clone()
    // <2> Write size, mainly for compatibility with the clone method
    s.writeInt(size);

    // Write out all elements in the proper order.
    // <3> Write the elements of the elementData array one by one
    for (int i = 0; i < size; i++) {
        s.writeObject(elementData[i]);
    }

    // If the number of other modifications changes, a ConcurrentModificationException is thrown
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

<1> Call ObjectOutputStream#defaultWriteObject() method to write non static and non transient attributes. Some fat friends may not know about Java serialization. You can have a look Serializable principle article.
<2> At, write size, mainly for compatibility with the clone method. But it's strange that size has been written at < 1 >, why is there such a thing here? All kinds of search data, only see for the time being Source code analysis: is it unnecessary to implement the writeobject method of ArrayList There is a discussion.
<3> Write the array of elementData elements one by one. Let's go back to the definition of elementData, which is a transient modified attribute. Why? Because the elementData array is not necessarily full, it may be reserved during capacity expansion. If it is serialized directly, there will be a lot of space waste. Therefore, only the elements from [0, size) are serialized to reduce the occupation of space.

18. Deserialize array

#The readObject(java.io.ObjectInputStream s) method deserializes the array. The code is as follows:

// ArrayList.java

@java.io.Serial
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {

    // Read in size, and any hidden stuff
    // Read non static attribute and non transient attribute
    s.defaultReadObject();

    // Read in capacity
    // Read size, but ignore it
    s.readInt(); // ignored

    if (size > 0) {
        // like clone(), allocate array based upon size not capacity
        SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size); // I don't know what to do, ha ha ha.
        // Create elements array
        Object[] elements = new Object[size];

        // Read in all elements in the proper order.
        // Read one by one
        for (int i = 0; i < size; i++) {
            elements[i] = s.readObject();
        }

        // Assign to elementData
        elementData = elements;
    } else if (size == 0) {
        // If the size is 0, the empty array is used directly
        elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new java.io.InvalidObjectException("Invalid size: " + size);
    }
}

And the serialization process, just the opposite (hahaha, what else do you want to do), you can see it at a glance.

19. Cloning

#clone() method to clone the ArrayList object. The code is as follows:

// ArrayList.java

public Object clone() {
    try {
        // Call the parent class to clone
        ArrayList<?> v = (ArrayList<?>) super.clone();
        // Copy a new array
        v.elementData = Arrays.copyOf(elementData, size);
        // Set the number of array modifications to 0
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

Note that elementData is a new array copied out again. Avoid sharing with the original array.

20. Create subarray

#subList(int fromIndex, int toIndex) method to create a subarray of ArrayList. The code is as follows:

// ArrayList.java

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList<>(this, fromIndex, toIndex);
}

private static class SubList<E> extends AbstractList<E> implements RandomAccess {

    /**
     * Root ArrayList
     */
    private final ArrayList<E> root;
    /**
     *  Parent SubList
     */
    private final SubList<E> parent;
    /**
     * Starting position
     */
    private final int offset;
    /**
     * size
     */
    private int size;

    // ...  Omit code
}

In actual use, it must be noted that SubList is not a read-only array, but shares the same elementData array as the root array, which only limits the range of [fromIndex, toIndex).
The source code of this piece is not complex, so it will not be expanded here. Generally, we don't need to know its source code, hehe.

21. Create Iterator iterator

#iterator() method to create an iterator. Generally, we use iterators to traverse the implementation classes of ArrayList, LinkedList, and so on. The code is as follows:

// ArrayList.java

public Iterator<E> iterator() {
    return new Itr();
}

Create Itr iterators. Itr implementation java.util.Iterator Interface, which is the internal class of ArrayList. Although AbstractList also provides an implementation of Itr, ArrayList implements it for better performance, and there is also a comment "An optimized version of AbstractList.Itr" on its class.

Itr has three attributes, as follows:

// ArrayList.java#Itr

/**
 * The location of the next access element, starting with the subscript 0.
 */
int cursor;       // index of next element to return
/**
 * The location of the last access element.
 *
 * 1. Initialize to - 1, indicating that there is no last accessed element
 * 2. When traversing to the next element, lastRet will point to the current element and cursor will point to the next element. In this way, if we want to implement the remove method and remove the current element, we can implement it.
 * 3. When removing an element, set it to - 1, which means that the last accessed element does not exist and is removed.
 */
int lastRet = -1; // index of last element returned; -1 if no such
/**
 * The number of times the array was modified when the iterator was created.
 *
 * During the iteration, if the array changes, a ConcurrentModificationException will be thrown.
 */
int expectedModCount = modCount;

// prevent creating a synthetic constructor
Itr() {}

For each attribute, see the comments for yourself.

Next, let's take a look at the four implementation methods of Itr for Iterator.

#hasNext() method to determine whether the iteration can continue. The code is as follows:

// ArrayList.java#Itr

public boolean hasNext() {
    return cursor != size;
}

If cursor is equal to size, it indicates that it has reached the end of the array and cannot continue the iteration.

#next() method, the next element. The code is as follows:

// ArrayList.java#Itr

public E next() {
    // Verify whether the array has changed
    checkForComodification();
    // Judge if it exceeds the size range, throw NoSuchElementException exception
    int i = cursor; // <1> I record the position of the current cursor
    if (i >= size)
        throw new NoSuchElementException();
    // Judge that if the size exceeds the elementData, it indicates that it may have been modified, and throw a ConcurrentModificationException
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    // <2> Cursor points to the next position
    cursor = i + 1;
    // <3> Returns the element of the current location
    return (E) elementData[lastRet = i]; // <4> Here, lastRet will be pointed to the current location
}

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

<1> Record the position of the current cursor. Because what we are currently returning is the element that requires the cursor position.
<2> cursor points to the next position.
<3> Returns the element of the current position. At the same time, at < 4 >, lastRet will point to the current position.

#remove() method to remove the current element. The code is as follows:

// ArrayList.java#Itr

public void remove() {
    // If lastRet is less than 0, it indicates that it does not point to any element, and an IllegalStateException is thrown
    if (lastRet < 0)
        throw new IllegalStateException();
    // Verify whether the array has changed
    checkForComodification();

    try {
        // <1> Position of the element rettlas to be removed
        ArrayList.this.remove(lastRet);
        // <2> The cursor points to the lastRet position. Because it has been moved, it needs to step back
        cursor = lastRet;
        // <3> Lastret is marked as - 1 because the current element has been removed
        lastRet = -1;
        // <4> Record the number of modifications to the new array
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

<1> At, call #remove(int index) method to remove the element at lastRet position. Therefore, if the element is removed and compared with the front, the position of the back will be moved forward, that is, copied, which may consume performance.
<2> The cursor points to the lastRet position. Because it has been moved, it needs to step back.
<3> At, lastRet is marked as - 1 because the current element has been removed.
<4> Record the modification times of the new array. Because the array is modified here, if it is not modified, errors will be reported in subsequent iterations.

#The forEachRemaining(Consumer action) method consumes the remaining non iterated elements. The code is as follows:

// ArrayList.java#Itr

@Override
public void forEachRemaining(Consumer<? super E> action) {
    // action is required to be non empty
    Objects.requireNonNull(action);
    // Gets the current array size
    final int size = ArrayList.this.size;
    // Record i points to cursor
    int i = cursor;
    if (i < size) {
        // Judge that if the size exceeds the elementData size, it indicates that it may have been modified, and throw a ConcurrentModificationException
        final Object[] es = elementData;
        if (i >= es.length)
            throw new ConcurrentModificationException();
        // Process one by one
        for (; i < size && modCount == expectedModCount; i++)
            action.accept(elementAt(es, i));
        // update once at end to reduce heap write traffic
        // Update cursor and lastRet pointing
        cursor = i;
        lastRet = i - 1;
        // Verify whether the array has changed
        checkForComodification();
    }
}

It's simple. Fat friends have a look. It seems that this method is not used very often.

22. Create ListIterator iterator

You may not know the ListIterator iterator because you don't usually use it much. You can go and have a look first Iterator and ListIterator of Java collection framework . In short, ListIterator is a more powerful Iterator designed for List.

#listIterator(...) Method to create a ListIterator iterator. The code is as follows:

// ArrayList.java

public ListIterator<E> listIterator(int index) {
    rangeCheckForAdd(index);
    return new ListItr(index);
}

public ListIterator<E> listIterator() {
    return new ListItr(0);
}

Create a ListItr iterator. ListItr implementation java.util.ListIterator Interface, which is the internal class of ArrayList. Although AbstractList also provides an implementation of ListItr, ArrayList implements it by itself for better performance. There is also a comment "An optimized version of AbstractList.ListItr" on its class.

ListItr directly inherits the Itr class and has no custom properties. The code is as follows:

// ArrayList.java#ListItr

ListItr(int index) {
    super();
    cursor = index;
}

You can manually set the specified position to start the iteration.

Because the implementation code of ListItr is relatively simple, we will not look at it one by one, but directly paste the annotated code. The code is as follows:

// ArrayList.java#ListItr

/**
 * @return Is there a previous one
 */
public boolean hasPrevious() {
    return cursor != 0;
}

/**
 * @return Next position
 */
public int nextIndex() {
    return cursor;
}

/**
 * @return Previous position
 */
public int previousIndex() {
    return cursor - 1;
}

/**
 * @return Previous element
 */
@SuppressWarnings("unchecked")
public E previous() {
    // Verify whether the array has changed
    checkForComodification();
    // Judge if it is less than 0, throw NoSuchElementException exception
    int i = cursor - 1;
    if (i < 0)
        throw new NoSuchElementException();
    // Judge that if the size exceeds the elementData, it indicates that it may have been modified, and throw a ConcurrentModificationException
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    // cursor points to the previous position
    cursor = i;
    // Returns the element of the current location
    return (E) elementData[lastRet = i]; // Rettlas will point to the current location here
}

/**
 * Set current element
 *
 * @param e Set element
 */
public void set(E e) {
    // If lastRet has no direction, an IllegalStateException is thrown
    if (lastRet < 0)
        throw new IllegalStateException();
    // Verify whether the array has changed
    checkForComodification();

    try {
        // set up
        ArrayList.this.set(lastRet, e);
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

/**
 * Add current position of element
 *
 * @param e Added element
 */
public void add(E e) {
    // Verify whether the array has changed
    checkForComodification();

    try {
        // Add element to current location
        int i = cursor;
        ArrayList.this.add(i, e);
        // cursor points to the next location. Because new elements are added to the current location, it needs to be moved back
        cursor = i + 1;
        // lastRet is marked as - 1 because the current element is not accessed
        lastRet = -1;
        // Record the number of modifications to the new array
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

summary

Cough, cough, an article that is much longer than expected. In fact, there are several methods of ArrayList that have not been resolved, as follows:

#spliterator()
#removeIf(Predicate filter)
#replaceAll(UnaryOperator operator)
#sort(Comparator c)
#forEach(Consumer action)

Let's make a simple summary of ArrayList:

ArrayList is a List implementation class based on [] array implementation. It supports automatic capacity expansion of 1.5 times when the array capacity is insufficient. At the same time, it supports manual capacity expansion and manual capacity reduction.
The random access time complexity of ArrayList is O(1), and the average time complexity of finding the specified element is O(n).
The best time complexity for ArrayList to remove elements at the specified location is O(1), the worst time complexity is O(n), and the average time complexity is O(n).

The best time complexity occurs when the end is removed.
The time complexity for ArrayList to remove the specified element is O(n).

Because you need to query first, and then remove the elements at the specified position in use, no matter how you calculate, you need the time complexity of O(n).
The best time complexity of adding elements to ArrayList is O(1), the worst time complexity is O(n), and the average time complexity is O(n).

The best time complexity occurs when added at the end.

Posted by neilcooper33 on Thu, 14 Apr 2022 04:19:13 +0930

Programs Wiki