preface

This article is the 1.8 version of ArrayList source code parsing, this article contains transient, serialVersionUID, shallow copy, reflection element creation, expansion logic, fail-fast mechanism, array translation, iterator and other content parsing.

Introduction to the

• ArrayList is an array queue, equivalent to a dynamic array. Compared to arrays in Java, its capacity can grow dynamically.

• It inherits from AbstractList and provides functions for adding, deleting, modifying, traversing, and so on.

• Unlike Vector, operations in ArrayList are not thread-safe, so it is recommended to use ArrayList only in single-thread Settings, whereas Vector or CopyOnWriteArrayList can be used in multithreaded Settings.

• RandmoAccess interface is implemented, which provides random access function. RandmoAccess is implemented by lists in Java to provide fast access to lists. In an ArrayList, we can quickly get an element object by its sequence number. This is called fast random access.

• Implements the Cloneable interface, which overwrites the clone() function and can be cloned.

• Implement the Java.io.Serializable interface, which means ArrayList supports serialization and can be serialized to transport.

  The relationship is as follows:

  Java.lang.object ↳ Java. Util. AbstractCollection < E > ↳ Java. Util. AbstractList < E > ↳ Java. Util. ArrayList < E >public class ArrayList<E> extends AbstractList<E> 
  		implements List<E>, RandomAccess.Cloneable.java.io.Serializable {}
  Copy the code

  Java assembly frame diagram is as follows:

The problem

1. Why is it ordered
2. Why is it thread unsafe
3. Why is query fast and delete and insert slow
4. Expansion logic
5. Copy the way

With the problem to begin parsing, open the source code, we start with attributes.

1. ArrayList attribute parsing

We trace the source and see the following properties

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static final long serialVersionUID = 8683452581122892189L;
Copy the code

---

1.DEFAULT_CAPACITY

This property is the default container size

2.EMPTY_ELEMENTDATA

This attribute is an array of empty element data

3.DEFAULTCAPACITY_EMPTY_ELEMENTDATA

This property is implemented as an empty array when constructing a capacity parameter

4.elementData

This property is where the actual data is stored

Note that this property is modified by the transient keyword, which indicates that a field is not part of the object’s sequentialization. When an object is sequenced, a transient variable is not serialized.

The purpose of using this modifier is to improve performance, because there is a lot of unused space in elementData, and if that space is also serialized, it’s meaningless, so we know that ArrayList is actually serialized, The implementation of serialization and deserialization is actually writeObject() and readObject(), which we will parse later.

5.size

This property is the size of the ArrayList

6.MAX_ARRAY_SIZE

This property is the maximum size

7.serialVersionUID

This property is the serialization UID, and the Java serialization mechanism verifies version consistency by determining the serialVersionUID of the class at run time. In deserialization, the Java virtual machine will compare the serialVersionUID of the passed byte stream to the local serialVersionUID of the corresponding entity class. If they are the same, they are considered to be the same entity class and can be deserialized. Otherwise, the Java virtual machine will refuse to deserialize the entity class and throw an exception.

---

After a brief description of the properties, let’s follow the idea to parse through the constructor.

2, ArrayList method parsing

1. Construction method

Trace the source to see the following code

/ / void structure
public ArrayList(a) {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }// Pass in the construction of the initial capacity
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); }}// Pass in the construction of the collection
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if((size = elementData.length) ! =0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

First, we see that ArrayList has three constructs, which we parse one by one

1.ArrayList()

An empty construct implementation, assigning the value DEFAULTCAPACITY_EMPTY_ELEMENTDATA(an empty array) to elementData.

2.ArrayList(int initialCapacity)

Implementation with initial capacity

1. If the capacity passed in is greater than zero, an array of the corresponding size is created for elementData
2. If the passed capacity is equal to zero, then elementData is assigned EMPTY_ELEMENTDATA
3. Otherwise, an exception is thrown and the capacity is invalid

At this point we find that the initialization assignment to elementData uses two different objects in the empty construct and the one passed in with an initial capacity of zero, even though both objects are empty array implementations.

The implementation of arrays.copyof () is new in 1.8. In 1.7, if the capacity is 0, the method of arrays.copyof () is called, which creates empty instances. If an application has many empty instances, it will have many empty Arrays. The EMPTY_ELEMENTDATA method of arrays.copyof () is used to create an empty array.

3.ArrayList(Collection<? extends E> c)

This method can pass a subclass of E that implements Collection and assign a value to elementData

1. Get an array of objects using the collection.toarray () method and assign it to elementData.

2. If you construct an ArrayList from another collection, you need to manually assign Size

3. The collection.toarray () method can fail, and in the case of an error, the incoming Collection is copied into elementData via the Arrays.copyof () method.

4. If the collection passed in is empty, the value EMPTY_ELEMENTDATA is assigned to elementData

   In step 3, one of the key methods is arrays.copyof (), which has many overloads. The following source code is a copyOf basic data types and a copyOf complex data types.

// Copy simple data types
public static int[] copyOf(int[] original, int newLength) {
    int[] copy = new int[newLength];
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}
// Copy complex data types
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
}

