騰訊一面對 ArrayList 集合的面試問題，帶你通過源碼分析回答這些問題

我是陳皮，一個在互聯網 Coding 的 ITer，微信搜索「陳皮的JavaLib」第一時間閱讀最新文章，回復【資料】，即可獲得我精心整理的技術資料，電子書籍，一線大廠面試資料和優秀簡歷模板。

1 前言

ArrayList 是開發中使用最頻繁的集合框架中的數據結構之一了，而且也是面試中必問考題。所以很有必要掌握，熟練使用。所以，我們將從源碼分析底層原理實現和面試中常用考點分析。

2 ArrayList 簡介

ArrayList 是 Java 集合框架中的成員之一，底層是基于數組實現，并且集合容量可動態變化的。它繼承自 AbstractList 抽象類，實現了 List 接口。同時還實現了 RandomAccess，Cloneable 和 Serializable 三個標記接口，說明 ArrayList 是支持快速隨機訪問，可克隆復制的，可序列化的。

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable { }

3 ArrayList 源碼分析

3.1 變量

ArrayList 底層是基于數組實現，并且集合容量可動態變化。類中定義了一個 Object 類型的數組存儲元素，因為是 Object 類型的數組，所以也只能存儲引用數據類型，如果存儲基本數據類型（例如 int ，double等），底層會自動將基本數據類型進行類的包裝。

ArrayList 中還定義了一個記錄數組元素個數的變量，以及一個代表默認初始化容量的靜態變量。

/** * ArrayList 中存儲元素的數組，數組的長度即集合的容量 * 不用 private 關鍵字修飾是為了內部類方便訪問此數組 * transient 關鍵字修飾代表此數組不作為序列化的一部分 */ transient Object[] elementData; /** * 記錄 ArrayList 集合中實際存儲的元素個數 */ private int size; /** * 默認初始化容量 */ private static final int DEFAULT_CAPACITY = 10;

ArrayList 中定義了兩個靜態空數組對象，主要用來當集合初始化，并且沒有添加任何元素時，作為一個空數組對象賦值給 elementData 數組對象，代表一個空 list。那為啥要定義2個空數組對象呢？后面會細講。

/** * 一個共享的靜態空數組對象，用于空 list 集合中 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 一個共享的靜態空數組對象，用于默認大小初始化的空 list 集合中 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

ArrayList 的父類 AbstractList 中定義了 modCount 變量，它記錄了集合被操作修改的次數，在使用迭代器 Iterator 中會被使用到，因為在使用迭代器遍歷集合元素的過程中集合結構不允許被修改（例如添加元素，刪除元素），通過比較 modCount 的值能防止在迭代的過程中集合被修改。

protected transient int modCount = 0;

3.2 構造函數

ArrayList 有三個構造函數，一個無參構造函數，一個指定集合容量大小的有參構造函數，以及一個使用指定 Collection 集合來構造集合的構造函數。

無參構造函數，即初始化一個容量為10的空 list 集合，雖說是初始化容量為10的集合，但是實際此時沒創建一個容量為10的數組，而只是將 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 這個空數組對象賦值給 elementData 變量，只有在第一次添加元素時才創建一個容量的為10的數組。

/** * 構造一個容量為10的空 list */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

指定初始化容量的有參構造函數，當初始化容量大于0時，直接創建指定容量大小的數組，如果初始化容量為0，則將 EMPTY_ELEMENTDATA 空數組對象賦值給 elementData 變量。

/** * 構造一個指定初始化容量大小的空 list */ 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); } }

使用指定 Collection 集合來構造 ArrayList 對象，如果 Collection 不為空，則將其元素拷貝賦值到 elementData 中，如果 Collection 為空，則還是創建一個空的 list，相當于 new ArrayList(0)。

/** * 構造一個 list，它包含了指定 Collection 集合元素，這些元素的順序是通過集合迭代器返回元素的順序決定的 */ public ArrayList(Collection 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; } }

3.3 常用方法

public boolean add(E e)

在 list 尾部添加一個元素，首先會將記錄對集合操作的次數加1，然后再判斷集合容量是否足夠，不夠則進行擴容。

