preface

JDK source code parsing series of articles, are based on JDK8 analysis, although JDK14 has come out, but JDK8 I will not, I…

The class diagram

  • To achieve theRandomAccessInterface, which can be accessed randomly
  • To achieve theCloneableInterface, which can be cloned
  • To achieve theSerializableInterface, can serialize, deserialize
  • To achieve theListInterface, it isListOne of the implementation classes of
  • To achieve theCollectionInterface, it isJava Collections FrameworkOne of the members
  • To achieve the可迭代Interface, availablefor-eachThe iteration

attribute

// Serialize version UID
private static final long
        serialVersionUID = 8683452581122892189L;

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

/** * Shared empty array instances for empty instances * new ArrayList(0); * /
private static final Object[]
        EMPTY_ELEMENTDATA = {};

/** * Shared empty array instance used to provide default size instance * new ArrayList(); * /
private static final Object[]
        DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** * The size of the ArrayList is the length of the array ** non-private to simplify nested class access */
transient Object[] elementData;

/** * The number of elements in the ArrayList */
private int size;
Copy the code

Do you have a lot of question marks?

  1. Why is the empty instance default array sometimesEMPTY_ELEMENTDATA“And sometimes it isDEFAULTCAPACITY_EMPTY_ELEMENTDATA
  2. whyelementDataWant to betransientmodified
  3. whyelementDataHas not beenprivateModified? Is it as it says in the notesnon-private to simplify nested class access

So with that question, let’s move on.

A constructor

Constructor with initial capacity

/** * a constructor that takes an initial capacity argument **@paramInitialCapacity initialCapacity *@throwsIf the initial capacity is illegal, throw * IllegalArgumentException */
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
  • ifinitialCapacity > 0, create a new length isinitialCapacityAn array of
  • ifinitialCapacity == 0, use EMPTY_ELEMENTDATA
  • In other cases,initialCapacityInvalid, throw an exception

Parameterless constructor

/** * The no-argument constructor assigns elementData to * DEFAULTCAPACITY_EMPTY_ELEMENTDATA */
public ArrayList(a) {
    this.elementData =
            DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

Constructor that takes a collection parameter

/** * a constructor that takes a set argument **@paramC set, which means that the elements in the set will be placed in the list *@throwsIf the collection is empty, NullPointerException */ is thrown
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    // 如果 size != 0
    if((size = elementData.length) ! =0) {
        // c.toarray may not be correct, do not return Object[]
        // https://bugs.openjdk.java.net/browse/JDK-6260652
        if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf( elementData, size, Object[].class); }else {
        // size == 0
        // Assign EMPTY_ELEMENTDATA to elementData
        this.elementData = EMPTY_ELEMENTDATA; }}Copy the code
  • Use methods that convert collections to arrays
  • In order to preventc.toArray()Method incorrectly executed, resulting in no returnObject[], special processing
  • If the array size is equal to0, use theEMPTY_ELEMENTDATA

When does c.toarray () not return Object[]?

public static void main(String[] args) {
    List<String> list = new ArrayList<>(Arrays.asList("list"));
    // class java.util.ArrayList
    System.out.println(list.getClass());

    Object[] listArray = list.toArray();
    // class [Ljava.lang.Object;
    System.out.println(listArray.getClass());
    listArray[0] = new Object();

    System.out.println();

    List<String> asList = Arrays.asList("asList");
    // class java.util.Arrays$ArrayList
    System.out.println(asList.getClass());

    Object[] asListArray = asList.toArray();
    // class [Ljava.lang.String;
    System.out.println(asListArray.getClass());
    // java.lang.ArrayStoreException
    asListArray[0] = new Object();
}
Copy the code

We can see that through this example Java. Util. ArrayList. ToArray () method returns the Object [] there is no problem. The toArray() method of ArrayList from java.util.Arrays’s private inner class might not return Object[].

Why is that?

ArrayList toArray() ¶

