ArrayList source code analysis

ArrayList (ArrayList, ArrayList, ArrayList, ArrayList, ArrayList)

In the source code analysis, there must be a lot of their own understanding, this time if you can put these understanding in the form of comments written next to the code will be next time we look at the source code, give us a hint, so how to write comments on the source code?

1. Enable source tracking Settings first:

2. Re-specify the source code of the current project

Create a new directory outside the SRC directory of the current project:

Unzip the native JDK source code src.zip and place it in this directory.

Respecify the referenced source code for the current project

3. Annotate the source code

ArrayList source code analysis 2: implementation of the interface

1. Inheritance system

public class ArrayList<E> extends AbstractList<E>
 implements List<E>, RandomAccess.Cloneable.java.io.Serializable
Copy the code

The ArrayList class implements four interfaces directly: List, Cloneable, Serializable, and RandomAcess. Except List, the other three interfaces have the same similarity as empty interfaces, which appear as tag interfaces.
Let’s look at the three interfaces in action:

2. RandomAccess

package java.util;

public interface RandomAccess{}
Copy the code

1. Introduction:

RandomAccess as a symbol of RandomAccess, represents as long as the implementation of this interface, can support fast RandomAccess.

2. Usage:

The binarySearch() method in the Collections class:

Instanceof is used to determine whether the object is a class or an interface type. So according to judge whether the list implementation execution RandomAccess interface: Collections. IndexedBinarySearch (list, key); Or Collections. IteratorBinarySearch (list, key);

2.1. The Collections. IndexedBinarySearch (list, key); The source code

The List collection that implements the RandomAccess interface is iterated through with a generic for loop

private static <T>
    int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
    int low = 0;
    int high = list.size()-1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        
        // Get (mid) uses the usual for loop
        Comparable<? super T> midVal = list.get(mid);
        int cmp = midVal.compareTo(key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found
}

/**
 * Returns the element at the specified position in this list.
 *
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throwsIndexOutOfBoundsException if the index is out of range * (<tt>index &lt; 0 || index &gt; = size()</tt>) */
E get(int index);
Copy the code

2.2. The Collections. IteratorBinarySearch (list, key);

Lists that do not implement the RandomAccess interface are iterated through.

