深入剖析ArrayList的底層源碼，再也不怕面試官問了！

寫在前面：我是「揚帆向海」，這個昵稱來源于我的名字以及女朋友的名字。我熱愛技術、熱愛開源、熱愛程式設計。 技術是開源的、知識是共享的
。

這部落格是對自己學習的一點點總結及記錄，如果您對 Java、算法感興趣，可以關注我的動态，我們一起學習。
用知識改變命運，讓我們的家人過上更好的生活 。

深入剖析LinkedList的底層源碼

ArrayList 與 LinkedList 的方法及其差別

文章目錄

- - 一、ArrayList介紹及其源碼剖析
  - 二、構造方法及其源碼剖析
  - - 1. 帶int類型的構造方法
    - 2. 無參構造方法
    - 3. Collection<? extends E>型構造方法
  - 三、常用方法及其源碼剖析
  - - 1. get()方法
    - 2. set() 方法
    - 3. add() 方法
    - 4. remove() 方法
    - 5. size() 方法
    - 6. indexOf(Object o) 方法
  - 四、ArrayList 和 Vector 的差別
  - 五、對擴容原理源碼剖析及其思考
  - 六、ArrayList的優缺點
  - - 1. 優點
    - 2. 缺點

一、ArrayList介紹及其源碼剖析

Resizable-array implementation of the List interface. Implements all

optional list operations, and permits all elements, including null. In

addition to implementing the List interface,this class provides

methods to manipulate the size of the array that is used internally to

store the list. (This class is roughly equivalent to Vector, except

that it is unsynchronized.)

ArrayList 是從JDK1.2 引入的。
ArrayList 是可調整大小的數組，實作了List接口。實作所有可選清單操作，并允許所有元素包括null 。除了實作List 接口之外，該類還提供了一些方法來操縱内部使用的存儲清單的數組的大小。（這個類是大緻相當于Vector，不同之處在于它是不同步的）。
ArrayList 内部封裝一個數組，用數組來存儲資料。内部數組的預設初始容量 10，存滿後 1.5 倍增長
從 JDK1.8開始， ArrayList 一開始建立一個長度為 0 的數組，當添加第一個元素時再建立一個始容量為 10 的數組。

繼承結構：

深入剖析ArrayList的底層源碼，再也不怕面試官問了！

ArrayList繼承于AbstractList，實作了Cloneable、List、RandomAccess、Serializable這些接口。
ArrayList 繼承了AbstractList，實作了List。它是一個數組隊列，提供了相關的添加、删除、修改、周遊等功能。
ArrayList 實作了Cloneable接口，即覆寫了函數clone()，是以它能被克隆。
ArrayList 實作了RandmoAccess接口，是以提供了随機通路功能。
ArrayList 實作了Serializable接口，這意味着ArrayList支援序列化

ArrayList 屬性源碼剖析

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
	// 序列化 id
    private static final long serialVersionUID = 8683452581122892189L;

    // 預設容量的大小為 10
    private static final int DEFAULT_CAPACITY = 10;

    // 空執行個體共享的一個空數組
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 預設的空數組常量為DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // transient不可序列化, 存放元素的數組
    transient Object[] elementData; // non-private to simplify nested class access

   // 元素的大小，預設是0
    private int size;

    ......
	
	// 最大數組容量為 Integer.MAX_VALUE – 8
	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

注意：被标記為transient的屬性在對象被序列化的時候不會被儲存，也就是它不會被序列化。

二、構造方法及其源碼剖析

1. 帶int類型的構造方法

源碼剖析

/**
 * 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
 */