public static native void arraycopy(java.lang.Object src, int srcPos, java.lang.Object dest, int destPos, int length);
Copy the code

• Both basic and complex data type copies actually call the system.arrayCopy () method, which is implemented at the native layer. This method takes five arguments, which are resolved as follows

  • The first argument, SRC, is the array to copy
  • Second argument srcPos: the starting position in the array to be copied
  • The third argument, dest, is a copy array. A pre-created array
  • The fourth argument destPos: the starting position in the replica array
  • Fifth parameter length: the number of array elements to copy

  A shallowCopy is a pointer that points to an existing memory address. A deepCopy is a pointer that points to a new memory address. A deepCopy is a pointer that points to a new memory address. When a deep copy is used, the memory is not freed because of an error that occurs when a shallow copy is used.

  This method SRC array subscript for srcPos began to copy, always copy length element to dest array, from destPos began to join in the dest array just copy of the array. For one-dimensional arrays, this copy property value is passed so that modifying the copy does not affect the original value. If there are objects in a two-dimensional or one-dimensional array, the copy result is a one-dimensional reference variable passed to the copy of the one-dimensional array, and when you modify the copy, the original array is affected.

• Complex data types are determined based on newType

  • If it is an Object array type, the Object is created with new
  • If not, the array.newinstance () method is called to create the object by dynamic reflection, which is resolved later

  Finally, let’s summarize the difference between arrays.copyof () and system.arrayCopy ()

  Arrays.copyof () returns a new array. The new array is created inside the method

  System.arraycopy() requires a pre-created target array and does not return any value. For example, if you want the data to be operated on in the original array, you can simply use the original array as the target array.

  Arrays.copyof () actually calls system.arrayCopy ()

conclusion

This section focuses on the concept of distinguishing EMPTY_ELEMENTDATA from DEFAULTCAPACITY_EMPTY_ELEMENTDATA. It is important to understand the system.arrayCopy () method. And the concept of deep and shallow copies. Finally, you need to understand how elements are created for arrays.copyof () of complex data types.

keywords

EMPTY_ELEMENTDATA, DEFAULTCAPACITY_EMPTY_ELEMENTDATA, deep copy, shallow copy, reflection element creation

---

2. Add methods

There are three methods to add, but the key logic inside is actually two steps

1. The grow() method is eventually called if there is enough capacity
2. System.arraycopy() does the element addition

Let’s move on to source code parsing around these two key points

// Element is added directly
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
}
// Add by subscript
public void add(int index, E element) {
        if (index > size || index < 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        elementData[index] = element;
        size++;
}
// Add the collection
public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        returnnumNew ! =0;
}
// Add the collection
public boolean addAll(int index, Collection<? extends E> c) {
        if (index > size || index < 0)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        int numMoved = size - index;
        if (numMoved > 0)System.arraycopy(elementData, index, elementData, index + numNew,numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        returnnumNew ! =0;
    }
// Determine whether to expand the capacity
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
}
// Determine whether to expand the capacity
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)grow(minCapacity);
}
/ / capacity
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
}
// Large capacity
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
Copy the code

1.add(E e)

1. First, call the ensureCapacityInternal() method, passing in size+1 as an argument

   1.1 Enter the ensureCapacityInternal() method, If elementData is implemented with an empty construct (that is, equal to DEFAULTCAPACITY_EMPTY_ELEMENTDATA), take the maximum value of the parameters passed in and the default container size as the minimum container size.

   1.2 Then call the ensureExplicitCapacity() method, passing in the minimum container size we just calculated

   1.2.1 Enter ensureExplicitCapacity() and increment modCount first

   1.2.2 If the passed minimum container size -elementData size >0 (call grow() method)

   1.2.2.1 Calculate the new container size, 1.5 times the current size (calculated by displacement)

   1.2.2.2 Default container size (DEFAULT_CAPACITY) if add() is called for the first time

   1.2.2.3 If the calculated container size exceeds the maximum limit (integer.max_value – 8), perform the following operations

   1.2.2.4 If minCapacity is greater than the maximum, assign an Integer.MAX_VALUE, if not, assign a value of MAX_ARRAY_SIZE, otherwise raise an exception

   1.2.2.5 Finally, we use arrays.copyof () to copy the previous data to the new array and expand it

