当前位置:网站首页>Analysis of ArrayList source code

Analysis of ArrayList source code

2020-11-08 09:41:48 Kaibao

1. AzrrayList brief introduction

java.util.ArrayList It's a An array of the queue , amount to The dynamic array . And Java The array in , It has Capacity can grow dynamically 、 Slow addition and deletion of elements 、 Quick search Characteristics .

ArrayList Inherited from AbstractList, Realized ListRandomAccessCloneablejava.io.Serializable These interfaces .

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
        --- omit ---
  }
  • ArrayList Inherited AbstractList Abstract method , Realized List Interface , Provides relevant add to 、 Delete 、 modify 、 Traverse And so on .
  • RandomAccess It's a logo interface , Indicates the implementation of this interface List Collection is support Fast random access Of . stay ArrayList in , We can quickly get the element object through the element's ordinal number , This is fast random access .
  • ArrayList Realized Cloneable Interface , That overrides the function clone(), Can be cloned .
  • ArrayList Realized java.io.Serializable Interface , It means ArrayList Support serialization , Can be transmitted by serialization .
Tips: ArrayList Operations in are not thread safe ! It is recommended to use in single thread ArrayList, Choose to use in multithreading Vector perhaps CopyOnWriteArrayList.

2. ArrayList Analysis of source code (JDK 1.8)

2.1 Member attribute

//  Default capacity size 
private static final int DEFAULT_CAPACITY = 10;

// ArrayList An empty array shared by empty instances 
private static final Object[] EMPTY_ELEMENTDATA = {};

// ArrayList An empty array shared by empty instances , Empty instance for default size .
//  And EMPTY_ELEMENTDATA Separate , So you can see how much space you need to create when you add the first element .
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//  Real storage ArrayList An array of elements in 
transient Object[] elementData;

// ArrayList  The number of elements contained , Notice that it's not elementData The length of 
private int size;

//  The maximum length of an array 
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

AbstractList The only attribute in an abstract class :

//  Express elementData Number of changes , Every time add perhaps remove Its value will add 1
protected transient int modCount = 0;

Why? size It's not used to mark elementData The length of the array ?

stay Java in , Generally speaking :

  • length Attributes are for arrays , For example, in the following source code elementData.length Express elementData Length of array .
  • length() Method is for Strings , You can call length() Get string length .
  • size() Methods are for generic collections , You can call size() To get the number in the collection .

such , It's easy to understand why size No ArrayList The length of the , It's not easy to remember .

2.2 Construction method

ArrayList There are three ways to initialize :

    /**
     *  Constructors with parameters 
     */    
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //  Initialization capacity is greater than 0, establish initialCapacity Array of sizes 
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //  Initialization capacity equal to 0, Create an empty array 
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     *  Default parameterless constructor ( Initialization capacity size not specified ), Use initial capacity 10 Construct an empty list .
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     *  Use Collection Set to initialize ArrayList
     */
    public ArrayList(Collection<? extends E> c) {
        //  Convert collection to array 
        elementData = c.toArray();
        //  If the length of the array size It's not equal to 0
        if ((size = elementData.length) != 0) {
            //  If not Object Type data 
            if (elementData.getClass() != Object[].class)
                //  Recreate a size Array of sizes .
                //  And will not be Object[] Contents of array ,Copy To the new is Object[] Array of 
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            //  Replace with empty array 
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

From the above analysis we can see that EMPTY_ELEMENTDATA And DEFAULTCAPACITY_EMPTY_ELEMENTDATA The difference between .

EMPTY_ELEMENTDATA When we instantiate an object, we specify the capacity 0, When adding 1 After elements , that elementData.length=1.

DEFAULTCAPACITY_EMPTY_ELEMENTDATA Indicates that instantiation is a parameterless construct , No capacity specified , Calling add Method to add 1 After elements, the default expansion capacity is 10, namely elementData.length=10.

2.3 Additive elements

    /**
     *  Add elements directly to the end of the array .
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    /**
     *  Adds an element to the specified index Location .
     */
    public void add(int index, E element) {
        //  Yes index Do a boundary check 
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // native Static methods , primary elementData Array of index( contain ) Later data , Copy to target elementData Array of index + 1 After the position 
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //  Will be taken from index All members after the start move one bit back , take element Insert into index Location .
        elementData[index] = element;
        //  Last size+1
        size++;
    }

    /**
     *  Appends all elements in the specified collection to the end of this list .
     */
    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;
        return numNew != 0;
    }

    /**
     *  Start at the designated location , Inserts all elements in the specified collection into this list .
     */
    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;
        return numNew != 0;
    }