public Object[] toArray() {
    // ArrayLisy defines elementData like this
    // transient Object[] elementData;
    return Arrays.copyOf(elementData, size);
}
Copy the code

Using the array.copyof () method:

public static <T> T[] copyOf(T[] original, int newLength) {
    // original.getClass() is class [ljava.lang.object
    return (T[]) copyOf(original, newLength, original.getClass());
}
Copy the code

A concrete implementation of copyOf() :

public static <T,U> T[] copyOf(U[] original, 
          int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    /** * If newType is Object[] copy array type is Object * otherwise newType is */
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}
Copy the code

We know that elementData in ArrayList is of type Object[], so the toArray() method of ArrayList must return Object[].

Java.util. Arrays’ internal ArrayList

private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess.java.io.Serializable {
        
    // An array of elements
    private final E[] a;

    ArrayList(E[] array) {
        // Assign the received array directly to a
        a = Objects.requireNonNull(array);
    }

    /** * obj if null throws an exception * if not null returns obj */
    public static <T> T requireNonNull(T obj) {
        if (obj == null)
            throw new NullPointerException();
        return obj;
    }

    @Override
    public Object[] toArray() {
        // Return the clone object of A
        returna.clone(); }}Copy the code

This is the source of arrays.aslist ()

public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}
Copy the code

The toArray() method of java.util.Arrays’ internal ArrayList returns the type of array the constructor receives.

So, in our example, we are actually returning an array of type String, and assigning the elements to type Object is an error.

Let’s move on to ArrayList…

Insert method

Adds the specified element at the end of the list

/** * adds the specified element ** to the end of the list@paramE Specifies the element * to be added@return true
 */
public boolean add(E e) {
    // Add modCount!!
    ensureCapacityInternal(size + 1); 
    elementData[size++] = e;
    return true;
}
Copy the code
  • In the parent classAbstractListUp, definedmodCountProperty to record the number of times an array has been modified.

Adds the specified element at the specified location

/** * adds the specified element at the specified location * If there is already an element at the specified location, that element and subsequent elements are moved one ** to the right@paramIndex Indicates the index * of the element to be inserted@paramElement Specifies the element to be inserted@throwsMay sell IndexOutOfBoundsException * /
public void add(int index, E element) {
    rangeCheckForAdd(index);


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

Insert other private methods of the method call

/** * Calculate the capacity */
private static int calculateCapacity(
        Object[] elementData, int minCapacity) {

    if (elementData ==
            DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(
            calculateCapacity(elementData, minCapacity)
    );
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

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

Expansion method

/** * The maximum size that an array can allocate * Some virtual machines reserve header words in an array * Attempting to allocate a larger size may result in OutOfMemoryError */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/** * Increase the capacity to be at least larger than minCapacity *@paramMinCapacity Minimum expected capacity */
private void grow(int minCapacity) {
    // Code that may overflow
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

/** * Maximum capacity Returns integer. MAX_VALUE */
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
  • Usually the new capacity is 1.5 times the original capacity
  • If the original capacity is 1.5 times ratiominCapacitySmall, so expand tominCapacity
  • In special cases, expand toInteger.MAX_VALUE

After looking at the constructors, additions, and expansions, the first question above is answered. New ArrayList() assigns elementData to DEFAULTCAPACITY_EMPTY_ELEMENTDATA, New ArrayList(0) assigns elementData to EMPTY_ELEMENTDATA, adding elements to EMPTY_ELEMENTDATA increases capacity to 1, The capacity of DEFAULTCAPACITY_EMPTY_ELEMENTDATA after capacity expansion is 10.

We can test this idea with reflection. As follows:

public static void main(String[] args) {
    printDefaultCapacityList();
    printEmptyCapacityList();
}

public static void printDefaultCapacityList(a) {
    ArrayList defaultCapacity = new ArrayList();
    System.out.println(
            "Default initialization length:" + getCapacity(defaultCapacity));

    defaultCapacity.add(1);
    System.out.println(
            Length after default add: + getCapacity(defaultCapacity));
}

public static void printEmptyCapacityList(a) {
    ArrayList emptyCapacity = new ArrayList(0);
    System.out.println(
            "Empty initializes length:" + getCapacity(emptyCapacity));

    emptyCapacity.add(1);
    System.out.println(
            "Empty add length:" + getCapacity(emptyCapacity));
}

public static int getCapacity(ArrayList
        arrayList) {
    Class<ArrayList> arrayListClass = ArrayList.class;
    try {
        // Get the elementData field
        Field field = arrayListClass.getDeclaredField("elementData");
        // Enable the access permission
        field.setAccessible(true);
        // Pass the example to GET the value of the instance field elementData
        Object[] objects = (Object[]) field.get(arrayList);
        // Returns the capacity of the current ArrayList instance
        return objects.length;
    } catch (Exception e) {
        e.printStackTrace();
        return -1; }}Copy the code

Remove method

Removes the specified subscript element method

/** * removes the element in the list at the specified subscript position ** moves all subsequent elements to the left **@paramThe specified subscript * to remove@returnReturns the removed element *@throwsThe subscript cross sell IndexOutOfBoundsException * /
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);
    // Empty the reference for GC to collect
    elementData[--size] = null;

    return oldValue;
}
Copy the code

Removes the specified element method

/** * Removes the first specified element to appear in the list * Returns true if it exists * otherwise returns false **@paramO Specifies the element */
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true; }}else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true; }}return false;
}
Copy the code