2. Return True when E is passed in and assigns a value to it by increasing its size

   At this point, it should be noted that the increment of modCount is to prevent the original set from being changed through the List method (non-iterator) during the iteration process, resulting in unexpected situations, and thus throwing the concurrent modification exception in advance, also known as fail-fast mechanism. Throw an exception early to terminate the operation if an error may occur. This property is not designed for multithreading and ArrayList is not suitable for multithreading.

2.add(int index, E element)

1. Like add(E E), this method will first call the ensureCapacityInternal() method, executing the same logic as described above.

2. Using system.arrayCopy (elementData, index, elementData, index + 1,size – index) to move the data from elementData index back one bit.

3. Pass the new element to the corresponding index

4. The size on the

   Note that Arraylist is a displacement implemented by system.arrayCopy (), and that this method only operates on the array passed in, not recreates it. Here we need to think about when we need to call arrays.copyof () and when we need to call system.arrayCopy ().

3.addAll(Collection<? extends E> c)

1. Use the collection.toarray () method to get an array of objects and the length of the array

2. Call ensureCapacityInternal(size + numNew) to determine whether to expand

3. Again, system.arrayCopy (a, 0, elementData, size, numNew) adds an array of objects directly to the end of elementData

4. Size Increases the length of the array to be added

5. Return True if the array of objects is greater than 0, False otherwise.

   As you can see from the reading, element addition to arrays is also done through system.arrayCopy ()

4.addAll(int index, Collection<? extends E> c)

1. First determine whether the passed subscript is valid, if not, throw an exception.

2. And addAll (Collection <? Extends E> c); extends E> c); extends E> c);

3. Shift the array length bit (c) of the elements after index from the index position by system.arrayCopy ().

4. Again, system.arrayCopy () adds the elements of array (c) to the index bit

   Again, element displacement and addition are implemented through system.arrayCopy ()

conclusion

According to the analysis, array addition should first check whether the capacity is sufficient through ensureCapacityInternal() method, if not, expand its size by 1.5 times, and the implementation of expansion is arrays.copyof (). Incrementing modCount each time you expand to prevent an exception from being thrown earlier if you make changes to element synchronization during iteration. Then, in either case, element additions and element shifts are done through system.arrayCopy (). Finally, the value of Size is increased.

The analysis shows that the final method called during capacity expansion is arrays.copyof (). According to the analysis above, this method will return a new array, which is created inside the method. In other words, every capacity expansion means re-creation, which is why the efficiency of capacity expansion will be low if the capacity expansion is required. Element displacement and increment calls to system.arrayCopy () are relatively efficient, operating only on the passed array and not repeatedly recreating it.

keywords

Capacity expansion logic, arrays.copyof (), system.arrayCopy (), fail-fast,

---

3. Delete methods

1.remove(int index)

// Delete the subscript element
public E remove(int index) {
        if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        modCount++;
        E oldValue = (E) elementData[index];
        int numMoved = size - index - 1;
        if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index,numMoved);
        elementData[--size] = null; // clear to let GC do its work
        return oldValue;
}
Copy the code

1. Verify subscript validity, if not, throw exception
2. ModCount increments, fail-fast mechanism
3. Get the corresponding element by subscript
4. System.arraycopy() is used to delete the index bit
5. Set the size-1 bit to NULL for GC collection
6. Return deleted elements

---

2.remove(Object o)

// Delete the element
public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true; }}else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true; }}return false;
}
Copy the code

1. If the deleted element is empty, the for loop takes the index of the first null element and calls the fastRemove(index) method. The same is true for non-empty elements.

2. Return true on successful deletion, False if no element is found.

   The fastRemove method is implemented as follows

   private void fastRemove(int index) {
           modCount++;
           int numMoved = size - index - 1;
           if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);
           elementData[--size] = null; // clear to let GC do its work
   }
   Copy the code

   1. ModCount increments, fail-fast mechanism
   2. System.arraycopy() is used to delete the index bit
   3. Set the size-1 bit to NULL for GC collection

   It’s basically the same logic as deleting by subscript