The source code calls a lot of arraycopy() Method , Its specific use can refer to from System.arraycopy The consolidation triggered : Object reference And object The difference between One article .

2.4 Remove elements

    /**
     *  Delete the element at the specified position in the list . Move any subsequent elements to the left ( Subtract from its index 1).
     */
    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;
          //  Elements removed from the list 
        return oldValue;
    }

    /**
     *  Delete the specified element from the list .
     */
    public boolean remove(Object o) {
        //  If the list does not contain the element , Then it will not change .
        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++)
                //  return true, This list contains the specified elements 
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    //  It skips the boundary check without returning the removed value .
    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;
    }

    /**
     *  Remove all elements from the list .
     */
    public void clear() {
        modCount++;

        //  Set the values of all elements in the array to null
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

    /**
     *  Remove all indexes from this list as fromIndex ( contain ) and toIndex Between the elements .
     */
    protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

    /**
     *  Removes all elements contained in the specified collection from this list .
     */
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        //  If this list is modified, return to true
        return batchRemove(c, false);
    }

2.5 ArrayList Expansion mechanism

You can find ,ArrayList When adding elements , Will be called ensureCapacityInternal Method .

With add(E e) Methods as an example :

    /**
     *  Add elements directly to the end of the array .
     */
    public boolean add(E e) {
        //  Check whether expansion is needed 
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

2.5.1 ensureCapacityInternal() and ensureExplicitCapacity()

see ensureCapacityInternal() Method :

    //  Get the minimum capacity to meet the demand 
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // elementData It's an empty list 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
             //  Expand the array to DEFAULT_CAPACITY(10)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // return size+1
        return minCapacity;
    }

    //  Determine whether capacity expansion is needed 
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        if (minCapacity - elementData.length > 0)
            // call grow Method for real expansion 
            grow(minCapacity);
    }
  1. When the 1 Elements to ArrayList In the middle of the day ,minCapacity by size+1=0,elementData Or empty? list,elementData.length=0 , All will be executed return Math.max(DEFAULT_CAPACITY, minCapacity);,minCapacity Turn into 10. here ,minCapacity - elementData.length > 0 establish , So it's going to enter grow(minCapacity) Method to really expand the capacity of .
  2. When the 2 Element time ,minCapacity by size+1 =2, because elementData.length After adding the first element, it has been expanded to 10 了 . here ,minCapacity - elementData.length > 0 Don't set up , Not execute grow(minCapacity) Method , It won't expand .
  3. Add para 3、4、5...... To the first 10 Element time , Still not expanding , The capacity of the array is still 10.

Until... Is added 11 Elements ,minCapacity - elementData.length > 0 establish , perform grow Methods to expand capacity .

2.5.2 grow()

grow The way is the whole ArrayList The core of expansion :

    private void grow(int minCapacity) {//11
        // oldCapacity Old capacity 
        int oldCapacity = elementData.length;//10
        //  Displacement operators are much faster than ordinary operators .>> It means that you will oldCapacity Moves to the right one ,(oldCapacity >> 1) amount to oldCapacity /2
        //  Update new capacity to old capacity 1.5 times 
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //  If the new capacity is still less than the minimum required capacity 
        if (newCapacity - minCapacity < 0)
            //  The direct minimum requirement capacity is used as the new capacity of the array 
            newCapacity = minCapacity;
       // If minCapacity Greater than maximum capacity , The new capacity is `Integer.MAX_VALUE`, otherwise , The new capacity is  MAX_ARRAY_SIZE  That is to say  `Integer.MAX_VALUE - 8`.
        //  The new capacity is greater than MAX_ARRAY_SIZE,
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //  perform hugeCapacity() Method 
            newCapacity = hugeCapacity(minCapacity);

        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    //  Compare minCapacity and MAX_ARRAY_SIZE
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)
            throw new OutOfMemoryError();

        // minCapacity > MAX_ARRAY_SIZE, The size of the new array is Integer.MAX_VALUE
        //  otherwise , The size of the new array is MAX_ARRAY_SIZE
        // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

Thus we can see that ,ArrayList The default expansion size is the original size 1.5 About times (oldCapacity Even, it must be 1.5 times , An odd number must be equal to 1.5 About times ).

  • If the expansion of newCapacity Still less than minCapacity, Then size the array to minCapacity size .
  • If minCapacity The value of the MAX_ARRAY_SIZE and Integer.MAX_VALUE Between , So the new array allocation Integer.MAX_VALUE size , Otherwise, distribute MAX_ARRAY_SIZE.
