閱讀優(yōu)秀的源碼是提升編程技巧的重要手段之一。
如有不對的地方，歡迎指正~
轉(zhuǎn)載請注明出處https://blog.lzoro.com。

前言

當(dāng)你對某件事情很感興趣的時候，時間的流逝在感知中都模糊了（是不是很文藝，繞口得都快聽不懂了），通俗來說，就是時間過得很快。

而且，只有感興趣才能驅(qū)動你繼續(xù)下去，不然讀源碼，寫解析博客這么高(Ku)大(Zao)上的事，是很難堅持的。

詳細地寫一篇源碼解析博客少則半天一天，比如本篇，多則幾天，比如紅黑樹在Java - HashMap中的應(yīng)用，又要畫圖又要注釋，還要排版，時不時要加點表情，開個車什么的，你說要是沒興趣，怎么堅持呢，還不如吃個雞實在(啊，暴露了我是吃雞選手)。

image

閑話少說，打開你的IDE，挽起袖子，開擼代碼，加上注釋，總計1461行代碼。

基本介紹

常量

相比HashMap來說，ArrayList的常量算是短小精悍了，只有幾個。

其中包含一個默認容量和兩個空數(shù)組等，如下。

 /**
 * 默認初始化容量
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 空數(shù)組共享實例
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 缺省大小的空數(shù)組共享實例
 * 與 EMPTY_ELEMENTDATA 區(qū)分開來，以便知道第一個元素添加時如何擴容
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 最大可分配大小
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

成員變量

成員變量也是簡單到令人發(fā)指，一個負責(zé)實際存儲的緩沖數(shù)組和一個表示大小的變量。

/**
 * 實際負責(zé)存儲的緩沖數(shù)組
 * ArrayList的容量就是緩沖數(shù)組的長度
 * 
 * 空的ArrayList(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)在第一個元素添加時將會以默認容量擴容
 */
transient Object[] elementData; // 非私有，以簡化嵌套類的訪問

/**
 * 大小
 */
private int size;

構(gòu)造函數(shù)

三個構(gòu)造函數(shù)，分別是利用默認初始容量/給定初始容量/給定特定集合來構(gòu)造ArrayList。

/**
 * 根據(jù)給定初始容量構(gòu)造一個空的list
 *
 * @param  initialCapacity  list的初始容量
 * @throws IllegalArgumentException 當(dāng)給定的初始容量非負時拋異常
 */
