ArrayList源码剖析

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

饮水思源——ArrayList

1. 属性

public class ArrayList<Eextends AbstractList<E>
        implements List<E>, RandomAccessCloneablejava.io.Serializable
{
    /*
     序列化id
    */

    private static final long serialVersionUID = 8683452581122892189L;

    
    /**
     * Default initial capacity.
     */

    /*
     默认初始化容量为10
    */

    private static final int DEFAULT_CAPACITY = 10

    
    /**
     * Shared empty array instance used for empty instances.
     */

    /*
     指定容量为0时,返回该数组
    */

    private static final Object[] EMPTY_ELEMENTDATA = {};

    
    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */

    /*
     调用无参构造返回该数组。
     它与EMPTY_ELEMENTDATA的区别就是:该数组是默认返回的,而EMPTY_ELEMENTDATA是在用户指定容量为0时返回。
    */

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 
    

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */

    /*
     保存添加到ArrayList中的元素。 
  ArrayList的容量就是该数组的长度。 
  该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,当第一次添加元素进入ArrayList中时,数组将扩容值DEFAULT_CAPACITY。 
  被标记为transient,在对象被序列化的时候不会被序列化。
    */

    transient Object[] elementData; // non-private to simplify nested class access

    
    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */

    /*
     ArrayList的实际大小(数组包含的元素个数/实际数据的数量)默认为0
    */

    private int size;
    
    
    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */

    /*
     分派给arraylist的最大容量
  为什么要减去8呢?
  因为某些VM会在数组中保留一些头字,尝试分配这个最大存储容量,可能会导致array容量大于VM的limit,最终导致OutOfMemoryError。
    */

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

2. 构造方法

/**
* Constructs an empty list with the specified initial capacity.
*
@param  initialCapacity  the initial capacity of the list
@throws IllegalArgumentException if the specified initial capacity
*         is negative
*/

/*
 ArrayList(int initialCapacity):构造一个指定容量为capacity的空ArrayList。这是一个带初始容量大小的有参构造函数。
  初始容量大于0,实例化数组,将自定义的容量大小当成初始化elementData的大小
  初始容量等于0,将EMPTY_ELEMENTDATA赋给elementData
  初始容量小于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);
    }
}


/**
* Constructs an empty list with an initial capacity of ten.
*/

/*
 构造一个初始容量为10的空列表
 我们知道DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空的Object[],将elementData初始化,elementData也是个Object[]类型。空的Object[]会给默认容量10。但是这里我们并没有看到数组的容量变为10啊,那么什么时候会被初始化为10的数组呢?答案是有元素被加入时(add方法).当进行第一次add的时候,elementData将会变成默认的长度:10。
*/

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


/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
@param c the collection whose elements are to be placed into this list
@throws NullPointerException if the specified collection is null
*/

/*
 构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。第二个有参构造方法构造时赋的值是它的父类Collection对象。
 将collection对象转换成数组,然后将数组的地址的赋给elementData。
 如果数组的实际大小等于0(c中没有元素),将空数组EMPTY_ELEMENTDATA赋值给elementData
 如果size的值大于0,则执行Arrays.copy方法,把collection对象的内容(可以理解为深拷贝)copy到elementData中。
*/

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

说明:ArrayList的构造方法就做一件事情,就是初始化一下储存数据的容器,其实本质上就是一个数组,在其中就叫elementData

3. 重点方法

3.1 get()

/**
* 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
@throws IndexOutOfBoundsException {@inheritDoc}
*/

/*
 获取指定下标位置的元素
*/

public E get(int index) {
    rangeCheck(index); //越界检查
    return elementData(index); //返回指定位置的元素
}


/**
* Checks if the given index is in range.  If not, throws an appropriate
* runtime exception.  This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
*/

/*
 越界检查
*/

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

3.2  set()

/**
* Replaces the element at the specified position in this list with
* the specified element.
*
@param index index of the element to replace
@param element element to be stored at the specified position
@return the element previously at the specified position
@throws IndexOutOfBoundsException {@inheritDoc}
*/

public E set(int index, E element) {
    rangeCheck(index); //越界检查

    E oldValue = elementData(index); //记录旧值
    elementData[index] = element; //新值替换旧值
    return oldValue; //返回旧值
}

3.3 add()

/**
* Appends the specified element to the end of this list.
*
@param e element to be appended to this list
@return <tt>true</tt> (as specified by {@link Collection#add})
*/

/*
 添加元素至数组的末尾
*/

public boolean add(E e) {
    //确认list容量,如果不够,容量加1。注意:只加1,保证资源不被浪费
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e; //更新末尾元素
    return true;
}

//数组容量检查,不够时则进行扩容
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //调用无参构造后,第一次添加元素时,扩容为10;否则每次扩容一个长度
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
 //判断最小容量是否超过当前数组的容量
    ensureExplicitCapacity(minCapacity);
}