---

3.removeAll(Collection<? > c)

// Delete the collection
public boolean removeAll(Collection
        c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
}

private boolean batchRemove(Collection<? > c,boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r];
        } finally {
            if(r ! = size) { System.arraycopy(elementData, r,elementData, w,size - r); w += size - r; }if(w ! = size) {// clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true; }}return modified;
}
Copy the code

1. Verify that the passed collection is not empty

2. Call batchRemove (Collection <? > c, Boolean complement) method

   2.1 In the for loop, the array is shifted by r and w. If the passed c does not contain elementData[r], w is incrementing and assigned.

   For example, if the list is [0, 1, 2, 3, 4, 5, 6] and the list to delete is [2, 5], then the array changes as follows:

   r=0,w=0: [0, 1, 2, 3, 4, 5, 6] r++, w++

   r=1,w=1: [0, 1, 2, 3, 4, 5, 6] r++, w++

   R =2,w=2: [0, 1, 2, 3, 4, 5, 6] R ++, w unchanged, so that all the following elements are shifted forward one bit

   r=3,w=2: [0, 1, 3, 3, 4, 5, 6] r++, w++

   r=4,w=3: [0, 1, 3, 4, 4, 5, 6] r++, w++

   R =5,w=4: [0, 1, 3, 4, 5, 6, 6] R ++, w unchanged

   r=6,w=4: [0, 1, 3, 4, 6, 6, 6]

   2.2. We’ll leave it at that. If (w! = size) = the size)

   2.2.1 If w==size indicates that there is no element to delete, return false

   2.2.2 if w! =size indicates that there are elements that need to be deleted. Then, starting from the table bit below w, loop to elementData and assign null for GC collection. After adding w to modCount, update size to return true

   2.3 Let’s see (r! C taines (elementData[r]) is an error that is likely to occur if the loop is not complete. The handling of this branch is to add elements that are not looping to elementData after the exception.

---

conclusion

The essence of the deletion is to first locate the element index, and then call system.arrayCopy () to achieve the index bit of the element deletion. And delete the starting modCount increment.

Pass the Collection removal method removeAll(Collection<? > c) use r and w to shift elements to the left, and delete elements after w, and remember that errors may occur in this method.

All deleted element bits will be null for GC collection

The keyword

ModCount increment, array translation, Null processing GC collection

---

4, modify, obtain, empty, replace methods

1.set(int index, E element)

Change the method

public E set(int index, E element) {
    if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    E oldValue = (E) elementData[index];
    elementData[index] = element;
    return oldValue;
}
Copy the code

1. Judge whether the subscript is legal, if not, throw an exception
2. Assigns the passed Element to the Element at the corresponding subscript

---

2.get(int index)

Access method

public E get(int index) {
    if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    return (E) elementData[index];
}
Copy the code

1. Judge whether the subscript is legal, if not, throw an exception
2. Return the element by subscript

---

3.clear()

Clear the way

public void clear(a) {
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    size = 0;
}
Copy the code

1. ModCount increments, fail-fast mechanism
2. Loop assignment to Null
3. Size is assigned to 0

---

4.replaceAll(UnaryOperator operator)

Replace method

public void replaceAll(UnaryOperator<E> operator) {
    Objects.requireNonNull(operator);
    final int expectedModCount = modCount;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        elementData[i] = operator.apply((E) elementData[i]);
    }
    if(modCount ! = expectedModCount) {throw new ConcurrentModificationException();
    }
    modCount++;
}
Copy the code

5. Other methods

1.clone()

cloning

public Object clone(a) {
    try{ ArrayList<? > v = (ArrayList<? >)super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw newInternalError(e); }}Copy the code

1. The shallow copyOf elementData is made through arrays.copyof () method, and then the modCount of the created Arraylist is set to 0, and then return.

   Note that if you need deep copies, you need to implement the Clone () method for complex objects.

---

2.contains(Object o)

Does it include

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

public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
}
Copy the code

1. It’s basically the same as the remove(Object o) method, except it returns the corresponding subscript

---

3.ensureCapacity(int minCapacity)

Pre-control initialization Arraylist size

public void ensureCapacity(int minCapacity) {
    intminExpand = (elementData ! = DEFAULTCAPACITY_EMPTY_ELEMENTDATA)?0: DEFAULT_CAPACITY;
    if(minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); }}Copy the code