public ArrayList(int initialCapacity) {
    //判斷給定初始化容量是否合法
    if (initialCapacity > 0) {
        //創(chuàng)建數(shù)組
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

/**
 * 按默認初始容量(10)構(gòu)造一個空的list
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * 根據(jù)給定集合構(gòu)造一個list，將按集合迭代的順序存儲
 *
 * @param c 集合
 * @throws NullPointerException  集合為null時拋異常
 */
public ArrayList(Collection<? extends E> c) {
    //集合轉(zhuǎn)數(shù)組后賦值給緩沖數(shù)組
    elementData = c.toArray();
    //判斷大小
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        //c.toArray方法可能不會返回Object[]形式的數(shù)組
        //下面做一層判斷
        if (elementData.getClass() != Object[].class)
            //做拷貝操作
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        //如果是空集合，則替換成共享空數(shù)組實例
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

功能

看完了基本介紹，應(yīng)該會覺得Just so so。

接下來就要逐一介紹各個功能的具體實現(xiàn)了。

ArrayList中，我們常用的功能有add/remove/get等。

無外乎增刪改查，下面一一介紹~

add

在ArrayList中，添加操作還分為幾種

• 從尾部添加元素
• 指定位置添加元素
• 從尾部添加集合
• 從指定位置添加集合

/**
 * 從尾部添加指定元素
 *
 * @param e 元素
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    //確保內(nèi)部容量，有一系統(tǒng)調(diào)用鏈但不復(fù)雜，下面分析
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //存儲元素
    elementData[size++] = e;
    return true;
}

/**
 * 在指定位置插入元素
 *  移動當(dāng)前位置的元素 (如果存在) 和后繼元素到右邊
 *
 * @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) {
    //判斷邊界，可能會產(chǎn)生數(shù)組越界
    rangeCheckForAdd(index);
    //確保內(nèi)部容量，同上
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //調(diào)用效率較高的System.arraycopy進行數(shù)組復(fù)制
    //目的是為了空出指定位置
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    //指定位置上放入指定元素
    elementData[index] = element;
    //容量+1
    size++;
}

在添加的元素的時候，有一個關(guān)鍵方法ensureCapacityInternal是來確保內(nèi)部緩存數(shù)組的容量，當(dāng)容量不夠時進行擴容，下面具體看下這個方法的調(diào)用鏈

/**
 * 私有方法
 */
private void ensureCapacityInternal(int minCapacity) {
    //判斷是否是默認空實例，如果是的話，計算擴容容量
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //調(diào)用ensureExplicitCapacity
    ensureExplicitCapacity(minCapacity);
}

...

private void ensureExplicitCapacity(int minCapacity) {
    //操作計算+1
    modCount++;
    
    // overflow-conscious code
    //只有當(dāng)容量不夠時才擴容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

/**
 * 緩沖數(shù)組擴容以確保能夠存儲給定元素
 *
 * @param minCapacity 期望的最小容量
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    //現(xiàn)有元素長度
    int oldCapacity = elementData.length;
    //新容量為 舊容量 + 舊容量的一半
    //如 10 + 5 = 15
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //如果計算的新容量比期望的最小容量小，則采用期望的最小容量作為擴容參數(shù)
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //判斷是否超過最大數(shù)組容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    //最小擴容容量通常是接近size的，所以這是一場勝利
    //這么臭美的嗎
    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;
}

set

這里的set其實可以理解為修改，將指定位置的元素替換為新元素。

/**
 * 修改指定位置的元素
 *
 * @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;
}

remove

數(shù)組的移除和添加一樣，也分為幾種方式

• 根據(jù)下標(biāo)移除
• 根據(jù)對象移除
• 根據(jù)集合移除
• 根據(jù)過濾器移除
• 根據(jù)范圍移除(受保護的方法)

/**
 * 刪除指定位置的元素，后繼元素左移(前移)
 *
 * @param index 下標(biāo)
 * @return the 被移除的元素
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    //下標(biāo)檢查
    rangeCheck(index);
    //操作計數(shù) + 1
    modCount++;
    //獲取指定位置的元素(用以返回)
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    //用system.arraycopy的方式移動元素
    //相當(dāng)于是index位置后的元素前移
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    //最后一個數(shù)組元素引用置為null，方便GC
    elementData[--size] = null; // clear to let GC do its work
    //返回
    return oldValue;
}


/**
 * 當(dāng)元素存在的時候，刪除第一個找到的指定元素
 * 
 * 如果元素不存在，則list不會變動
 *
 * @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) {
    //o是否是null元素(數(shù)組允許存儲null)
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                //調(diào)用內(nèi)部的fastRemove方法，后面分析
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            //這里跟上面不一樣的是，是用equals來比較，而不是比較地址
            if (o.equals(elementData[index])) {
                //同上
                fastRemove(index);
                return true;
            }
    }
    return false;
}

/**
 * 根據(jù)給定的集合，將list中與集合相同的元素全部刪除
 *
 * @param c collection containing elements to be removed from this list
 * @return {@code true} if this list changed as a result of the call
 * @throws ClassCastException if the class of an element of this list
 *         is incompatible with the specified collection
 * (<a href="Collection.html#optional-restrictions">optional</a>)
 * @throws NullPointerException if this list contains a null element and the
 *         specified collection does not permit null elements
 * (<a href="Collection.html#optional-restrictions">optional</a>),
 *         or if the specified collection is null
 * @see Collection#contains(Object)
 */
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    //調(diào)用批量刪除，后續(xù)分析
    return batchRemove(c, false);
}


/**
 * 通過一個過濾器接口實現(xiàn)，來實現(xiàn)刪除
 */
@Override
public boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    // figure out which elements are to be removed
    // any exception thrown from the filter predicate at this stage
    // will leave the collection unmodified
    int removeCount = 0;
    //用bitset來存儲哪些下標(biāo)對應(yīng)的元素要刪除，哪些下標(biāo)對應(yīng)的元素要保存
    //這里不清楚BitSet的用法的，可以先行了解一下
    final BitSet removeSet = new BitSet(size);
    //判斷并發(fā)修改用
    final int expectedModCount = modCount;
    final int size = this.size;
    //按順序遍歷且沒有并發(fā)修改
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        @SuppressWarnings("unchecked")
        final E element = (E) elementData[i];
        //利用過濾器匹配元素，如果匹配，則刪除計數(shù)+1，并將下標(biāo)進行存儲
        if (filter.test(element)) {
            removeSet.set(i);
            removeCount++;
        }
    }
    //判斷是否存在并發(fā)修改
    if (modCount != expectedModCount) {
        //拋出并發(fā)修改異常
        throw new ConcurrentModificationException();
    }

    // shift surviving elements left over the spaces left by removed elements
    //判斷是否有要刪除的元素
    final boolean anyToRemove = removeCount > 0;
    if (anyToRemove) {
        final int newSize = size - removeCount;
        for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
            //下一個要保存的元素
            i = removeSet.nextClearBit(i);
            //存放到新數(shù)組
            elementData[j] = elementData[i];
        }
        //把實際要保存的元素之后的全部置為null，用以GC
        //實際上，上面的操作已經(jīng)將要保留的元素全部前移了，后面的元素都是不保留的，所以要置為null來幫助gc
        for (int k=newSize; k < size; k++) {
            elementData[k] = null;  // Let gc do its work
        }
        //設(shè)置size
        this.size = newSize;
        //判斷是否并發(fā)修改
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    return anyToRemove;
}


/**
 * 刪除list中指定范圍的元素
 * 
 * Shifts any succeeding elements to the left (reduces their index).
 * This call shortens the list by {@code (toIndex - fromIndex)} elements.
 * (If {@code toIndex==fromIndex}, this operation has no effect.)
 *
 * @throws IndexOutOfBoundsException if {@code fromIndex} or
 *         {@code toIndex} is out of range
 *         ({@code fromIndex < 0 ||
 *          fromIndex >= size() ||
 *          toIndex > size() ||
 *          toIndex < fromIndex})
 */
protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    //范圍刪除時，其實數(shù)組被分成三個部分
    //分別為[保留區(qū) - 刪除區(qū) - 保留區(qū)]
    //實際操作，則是計算出最后那部分保留區(qū)的長度
    //利用arraycopy拷貝到第一個保留區(qū)的后面
    //然后置空多余部分，幫助GC
    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;
}

