ArrayList source Code Analysis

This post is from my personal blog

The text before

Recently in the review of Java foundation, I feel that I have learned a lot again, as a major focus of Java, before I was looking at “Java Programming Ideas” to learn, this time just with the source code to learn again, first learn is ArrayList, by the way do some summary (iterator is not relevant) :

The basic concepts of ArrayList

Source code analysis of ArrayList (Constants, constructors, common methods)

The source code for ArrayList should take at least three or four articles, which is about 1,500 lines (half of which are comments)

The body of the

Basic concepts of ArrayList

When I first learned it, I called it a Dynamic array, because it automatically changes size based on the amount of data, and its structure is based on a Dynamic array.

annotation

I right-click on ArrayList in IDEA to see the source code, and put the comments in the browser as HTML to see:

I’ll call it Resizable array to show you what it is

Here’s a summary of the entire page:

It implements the List interface, implements all the List methods, can hold all element types (including NULL), and an ArrayList is much the same as a Vector except that it is not multithreaded
The operation time of size, isEmpty, get, set, iterator and listIterator is constant, and the operation time of Add depends on the insertion position. Besides, the operation time of other operations increases linearly, which will be verified by an experiment below
Arraylist has the concept of capacity, which grows as the amount of data increases. You can also directly define the size of the container. Using the ensureCapacity operation, you can grow the required capacity at a time, improving efficiency and avoiding increasing the capacity one by one
If you are using multiple threads, when a thread changes the structure of the container, it needs to be synchronized outside the container. The official recommendation is to wrap it in a synchronized container:

List list = Collections.synchronizedList(new ArrayList(...) );Copy the code

We will skip the rest of the iterators in the comments and have the source code dedicated to analyzing iterators

Demo:

Test the running time in point 2:

Let’s calculate the running time of the add operation:

import java.util.ArrayList; import java.util.List; public class Test { public static void main(String[] args) { List<String> list = new ArrayList<>(); long startTime = 0, endTime = 0; // Insert startTime = system.currentTimemillis (); // A larger amount of data is required to calculate the timefor (int i = 0; i < 100000; i++) {
            list.add(String.valueOf(i));
        }
        endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);

        //
        startTime = System.currentTimeMillis();
        for(int i = 100000; i < 200000; i++) { list.add(String.valueOf(i)); } endTime = System.currentTimeMillis(); System.out.println(endTime - startTime); list.clear(); }}Copy the code

Starting at the position of one hundred thousand, one millisecond longer, indicates that the running time is dependent on the position of the insertion

Get operation

import java.util.ArrayList; import java.util.List; public class Test { public static void main(String[] args) { List<String> list = new ArrayList<>(); long startTime = 0, endTime = 0; String index; // Insert startTime = system.currentTimemillis ();for (int i = 0; i < 2000000; i++) {
            list.add(String.valueOf(i));
        }
        endTime = System.currentTimeMillis();
        System.out.println(Insert 2 million data time:);
        System.out.println(endTime - startTime);

        startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            index = list.get(i);
        }
        endTime = System.currentTimeMillis();
        System.out.println("Time to get first million data:");
        System.out.println(endTime - startTime);


        startTime = System.currentTimeMillis();
        for (int i = 1000000; i < 2000000; i++) {
            index = list.get(i);
        }
        endTime = System.currentTimeMillis();
        System.out.println("Time to get first million data:"); System.out.println(endTime - startTime); list.clear(); }}Copy the code

The get operation time is the same with the same amount of data

All the others are verified in a similar way, so I won’t do it

Source analysis

class

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

This class implements several interfaces:

List
RandomAccess
Cloneable
java.io.Serializable

The first one is not to say, but to say the last three, these three interfaces are empty, just to illustrate:

Fast random access is supported

You can use the object.clone () method

serializable

constant

The constant part is used in the method, directly from the source:

The default capacity is 10

    private static final int DEFAULT_CAPACITY = 10;
Copy the code

Defines an array to hold elements

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

Define an array similar to the above, as explained below

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

An unserialized array that holds elements

transient Object[] elementData;
Copy the code

The container size

private int size;
Copy the code

The constructor

There are three types of constructors:

public ArrayList(int initialCapacity) {} public ArrayList() {} public ArrayList(Collection<? extends E> c) {}

Constructor for the given capacity parameter

Use two of the constants above