1. If the container size passed in is larger than the default size (or 0), it is opened as the passed parameter.

   The ensureExplicitCapacity() method is actually called, which leads us to conclude that if the arrayList is getting a large amount of data the first time, it will greatly improve performance because there will be fewer expansion steps (current capacity *1.5).

---

4.lastIndexOf(Object o)

The index of the search element that appears last

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
Copy the code

1. It’s almost the same as contains(Object o), except I –, then we end it. Returns -1 if there is no corresponding element

---

5.retainAll(Collection<? > c)

Whether two ArrayLists contain the same elements

public boolean retainAll(Collection
        c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

private boolean batchRemove(Collection<? > c,boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if(r ! = size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; }if(w ! = size) {// clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true; }}return modified;
    }
Copy the code

1. See the code familiar, and removeAll(Collection

---

6.trimToSize()

Remove elements from ArrayList that do not contain Null nodes

public void trimToSize(a) {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }}Copy the code

1. ModCount increments, fail-fast mechanism

2. If the container size of elementData is greater than the number of substantive elements, do the following

   2.1 If the number of elements is 0, assign EMPTY_ELEMENTDATA directly

   2.2 Otherwise, the actual elements are retained directly through arrays.copyof ().

---

7.toArray()

Converted to an Array

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

1. Return Arrays directly through arrays.copyof ()

---

conclusion

Clone (), ensureCapacity(int minCapacity), trimToSize(), and toArray() are all processed through Arrays. CopyOf (), which proves why query is faster and deletion and insertion is slower.

iterators

public Iterator<E> iterator(a) {
    return new Itr();
}
private class Itr implements Iterator<E> {
        protected int limit = ArrayList.this.size;
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;
        public boolean hasNext(a) {
            return cursor < limit;
        }
        public E next(a) {
            if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
            int i = cursor;
            if (i >= limit)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return(E) elementData[lastRet = i]; }}Copy the code

1. When you get an Iterator for a collection, you go to new an Itr object that implements the Iterator interface. The main focus is on the next method of the Iterator interface

   Properties:

   • Limit: Records the size value of the current collection
   • Cursor: specifies the cursor. The default value is 0
   • AstRet: The last subscript of the element returned
   • ExpectedModCount: Is the number of changes that will be added to the ArrayList contents, and will be assigned to the iterator’s expectedModCount during iterator initialization.

   Next () :

   1. During the iteration, determine whether modCount and expectedModCount are equal. If they are not, another thread has modified the Arraylist. Throw ConcurrentModificationException (thread sync)
   2. NoSuchElementException is thrown if the cursor is larger than the maximum limit.
   3. Get the array of elemenData that stores the elements in the collection, return the element with cursor+1, and assign the subscript of the returned element to lastRet

Based on the analysis, in the Arraylist, it is proven that elements need to be traversed, and that iterators should be used for thread-safety reasons if multiple threads are necessary.

The iterator, subscript (random access), and for loops that arrayList supports take the following time to iterate over each of 100,000 elements

RandomAccess: 3 ms Iterator: 8 ms For: 5 ms

It is concluded that subscript (random access) is the most efficient

---

conclusion

1. Why is it ordered
   • It’s essentially an array, only it’s not just ordered, it’s repeatable.
2. Why is it thread unsafe
   • None of the synchronized code blocks are added, deleted, modified, and checked. The only thread safety handling is actually modCount handling, fail-fast mechanism, which throws an exception if the thread is not synchronized.
   • Use iterators whenever possible when iterating over elements to prevent threads from getting out of sync
3. Why is query fast and delete and insert slow
   • It’s basically an array, and it locates the elements by the subscript, so it’s fast
   • The methods of adding, deleting, expanding, and cloning are all implemented through arrays.copyof (), which returns a new array internally. The new array is created inside the method, so it is slow
4. Expansion logic
   • 1.5 times the size of itself
   • If the data is large for the first time, call ensureCapacity(int minCapacity) to open up space to prevent multiple enlargements and improve performance
5. Copy the way
   • It is a deep copy for basic types and wrappers, and a shallow copy for reference types. You need to implement your own copy logic

For example, removeIf(Predicate<? super E> filter),replaceAll(UnaryOperator operator),sort(Comparator<? Methods such as super E> c) are not resolved, because they include Predicate, UnaryOperator, Comparator, and other constructs, which are then resolved one by one.