/** * 在 list 尾部添加一個元素 */ public boolean add(E e) { // 修改操作次數，并且是否進行擴容操作 ensureCapacityInternal(size + 1); // 將新元素添加在數組尾部 elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { // 如果是采用默認初始化容量10構造的 list，則取默認初始化容量10和當前需要添加元素的下標+1的最大值來初始化 list // 這里就說明了為什么要定義2個空數組對象，因為通過判斷空 list 是否等于 DEFAULTCAPACITY_EMPTY_ELEMENTDATA， // 如果是，則使用默認的初始化容量10來進行擴容 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { // 修改次數加1 modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) // 擴容 grow(minCapacity); } 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; // 最大容量為 Integer.MAX_VALUE if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 拷貝數組 elementData = Arrays.copyOf(elementData, newCapacity); }

public void add(int index, E element)

在 list 指定下標位置添加一個元素，首先會檢查下標是否在范圍內，將記錄對集合操作的次數加1，然后再判斷集合容量是否足夠，不夠則進行擴容。

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++; } private void rangeCheckForAdd(int index) { if (index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }

public E set(int index, E element)

修改 list 指定下標位置的元素，首先會檢查下標是否在范圍內，然后替換指定下標的元素，返回舊的元素。

/** * 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; } private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }

public boolean addAll(Collection c)

將指定 Collection 的所有元素添加到 list 的尾部中去，還是先檢查是否需要擴容，最后再將 Collection 集合拷貝到 list 尾部。

public boolean addAll(Collection 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; }

public int size()

返回集合中元素的個數

public int size() { return size; }

public boolean isEmpty()

判斷集合是否為空，即集合是否有元素

/** * Returns true if this list contains no elements. * * @return true if this list contains no elements */ public boolean isEmpty() { return size == 0; }

public boolean contains(Object o)

判斷集合是否包含某元素，主要通過 equals 方法比較是否存在某元素。

public boolean contains(Object o) { return indexOf(o) >= 0; } 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; }

public E get(int index)

返回指定下標位置的元素，訪問速度快。

public E get(int index) { rangeCheck(index); return elementData(index); } E elementData(int index) { return (E) elementData[index]; }

public Iterator iterator()

獲取 list 的迭代器，用于遍歷集合中的元素。

public Iterator iterator() { return new Itr(); }

4 常見面試題分析

4.1 ArrayList 是線程安全的嗎？

我們通過分析 ArrayList 源碼可知，對它的任何操作都是沒有加鎖的，所以在多線程場景下，它是線程不安全的。如果在非多線程使用場景下，我們還是使用很頻繁，因為主要用來存儲數據，查詢比較多，增刪操作比較少。

如果增刪操作比較多的話，可以使用 LinkedList，LinkedList 增刪操作速度比較快。（下期我們介紹 LinkedList ）。

如果需要線程安全的話，可以推薦使用 Vector 集合，分析 Vector 源碼會發現好多方法加了 synchronized 關鍵字修飾，即同一時間只允許一個線程進行操作，所以效率比較低，但是 Vector 是線程安全的。不過JDK集合中的工具類 Collections 提供一個方法 synchronizedList 可以將線程不安全的 ArrayList 集合變成線程安全的集合對象，所以 Vector 慢慢地也很少人使用了。