//最后，來看一下批量刪除這個私有方法

/**
 * 批量刪除
 */
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            //這里其實有可能拋異常的
            //complement
            //為false時，則證明下標(biāo)r的元素不在刪除集合c中，所以這個時候存儲的是不刪除的元素

            //為true時，則證明下標(biāo)r的元素在刪除集合c中，所以這個時候存儲的是要刪除的元素
            
            //這個布爾值的設(shè)計很巧妙。所以本方法可以供removeAll、retainAll兩個方法來調(diào)用
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        //所以這里要實際進行判斷循環(huán)是否正常
        if (r != size) {
            //如果不正常的話，需要挪動元素
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        //如果有需要刪除的元素的話，則證明有一部分位置需要只為null，來幫助GC
        //并且設(shè)置是否有修改的標(biāo)志為true
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

至此，刪除相關(guān)的方法都已經(jīng)分析完畢。

有幾個比較有意思的應(yīng)用

• BitSet 標(biāo)志哪些下標(biāo)要刪除，哪些不刪除
• batchRemove 方法中的布爾值很巧妙

get

作為數(shù)組型的list，獲取方法時比較簡單的，只需要根據(jù)給定下標(biāo)，讀取指定下標(biāo)的數(shù)組元素即可。

public E get(int index) {
    //范圍檢查
    rangeCheck(index);

    return elementData(index);
}

contains

當(dāng)前l(fā)ist是否包含指定元素

/**
 * 返回布爾值表示是否包含
 */
public boolean contains(Object o) {
    //實際上是判斷下標(biāo)是否存在
    return indexOf(o) >= 0;
}

/**
 * 指定元素在list中首次出現(xiàn)的下標(biāo)，不存在則返回-1
 */
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;
}

//另外，還有一個，最后一次出現(xiàn)的下標(biāo)

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

clear

清空緩沖數(shù)組。

public void clear() {
    //修改計數(shù) + 1
    modCount++;

    // clear to let GC do its work
    //全部置為null，幫助GC
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    //size設(shè)置為0
    size = 0;
}

以上相關(guān)方法基本都已經(jīng)介紹完畢。

總結(jié)

Array相比其他集合框架，如Map、Set之類的，還是比較簡單的。

只需要了解相關(guān)方法的應(yīng)用和原理，注意下標(biāo)越界問題，以及內(nèi)部的緩沖數(shù)組是如何擴容的，基本上就OK了。

溜了溜了。有幫助的話給格子點個贊唄~_3Q

我的博客即將入駐“云棲社區(qū)”，誠邀技術(shù)同仁一同入駐。