jdk源碼閱讀筆記-ArrayList

一、ArrayList概述

首先我們來說一下ArrayList是什麼？它解決了什麼問題？ArrayList其實是一個數組，但是有區別於一般的數組，它是一個可以動態改變大小的動態數組。ArrayList的關鍵特性也是這個動態的特性了，ArrayList的設計初衷就是為了解決Java數組長度不可變的問題。我們都知道在Java中數組一旦被創建出來，那麼這個數組的大小就不可以改變了，而且初始化的時候就必須要指定數組的大小。在開發的場景中很多時候我們並不知道我們的數據量有多少，如果數組創建得太大就會造成極大的空間資源的浪費，如果太小了又會報數組下標越界異常。這是我們在開發的過程中使用數組來存儲數據時經常會遇到的問題，但是如果使用ArrayList的話，就可以輕易的解決這個問題，它能夠根據你存放的數據的大小動態的改變數組的大小（本質創建新數組），所以我們在寫代碼的時候就不需要關心數組的大小了，我覺得這也是ArrayList創建出來所需要解決的問題。當然，如果在知道數組的大小且對數組的數據不增加的話，建議使用數組的存儲數據，這樣對性能的提升有一定的幫助。

那麼，ArrayList是怎麼動態擴展數組大小的呢？下面通過源碼一步一步揭開ArrayList的神秘面紗吧。