public static void main(String[] args) { ArrayList arrayList = new ArrayList<>(); arrayList.add("Java"); arrayList.add("C++"); // 封裝成線程安全的集合 List list = Collections.synchronizedList(arrayList); }

4.2 ArrayList 優缺點

優點：查詢速度快，因為底層是基于數組實現，數組在內存中是一塊聯系的內容空間，所以根據地址和索引的方式可以快速隨機訪問集合中的元素。

缺點：增刪慢，每次添加和刪除元素，都有可能涉及到數組長度的改變和元素的拷貝移動，特別是數組元素很多時比較耗時。線程不安全。

4.3 ArrayList 底層是數組實現的，那為什么不直接使用數組？

ArrayList 底層雖然是通過數組實現的，但是它內部對數組進行了封裝，能支持自動動態擴容，而直接使用數組的話，如果想要實現動態擴容效果，需要開發人員自己去處理擴容機制，容易出錯。而且 ArrayList 內部封裝了許多方法（例如在指定位置添加元素，刪除指定下標的元素，遍歷集合等）方便開發人員操作集合，減少開發成本。

4.4 JDK 1.7 前后有什么變化？

在 JDK 1.7之前，ArrayList 初始化的時候，會直接調? this(10) 達到真正初始化創建數組，而在 JDK 1.7以及之后只是將靜態空數組賦值給 elementData，并沒有真正初始化容量10，等到第一次添加元素時容量才變化為10。

再者，之前容量擴容的時候，是擴容到原來容量的1.5倍+1，而且之后是采用位操作擴容1.5倍，擴容速度更快。

// 1.7之前 int newCapacity = (oldCapacity * 3)/2 + 1; // 1.7之后 int newCapacity = oldCapacity + (oldCapacity >> 1);

4.5 初始化 ArrayList 后，直接調用 set方法會怎么樣？

通過源碼分析，通過構造方法初始化 ArrayList 之后（new ArrayList(Collection c) 除外），不管是默認的初始化還是指定容量大小的初始化，它們底層的 size 值都是為0，但是調用 set(int index, E element) 方法，它首先會檢查下標是否大于等于 size 值，如果是會報錯。 所以初始化后的 ArrayList 對象，不能馬上直接調用 set 方法，會報錯。

// 初始化后，此時 size 的值還是為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); } } public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }

4.6 ArrayList 增刪為什么會慢？

通過源碼分析，對 ArrayList 集合的添加元素和刪除元素，會涉及到數組的擴容和數據拷貝，如果數組元素個數巨大的話，會減低速度。但是如果是在尾部插入刪除的話，如果在不超出數組原有長度的話，就不會涉及數組的擴容和數據拷貝，所以這時執行速度還是很快的。

所以我們要結合實際場景選擇合適的數據結構，業務場景到底是增刪多，還是查詢多，增刪多我們可以選擇 LinkedList ，如果是查詢多可以選擇 ArrayList 。

4.7 使用迭代器 Iterator 過程中，可以增刪元素嗎？

通過源碼分析，在獲取集合的迭代器方法中，實際是返回了 Iterator 接口的實現類 Itr。而且 Itr 是 ArrayList 類中的一個內部類。

public Iterator iterator() { return new Itr(); }

查看 內部類 Itr ，定義了三個變量，cursor 變量指示下一個需要返回元素的下標；lastRet 變量指示當前需要返回元素的下標，-1代表不返回；expectedModCount 變量在 new Itr () 時被賦值 ArrayList 集合中 modCount 變量此時的值。

在獲取下一個元素的方法 next() 中，會先 checkForComodification() 方法，它的作用是檢查當前 expectedModCount 的值是否等于 ArrayList 對象目前 modCount 的值，如果不相等會報錯，這也就是為什么在使用迭代器的過程中，不允許對 ArrayList 對象的做增刪操作。

private class Itr implements Iterator { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }

4.8 Arrays.asList 創建 ArrayList 的使用問題

Arrays.asList() 方法生成的 ArrayList 類對象，在調用 add，remove等方法時會報錯。

public static void main(String[] args) { List list = Arrays.asList("Java", "C++", "Python"); list.add("C#"); // 這行會報錯 }

通過源碼分析，Arrays.asList() 生成的 ArrayList 對象不是我們本文所講的 java.util.ArrayList，Arrays 中的內部類 ArrayList 繼承了 AbstractList 類，但是它沒有重寫 AbstractList 類的 add 和 remove 等法，所以直接調用這些方法時會調用它父類 AbstractList 的同名方法，而 AbstractList 類中這些方法是沒有具體的實現操作的，而是簡單地拋出了異常。

public class Arrays { public static List asList(T... a) { return new ArrayList<>(a); } /** * @serial include */ private static class ArrayList extends AbstractList implements RandomAccess, java.io.Serializable { private static final long serialVersionUID = -2764017481108945198L; private final E[] a; ArrayList(E[] array) { a = Objects.requireNonNull(array); } // 省略一些代碼 } // 省略一些代碼 }

AbstractList 類中方法的定義如下：

public void add(int index, E element) { throw new UnsupportedOperationException(); } /** * {@inheritDoc} * *

This implementation always throws an * {@code UnsupportedOperationException}. * * @throws UnsupportedOperationException {@inheritDoc} * @throws IndexOutOfBoundsException {@inheritDoc} */ public E remove(int index) { throw new UnsupportedOperationException(); }

4.9 ArrayList 可以存儲null值嗎？元素可以重復嗎？

ArrayList 底層是數組實現的，并且在添加元素的時候。沒有對元素進行值校驗，而是直接賦值到數組中，所以 ArrayList 是可以存儲 null 值，并且存儲的元素是可以重復的。

/** * 在 list 尾部添加一個元素 */ public boolean add(E e) { // 修改操作次數，并且是否進行擴容操作 ensureCapacityInternal(size + 1); // 將新元素添加在數組尾部 elementData[size++] = e; return true; }

4.10 如何邊遍歷 ArrayList 元素，邊刪除指定元素？

可能有人會使用下面的方式來實現邊遍歷 ArrayList 元素，邊刪除指定元素：

你會發現執行報錯了，ConcurrentModificationException 并發修改異常，前面我們提到使用迭代器 Iterator 遍歷集合時，不能對集合進行增刪操作（會導致 modCount 值變化），而增強 for 循環底層也是使用迭代器實現的，所以會報錯。應該使用 Iterator 類的 remove 方法。

5 總結

關于 ArrayList 集合類的相關知識先介紹到這，也建議大家自己翻閱下源碼，然后寫幾個demo調試下，這樣才能更加深對它的了解。大家也可以在下方評論你遇到過的 ArrayList 面試題，我來給你解答或者一起探討。

下期我會繼續講解和 ArrayList 比較相似的集合類 LinkedList，歡迎大家關注，，，下期文章及時學習！

Java 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。