Public ArrayList(int initialCapacity) {// If given a positive capacity value, the array is initialized with that valueif(initialCapacity > 0) { this.elementData = new Object[initialCapacity]; // Otherwise define an empty array}else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the code

No parameter constructor

This one is simple, just define an array of size 10 with the default size 10

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
Copy the code

Constructor with generic parameters

public ArrayList(Collection<? AbstractCollection<E> and List<E> classes elementData = c.toarray (); AbstractCollection<E> class elementData = c.toarray ();if((size = elementData.length) ! = 0) { // c.toArray might (incorrectly) notreturnObject[] (see 6260652) // This is an official bug that does not necessarily return the Object[] classif(elementData.getClass() ! ElementData = array.copyof (elementData, size, Object[].class); }else{// replace with empty array. // If the size of the container parameter passed is 0, replace with the empty array this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

Commonly used method

The first methods given here are commonly used, excluding iterators. The content of iterators needs a separate article

We’ll start with add, delete, change, and we’ll have a Demo at the end

increase

There are several ways to add elements, including end-of-add, point-add, and directly add an entire container of elements

Add at the end:

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

Add additional container elements at the end:

public boolean addAll(Collection<? Extends E> c) {// convert to array Object[] a = c.toarray (); int numNew = a.length; // ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew;returnnumNew ! = 0; }Copy the code

Fixed point add:

Here’s a way to check if an array subscript is out of bounds:

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

For exception messages, the source code looks like this:

Public void add(int index, E element) {rangeCheckForAdd(index); // Expand ensureCapacityInternal(size + 1); // Increments modCount!! System. arrayCopy (elementData, index, elementData, index + 1, size-index); // Add element elementData[index] = element; // array size plus 1 size++; }Copy the code

For system.arrayCopy (), I checked the source code:

The parameters are: 1. Original array 2. Original location 3. Target location 5. Number of elements to move

In fact, the method added above is to move elements within the same array

There is also the ability to directly add elements from other containers to the specified location

Public Boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toarray (); int numNew = a.length; EnsureCapacityInternal (size + numNew); Int numMoved = sire-index; // Increments modCount // Increments modCount // If you want to move, move backif(numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System. arrayCopy (a, 0, elementData, index, numNew); Size += numNew; // Determine if the list structure has changedreturnnumNew ! = 0; }Copy the code

delete

There are fixed-point deletes, specific element deletes, batch deletes, and empty lists. The idea is to set the value of the deleted location to NULL and let the garbage collector handle it

Fixed-point deletion:

First, we will give a method to check whether the array is out of bounds, similar to the above method:

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

Public E remove(int index) {rangeCheck(index); modCount++; E oldValue = elementData(index); Int numMoved = size-index - 1;ifArraycopy (elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear tolet GC doIts work // Returns the deleted valuereturn oldValue;
    }
Copy the code

Deleting specific elements

We need to specify a private method, which is used here:

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 tolet GC do its work
    }
Copy the code

Public Boolean remove(Object o) {// If the specified element is not found, the array does not changeif (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true; }}else{// Iterate over the number groupfor (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true; }}return false;
    }
Copy the code

Batch delete:

This method is private and implemented by two other methods, removeAll() and retainAll(), which are involved in the batch delete method’s Boolean type arguments:

Pass in a container. If complement is true, only the same elements as the container element are retained. If complement is false, the same elements are deleted

Here, the first complement is true and the second complement is false:

private boolean batchRemove(Collection<? > c, Boolean complement) {final Object[] elementData = this.elementData; Int r = 0, w = 0; // Check whether the structure has changed Boolean modified =false; Try {// traversalfor(; r < size; R++) // if the container passed in contains the same elements as the original array, the new array is assignedif (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even ifC. taines () throws. // If an exception is thrown, copy the elements after r to wif(r ! = size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } // After the filter, if there is a space behind the w position, clean it upif(w ! = size) { // clear tolet GC do its work
                for(int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; // Struct modified =true; }}return modified;
    }
Copy the code

Next is to call the batch delete method:

Delete container elements:

Public Boolean removeAll(Collection<? > c) { Objects.requireNonNull(c);return batchRemove(c, false);
    }
Copy the code

Preserve container elements:

Public Boolean retainAll(Collection<? > c) { Objects.requireNonNull(c);return batchRemove(c, true);
    }
Copy the code

Clear the list:

The removeAll() method can also clear the list, but it is less efficient, so the following is recommended:

public void clear() {
        modCount++;

        // clear to let GC doIts work // Traversal number group, set the value to NULLfor (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }
Copy the code

change

An out-of-bounds array index error may be thrown

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

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

check

An exception with an out-of-bounds array index may be thrown

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

        return elementData(index);
    }
Copy the code

The text before

The body of the

Basic concepts of ArrayList

annotation

Demo:

Source analysis

Related Posts

Quick BI spreadsheet: Beginners can form freely

[Redis prequel] A data structure that saves memory to the extreme

Side of the Day – In Java, describe a situation in which an object moves from a young generation to an old one?