簡(jiǎn)單剖析下常用的ArrayList類的源碼

ArrayList的核心還是基于數(shù)組實(shí)現(xiàn)的。

//實(shí)現(xiàn)了Serializable接口，因此它支持序列化，能夠通過(guò)序列化傳輸
//實(shí)現(xiàn)了RandomAccess接口垫毙，支持快速隨機(jī)訪問(wèn)贪嫂，實(shí)際上就是通過(guò)下標(biāo)序號(hào)進(jìn)行快速訪問(wèn)
//實(shí)現(xiàn)了Cloneable接口，能被克隆俐巴。
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    //提供序列化用的
    private static final long serialVersionUID = 8683452581122892189L;
    
    //默認(rèn)的初始容量為10
    private static final int DEFAULT_CAPACITY = 10;
    
    //...
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    //arraylist用來(lái)保存對(duì)象的數(shù)組，transient告訴序列化的時(shí)候不要管這個(gè)數(shù)組
    transient Object[] elementData;
    
    //arraylist的大小
    private int size;
    
    //構(gòu)造函數(shù)硬爆，不能傳入負(fù)數(shù)欣舵，否則報(bào)錯(cuò)，然后初始化elementData數(shù)組的大小
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
    
    /*
  空構(gòu)造函數(shù)缀磕，以前的代碼直接初始化容量為10的容量數(shù)組：this(10)
  現(xiàn)在Android Api25中缘圈，這里直接初始化一個(gè)空數(shù)組，等add的時(shí)候再設(shè)置容量為10
  懶加載模式
   */
    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }
    
    //構(gòu)造函數(shù)袜蚕，將c集合里面的東西放array里面
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }
    
    /*
  將array的size設(shè)為實(shí)際size大小
  modCount表示修改的次數(shù)糟把，給迭代器iterator用的,實(shí)現(xiàn)fail-fast機(jī)制
  用于多線程的時(shí)候modCount不一致，快速拋出異常
   */
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }
    
    //這個(gè)方法就是確保array的容量至少為minCapacity
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != EMPTY_ELEMENTDATA)
            // any size if real element table
            ? 0
            // larger than default for empty table. It's already supposed to be
            // at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
    
    //接上面的方法牲剃，增加修改次數(shù)遣疯，判斷需要的最小容量大于實(shí)際容量再操作
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    /*
  以前增加的容量為old的三分之二再加一：
  int newCapacity = (oldCapacity * 3)/2 + 1
  現(xiàn)在增加的容量為old的二分之一：
  int newCapacity = oldCapacity + (oldCapacity >> 1)
   */
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        //右移一位表示除以2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //這個(gè)newCapacity < minCapacity的代碼下面這樣寫有什么優(yōu)勢(shì)？
        //下面主要是判斷oldCapacity=1的情況下凿傅，newCapacity其實(shí)等于oldCapacity的情況缠犀？
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
    
    public int size() {return size;}
    
    public boolean isEmpty() {return size == 0;}
    
    //判斷包含
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }
    
    //這里先判斷null對(duì)象,非null的對(duì)象是通過(guò)equals()來(lái)判斷的
    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;
    }
    
    //反過(guò)來(lái)查詢返回第一個(gè)的i
    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;
    }
    
    //淺拷貝数苫，并且將修改次數(shù)置0
    public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }
    
    //轉(zhuǎn)化為數(shù)組
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
    
    /*
  返回ArrayList元素組成的數(shù)組
  如果數(shù)組a的容量小于list，則新建一個(gè)數(shù)組辨液，反之直接復(fù)制到數(shù)組
   */
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }
    
    //取出列表中指定的元素
    public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        return (E) elementData[index];
    }
    
    //替換指定位置的元素
    public E set(int index, E element) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }
    
    //添加元素
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        //和ensureExplicitCapacity的區(qū)別在這里
        //如果是一開始沒有指定大小的初始化list虐急，則比較默認(rèn)的容量和傳入的值哪個(gè)大，就用哪個(gè)
        //反正不要小于10即DEFAULT_CAPACITY
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
    
    //添加元素到指定位置滔迈，指定位置和之后的元素后移一個(gè)位置
    public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    
    //刪除指定位置的元素止吁，就是將指定位置后面的元素都往前挪一個(gè)位置，再把最后一個(gè)元素置空亡鼠，交給垃圾回收器處理
    public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) 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

        return oldValue;
    }
    
    //移除指定元素對(duì)象
    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;
    }
    
    //上面的內(nèi)部方法赏殃，原理主要還是找出那個(gè)對(duì)象的位置，然后跟remove(index)類似
    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 to let GC do its work
    }
    
    //將所有元素置空间涵，交給gc處理
    public void clear() {
        modCount++;

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

        size = 0;
    }
    
    //將c集合轉(zhuǎn)化為數(shù)組仁热，然后拷貝到list數(shù)組后面
    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;
    }
    
    //上面一個(gè)方法指定位置的拷貝
    public boolean addAll(int index, Collection<? extends E> c) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(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;
    }
    
    //保護(hù)方法，不是供程序員調(diào)用的勾哩，核心還是拷貝方法抗蠢，將移除的那些置空
    protected void removeRange(int fromIndex, int toIndex) {
        // Android-changed : Throw an IOOBE if toIndex < fromIndex as documented.
        // All the other cases (negative indices, or indices greater than the size
        // will be thrown by System#arrayCopy.
        if (toIndex < fromIndex) {
            throw new IndexOutOfBoundsException("toIndex < fromIndex");
        }

        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }
    
    //序列化的寫入，讀取思劳，迭代器部分
    ...
    
}

其他注意的就是ArrayList基于數(shù)組實(shí)現(xiàn)迅矛，可以通過(guò)下標(biāo)索引直接查找到指定位置的元素，因此查找效率高潜叛，但每次插入或刪除元素秽褒，就要大量地移動(dòng)元素，插入刪除元素的效率低威兜；在查找給定元素索引值等的方法中销斟，源碼都將該元素的值分為null和不為null兩種情況處理，ArrayList中允許元素為null椒舵。

自己先看一遍源碼再看別人的分析效果棒棒的,參考:
ArrayList源碼剖析