The name of the removal method and the number of parameters are the same.

Private remove method

/* * Private remove methods skip bounds checking and do not return the removed element */
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // Empty the reference for GC to collect
    elementData[--size] = null;
}
Copy the code

To find the way

Finds the location of the specified element

/** * returns the first occurrence of the specified element * if the element does not exist, returns -1 * if o ==null is treated specially */
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

Finds the element at the specified location

/** * returns the element ** at the specified position@paramIndex specifies the position of the element *@throwsThe index cross sell IndexOutOfBoundsException * /
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}
Copy the code

This method returns the element with the specified index in the elementData array directly, which is quite efficient. So the ArrayList for loop is also efficient.

Serialization method

/** * Saves the state of ArrayLisy instances to a stream */
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 all elements in order
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

    if(modCount ! = expectedModCount) {throw newConcurrentModificationException(); }}Copy the code

Deserialization method

/** * Regenerates an ArrayList */ from a stream (argument)
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();

    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

After looking at serialization, deserialization methods, we can finally answer the second question from the beginning. ElementData is decorated transient because the JDK does not want to serialize or deserialize the entire elementData, but only size and the actual stored elements to save space and time.

Creating subarrays

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

Let’s take a look at the short version of SubList:

private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;

    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }

    public E set(int index, E e) {
        rangeCheck(index);
        checkForComodification();
        E oldValue = ArrayList.this.elementData(offset + index);
        ArrayList.this.elementData[offset + index] = e;
        return oldValue;
    }
    
    // omit code...
}
Copy the code
  • SubList’s set() method,Is to modify the ArrayList directlyIn theelementDataArray, use should be careful
  • SubList is not implementedSerializableOf the interface,It can’t be serialized

The iterator

Create iterator methods

public Iterator<E> iterator(a) {
    return new Itr();
}
Copy the code

Itr properties

// The index of the next element to return
int cursor;
// The last index of the element to return does not return -1
int lastRet = -1;
// Expected modCount
int expectedModCount = modCount;
Copy the code

Itr’s hasNext() method

public boolean hasNext(a) {
    returncursor ! = size; }Copy the code

Itr’s next() method

public E next(a) {
    checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}

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

At the time of iteration, will check whether modCount equals expectedModCount, is not equal to will be thrown famous ConcurrentModificationException anomalies. When will throw ConcurrentModificationException?

