目錄

ArrayList簡介

ArrayList和vector的區別（了解即可）

ArrayList添加null值

?ArrayList和LinkedList區別

?ArrayList核心源碼解讀

?ArrayList擴容機制分析

一步一分析ArrayList擴容機制

?hugeCapacity()方法

System.arraycopy()

?Arrays.copyOf()方法

---

ArrayList簡介

ArrayList 的底層是數組隊列，相當于動態數組。與 Java 中的數組相比，它的容量能動態增長。在添加大量元素前，應用程序可以使用ensureCapacity操作來增加 ArrayList 實例的容量。這可以減少遞增式再分配的數量。

ArrayList繼承于AbstractList，實現了List，RandomAccess，Cloneable，java.io.Serializable這些接口。

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

?List?：是一個列表，支持添加，刪除，查找等操作，并且可以通過下標隨機訪問。

RandomAccess?：這是一個標志接口，表明實現這個接口的List結合支持快速隨機訪問的。在ArrayList中，我們即可通過元素的序號快速獲取元素對象，這就是隨機訪問。

Cloneable：表明有拷貝能力，可以進行深拷貝或淺拷貝操作。

Serializable：表明他可以進行序列化操作，也就是可以將對象轉換為字節流對象進行持久化存存儲網絡傳輸，非常方便。

ArrayList和vector的區別（了解即可）

ArrayList是List的主要實現類，底層使用Object[]存儲，適用于頻繁的查找工作，線程不安全。

Vector是List的古老實現類，底層使用Object[]存儲，線程安全。?

ArrayList添加null值

ArrayList中可以存儲任何類型的對象，包括null值。不過，不建議向ArrayList添加null值，null值毫無意義，會讓代碼難以維護比如忘記做判空處理就會導致空指針異常。

ArrayList<String> listOfStrings = new ArrayList<>();
listOfStrings.add(null);
listOfStrings.add("java");
System.out.println(listOfStrings);

[null, java]

?ArrayList和LinkedList區別

是否保證線程安全：ArrayList和LinkedList都是不同步的，也就是不保證線程安全；

底層數據結構：ArrayList底層使用的是Object數組；LinkedList底層使用的是雙向鏈表數據結構（JDK1.6 之前為循環鏈表，JDK1.7 取消了循環。注意雙向鏈表和雙向循環鏈表的區別）

插入和刪除是否受元素位置的影響：

ArrayList 采用數組存儲，所以插入和刪除元素的時間復雜度受元素位置的影響。 比如：執行add(E e)方法的時候， ArrayList 會默認在將指定的元素追加到此列表的末尾，這種情況時間復雜度就是 O(1)。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element)），時間復雜度就為 O(n)。因為在進行上述操作的時候集合中第 i 和第 i 個元素之后的(n-i)個元素都要執行向后位/向前移一位的操作。

LinkedList 采用鏈表存儲，所以在頭尾插入或者刪除元素不受元素位置的影響（add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、 removeLast()），時間復雜度為 O(1)，如果是要在指定位置 i 插入和刪除元素的話（add(int index, E element)，remove(Object o),remove(int index)）， 時間復雜度為 O(n) ，因為需要先移動到指定位置再插入和刪除。

是否支持快速隨機訪問： LinkedList 不支持高效的隨機元素訪問，而 ArrayList（實現了 RandomAccess 接口） 支持。快速隨機訪問就是通過元素的序號快速獲取元素對象(對應于get(int index)方法)。

內存空間占用： ArrayList 的空間浪費主要體現在在 list 列表的結尾會預留一定的容量空間，而 LinkedList 的空間花費則體現在它的每一個元素都需要消耗比 ArrayList 更多的空間（因為要存放直接后繼和直接前驅以及數據）。

---

?ArrayList核心源碼解讀

?ArrayList擴容機制分析

先從構造函數說起，ArrayList有三種方式來進行初始化

?以無參數構造方法創建ArrayList時，實際上初始化賦值的是一個空數組。當真對數組進行添加元素操作時，才真正分配容量。即向數組中添加第一個元素時，數組容量擴為10。

一步一分析ArrayList擴容機制

這里以無參構造函數創建ArrayList為例分析。

add方法

/**
* 將指定的元素追加到此列表的末尾。
*/
public boolean add(E e) {// 加元素之前，先調用ensureCapacityInternal方法ensureCapacityInternal(size + 1);  // Increments modCount!!// 這里看到ArrayList添加元素的實質就相當于為數組賦值elementData[size++] = e;return true;
}

注意：JDK11移除了ensureCapacityInternal()和ensureExplicitCapacity()方法

ensureCapacityInternal方法源碼如下：

// 根據給定的最小容量和當前數組元素來計算所需容量。
private static int calculateCapacity(Object[] elementData, int minCapacity) {// 如果當前數組元素為空數組（初始情況），返回默認容量和最小容量中的較大值作為所需容量if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}// 否則直接返回最小容量return minCapacity;
}// 確保內部容量達到指定的最小容量。
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

?ensureCapacityInternal方法非常簡單，內部直接調用了ensureExplicitCapacity()方法：