private static <T>
    int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
{
    int low = 0;
    int high = list.size()-1;
    ListIterator<? extends Comparable<? super T>> i = list.listIterator();

    while (low <= high) {
        int mid = (low + high) >>> 1;
        
        //get(i, mid); Iterators are used to traverse
        Comparable<? super T> midVal = get(i, mid);
        int cmp = midVal.compareTo(key);

        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found
}

/** * Gets the ith element from the given list by repositioning the specified * list listIterator. */
private static <T> T get(ListIterator<? extends T> i, int index) {
    T obj = null;
    int pos = i.nextIndex();
    if (pos <= index) {
        do {
            obj = i.next();
        } while (pos++ < index);
    } else {
        do {
            obj = i.previous();
        } while (--pos > index);
    }
    return obj;
}
Copy the code

3. Summary:

Arraylists are iterated faster with a for loop than iterator, and LinkedLists are iterated faster with an iterator than with a for loop.
To determine whether the List subclass is ArrayList or LinkedList, use instanceof to determine whether the List subclass implements RandomAccess interface. In this way, we can choose a better traversal mode and improve performance.

Three Cloneable.

public interface Cloneable {}Copy the code

introduce

Cloneable is also a tag decoupling. Only after the interface is implemented and the clone method in Object is overridden in the class, the clone can be successfully cloned by calling the Clone method in the class. If the interface is not implemented, Will throw CloneNotSupportedException (cloning is not supported)

Clone method in Object:
```
protected native Object clone throws CloneNotSupportedException;
Copy the code
```
usage

The clone() method in Object is empty, and there is no instanceof method to determine whether a class implements the Cloneable interface. How does the Clone () method determine whether a class implements the Cloneable interface, allowing a class to call the Clone () method successfully?

The reason is that there is a native keyword modifier in this method.

1.Native keyword simple explanation:

Native keyword functions are implemented by the operating system, Java can only call. Simply put, a native method is a Java interface that calls non-Java code.
Java is a cross-platform language, and being cross-platform comes at the expense of some low-level control. However, if you want to play the role of some underlying functions, you need some help from other languages, which is the role of Native.
Native means to tell the operating system, this is a function that you have to implement for me because I’m going to use it. So the functions of native keywords are implemented by the operating system.
The native method is useful because it effectively extends the JVM. In fact, our Java code already uses native methods, and in Sun’s Implementation of Java concurrency (multithreading) mechanisms, many of the touchpoints with the operating system use native methods, allowing Java programs to transcend the boundaries of the Java runtime. With native methods, Java programs can do any application-level task.
Each native method has an implementation body of the same name in the JVM, and the logical judgment of the native method is realized by the implementation body. In addition, this native modification method has no constraints on return type, exception control, etc.
The implementation of the Cloneable interface is determined when the implementation body in the JVM is called.

2. How does the JVM make Native methods run:

We know that when a class is first used, its bytecode is loaded into memory and only once.
At the entry to the loaded bytecode maintains a list of all the method descriptors of the class, which contain information such as where the method code is stored, its Nair arguments, the method descriptor (public), and so on.
If a method descriptor uses native, the descriptor block will have a reference to the implementation of the method (operating system implementation, JVM implementation body of the same name). The pointer.
These implementations are in some DLL files, but they are loaded by the operating system into the Address space of the Java program.
When a class with a local method is clipped, its associated DLL is not loaded, so Pointers to the method implementation are not set. These DLLS are loaded only when local methods are about to be called, which is done by calling java.system.loadLibrary().
Tip: Using native methods is overhead, and it loses many of the benefits of Java. We use local methods only if there is no alternative.

3. Shallow cloning

The shallow clone

Define a student class:

public class Student{
    private String name;
    private int age;
    private StringBuffer sex;

    //get, set, toString, etc
}
Copy the code

Define a school class and override the Clone method


public class School implements Cloneable{
    private String schoolName; // School name
    private int stuNums;	// The number of schools
    private Student stu;	// A student

    // Get, set, toString methods
    @Override
    protected School clone(a) throws CloneNotSupportedException{
        return (School)super.clone(); }}Copy the code

Write a test for the main method:

public class CloneTest {
    public static void main(String[] args) throws CloneNotSupportedException {

        Student student = new Student();
        student.setAge(18);
        student.setName("Wang");
        student.setSex(new StringBuffer("Male"));

        School school = new School();
        school.setSchoolName("Experimental primary School");
        school.setStu(student);
        school.setStuNums(100);

        System.out.println("School of hashCode."+school.hashCode()+"\n"+
                "school的student的hashCode:"+school.getStu().hashCode());

        School school2 = school.clone();
        System.out.println("school2的hashCode:"+school2.hashCode()+"\n"+
                "School2's student hashCode:"+school2.getStu().hashCode()); }}Copy the code

Console results:

Shallow clone summary:

Create a new object whose non-basic (reference) type attributes are identical to the original, pointing to the memory address of the object to which the original attributes point.
Basic type attributes such as int are reassigned to a 4 byte space during clone.

There’s an extra copy

You need to clone the Student (reference type) property when you clone school. Then you need the Student class to implement the Cloneable interface as well, overriding the clone() method.

Clone (); //1
class Student implements Cloneable{

    @Override
    protected Student clone(a) throws CloneNotSupportedException {
        return (Student)super.clone(); }}//2. Clone the school object as well as its student property
@Override
protected School clone(a) throws CloneNotSupportedException {

    School school = null;
    // The student property in the school object is the same as the student property in the original school.
    school = (School)super.clone();
    // Create a new student property by cloning the student property from school
    // If the reference attribute is Null, no cloning is required.
    if(stu ! =null){
        school.stu = stu.clone();
    }

    return school;
}
Copy the code

Console results:

Don’t say deep cloning: you’re just copying one more layer

If the clone() method is not overridden, class B will copy object A with the same object property B. The operation affects both cloned and cloned objects.
It’s like a nesting doll.

4. Deep clone:Serialized copy

Serialize the object to JSON, and then convert the JSON to the specified object. The result would be a new object cloned completely from the inside out. Unlike the cloned object, manipulating it does not affect the cloned object.
Method 1. Use the API of the third-party JAR package to achieve JSON serialization, and deserialize back

// Implement deep copy 1: serialize with fastJson
String s = JSON.toJSONString(father);
Father jFather = (Father)JSON.parseObject(s, Father.class);
Copy the code

Method 2. Java’s object input and output streams provide an implementation of this deep copy.

The premise is that the cloned object and its object attributes implement the Serializable interface.

public static <T> List<T> deepCopy(List<T> src) throws IOException, ClassNotFoundException {
        ByteArrayOutputStream byteOut = new ByteArrayOutputStream();
        ObjectOutputStream out = new ObjectOutputStream(byteOut);
        out.writeObject(src);

        ByteArrayInputStream byteIn = new ByteArrayInputStream(byteOut.toByteArray());
        ObjectInputStream in = new ObjectInputStream(byteIn);

        List<T> copy_list = (List<T>) in.readObject();
        return copy_list;
    }
Copy the code

Deep cloning summary:

A new object is also created, and other objects referenced in the property are cloned, no longer pointing to the original object address.

If the reference property is Null, the property is not cloned.

Four Serializable.

public interface Serializable {}Copy the code

1. Introduction

Serialzable is also a markup interface. A class can only serialize its objects if it implements the Serializable interface.
Serialization: The process of converting the state of an object into a format (sequence of bytes) that can hold transmission. The opposite of serialization is deserialization, which converts a stream to an object. Together, these two procedures make it easy to store and transfer object data.

2. Serialization usage: Output objects to files

Create a class that implements the serialization interface.

class Person implements Serializable {
    private String name;
    private int age;
    private String sex;

    public String getName(a) {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge(a) {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getSex(a) {
        return sex;
    }

    public void setSex(String sex) {
        this.sex = sex;
    }

    @Override
    public String toString(a) {
        return "Person{" +
                "name='" + name + '\' ' +
                ", age=" + age +
                ", sex='" + sex + '\' ' +
                '} '; }}Copy the code

Serialize to person.txt file test:

public class SerializableTest {

    public static void main(String[] args) throws IOException {
        //1. Create objects
        Person person = new Person();
        person.setAge(11);
        person.setName("Gao");
        person.setSex("Male");

        //2. Create an object output stream
        FileOutputStream fileOutputStream = new FileOutputStream("D:\\person.txt");
        ObjectOutputStream objectOutputStream = new ObjectOutputStream(fileOutputStream);

        //3. Call the method to write the object to the stream
        objectOutputStream.writeObject(person);

        //4. Close the output streamobjectOutputStream.close(); }}Copy the code

Results:

3. Serialize to file

1. First create FileOutputStream

	FileOutputStream fileOutputStream = new FileOutputStream("D:\\person.txt");
Copy the code

2. Encapsulate it into ObjectOutputStream

	ObjectOutputStream objectOutputStream = new ObjectOutputStream(fileOutputStream);
Copy the code

3. Call writeObject() to serialize the object and send it to FileOutputStream

	objectOutputStream.writeObject(person);
Copy the code

4. Close the flow resource

	objectOutputStream.close();
	fileOutputStream.close();
Copy the code

4. Some specification of Serializable

Serialization of an object is simple, requiring only that the object implements the Serializable interface. Serialized objects include basic data types, all collection classes and many other things, as well as Class objects.
Object serialization not only holds a “panorama” of the object, but also tracks all handles contained within the object and saves those objects, which in turn tracks handles contained within each object.
Use transient, static variables that will not be serialized during object serialization.
However, you will find that static member variables are serialized and then deserialized, printing out values for the class’s member variables. The reason is that the value read is the value of this variable corresponding to the method area in the current JVM.

deserialization

Code:

// Deserialize tests
public class DeSerializable {
    public static void main(String[] args) throws IOException, ClassNotFoundException{

        Person person = deSerializable();
        System.out.println(person);

    }

    private static Person deSerializable(a) throws IOException, ClassNotFoundException {
        //1. Create input stream
        FileInputStream fileInputStream = new FileInputStream("D:\\person.txt");

        //2. The input stream is encapsulated in the object operation stream
        ObjectInputStream objectInputStream = new ObjectInputStream(fileInputStream);

        //3. Call the method to read the object
        Person person = (Person)objectInputStream.readObject();

        / / 4. Close the flow
        objectInputStream.close();
        fileInputStream.close();

        returnperson; }}Copy the code

Results:

6. Deserialize conflicts

When a class is created that implements the Serializable interface, a serialization number is added to the class. When the class is modified, the serialization number of the class also changes.
Therefore, before modifying the class sequence; Deserialization will check whether the serialization number of the file is consistent with the serialization number of the class after modifying the class.
Solution:

Specifies the sequence number in the specified class:

    private static final long serialVersionUID = 123456789L;
Copy the code

In general, serial number conflicts in serialization occur as follows:

1. Suppose there is a User class that implements the Serializable interface

2. This class is compiled to form a bytecode file. Due to the serialization interface, the compiled class file carries a sequence ID that loads memory and creates objects, etc.

3. We then serialize the object to a file through the object output stream, where the serial number ID is also written to the file.

4. The most critical step: we modify the source code and recompile, at which point the sequence ID changes.

5. Read the file through deserialization, it will be compared with the sequence ID of the newly compiled bytecode file, the result is different, resulting in a conflict.

6. So as long as we ensure that the sequence ID does not change even if we modify the source code, we can write a sequence number attribute to the class, just add a fixed sequence ID, even if the source code changes, the compiled sequence ID will not change.

ArrayList source code analysis 3: properties and methods

Member variables

1. serialVersionUID

The serialization number

private static final long serialVersionUID = 8683452581122892189L;
Copy the code

2. DEFAULT_CAPACITY

Capacity is initialized by default

private static final int DEFAULT_CAPACITY = 10;
Copy the code

EMPTY_ELEMENTDATA: new ArrayList(0)

When the ArrayList constructor specifies that the ArrayList has a capacity of 0, the empty object array EMPTY_ELEMENTDATA is internally assigned to the elementData array, returning the empty array.

    private static final Object[] EMPTY_ELEMENTDATA = {};
Copy the code

4. DEFAULTCAPACITY_EMPTY_ELEMENTDATA :new ArrayList()

When the user does not specify the size of the ArrayList (the no-argument constructor is called), the class will change the size of the ArrayList
DEFAULTCAPACITY_EMPTY_ELEMENTDATA The empty object array assigned to elementData is returned. That is, when the constructor of an ArrayList does not display the array length of an ArrayList, the default object array is used internally: DEFAULTCAPACITY_EMPTY_ELEMENTDATA.

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
Copy the code

When the user adds an element for the first time, the array is expanded to an array with a default capacity of 10 (DEFAULT_CAPACITY), which is augmented via ensureCapacityInternal.
It differs from EMPTY_ELEMENTDATA in that this array is returned by default, whereas EMPTY_ELEMENTDATA is returned when the user specifies a capacity of 0.

5. elementData

An array buffer that holds data in the elements of an ArrayList, the size of which is the length of the array.
When the default constructor is called, elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA, the array is expanded to DEFAULT_CAPACITY the first time an element is added to the ArrayList.
Is the underlying data structure of an ArrayList, which is just an array of objects that hold a dozen elements and is marked transient, meaning that this field will not be serialized during serialization.

    transient Object[] elementData; 
Copy the code

5.1. Why is this attribute transient?

    transient Object[] elementData; 
Copy the code

A question:

Transient is used to indicate that a field is not part of the serialization of the object. When an object is serialized, the value of the transient variable will not be serialized. ArrayList is a serializable class, and elementData is a member of the ArrayList that stores elements.
The reason:

ElementData is a cache array whose maximum size is integer.maxvalue -8. And it usually reserves some capacity for expansion when it is insufficient, so some space may have no actual storage elements. If elementData is serialized entirely with each serialization, including no space to store elements. Deserialization also initializes a new elementData array, which initializes unused space and wastes space. So to save space, let transient modify elementData so that it will not be serialized by default. When there is a serialization requirement, ArrayList’s own methods are called to serialize elementData, and only the actual stored elements.
Serializing elementData:

When the ArrayList is serialized, it calls writeOject, writing size and elementData directly to the ObjectOutputStream.

Readject is called when deserializing, retrieving size and elementData from ObjectOutputStream, and then restoring to elementData.

/**
 * Save the state of the <tt>ArrayList</tt> instance to a stream (that
 * is, serialize it).
 *
 * @serialData The length of the array backing the <tt>ArrayList</tt>
 *             instance is emitted (int), followed by all of its elements
 *             (each an <tt>Object</tt>) in the proper order.
 */
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();
 
    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);
 
    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }
 
    if(modCount ! = expectedModCount) {throw newConcurrentModificationException(); }}Copy the code

/** * Reconstitute the ArrayList instance from a stream (that is, * deserialize it). */
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;
 
    // Read in size, and any hidden stuff
    s.defaultReadObject();
 
    // Read in capacity
    s.readInt(); // ignored
 
    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);
 
        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) { a[i] = s.readObject(); }}}Copy the code