二、ArrayList全局變量

 /**
 * Default initial capacity.
 */
 //默認的初始化大小
 private static final int DEFAULT_CAPACITY = 10;
 /**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
 //這個是用來存放數據用的數組，add進來的數據都是放到這個數組裡面的
 transient Object[] elementData; // non-private to simplify nested class access
 /**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
 //數組的大小
 private int size;

三、ArrayList構造函數

ArrayList的構造函數有三個：

1、ArrayList(int initialCapacity)：initialCapacity，數組的初始化大小，該構造器創建一個指定大小的空數組。

2、ArrayList（）：創建一個默認大小為0的空數組

3、ArrayList(Collection extends E> c)：創建一個與c一樣大小的數組，並將c的元素賦值到數組中。

**
 * 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) {//創建一個 initialCapacity大小的空數組
 if (initialCapacity > 0) {
 this.elementData = new Object[initialCapacity];
 } else if (initialCapacity == 0) {
 this.elementData = EMPTY_ELEMENTDATA;
 } else {
 throw new IllegalArgumentException("Illegal Capacity: "+
 initialCapacity);
 }
 }
 /**
 * Constructs an empty list with an initial capacity of ten.
 */
 public ArrayList() {//創建空數組
 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }
 /**
 * 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) {
 //將c轉換成數組，toArray方法返回的數組類型有可能不是Object類型的
 elementData = c.toArray();
 if ((size = elementData.length) != 0) {
 // c.toArray might (incorrectly) not return Object[] (see 6260652)
 //數組類型不是Object類型，需要將類型轉換成Object類，避免後面調用方法
 // 的時候出現類型轉換異常
 if (elementData.getClass() != Object[].class)
 elementData = Arrays.copyOf(elementData, size, Object[].class);
 } else {
 // replace with empty array. 

 this.elementData = EMPTY_ELEMENTDATA;
 }
 }

這裡我們主要看一下Arrays.copyOf()方法是如何轉換類型的：

public static  T[] copyOf(U[] original, int newLength, Class extends T[]> newType) {
 @SuppressWarnings("unchecked")
 T[] copy = ((Object)newType == (Object)Object[].class)
 ? (T[]) new Object[newLength]
 : (T[]) Array.newInstance(newType.getComponentType(), newLength);
 System.arraycopy(original, 0, copy, 0,
 Math.min(original.length, newLength));
 return copy;
 }

這個方法中，如果傳入的類型為Object類型，那麼就直接創建一個Object數組，否則創建一個對應類型的數組。然後調用System.arraycopy方法，將原數組賦值到新創建的數組中，強調一下，凡是使用到數組的地方就一定會使用到arraycopy的方法，這個方法我在String源碼閱讀有說到過，在這裡我再跟大家說一下這個方法吧。

public static native void arraycopy(Object src, int srcPos,
 Object dest, int destPos,
 int length);

這是一個本地方法所以無法繼續往下看源碼了，但是從源碼中可以知道每個參數代表的含義

src：原數組

srcPos：原數組中開始複製的位置

dest：新數組，即目標數組

destPos：目標數組存放的位置，即從原數組的複製過來的元素從這個位置開始放

length：複製數組的長度

舉個代碼示例：

public static void main(String[] args) {
 int[] src = {1,2,3,4,5};
 int[] dest = new int[6];
 for (int i : dest) {
 System.out.print(i + " ");
 }
 System.out.println();
 System.arraycopy(src,0,dest,0,src.length);
 for (int i : dest) {
 System.out.print(i + " ");
 }
 }
 //運行結果：
 //0 0 0 0 0 0 
 //1 2 3 4 5 0 

看示例代碼應該能夠懂，第一次打印的時候dest只是被初始化沒有賦值，所以裡面每個元素存放的都是默認值，而int的默認值為0，所以打印出來的都是0，之後arraycopy後將src的所有數據複製到dest從0位置開始，所以打印的結果是 1 2 3 4 5 0

四、add方法

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return  
true (as specified by {@link Collection#add})
 */
 public boolean add(E e) {
 //確認當前數組大小不會發生越界異常，否者對數組進行擴容
 ensureCapacityInternal(size + 1); // Increments modCount!!
 elementData[size++] = e;
 return true;
 }
 /**
 * 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位置上
 elementData[index] = element;
 size++;
 }

添加元素之前都需要檢查一下當前的數組是否已經滿了，如果滿了就按照添加元素後的大小進行擴容。可以說在整個ArrayList類中最核心的方法就是ensureCapacityInternal了，這個方法就是用來動態擴容的。

private void ensureCapacityInternal(int minCapacity) {
 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
 //修改次數+1，主要實現快速失敗機制的
 modCount++;
 // overflow-conscious code
 //如果最小所需容量比當前數組的長度大的話就進行擴容
 if (minCapacity - elementData.length > 0)
 grow(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:
 //創建一個新的數組，長度為 newCapacity，然後將原來數組的元素複製到新數組上並返回新數組，達到動態擴容數組的目的
 elementData = Arrays.copyOf(elementData, newCapacity);
 }

在每次添加數據的時候都需要檢查一下添加數據後的長度是否大於當前數組的長度，大於的話就創建一個大小為原來數組的1.5倍的新數組，然後將原數組的數據都複製到新數組中，最後將原數組的引用指向新數組，從而達到了擴容的目標。

五、get方法

/**
 * 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);
 }
// Positional Access Operations
 @SuppressWarnings("unchecked")
 E elementData(int index) {
 return (E) elementData[index];
 }

獲取數據的方法比較簡單，直接根據數組的下標index找到元素就行了，所以查找的速度比較快。

六、delete方法

/**
 * 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)
 //在刪除位置後面的所有元素都往前挪一位
 System.arraycopy(elementData, index+1, elementData, index, 

 numMoved);
 elementData[--size] = null; // clear to let GC do its work
 return oldValue;
 }
 /**
 * 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
 * i such that
 * (o==null ? get(i)==null : o.equals(get(i)))
 * (if such an element exists). Returns true 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 true 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;
 }
 /*
 * 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
 }

刪除有兩個重載的方法，一個是傳入一個數組的下標，另一個是傳入具體的內容，但是最總還是根據equals方法查到index，然後根據index刪除元素。假設有個數組為 String[] strs = {"a","b","c","d","e"}，現在調用 remove(3),那個大概流程為：

七、ArrayList的使用：

public static void main(String[] args) {
 List list = new ArrayList<>();
 
 //添加操作
 list.add(1);
 list.add(2);
 list.add(3);
 
 //刪除操作
 list.remove(0);
 
 //查詢操作
 //1、隨機訪問：
 for (int i = 0; i < list.size(); i++) {
 System.out.println(list.get(i));
 }
 
 //增強for循環遍歷
 for (Integer integer : list) {
 System.out.println(integer);
 }
 //使用迭代器遍歷
 Iterator iterator = list.iterator();
 while (iterator.hasNext()){
 Integer integer = iterator.next();
 System.out.println(integer);
 }
 }

八、總結：

1、ArrayList的增刪改查等所有操作，其內部都是對數組進行操作。

2、ArrayList的動態擴容其本質是創建一個更大的數組。

3、每次擴容都擴大到原來的1.5倍，1.5倍是比較理想的，如果每次擴容太小的話就會頻繁擴容，每次擴容都需要進行數組的複製，性能消耗比較大，應該儘量避免。如果擴容的倍數太大可能會造成空間的浪費。

4、ArrayList允許存放null值。

九、建議：

1、在知道數據大小且後期不會在添加數據的情況下建議使用數組，而不是ArrayList；

2、初始化前估計數據量的大小，儘量指定ArrayList的初始化容量，避免進行頻繁的數組複製操作；

3、在刪除比較多場景中不建議使用ArrayList；

4、在查多刪少的場景中建議使用ArrayList，原因是這個類查找的速度非常快，時間複雜度為O(1),即不管數據量有多大，查找速度都一樣的，而且非常快。但是刪除操作是比較慢的，上面我也有提到過，ArrayList中每一次刪除一個數據，後面所有的元素都要往前挪一位。如果數據量非常大，刪除的數據剛好在第一個位置，那個後面的所有元素都要前移，時間複雜度為O(N),這樣是非常耗費時間的。

5、ArrayList是非線程安全的，如果在多線程環境中對安全的要求比較高的，建議使用 CopyOnWriteArrayList這個類，不懂得可以百度一下，或者將ArrayList轉成線程安全得，使用這種方式就可以：List list = Collections.synchronizedList(new ArrayList());

閱讀更多 Java的小本家 的文章

關鍵字: 讀書 編程語言 技術