//数组容量检查,不够时则进行扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        //当前需要的最小容量超过了当前数组的容量,进行扩容操作
        grow(minCapacity);
}

/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
@param minCapacity the desired minimum capacity
*/

/*
 扩容操作:扩容,保证ArrayList至少能存储minCapacity个元素 
  第一次扩容,逻辑为newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基础上增加一半。
   第一次扩容后,如果容量还是小于minCapacity,就将容量扩充为minCapacity。
*/

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; //当前数组容量
    int newCapacity = oldCapacity + (oldCapacity >> 1);  //新容量为当前容量的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity; //如果新的容量小于minCapacity,则扩容为minCapacity
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity); //如果新的容量大于MAX_ARRAY_SIZE,进行大容量分配
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity); //容量确定好之后,进行数组的复制操作。参数列表(原数组,新数组长度)
}

//大容量分配
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0// overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}


/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
@param index index at which the specified element is to be inserted
@param element element to be inserted
@throws IndexOutOfBoundsException {@inheritDoc}
*/

/*
 添加元素到指定位置。原理基本同上。
*/

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

3.4 remove()

/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
@param index the index of the element to be removed
@return the element that was removed from the list
@throws IndexOutOfBoundsException {@inheritDoc}
*/

/*
 删除指定下标位置的元素
*/

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 释放最后一个位置的元素,并且置NULL

    return oldValue; //返回旧值
}

/**
* Removes the first occurrence of the specified element from this list,
* if it is present.  If the list does not contain the element, it is
* unchanged.  More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
* (if such an element exists).  Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
@param o element to be removed from this list, if present
@return <tt>true</tt> if this list contained the specified 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;
}

/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1//需要左移的元素的数量
    if (numMoved > 0)
        //arraycopy(原数组,源数组中的起始位置,目标数组,目标数据中的起始位置,要复制的数组元素的数量)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null// clear to let GC do its work
}

3.5 indexOf()和lastIndexOf()

/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/

/*
 返回指定元素在arraylist中第一次出现时的下标
*/

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

/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index <tt>i</tt> such that
* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/

/*
 返回指定元素在arraylist中最后一次出现时的下标
*/

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

3.6 clear()

/**
* Removes all of the elements from this list.  The list will
* be empty after this call returns.
*/

/*
 清空arraylist中的元素
*/

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

1)arrayList可以存放null。2)arrayList本质上就是一个elementData数组。3)arrayList区别于数组的地方在于能够自动扩展大小,其中关键的方法就是grow()方法。4)arrayList中removeAll(collection c)和clear()的区别就是removeAll可以删除批量指定的元素,而clear是删除集合中的全部元素。5)arrayList由于本质是数组,所以它在数据的查询方面会很快,而在插入删除这些方面,性能下降很多,有移动很多数据才能达到应有的效果。6)arrayList实现了RandomAccess,所以在遍历它的时候推荐使用for循环。

4. 面试题

4.1 ArrayList和LinkedList的区别?

  1. 线程安全:两者都不保证线程安全。如果需要线程安全的可以使用:

线程安全解决办法 :方法1:Collections.synchronizedList(new LinkedList()) 方法2: LinkedList和ArrayList换成线程安全的集合,如CopyOnWriteArrayList,ConcurrentLinkedQueue… 方法3:Vector(内部主要使用synchronized关键字实现同步)

  1. 底层数据结构:ArrayList底层数据结构是Object数组。LinkedList的是双向链表(1.6及之前使用的是循环链表)。
  2. 插入和删除操作的时间复杂度不同:ArrayList的底层是数组存储。插入和删除元素的时间复杂度受元素位置的影响。如果没有指定位置默认加入到链表尾部,为O(1),如果是指定加入到 i 位置则为O(n-i) LinkedList底层是链表,在插入和删除元素时间复杂度不受元素位置影响近似于O(1),如果插入到指定位置是O(n)。
  3. 是否支持快速访问:LinkedList不支持,ArrayList支持,因为底层是数组。
  4. 内存空间占用情况:ArrayList的内存占用在相同情况下小于LinkedList。ArrayList的内存占用主要在于尾部没有存储数据时。而LinkedList的内存每个元素需要额外存储前驱结点和后继结点。

4.2 RandomAccess接口?

  1. RandomAccess接口什么也没定义。只是作为一个标识符。标识实现这个接口的类具有随机访问的功能。
  2. 如:在binarySearch()方法中,他被用来判断传入的list是否RandomAccess实例,如果是,调用indexedBinarySearch()方法,如果不是,那么调用iteratorBinarySearch()方法。
  3. 实现了RandomAccess的list,优先遍历的方式是for循环,然后再是foreach(foreach底层是iterator实现的)。没有实现的优先选择iterator。
  4. 对于ArrayList就实现了该接口而LinkedList没有实现。因为ArrayList的底层是数组,数组天然支持随机访问,时间复杂度为O(1)。而LinkedList底层是链表不能随机访问,只能从头指针处进行遍历。

4.3 ArrayList与Vector区别,为什么用ArrayList取代Vector?

  1. Vector类的所有方法都是同步的,如果仅仅是一个线程去操作的话,就会消耗很多的时间在同步操作上。
  2. ArrayList不是同步的,所以在不需要保证线程安全的情况下使用ArrayList更好。

4.4 ArrayList的扩容机制?

/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
@param minCapacity the desired minimum capacity
*/

/*
 扩容操作:扩容,保证ArrayList至少能存储minCapacity个元素 
  第一次扩容,逻辑为newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基础上增加一半。
   第一次扩容后,如果容量还是小于minCapacity,就将容量扩充为minCapacity。
*/

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; //当前数组容量
    int newCapacity = oldCapacity + (oldCapacity >> 1);  //新容量为当前容量的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity; //如果新的容量仍然小于minCapacity,则扩容为minCapacity
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity); //如果新的容量大于MAX_ARRAY_SIZE,进行大容量分配
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity); //容量确定好之后,进行数组的复制操作。参数列表(原数组,新数组长度)
}

首先是无参构造初始化的集合在调用一次add过后就会扩展数组长度为10除此之外每次扩容都是在原有长度的基础上扩展二分之一

4.5 ArrayList<Integer>  arrayList = new ArrayList<>(20)中list的扩充了几次?

这种是指定数组大小的创建,创建时直接分配其大小,没有扩充。一次性为创建了传入的数字的长度的数组,所以,扩充为0次。

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity]; //Look here
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

4.6 在 foreach 循环里可否进行元素的 remove/add 操作?为什么?

我们知道集合的foreach 最终都是依赖内部的一个Iterator的实现类Itr,在new一个Itr的实例的时候会保存当前的modCount,next方法首先就会校验记录modCount与集合的modCount是否一致,所以是不允许在 foreach 循环里进行元素的 remove/add 操作。

那么为什么要这么做呢?为什么这种遍历的时候不让删除呢?前面分析我们知道当删除元素后,后面的元素会往前移,比如现在遍历到索引2然后删除了它,原来3的位置就到了2,下次遍历就是3了,那么实际上原来在3位置的元素就没有遍历到。

实在需要遍历删除,不要使用ArrayList的remove,改为用Iterator的remove即可。

- END -


原文始发于微信公众号(AJCoder):ArrayList源码剖析