6. size

The current number of elements in an ArrayList. Default is 0. Not the capacity, but the number of elements already stored.

    private int size;
Copy the code

7. MAX_ARRAY_SIZE

Maximum storage capacity of array buffer.
The maximum value of a Java int is integer. MAX_VALUE is 2147483647, and the maximum size of an array of objects in an ArrayList is

Integer. MAX_VALUE – 8.
Why subtract 8: The JVM stores some data in this array.

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Copy the code

8. modCount

protected transient int modCount = 0;
Copy the code

Classes that inherit from AbstractList and are not directly defined in the ArrayList class.
This member variable keeps track of the number of changes to the collection, so every time you add or remove it increases in value by 1.

2. Construction method

1. No-parameter construction

    /** * Constructs an empty list with an initial capacity of ten. * Constructs an ArrayList with an initial capacity of zero. The array buffer elementData has a length of 0 * and is expanded to the default size of 10. */ in the add method when an element is first added to it
	public ArrayList(a) {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
Copy the code

2. Parameter construction: initialCapacity

    /** * Constructs an empty list with the specified initial capacity * / Constructs an empty list with the specified initial capacity *@paramInitialCapacity The initial capacity of the list * Parameters: Initial capacity of the list *@throwsIllegalArgumentException if the specified Initial capacity * is negative * An invalid argument exception will be thrown if the specified capacity is less than 0. * /
	public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the code

3. Parameter construction: Pass in the collection

    /** * Constructs a list containing the elements of the specified * collection, In the order they are returned by the collection's * iterator. * Construct a collection containing the elements of the specified collection in the order returned by the iterator of the original collection. * *@paramC The collection whose elements are to be placed into this list * parameter: specifies the collection whose elements are to be placed into the new collection. *@throwsNullPointerException if the specified collection is null * NullPointerException if the specified collection is null * * /
	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

Analysis 1: elementData = c.toarray ();

1. Convert the incoming collection into an array and assign the value to elementData. Note that elementData is an Object[] reference, but refers to the result returned by C.toarray (), which may be of another type (a subclass of Object[]), so the elementData type may not be Object[].

    elementData = c.toArray();
Copy the code

Analysis 2: elementData.getClass()! = Object[].class

elementData.getClass() ! Class = Object[].

The list.toarray () method does not necessarily return the ArrayList<> of the Object generic. Calling arrays.aslist () to convert an array to a collection returns ArrayList, the inner class of Arrays, which is also a generic collection.

So when the generic type is String, the resulting inner class type is ArrayList:

String[] strArray = {"a"."b"."c"};
List<String> list = Arrays.asList(strArray); // ArrayList is the inner class of Arrays
Copy the code

ToArray (); list.toarray (); If you convert it to an array, you get a String[] instead of an Object[].

  String[] strArray = {"a"."b"."c"};
  List<String> list = Arrays.asList(strArray); // ArrayList is the inner class of Arrays

  Object[] array2 = list.toArray();
  System.out.println(array2.getClass());

  // Output result:
  class [Ljava.lang.String; / / String [] array
Copy the code

Analysis 3. Summary:

AsList (array) converts the list to the original type, and list.toarray () converts the list to the original type.

  String[] strArray = {"a"."b"."c"};
  List<String> list = Arrays.asList(strArray); // ArrayList is the inner class of Arrays

  Object[] array2 = list.toArray();
  System.out.println(array2.getClass());

  // Output result:
  class [Ljava.lang.String; / / String [] array
Copy the code

ArrayList ArrayList = new ArrayList(); ArrayList is a true java.util.ArrayList whose toArray returns Object[].

Analysis 4: Overall logic

Turn the incoming collection into an array, because the bottom line of an ArrayList is array storage, implemented in arrays.

 elementData = c.toArray();
Copy the code

Assign the length of the collection parameter passed to size, the number of elements in the actual ArrayList. And check if it’s 0.

(size = elementData.length) ! = 0Copy the code

If 0, an empty collection is passed in, and object[] EMPTY_ELEMENTDATA is assigned to elementData. Similar to calling the constructor new ArrayList(0) with an argument of 0, specifying that the collection has an initial length of 0.

   this.elementData = EMPTY_ELEMENTDATA
Copy the code

If it is not 0, the incoming collection has elements, and the new ArrayList collection is built to contain those elements.

3.1. Determine whether the type of the incoming collection has changed after it is converted into an array and assigned to Object[] elementData array. It may become an array of other subtypes, such as String []. The common reason is arrays.asList (array), which results in ArrayList, the inner class of Arrays.
```
if (elementData.getClass() ! = Object[].class)Copy the code
```
3.2. If elementData is not of type Object[], then we rewrite to construct a String [] that is the length of the passed collection, is of type String [], and contains the original elements of the passed collection.
```
   elementData = Arrays.copyOf(elementData, size, Object[].class);
Copy the code
```

The elementData Object [] array is now initialized.

Analysis 5. supplement

The ArrayList () call to arrays.asList () replaces assembly of numbers with collections, and returns the ArrayList inner class of Arrays instead of java.util.arrayList.
ArrayList and Java.util.ArrayList inherit From AbstractList. And the methods of the add/remove in AbstractList is the default throw UnsupportedOperationException.
But java.util.arrayList overrides these methods, whereas the ArrayList inner class of Arrays doesn’t, so ArrayList derived from asList() throws an exception by calling add/remove etc.

3. From adding elements: see the method of adding and expanding

// Test the code
ArrayList arrayList = new ArrayList();
arrayList.add("a"); // It will be expanded for the first time
arrayList.add("b"); // The second time will not be expanded
arrayList.add("c");
Copy the code

1. Default no-argument constructor: new ArrayList();

Constructs an empty list with an initial capacity of ten. */ Constructs an empty list with an initial capacity of ten
public ArrayList(a) { // Initializes the constructor by default
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

The no-argument constructor is called when the user does not specify the capacity of the ArrayList. The defaultcapacity_empty_elementData array is internally assigned to the elementData array object reference.

2. Add elements for the first time (Capacity expansion) : Add methods

// Test the code
arrayList.add("a");
Copy the code

// Add method source code
public boolean add(E e) {
    //minCapacity: the minimum length to satisfy elementData. Determine whether the capacity is sufficient, if not, expand Increments modCount!!
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}
Copy the code

1.1 Analysis: Add (E E)

Call ensureCapacityInternal(size + 1);

Size is the effective length (with several pieces of data) of the current collection (the underlying array). Size +1 represents the minimum size required for the underlying array when new elements are added. So enrecapacityInternal (size + 1); Determine whether the current array length (not valid length, but capacity) meets the minimum capacity required by elementData for this addition (current valid length size+1).

  // Determine the minimum size required for the array
  //minCapacity: the minimum length of elementData required to satisfy this addition operation
  private void ensureCapacityInternal(int minCapacity) { 
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//elementData is not an empty array
          // Set minCapacity to DEFAULT_CAPACITY=10 and the maximum value of minCapacity. 10 is returned for the first capacity expansion
          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      ensureExplicitCapacity(minCapacity);
  }
Copy the code

1.2 Analysis: enrecapacityInternal (size + 1);

Role: Confirm the minimum capacity required for elementData for this operation.
Check whether elementData is an empty array, elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA. Is the default construct used (defaultcapacity_empty_elementData is an empty array of length 0)?

  // Review the DEFAULTCAPACITY_EMPTY_ELEMENTDATA property again
  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
Copy the code

In this case, the following conditions are met: Set the default capacity and the maximum value of minCapacity to the minimum capacity.

  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
Copy the code

Call ensureExplicitCapacity (minCapacity);

1.3 ensureExplicitCapacity (minCapacity);

Effect: If the total array capacity is smaller than the required size, the expansion method is invoked.

  // If the minimum size is greater than the current array size, call grow(minCapacity).
  private void ensureExplicitCapacity(int minCapacity) {
      modCount++;

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

Obviously, the first time you insert it, the current array is an empty array of length 0, and the minimum length you need is 1, so you call the expansion method.

1.4 turns (int minCapacity)

Function: Core expansion method

// Expansion method: there is a small algorithm
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;

    // Shift it one bit to the right, divided by base 2. Add oldCapacity, so it is equivalent to expanding the current length by 1.5 times
    int newCapacity = oldCapacity + (oldCapacity >> 1);

    // If the new capacity is smaller than the minimum required capacity, assign the minimum required capacity to the new capacity
    if (newCapacity - minCapacity < 0) 
        newCapacity = minCapacity;
    // Does the length exceed the maximum value
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:
    // minCapacity is usually close to size, so this is a win
    // Copy the array to get a new array with the new length and the original elements
    elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code

Expand the ArrayList collection here.

1. Define a variable. OldCapacity equals the total capacity of the current array.

2. Define a variable newCapacity equal to 1.5 times the current capacity:

   int newCapacity = oldCapacity + (oldCapacity >> 1);
Copy the code

OldCapacity =0, newCapacity =0 after 1.5 is added. So there’s a judgment call to make

3. If the new capacity is smaller than the minimum required capacity (this situation occurs during the first add), assign the minimum required capacity to the new capacity

    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
Copy the code

4. If the new capacity exceeds the maximum storage capacity of the array buffer, call hugeCapacity(minCapacity). To determine the size of the washing capacity.

    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
Copy the code

5. Capacity expansion is complete.

Construct a new elementData array based on the existing elements and new capacity of the current elementData. Finally, copy the old array into the expanded new array.Copy the code

	elementData = Arrays.copyOf(elementData, newCapacity);
Copy the code

1.5 hugeCapacity (minCapacity);

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
Copy the code

Effect: Ensure that it is not less than 0 and does not exceed the maximum capacity. An error is reported if the value is less than 0, and integer.max_value is returned if the value is greater than 0.

3. Expansion mechanism Summary: Grow (int minCapacity)

Call ensureCapacityInternal(size+1) in the add() method to determine the minimum size of the elementData array to be added. Size +1 indicates the minimum capacity required for the element addition or the actual capacity after the element is added successfully.
The ensureCapacityInternal(minCapacity) method passes:

If (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) to determine if elementData is an empty array constructed by the default method. If yes, it means that this is the first time an element has been added to the spacetime array, and the default capacity is returned directly to minCapacity. The collection constructed by the default method, expanded to capacity 10 for the first time.
EnsureCapacityInternal calls ensureExplicitCapacity(minCapacity) to determine if the total capacity of the current array is less than the minimum capacity required for the add operation. If so, expand the array and call the expand method.

First, increment the structural change counter modCount by 1, and then determine the size of minCapacity and the total capacity of the current array. If minCapacity is larger than the total capacity of the current array, it needs to be expanded.
Grow (int minCapacity)

Parameter minCapacity indicates the minimum capacity required to ensure successful addition. Then, ignoring the minCapacity, increase the total size of the current array by 1.5 times to get newCapacity. Then compare the array capacity with minCapacity:

A: if newCapacity is less than 1.5 times minCapacity: 0, it is 0. If minCapacity is not added for the first time, specify minCapacity as the newCapacity.

B: newCapacity > minCapacity: specifies newCapacity as the newCapacity.

// minCapacity is usually close to size, so this is a win: minCapacity is usually close to size, so this is a win

C: Copy the old array to the expanded new array.

Other methods

1. Get the current set size: number of valid elements

Note: The elementData underlying the collection is wrapped, and its capacity is also wrapped, so it is not visible.

public int size(a) {
    return size;
}
Copy the code

2. Check whether the set is empty

public boolean isEmpty(a) {
	return size == 0;
}
Copy the code

3. Determine whether the element object exists in the collection

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

// Iterate through the collection to find the same elements
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

Note: AaaryList can store null elements, and the values of null and non-null elements are judged differently:

elementData[i]==null // Null element judgment: ==
o.equals(elementData[i] // Determine non-null objects: equals
Copy the code

If there are two different objects, which obviously have different address values, == false. But if they all have the same properties and contents, we want to get true, so we need to override equals in the class to compare the contents of the objects.
It is generally recommended to override hashCode alongside equals because two objects that equasl determines true may have hashCode values that are false. To avoid this, we override the hashCode method so that the two objects that Equasl evaluates to true also have hashCode evaluates to true.

Here’s an experiment: There are two objects with the same attribute value, but the list stores only one object

// Test the code
ArrayList arrayList1 = new ArrayList();

Test1 test1 = new Test1();
test1.setAge(1);
test1.setName("ttt");

Test1 test2 = new Test1();
test2.setAge(1);
test2.setName("ttt");

arrayList1.add(test1);

System.out.println(arrayList1.contains(test1));
System.out.println(arrayList1.contains(test2));
Copy the code

/ / Test1:
public class Test1 {
    
    private int age;
    private String name;
    
	/ / get/set omitted
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if(! (oinstanceof Test1)) return false;
        Test1 test1 = (Test1) o;
        return getAge() == test1.getAge() &&
                Objects.equals(getName(), test1.getName());
    }

    @Override
    public int hashCode(a) {
        returnObjects.hash(getAge(), getName()); }}Copy the code

Results:

Note: ArrayList determines whether an object element in a collection exists based on whether the object’s class overrides equals.

4. Find the same element from the tail loop, returning the subscript

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

5. Shallow copy: super.clone();

    /**
     * Returns a shallow copy of this <tt>ArrayList</tt> instance.  (The
     * elements themselves are not copied.)
     *
     * @return a clone of this <tt>ArrayList</tt> instance
     */
    public Object clone(a) {
        try{ ArrayList<? > v = (ArrayList<? >)super.clone();
            // The Object[] elementData member variable of rrayList will not be cloned; it will be cloned separately
            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

Shallow copy means:

Objects and all of their primitive members and immutable member types like String are copied, but object member variables are not assigned. So the Object[] elementData member variable of the ArrayList will not be cloned; it will be cloned separately

   v.elementData = Arrays.copyOf(elementData, size);
Copy the code

6. Set to array: no parameter

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

The returned array is “safe” because toArray() returns a new array object, so the caller is free to modify the returned array without affecting the original element values of the list itself.
This method acts as a bridge between array – and collection-based apis.

Set to array: has parameters

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}
Copy the code

ToArray (T[] a) has a parameter method that takes an array as an argument and defines the parameter type by way of the generic T. The returned array type is the caller’s generic, so you don’t need to transform it yourself. Depending on how the length of the array passed in relates to the actual length of the collection, the processing is different:
- A. The length of the array must be at least the length of the collection. Copy the array directly without generating new array objects. A [size] = null; Size is the size of the valid elements in the list. This null value allows the caller of the toArray(T[] a) method to determine that there are no elements after null.
```
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
    a[size] = null;
Copy the code
```
- B. If the array length is smaller than the collection length, a new array with the same length will be created, and the elements of the collection will be copied to the new array and the reference to the new array will be 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());
Copy the code
```

8. Location access

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}
Copy the code

Note: The modifier for this method is default: this means that the method can only be accessed under the current class and the same package.
Protected: In addition to the current class and access under the same package, there is a way for subclasses that are not under the same package to access members of the parent class

9. Returns the element at the specified position

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the code

10. Replace the specified element in the set with the specified element.

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
Copy the code

Insert element at specified position:

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

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

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

If there are elements at and after the index, move them all back one index.
The five parameters of the native method ArrayCopy:
- SRC: the array elementData to be copied
- 2. SrcPos: index to which the array to be copied starts assignment
  
  These two parameters determine the index of the element to be moved: index~size-1
- 3. Dest: Destination array, i.e. array to put data in
- DestPos: Saves data from the index of the destination array.
- 5. Length: Takes several elements from the assigned array and puts them in the target array.
  
  These two parameters determine where to place the element to be moved into the target array.

12. Deletion method:

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = 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

Determine if the array subscript is out of bounds and extract the element to be deleted. Move the element after the deleted position forward, set the value of the size position to null, size-1, and return the old value.
Move the element after the deleted position forward: assume index=4, size=10 index: 0~9
If index+1=5 ~ size-1, move the element to the position where index=4 ~ size-2. And assign null at position size-1.

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;
}

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

13. Empty elements

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

14. Add elements from the parameter collection to the collection, index the insert from index.

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;
}

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(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;
}
Copy the code

15. Delete elements in the specified range:

protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // clear to let GC do its work
    int newSize = size - (toIndex-fromIndex);
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    size = newSize;
}
Copy the code

16. Remove intersection elements from collection parameters: removeAll

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

// Method in Object
public static <T> T requireNonNull(T obj) {
    if (obj == null)
        throw new NullPointerException();
    return obj;
}

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

Analyze this method:

First determine if the incoming collection is empty
```
Objects.requireNonNull(c);
Copy the code
```

Call batchRemove(c, false);

return batchRemove(c, false);
Copy the code

BatchRemove (Collection<? > c, Boolean complement) method

//retainAll:complement=true ; removeAll:false
private boolean batchRemove(Collection<? > c,boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false; // Whether the flag set has been modified and returns the flag
    try {
        for (; r < size; r++) When complement is false, fetch all difference sets: do not delete elements
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws. It means something might have gone wrong
        if(r ! = size) {//r! =size indicates that something may have gone wrong: w indicates the number of elements to keep, and it has already been saved. So when something goes wrong, it means that the element after r has not been decided whether to keep it or not. So if something goes wrong, you keep it all.
            // Copy the subscript r of elementData to the last element (the remaining element that has not been decided whether to keep), and put w in the elementData array to w+ sie-r-1 (the following elements are reserved as all elements).
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if(w ! = size) {//w == size: indicates that all elements of elementData need to be preserved, so the elements in the set are not deleted, i.e. there is no intersection element between the original set and the parameter C
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;// when w == size, I can't get here. Modified =false indicates that the array has not been modified.}}return modified;
}
Copy the code

3.1. Several variables
```
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false; // Whether the flag set has been modified and returns the flag
Copy the code
```
a. final Object[] elementData = this.elementData;

This is a final modified reference variable. Note that final immutable means that the reference variable elementData is immutable, that is, the address value of the object to which it refers is unchanged. But the content of the object is not constrained.

b. boolean modified = false

Whether the flag collection has been modified and returns the flag.

3.2. Specific methods

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

a. c.contains(elementData[r]) == complement
```
    for (; r < size; r++) 
        if (c.contains(elementData[r]) == complement)
            elementData[w++] = elementData[r];
Copy the code
```
The batchRemove method (” batchRemove “, “batchRemove”, “batchRemove”, “batchRemove”, “batchRemove”, “batchRemove”, “batchRemove”, “batchRemove”, “batchRemove”, “batchRemove”, “batchRemove” Retain c. taines (elementData[r] elements whose result is false. Elements that exist in elementData but do not exist in C should not be deleted. Remove elements in parameter c that are also present in elementData.

ElementData [w++] = elementData[r];

And I didn’t save an element that didn’t need to be deleted, w plus 1.

b. if (r ! = size)

 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; }}Copy the code

ElementData should be iterated, r == size. So r! The = size case means that an exception may have been thrown in the for code, causing elementData not to be iterated.

ElementData not traversed: traversed to the element with subscript R, all elements before r need to be retained, elements after r have not been determined. Then, due to the error, do not delete the elements that have not been judged after r. First, copy all the elements and copy them to the end of the reserved elements.

Copy the code for the element after r:

// Take the element from r subscript of elementData, size -r, and place it in elementData starting at w.
System.arraycopy(elementData, r,
                   elementData, w,
                   size - r);
Copy the code

And the number of saved elements w: w += size-r;

c. if (w ! = size)

When w == size, it means that the number of retained elements w is equal to the total number of elements of elementData, preserving all elements of elementData. This means that there are no elements in the C collection that exist in elementData, that is, there are no deleted elements. The collection’s modification flag: modified Does not assign, does not modify, and returns it.

w ! When = size, it means that the retained element format is less than the total number of elements in elementData, so the other elements are the elements to be deleted. Set the values of these locations to NULL and set the collection’s modification flag: Modified =true; And return.
```
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;
}
Copy the code
```

17 Preserve the intersection in set parameters: retainAll

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

Note: call batchRemove(c, true); The argument passed in is true, so the for loop says:

    for (; r < size; r++) 
        if (c.contains(elementData[r]) == complement)
            elementData[w++] = elementData[r];
Copy the code

Save is the element that exists as elementData also exists in parameter C, otherwise similar to removeAll.

ArrayList iterator source code implementation

1. Iterator interface definition: java.util.Iterator

package java.util.Iterator;

public interface Iterator<E> {

    boolean hasNext(a);

    E next(a);

    default void remove(a) {
        throw new UnsupportedOperationException("remove");
    }

    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while(hasNext()) action.accept(next()); }}Copy the code

We can see that there are only four methods defined in the iterator:

A.hasnext () determines if there is a next element

B.ext () retrieves an element

C. emove() deletes elements

D.froachremaining () performs the given operation on each remaining element until all elements are processed or an action raises an exception.

2. Iterator implementation source in ArrayList

Internal class: Private class Itr implements Iterator

Iterator Iterator = arrayList2.iterator();
public Iterator<E> iterator(a) {
    return new Itr();
}

/** * An iterator optimized version of abstractlist. Itr * ArrayList * /
private class Itr implements Iterator<E> {
    
    int cursor;       // Cursor to the next element: index of next element to return
    int lastRet = -1; // Index of last element returned; // Index of last element returned; -1 if no such
    
    // The number of changes to the ArrayList. This value is increased each time the contents of the ArrayList are modified.
    int expectedModCount = modCount;

    // Determine if there is a next element: Cursor does not equal size, indicating that there is a next value
    public boolean hasNext(a) {
        returncursor ! = size; }// Get the next element
    @SuppressWarnings("unchecked")
    public E next(a) {
        // Check if the ArrayList has been modified by non-iterator methods
        checkForComodification();
        
        // Assign the current cursor to I
        int i = cursor;
        
        Size is the length of the set list
        if (i >= size)
            throw new NoSuchElementException();
        
        // The inner class accesses the external attribute: the class name.this
        Object[] elementData = ArrayList.this.elementData;
        
        //length is the length of the elementData array
        if (i >= elementData.length)
            // Why Fail Fast when cursor I >=elementData array length?
            throw new ConcurrentModificationException();
        // Cursor +1: points to the next element
        cursor = i + 1;
        
        // Returns the next element and points lastRet to the index of the most recently fetched element
        return (E) elementData[lastRet = i];
    }

    public void remove(a) {
        if (lastRet < 0)
            throw new IllegalStateException();
        // Check whether the collection version number is the same as the collection iterator version number
        checkForComodification();

        try {
            // Call the remove method of ArrayList
            ArrayList.this.remove(lastRet);
            // Note that the cursor is larger than lastRet, so this operation moves the cursor pointer back one bit
            cursor = lastRet;
            // Set the subscript of the last returned data to -1.
            lastRet = -1;
            / / reset expectedModCount avoid ConcurrentModificationException anomalies
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw newConcurrentModificationException(); }}@Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while(i ! = size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); }// update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification(a) {
        if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the code

2.1. Separate: forEachRemaining()

@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
    Objects.requireNonNull(consumer);
    final int size = ArrayList.this.size;
    int i = cursor;
    if (i >= size) {
        return;
    }
    final Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length) {
        throw new ConcurrentModificationException();
    }
    // Give all the elements in the list to the consumer.
    while(i ! = size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); }// update once at end of iteration to reduce heap write traffic
    cursor = i;
    lastRet = i - 1;
    checkForComodification();
}
Copy the code

This method is the default method in Java1.8’s new Iterator interface, and is described in the official documentation as operating on the remaining elements in the collection until the elements are complete or an exception is thrown.
So what do we know about the remainder? Take a look at this code:

ArrayList arrayList2 = new ArrayList();
arrayList2.add(3);
arrayList2.add(4);
arrayList2.add(7);
arrayList2.add(5);
arrayList2.add(6);

arrayList1.removeAll(arrayList2);

Iterator iterator = arrayList2.iterator();
int i = 0;
while (iterator.hasNext()){
    System.out.println(iterator.next());
    i++;
    if(i == 2) {break;
    }
}
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = =");

iterator.forEachRemaining(new Consumer() {
    @Override
    public void accept(Object o) { System.out.println(o); }});Copy the code

So after looking at the Itr source code, it is easy to understand the remaining elements. The remaining elements are the elements after the cursor property pointing to the next element of the inner iterator implementation of the ArrayList.

2.2 the Fail – Fast mechanism

1. ModCount is the number of modifications, which increases with each modification to the contents of the ArrayList
ModCount is designed to prevent unexpected changes to the collection during iteration through methods of the List (other than methods in the iterator), thus prematurely throwing concurrent modification exceptions. Note: “advance”, which throws an exception abort operation ahead of time in case of possible error.

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

1. The following code will throw ConcurrentModificationException:

ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
    arrayList.add(i);
}

Iterator iterator = arrayList.iterator();

while (iterator.hasNext()) {
    arrayList.remove(1);
    iterator.next();
}
Copy the code

1. Abnormal cause:
When iterating, we use iterator.next() to get the next element. Iterator.next () returns the element it points to by cursor: iterator.next()
```
int i = cursor; cursor = i+1; Return elementData[lastRet = I];Copy the code
```
If cursor = 3, return the element with index 3.

Arrayist.remove, which is called during iterator traversal, removes the element with subscript 1
```
while (iterator.hasNext()) {
    arrayList.remove(1);
    iterator.next();
}
Copy the code
```
The set result is:

Result of traversal: element 4 was traversed instead of 3, which is obviously wrong for traversal.

For this reason, the modCount is assigned to the expectedModCount during the iterator initialization to determine whether the two are equal during the iteration. If they are not equal, it means that the ArrayList has been modified, and it is likely that errors will occur when the iterator continues to operate the ArrayList. So an error in advance: throw new ConcurrentModificationException ();

When using an Iterator, you can use the Iterator’s built-in operation set, such as remove, without affecting the Iterator operation. Because he’s going to change the set and move the cursor accordingly.

public void remove(a) {
    if (lastRet < 0)
        throw new IllegalStateException();
    // Check whether the collection version number is the same as the collection iterator version number
    checkForComodification();

    try {
        // Call the remove method of ArrayList
        ArrayList.this.remove(lastRet);
        // Note that the cursor is larger than lastRet, so this operation moves the cursor pointer back one bit
        cursor = lastRet;
        // Set the subscript of the last returned data to -1.
        lastRet = -1;
        / / reset expectedModCount avoid ConcurrentModificationException anomalies
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw newConcurrentModificationException(); }}Copy the code

3. Private Class ListItr extends Itr implements ListIterator

Introduction:

ArrayList is an iterator implementation class that extends some of the functionality of Itr.

It can move in both directions, whereas normal iterators can only move in one direction.

It has the add method, which does not.

public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}

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

/** * An optimized version of AbstractList.ListItr */
private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super(a); cursor = index; }public boolean hasPrevious(a) {
        returncursor ! =0;
    }

    public int nextIndex(a) {
        return cursor;
    }

    public int previousIndex(a) {
        return cursor - 1;
    }

    @SuppressWarnings("unchecked")
    public E previous(a) {
        checkForComodification();
        int i = cursor - 1;
        if (i < 0)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i;
        return (E) elementData[lastRet = i];
    }

    public void set(E e) {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.set(lastRet, e);
        } catch (IndexOutOfBoundsException ex) {
            throw newConcurrentModificationException(); }}public void add(E e) {
        checkForComodification();

        try {
            int i = cursor;
            ArrayList.this.add(i, e);
            cursor = i + 1;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw newConcurrentModificationException(); }}}Copy the code

ArrayList source code analysis

ArrayList source code analysis

ArrayList (ArrayList, ArrayList, ArrayList, ArrayList, ArrayList)

1. Enable source tracking Settings first:

2. Re-specify the source code of the current project

3. Annotate the source code

ArrayList source code analysis 2: implementation of the interface

1. Inheritance system

2. RandomAccess

1. Introduction:

2. Usage:

2.1. The Collections. IndexedBinarySearch (list, key); The source code

2.2. The Collections. IteratorBinarySearch (list, key);

3. Summary:

Three Cloneable.

1.Native keyword simple explanation:

2. How does the JVM make Native methods run:

3. Shallow cloning

4. Deep clone:Serialized copy

Four Serializable.

1. Introduction

2. Serialization usage: Output objects to files

3. Serialize to file

4. Some specification of Serializable

deserialization

6. Deserialize conflicts

ArrayList source code analysis 3: properties and methods

Member variables

1. serialVersionUID

2. DEFAULT_CAPACITY

EMPTY_ELEMENTDATA: new ArrayList(0)

4. DEFAULTCAPACITY_EMPTY_ELEMENTDATA :new ArrayList()

5. elementData

5.1. Why is this attribute transient?

6. size

7. MAX_ARRAY_SIZE

8. modCount

2. Construction method

1. No-parameter construction

2. Parameter construction: initialCapacity

3. Parameter construction: Pass in the collection

Analysis 1: elementData = c.toarray ();

Analysis 2: elementData.getClass()! = Object[].class

Analysis 3. Summary:

Analysis 4: Overall logic

Analysis 5. supplement

3. From adding elements: see the method of adding and expanding

1. Default no-argument constructor: new ArrayList();

2. Add elements for the first time (Capacity expansion) : Add methods

1.1 Analysis: Add (E E)

1.2 Analysis: enrecapacityInternal (size + 1);

1.3 ensureExplicitCapacity (minCapacity);

1.4 turns (int minCapacity)

1.5 hugeCapacity (minCapacity);

3. Expansion mechanism Summary: Grow (int minCapacity)

Other methods

1. Get the current set size: number of valid elements

2. Check whether the set is empty

3. Determine whether the element object exists in the collection

4. Find the same element from the tail loop, returning the subscript

5. Shallow copy: super.clone();

6. Set to array: no parameter

Set to array: has parameters

8. Location access

9. Returns the element at the specified position

10. Replace the specified element in the set with the specified element.

Insert element at specified position:

12. Deletion method:

13. Empty elements

14. Add elements from the parameter collection to the collection, index the insert from index.

15. Delete elements in the specified range:

16. Remove intersection elements from collection parameters: removeAll

17 Preserve the intersection in set parameters: retainAll

ArrayList iterator source code implementation

1. Iterator interface definition: java.util.Iterator

2. Iterator implementation source in ArrayList

2.1. Separate: forEachRemaining()

2.2 the Fail – Fast mechanism

3. Private Class ListItr extends Itr implements ListIterator

Related Posts