">>"( Shift right operator ):”>>1“ To the right 1 position ; Move right n Bits are equal to dividing by 2 Of n Power .

2.6 ensureCapacity

From the above source analysis , In the use of Arraylist When initializing capacity , It will go through a series of logical judgments before expansion . If the amount of data is large , Isn't the operation efficiency very low .

and ensureCapacity() Method , Let's set it up in advance Arraylist Size , This can greatly improve the initialization speed .

    public void ensureCapacity(int minCapacity) {
        //  In this way, we can judge whether we call the parameterless constructor when we instantiate . If not ,minExpand=0; If it is ,minExpand=10.
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        //  We set up minCapacity Greater than minExpand Before expansion 
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

Best in add A lot of elements were used before ensureCapacity Method , To reduce the number of incremental reallocation .

Let's test the use of ensureCapacity The difference between before and after :

public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int minCapacity = 10000000;
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < minCapacity; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println(" Don't use ensureCapacity Time consuming :" + (endTime - startTime));

        list = new ArrayList<Object>();
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(minCapacity);
        for (int i = 0; i < minCapacity; i++) {
            list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println(" Use ensureCapacity Time consuming :" + (endTime1 - startTime1));
    }
}

Running results :

 Don't use ensureCapacity Time consuming :2471
 Use ensureCapacity Time consuming :289

3 Traverse

ArrayList It mainly supports three traversal modes :

  • foreach Loop traversal
Integer value = null;
for (Integer integ:list) {
    value = integ;
}
  • Iterator traversal
Integer value = null;
Iterator iter = list.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}
  • Random access , Traverse through index values

because ArrayList Realized RandomAccess Interface , It supports random access to elements through index values .

Integer value = null;
int size = list.size();
for (int i=0; i<size; i++) {
    value = (Integer)list.get(i);        
}

4 fail-fast Mechanism

Fast failure (fail-fast) yes Java An error detection mechanism in a collection . Its characteristic is to traverse Java When the collection , Modification of values is not allowed , Otherwise it will throw ConcurrentModificationException abnormal .

For example, in Multithreading In development , Threads A Passing iterator Traverse a collection , Threads B It happens that the contents of the collection have been modified , So thread A Continue to traverse the collection and throw ConcurrentModificationException abnormal , produce fail-fast event .

see AbstractList Source code :

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    ... ...

    //  Used to record List Number of changes : Every modification ( add to / Delete and other operations ), take modCount+1
    protected transient int modCount = 0;

    //  return List Corresponding iterator . actually , Is to return Itr object .
    public Iterator<E> iterator() {
        return new Itr();
    }

    // Itr yes Iterator( iterator ) Implementation class of 
    private class Itr implements Iterator<E> {
        int cursor = 0;

        int lastRet = -1;

        //  The record value of the modified number .
        //  Every time a new Itr() Object time , When the object is created, it will be saved modCount.
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size();
        }

        public E next() {
            checkForComodification();
            --- omit ---
        }

        public void remove() {
            if (lastRet == -1)
                throw new IllegalStateException();
            checkForComodification();
            --- omit ---
        }

        final void checkForComodification() {
            //  Every time I traverse List When it comes to the elements in , Will compare expectedModCount and modCount Whether it is equal or not .
            //  If not equal , Throw out ConcurrentModificationException abnormal , produce fail-fast event .
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
     ... ...   
}

so ,ArrayList When adding or deleting elements , Whether it's calling add()、remove() still clear() And so on , When it comes to modifying the number of elements in a collection , Will change modCount Value .

And every time the iterator iterates through the next element , Metropolitan detection modCount Is the variable expectedModCount value . If you modify the collection while it is traversed modCount Value , that modCount != expectedModCount , And then throw ConcurrentModificationException abnormal .

therefore , In multithreaded development , It is recommended to use java.util.concurrent Package to replace the thread safety class java.util Thread unsafe class under package . such as ArrayList The corresponding thread safety class is CopyOnWriteArrayList.

Special note , It's not only in multithreading that fail-fast event . Under single thread , If the content of the collection object is modified during traversal, it will also trigger fail-fast Mechanism .

foreach Loops are also traversed by means of iterators .

You should avoid writing code like this :

        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        for (String str : list) {
            if("b".equals(str)){
                list.remove(str);
            }
        }

Reference resources

版权声明
本文为[Kaibao]所创,转载请带上原文链接,感谢