public ArrayList(int initialCapacity) {
	// 如果初始容量大于0
    if (initialCapacity > 0) {
    	// 建立一個初始容量大小的數組
        this.elementData = new Object[initialCapacity];
     // 如果初始容量為0
    } else if (initialCapacity == 0) {
    	// 将EMPTY_ELEMENTDATA指派給 elementData
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
    	// 否則初始容量小于0，則抛出異常 “非法的容量”
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

總結：

如果傳入參數也就是初始容量大于0，則建立一個初始容量大小的數組；
如果傳入的參數初始容量等于0，将EMPTY_ELEMENTDATA指派給 elementData；
如果傳入的參數初始容量小于0，将抛出異常。

2. 無參構造方法

源碼剖析

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
	// 沒有指定初始容量，将成員變量elementData的值設為預設值
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

總結：

如果沒有傳入參數，則使用預設無參建構方法建立ArrayList對象。elementData是一個大小為0的空數組。

3. Collection<? extends E>型構造方法

源碼剖析

/**
 * 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
 */
public ArrayList(Collection<? extends E> c) {
	// 将參數中的集合轉換為數組，指派給 elementData 
    elementData = c.toArray();
    // 如果數組的大小不等于 0
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        // 如果c.toArray()傳回的數組類型不是Object[]類型的
        // 則利用Arrays.copyOf()建立一個大小為size的、類型為Object[]的數組, 并将elementData中的元素複制到新的數組中
        // 最後讓elementData 指向新的數組
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else { // 否則設定元素數組為空數組
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

總結：

将參數中的集合轉換為數組，指派給 elementData
.給size進行指派，size代表集合元素數量。判斷參數是否為空，如果數組的大小不等于 0，則進一步判斷是否轉化為Object類型的數組，如果不是，則進行複制；
否則，設定元素數組為空數組

三、常用方法及其源碼剖析

1. get()方法

get(int index)

方法是傳回集合中指定位置的元素。

源碼剖析

/**
 * 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);
}

首先會檢查索引值是否越界，如果索引值大于數組大小，則會抛出異常。

源碼如下：

private void rangeCheck(int index) {
	// 索引值大于數組大小
    if (index >= size)
    	// 抛出異常
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

如果所引是合法的，則調用elementData(int index)方法擷取指定位置的元素。

2. set() 方法

set(int index, E element)

方法将index索引處的元素替換成element對象，傳回被替換的舊元素。

源碼剖析

/**
 * 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. add() 方法

add(E e) 方法将指定的元素追加到此集合的末尾

源碼剖析

/**
 * 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) {
	// 插入元素之前，會檢查是否需要擴容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将元素添加到數組中最後一個元素的後面,最後将集合中實際的元素個數加 1
    elementData[size++] = e;
    return true;
}

add(int index, E element) 在集合元素序列 index 位置處插入

源碼剖析

/**
 * 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!!
    // 将 index 位置及其後面的所有元素都向後移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 将新元素插入到 index 位置處,元素個數加 1
    elementData[index] = element;
    size++;
}

4. remove() 方法

remove(int index) 方法是删除該集合中指定位置的元素

源碼剖析

/**
 * 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)
        	// 将 index + 1 及其後面的元素向前移動一位，覆寫被删除的元素值
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 把數組最後一個元素指派為null，将元素個數減一
        elementData[--size] = null; // clear to let GC do its work
		// 傳回舊值
        return oldValue;
    }

remove(Object o) 方法是删除指定的元素，如果有重複的元素，則隻會删除下标最小的元素

源碼剖析

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

fastRemove(int index) 方法是快速删除，删除跳過邊界檢查的方法，也不傳回删除的元素值

源碼剖析

/*
 * 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)
	       System.arraycopy(elementData, index+1, elementData, index,
	                        numMoved);
	   elementData[--size] = null; // clear to let GC do its work
}

5. size() 方法

傳回集合中的元素個數

源碼剖析

/**
 * Returns the number of elements in this list.
 *
 * @return the number of elements in this list
 */
public int size() {
    return size;
}

6. indexOf(Object o) 方法

傳回對象o在集合中第一次出現的位置的索引

源碼剖析

/**
 * 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.
 */
public int indexOf(Object o) {
		// 如果查找的元素為空
        if (o == null) {
        	// 循環周遊數組
            for (int i = 0; i < size; i++)
            	// 如果 i 位置的原素為空 
                if (elementData[i]==null)
                	// 傳回下标
                    return i;
        // 否則，查找的元素不為空
        } else {
            // 循環周遊數組
            for (int i = 0; i < size; i++)
            	// 找到第一個和要查找的元素相等的元素
                if (o.equals(elementData[i]))
                	// 傳回下标
                    return i;
        }
        // 傳回 -1.則表示沒有找到
        return -1;
    }

四、ArrayList 和 Vector 的差別

ArrayList 和 Vector 底層都是數組
ArrayList 每次擴容的情況下擴容為原來的1.5 倍。線程不安全，當多個線程同時通路同一個ArrayList 集合時，如果兩個或兩個以上的線程修改了 ArrayList 集合，則必須手動保證該集合的同步性。
Vector 是同步類，其線程安全，但是它的通路比較慢。Vector 每次擴容為其空間大小的 2 倍。

五、對擴容原理源碼剖析及其思考

在add()方法中調用ensureCapacityInternal()方法，用來確定添加元素的時候，最小容量是 minCapacity。

源碼剖析

private void ensureCapacityInternal(int minCapacity) {
	// 判斷元素數組是否為空數組
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    	// 取最大值
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

在ensureCapacityInternal()方法裡面調用ensureExplicitCapacity(int minCapacity)方法，用來判段集合在添加元素的時候是否需要對目前的數組進行擴容。

源碼剖析

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

    // overflow-conscious code
    // 判斷minCapacity與目前元素數組的長度的大小
    // 如果minCapacity比目前元素數組的長度的大小大的時候需要擴容
    if (minCapacity - elementData.length > 0)
    	// 擴容
        grow(minCapacity);
}

在ensureExplicitCapacity() 方法裡面調用grow(int 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
  */
private void grow(int minCapacity) {
    // overflow-conscious code
    // 原本的容量
    int oldCapacity = elementData.length;
    // 新的容量是原本容量的1.5倍
    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);
}
/**
 *hugeCapacity()方法，用于處理minCapacity超出MAX_ARRAY_SIZE的情況
 */
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

最後調用 Arrays.copyOf()方法，用來複制原數組，将 elementData 指派為得到的新數組。

注意：

由于數組複制的代價比較大，是以建議在建立 ArrayList 對象的時候就指定大概的容量大小，進而減少擴容操作的次數

。

六、ArrayList的優缺點

1. 優點

能夠自動擴容，預設每次擴容為原來容量大小的1.5倍。
根據下标周遊元素，效率高。
根據下标通路元素，效率高。

2. 缺點

線程不安全。
在中間插入或删除元素的時候需要移動元素，效率低。

由于水準有限，本部落格難免有不足，懇請各位大佬不吝賜教！

深入剖析ArrayList的底層源碼，再也不怕面試官問了！

文章目錄

一、ArrayList介紹及其源碼剖析

二、構造方法及其源碼剖析

1. 帶int類型的構造方法

2. 無參構造方法

3. Collection<? extends E>型構造方法

三、常用方法及其源碼剖析

1. get()方法

2. set() 方法

3. add() 方法

4. remove() 方法

5. size() 方法

6. indexOf(Object o) 方法

四、ArrayList 和 Vector 的差別

五、對擴容原理源碼剖析及其思考

六、ArrayList的優缺點

1. 優點

2. 缺點

繼續閱讀

2021年銀行從業考試考情介紹,果斷收藏!

證券從業合格證書什麼時候列印？有哪些注意事項？

【幹貨滿滿】初級銀行從業考試《個人理财》重點梳理

2020年經濟師考試，難嗎？

初級銀行從業資格證有什麼用？

MBA提前面試純幹貨分享

MBA值得學麼

30歲以上的程式員何去何從。。。

IT牛們的bat面試心得與經驗總結

新鮮傳媒CEO紀中展：經濟危機對年輕人是機會新鮮傳媒CEO紀中展：經濟危機對年輕人是機會紀中展：加入創業團隊初期不要考慮名利紀中展：創業者骨子裡要有霸氣紀中展：創業是颠覆過去的過程

Java經典面試題詳解：帶你手撸紅黑樹總結

python面試題之Python 的特點和優點是什麼

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

測試理論面試題

軟體測試面試題整理

軟體測試工程師跳槽：收到面試電話後，我會做的事。