public static void main(String[] args) {
    ArrayList arrayList = new ArrayList();
    for (int i = 0; i < 10; i++) {
        arrayList.add(i);
    }
    remove(arrayList);
    System.out.println(arrayList);
}

public static void remove(ArrayList<Integer> list) {
    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()) {
        Integer number = iterator.next();
        if (number % 2= =0) {
            / / throw ConcurrentModificationExceptionlist.remove(number); }}}Copy the code

That how to write can not throw ConcurrentModificationException? Remove (number); For the iterator. Remove (); Can. According to? Itr remove()…

Itr’s remove() method

public void remove(a) {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        // Re-assign modCount to expectedModCount after removal
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw newConcurrentModificationException(); }}Copy the code

The reason is because of Itr’s remove() method, which re-assigns modCount to the expectedModCount after removal. This is the source code, whether single thread or multithreading, as long as the rules are violated, will throw exceptions.

Source code to see almost, the opening of the problem is still a! Why isn’t elementData decorated in private anyway?

We know that private modified variables and inner classes are also accessible. Is there something wrong with the statement in the annotation that non-private to simplify class access?

When we see nothing on the surface, we might as well take a look at the bottom.

Test class code:

After a javAC, javAP meal (using JDK8) :

After another javac, javAP meal (using JDK11) :

While I can’t quite read the bytecode instructions, I can tell that comments are fine, and private decorations do affect access to inner classes.

ArrayList class annotation translation

Class comments are still needed to give us an overview of the class. I’ve compiled a rough translation of ArrayList’s class comments:

  • ArrayList is to achieveListAn automatically scalable array of interfaces. Implements all of themListOperation that allows all elements, includingnullValue.
  • An ArrayList is roughly the same as a Vector, except that an ArrayList is asynchronous.
  • size isEmpty get set iterator 和 listIteratorMethod time complexity is zeroO(1)Constant time. The other way isO(n)Linear time.
  • Each ArrayList instance has onecapacity(Capacity).capacityIs the size of the array used to store the elements in the list.capacityAt least as big as the list.
  • If multiple threads access an instance of ArrayList at the same time, and at least one thread makes changes, synchronization of ArrayList must be externally guaranteed. Modification includes operations such as adding, deleting, and expanding capacity. This scenario can be synchronized with some other encapsulationlist. If there is no such thingObjectArrayList should be usedCollections.synchronizedListWrapping is best done at creation time to ensure synchronous access.
  • iterator()andlistIterator(int)Method isfail-fastIf the list is structurally modified after the iterator is created, the iterator will throwConcurrentModificationException.
  • In the face of concurrent modifications, iterators fail quickly and clean up rather than risk unknown time uncertainties. Please note that fast failure behavior is not guaranteed. In general, it is almost impossible to guarantee concurrent changes that cannot be made synchronously. Therefore, it would be wrong to write code that relies on this exception, and fast failure behavior should only be used for preventionbug.

conclusion

  • The underlying data structures of an ArrayList are arrays
  • ArrayList can be automatically expanded without passing the initial capacity or the initial capacity is0, will initialize an empty array, but if you add elements, it will automatically expand, so when you create an ArrayList, it is necessary to give the initial capacity
  • Arrays.asList()Method returns yesArraysInternal ArrayList, you need to be careful when you use it
  • subList()Returns an inner class that cannot be serialized and shares the same array as ArrayList
  • Iterating to delete using iteratorsremoveMethod, or you can use reverse orderforcycle
  • ArrayList rewrites the serialization and deserialization methods to avoid serializing and deserializing all arrays, which is a waste of time and space
  • elementDataDo not useprivateModifier to simplify access to inner classes

Source code series first, accidentally write a little long. But the process from ignorance to profound is quite intriguing. If there are points in this article that are not expanded, or if you have any other curious points, feel free to leave a comment. See you in the next article…

Welcome to pay attention to personal wechat public number [such as sailing against the current], attentively output base, algorithm, source code series of articles.