A preface

Knowledge Seeker’s current series are all based on JDK1.8 for learning analysis; This source code analysis will be every step of the analysis, when all the methods of analysis will finally make a big summary; If you don’t like the source code analysis step, as long as the reader interview the final conclusion can see the summary at the end of the article;

Inheriting the spirit of open Source, Spreading technology knowledge;

ArrayList source code analysis

2.2 Empty parameter constructor source code analysis

Debugging code

Public static void main(String[] args) {// Initialization length is 0 ArrayList list = new ArrayList(); / / breakpoint}Copy the code

When you first start calling a breakpoint, the default ArrayList initialization length is 0;

Next, enter the constructor

   public ArrayList() {// elementData is Object[] --> so Arraylist is implemented by Object array. }Copy the code

DEFAULTCAPACITY_EMPTY_ELEMENTDATA is assigned to elementData;

DEFAULTCAPACITY_EMPTY_ELEMENTDATA DEFAULTCAPACITY_EMPTY_ELEMENTDATA DEFAULTCAPACITY_EMPTY_ELEMENTDATA

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

What is elementData

// Dynamic array buffer, where ArrayList stores elements, // DEFAULT_CAPACITY is expanded when the first element is added. [] elementData; // non-private to simplify nested class accessCopy the code

And then when you debug, you go to the parent classes, and you give a class diagram to see what kind of parent classes ArrayList inherits

The real step in sequence is as follows

AbstractList –> AbstractCollection–> Object

Interesting knowledge seeker is also released in the process of analysis carried out the following line of code, which is record list size change the number of times, if the unforeseen change will throw ConcurrentModificationException; This explains why iterators can’t be used to remove a List. This is provided by the Fail-fast mechanism;

Fail fast mechanism:

Fail – fast is fast failure mechanism, which is sent on collection structure change will throw ConcurrentModificationException, for fast to test the bug to fail;

// Count the number of times the list is modified, i.e. the number of times the size is changed. Made not expecting change will throw ConcurrentModificationException protected transient int modCount = 0;Copy the code

Tip1: What happens to the List collection after the remove method is called during iteration? A: I’ve seen knowledge seeker ArrayList source series, is due to fail – fast mechanism to detect structural changes in the List throw ConcurrentModificationException anomaly; Is it due to the remove, add, set, next, previous operations that occur during the iteration of the set? Too details, too low bar, the strength of the interviewer will know your level, the boy back of the good forehead!

Tip: The underlying implementation of ArrayList is based on dynamic Object arrays

2.2 Initializing capacity source code analysis

The initialization capacity of the ArrayList is roughly the same as the initialization value, then the corresponding size of the Object array is created. If no initial value is given, an empty Object array is traversed using a member share; Otherwise, illegal parameter exceptions are thrown in other cases.

The test code

Public static void main(String[] args) {// Initialize to 0 ArrayList list = new ArrayList(5); }Copy the code

The source code

Public ArrayList(int initialCapacity) {// create an object array of a specified size if the initialCapacity is greater than 0if(initialCapacity > 0) { this.elementData = new Object[initialCapacity]; // Initialize capacity = 0, empty object array}else if(initialCapacity == 0) {private static final Object[] EMPTY_ELEMENTDATA = {}; this.elementData = EMPTY_ELEMENTDATA; }elseThrow new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the code

Tip Initialize ArrayList given a specified size of capacity returns an ArrayList of the specified size

2.3 Source code analysis of add method

The test code

Public static void main(String[] args) {// Initialize to 0 ArrayList list = new ArrayList(); list.add("a");
        System.out.println(list);
    }
Copy the code

First: Take a look at the Add source code

Public Boolean add(E E) {// Add (E E) {// add(E E) {// add(E E) {// Add (E E) {// Add (E E) {// Add (E E) {// Add (E E); // Increments modCount!! elementData[size++] = e;return true;
    }
Copy the code

So you can see that there’s a method called ensureCapacityInternal(size + 1) that does the capacity assurance, and you can just add one to the original array length from this expression; Enter to see

Private void ensureCapacityInternal(int minCapacity) {//if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = math. Max (DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); // Select the maximum value in 1 and 10 (DEFAULT_CAPACITY)} ensureExplicitCapacity(minCapacity); // this is 10}Copy the code

If, since the element added is 1, the expected capacity is 1, and when compared with the default initial capacity, the maximum value is 10; So adding an element increases the expected expansion of the ArrayList to 10

Let’s make sure that the specific expansion, the number of changes to the set is increased by one, and if the desired expansion is greater than or equal to the ArrayList length, it will be expanded again;

private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code // If the desired expansion is smaller than the element ArrayList length, the expansion will be done againif(minCapacity - elementData.length > 0) grow(minCapacity); / / expansion}Copy the code

Expand grow(minCapacity); Its internal implementation idea is also very simple, each expansion is to add 50% to the original List length; If the desired size exceeds the maximum size of the array (the maximum size of an int integer -8), the maximum size of an int integer is used. Finally, the array is copied and resized; If the allocated length exceeds MAX_ARRAY_SIZE, OutOfMemoryError will be raised. The VM usually limits this size, and in practice it may not reach MAX_ARRAY_SIZE before throwing a maximum exception, let alone the maximum int;

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; Int newCapacity = oldCapacity + (oldCapacity >> 1); //oldCapacity=0; //newCapacity=0; //newCapacity=0; //newCapacity=0; If the length is 10, it becomes 15 after expansionif(newCapacity - minCapacity < 0) newCapacity = minCapacity; // (0-10) < 0, so the new capacity is 10; Namely newCapacity = 10if(newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // If the desired size is greater than the maximum size of the array, Int is used. // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); // Array copy with capacity 10}Copy the code

hugeCapacity(minCapacity); The source code is as follows

    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

Tip: ArrayList initializes to 0, adds an element, expands to 10; When the number exceeds 10, increase the length of the array by 50% each time. The maximum length of an ArrayList is integer.max_value – 8; Finally, the arrays.copyof method is called to reassign the Object array

2.4 Set source code analysis

The test code

    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add("a");
        list.set(0,"b");
        System.out.println(list);
    }
Copy the code

Let’s start with the set method

   public E set(int index, E element) { rangeCheck(index); // index =0 ; element = b ; E oldValue = elementData(index); ElementData [index] = element; // Reassign the corresponding valuereturnoldValue; // Return object}Copy the code

The first line is to check if the ArrayList is out of bounds

  private void rangeCheck(int index) {
        if(index) > = size / / given index greater than or equal to the length of the array throw new exception IndexOutOfBoundsException (outOfBoundsMsg (index)); }Copy the code

The second line is to get the Object in the original Object array position;

  @SuppressWarnings("unchecked")
    E elementData(int index) {
        return(E) elementData[index]; // index =0 ; ElementData is an object[]}Copy the code

The third line is reassigned based on the index and returns; So oldValue is elementData[index];

Tip: The set method reassigns the value of the array position; Equivalent to an update operation; If there is no element in a given position, an exception is thrown;

2.5 Get source code analysis

The test code

    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add("a");
        list.get(0);
        System.out.println(list);
    }
Copy the code

Get method

public E get(int index) { rangeCheck(index); // Check if the array is out of boundsreturnelementData(index); // Get the object at the corresponding position of the array}Copy the code

Same as after the set method, we call elementData to get the object at the corresponding position of the array. There’s nothing weird about the GET method;

2.6 Remove source analysis

The test code

    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add("a");
        list.add("b");
        list.remove(0);
        System.out.println(list);
    }
Copy the code

Source code as follows, as a whole

public E remove(int index) { rangeCheck(index); // check if array is out of bounds modCount++; E oldValue = elementData(index); OldValue =a int numMoved = size-index - 1; // numMoved = 2-0-1 = 1; Represents the number of movesif(numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); // Copy elementData[--size] = null; // clear tolet GC doIts work. Set array length -1 to null.returnoldValue; // return the removed value}Copy the code

Here’s a quick explanation of the ArrayCopy method

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

parameter

  • SRC The array to be copied
  • SrcPos The subscript to start replication
  • Dest target array
  • DestPos Indicates the location where data is stored
  • Length Number of places

Say that don’t understand the people are still confused, let’s take a look

Public static void main(String[] args) {int[] SRC = new int[]{1,2,3,4,5}; Int [] desc = new int[]{6,7,8,9,10}; System. Arraycopy (SRC, 2, desc, 1, 2); Arrays.stream(desc).boxed().forEach(des ->{ System.out.println(des); // 6,3, 4, 9, 10}); }Copy the code

SRC = index = 2; SRC = length = 2; Put it in desc’s index = 1, and it will be overwritten that is, (3,4 will overwrite 7,8)

SRC =0; SRC =0; SRC =0; How many bits should I copy? movNum = size – index -1 = 5 – 0- 1 = 4 ; Need to copy 4 bits; SRC 2,3,4,5 overwrites 1,2,3,4; You end up with 2, 3,4,5,5; Set the last element to NULL to complete the deletion operation!! Oh, oh, oh, did you learn, knowledge seekers learned, instant high fashion, later write data structure again;

Public static void main(String[] args) {int[] SRC = new int[]{1,2,3,4,5}; Int [] desc = new int[]{1,2,3,4,5}; System. Arraycopy (SRC, 1, desc, 0, 4); Arrays.stream(desc).boxed().forEach(des ->{ System.out.println(des); / / 2,3,4,5,5}); }Copy the code

The Tip remove operation invokes the system. arrayCopy method, which copies all elements following the element to be deleted to the index of the deleted element, and sets the end node of the array to NULL

Three summary

  1. Set remove happened in the process of iteration, the add, set, next, and previous operations, will trigger fast – fail mechanism, made is not expecting change will throw ConcurrentModificationException;
  2. ArrayList is based on dynamic Object array. All arrays have similar advantages and disadvantages as ArrayList.
  3. ArrayList is initialized to 0 and expanded to 10 by adding an element. When the number exceeds 10, increase the length of the array by 50% each time. The maximum length of an ArrayList is integer.max_value – 8; An ArrayList initialized with a specified capacity returns an ArrayList of the specified size.
  4. The set method reassigns the value of the array position; Equivalent to an update operation; If there is no element in a given position, an exception is thrown;
  5. The System. Arraycopy method is called at the bottom of the remove operation, which copies all elements following the element to be deleted to the index of the deleted element, and sets the end node of the array to NULL.

Half a day passed; Knowledge seekers can fill in the source code for other methods of ArrayList;