//判斷是否需要擴容
private void ensureExplicitCapacity(int minCapacity) {modCount++;//判斷當前數組容量是否足以存儲minCapacity個元素if (minCapacity - elementData.length > 0)//調用grow方法進行擴容grow(minCapacity);
}

?我們來分析一下：

1.當我們要add進第一個元素到ArrayList時，elementData.length為0，此時還是一個空數組，因為執行了ensureCapacityInternal方法，所以minCapacity此時為10.此時，minCapacity-elementData.length大于0，成立，所以會進入到grow(minCapacity);方法。

2.添加第3、4到第十個元素的時候，依然不會執行grow方法，數組容量都為10。

知道添加第11個元素的時候，minCapacity為11比elementData.length（10）要大。進入到grow方法進行擴容。

grow方法

/*** 要分配的最大數組大小*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;/*** ArrayList擴容的核心方法。*/
private void grow(int minCapacity) {// oldCapacity為舊容量，newCapacity為新容量int oldCapacity = elementData.length;// 將oldCapacity 右移一位，其效果相當于oldCapacity /2，// 我們知道位運算的速度遠遠快于整除運算，整句運算式的結果就是將新容量更新為舊容量的1.5倍，int newCapacity = oldCapacity + (oldCapacity >> 1);// 然后檢查新容量是否大于最小需要容量，若還是小于最小需要容量，那么就把最小需要容量當作數組的新容量，if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果新容量大于 MAX_ARRAY_SIZE,進入(執行) `hugeCapacity()` 方法來比較 minCapacity 和 MAX_ARRAY_SIZE，// 如果minCapacity大于最大容量，則新容量則為`Integer.MAX_VALUE`，否則，新容量大小則為 MAX_ARRAY_SIZE 即為 `Integer.MAX_VALUE - 8`。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);
}

int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次擴容之后容量都會變為原來的 1.5 倍左右（oldCapacity 為偶數就是 1.5 倍，否則是 1.5 倍左右）！ 奇偶不同，比如：10+10/2 = 15, 33+33/2=49。如果是奇數的話會丟掉小數.

?hugeCapacity()方法

從上面 grow() 方法源碼我們知道：如果新容量大于 MAX_ARRAY_SIZE,進入(執行) hugeCapacity() 方法來比較 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity 大于最大容量，則新容量則為Integer.MAX_VALUE，否則，新容量大小則為 MAX_ARRAY_SIZE 即為 Integer.MAX_VALUE - 8。

private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();// 對minCapacity和MAX_ARRAY_SIZE進行比較// 若minCapacity大，將Integer.MAX_VALUE作為新數組的大小// 若MAX_ARRAY_SIZE大，將MAX_ARRAY_SIZE作為新數組的大小// MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

System.arraycopy()和Arrays.copyOf()方法

System.arraycopy()

源碼：

    // 我們發現 arraycopy 是一個 native 方法,接下來我們解釋一下各個參數的具體意義/***   復制數組* @param src 源數組* @param srcPos 源數組中的起始位置* @param dest 目標數組* @param destPos 目標數組中的起始位置* @param length 要復制的數組元素的數量*/public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);

?場景：

    /*** 在此列表中的指定位置插入指定的元素。*先調用 rangeCheckForAdd 對index進行界限檢查；然后調用 ensureCapacityInternal 方法保證capacity足夠大；*再將從index開始之后的所有成員后移一個位置；將element插入index位置；最后size加1。*/public void add(int index, E element) {rangeCheckForAdd(index);ensureCapacityInternal(size + 1);  // Increments modCount!!//arraycopy()方法實現數組自己復制自己//elementData:源數組;index:源數組中的起始位置;elementData：目標數組；index + 1：目標數組中的起始位置； size - index：要復制的數組元素的數量；System.arraycopy(elementData, index, elementData, index + 1, size - index);elementData[index] = element;size++;}

?我們寫一個簡單的方法進行測試一下：

public class ArraycopyTest {public static void main(String[] args) {// TODO Auto-generated method stubint[] a = new int[10];a[0] = 0;a[1] = 1;a[2] = 2;a[3] = 3;System.arraycopy(a, 2, a, 3, 3);a[2]=99;for (int i = 0; i < a.length; i++) {System.out.print(a[i] + " ");}}}

?結果：

0 1 99 2 3 0 0 0 0 0

?Arrays.copyOf()方法

源碼：

    public static int[] copyOf(int[] original, int newLength) {// 申請一個新的數組int[] copy = new int[newLength];// 調用System.arraycopy,將源數組中的數據進行拷貝,并返回新的數組System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));return copy;}

?場景：

   /**以正確的順序返回一個包含此列表中所有元素的數組（從第一個到最后一個元素）; 返回的數組的運行時類型是指定數組的運行時類型。*/public Object[] toArray() {//elementData：要復制的數組；size：要復制的長度return Arrays.copyOf(elementData, size);}

?個人覺得使用?Arrays.copyOf()方法主要是為了給原有數組擴容，測試代碼如下：

public class ArrayscopyOfTest {public static void main(String[] args) {int[] a = new int[3];a[0] = 0;a[1] = 1;a[2] = 2;int[] b = Arrays.copyOf(a, 10);System.out.println("b.length"+b.length);}
}

結果：

10