ArrayList的原理和使用方法

這篇文章主要講解了“ArrayList的原理和使用方法”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“ArrayList的原理和使用方法”吧！

前言

ArrayList 作為 Java 集合框架中最常用的類，在一般情況下，用它存儲集合數據最適合不過。知其然知其所以然，為了能更好地認識和使用 ArrayList，本文將從下面幾方面深入理解 ArrayList：

• 為什么不用數組，用 ArrayList

• ArrayList 特性的源碼分析

• Java 8 后 的 ArrayList

• 正確的 ArrayList 使用姿勢

為什么不用數組，用 ArrayList。

在 Java 語言中，由于普通數組受到長度限制，初始化時就需要限定數組長度，無法根據元素個數動態擴容，并且 Java 數組供開發者調用方法有限，只有取元素，獲取數組長度和添加元素一些簡單操作。后臺在 Java 1.2 引入了強大豐富的 Collection 框架，其中用 ArrayList 來作為可動態擴容數組的列表實現來代替 Array 在日常開發的使用，ArrayList 實現所有列表的操作方法，方便開發者操作列表集合。這里我們先列舉下 ArrayList 的主要特點，在后文進行一一闡述：

• 有序存儲元素

• 允許元素重復，允許存儲 null 值

• 支持動態擴容

• 非線程安全

為了更好地認識 ArrayList，我們首先來看下從 ArrayList 的UML類圖：

從上圖可以看出 ArrayList 繼承了 AbstractList, 直接實現了 Cloneable, Serializable，RandomAccess 類型標志接口。

• AbstractList 作為列表的抽象實現，將元素的增刪改查都交給了具體的子類去實現，在元素的迭代遍歷的操作上提供了默認實現。

• Cloneable 接口的實現，表示了 ArrayList 支持調用 Object 的 clone 方法，實現 ArrayList 的拷貝。

• Serializable 接口實現，說明了 ArrayList 還支持序列化和反序列操作，具有固定的 serialVersionUID 屬性值。

• RandomAccess 接口實現，表示 ArrayList 里的元素可以被高效效率的隨機訪問，以下標數字的方式獲取元素。實現 RandomAccess 接口的列表上在遍歷時可直接使用普通的for循環方式，并且執行效率上給迭代器方式更高。

ArrayList 源碼分析

進入 ArrayList 源代碼，從類的結構里很快就能看到 ArrayList 的兩個重要成員變量：elementData 和 size。

• elementData 是一個 Object 數組，存放的元素，正是外部需要存放到 ArrayList 的元素，即 ArrayList 對象維護著這個對象數組 Object[]，對外提供的增刪改查以及遍歷都是與這個數組有關，也因此添加到 ArrayList 的元素都是有序地存儲在數組對象 elementData 中。

• size 字段表示著當前添加到 ArrayList 的元素個數，需要注意的是它必定小于等于數組對象 elementData 的長度。一旦當 size 與 elementData 長度相同，并且還在往列表里添加元素時，ArrayList 就會執行擴容操作，用一個更長的數組對象存儲先前的元素。

由于底層維護的是一個對象數組，所以向 ArrayList 集合添加的元素自然是可以重復的，允許為 null 的，并且它們的索引位置各不一樣。

如何擴容

了解完 ArrayList 為何有序存儲元素和元素可以重復，我們再來看下作為動態數組列表，底層擴容是如何實現的。

首先，要確定下擴容的時機會是在哪里，就如上面描述 size 字段時提到的，當 size 與 elementData 長度相同，此刻再添加一個元素到集合就會出現容量不夠的情況，需要進行擴容，也就是說 ArrayList 的擴容操作發生在添加方法中，并且滿足一定條件時才會發生。

現在我們再來看下 ArrayList 類的代碼結構，可以看到有四個添加元素的方法，分為兩類：添加單個元素和添加另一個集合內的所有元素。

先從簡單的方法下手分析，查看 add(E):boolean 方法實現：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e; 
    return true;
}

從上面可以看出第三行代碼是簡單地添加單個元素，并讓 size 遞增加 1；那么擴容實現就在 ensureCapacityInternal 方法中，這里傳入參數為 size+1，就是要在真正添加元素前判斷添加后的元素個數，也就是集合所需要的最小容量是否會超過原數組的長度。再看下這個 ensureCapacityInternal 方法實現

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData,minCapacity));
}

其內部仍有兩個方法調用，首先看下比較簡單的 calculateCapacity 方法：

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

當 elementData 與 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 相等，也就是空數組時，返回一個可添加元素的默認最小容量值 DEFAULT_CAPACITY 對應的10 ，否則按照傳入的 size +1 為最小容量值；執行完之后接著看 ensureExplicitCapacity 方法：

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

    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

從代碼中可以看到擴容實現在 grow 方法之中，并且只有當數組長度小于所需要的最小容量時執行：當數組存儲元素已滿，無法再存儲將新加入的元素。

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

進一步跳轉到 grow 方法的實現，可以看到第8行利用工具類方法 java.util.Arrays#copyOf(T[], int) ,對原有數組進行拷貝，將內部所有的元素存放到長度為 newCapacity 的新數組中，并將對應新數組的引用賦值給 elementData。此刻 ArrayList 內部引用的對象就是更新長度了的新數組，實現效果就如下圖一樣：

現在我們再來關注下代表數組新容量的 newCapacity 被調整為多少。首先 newCapacity 通過 oldCapacity + (oldCapacity >> 1) 計算獲得，使用位運算將原容量值 oldCapacity 通過右移一位，獲得其一半的值（向下取整）, 然后加上原來的容量值，那么就是原容量值 oldCapacity 的1.5倍。

>> 右位運算符，會將左操作數進行右移，相當于除以2，并且向下取整，比如表達式 (7 >> 1) == 3 結果為真。

當計算得到的 newCapacity 仍然小于傳入最小容量值時，說明當前數組個數為空，采用默認的 DEFAULT_CAPACITY作為容量值分配數組。

額外需要注意的是還有最大數組個數的判斷，MAX_ARRAY_SIZE 在文件對應的代碼定義如下：

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

ArrayList 存儲元素個數有最大限制，如果超過限制就會導致 JVM 拋出 OutOfMemoryError 異常。

到這里 java.util.ArrayList#add(E) 方法的擴容邏輯就分析結束了。類似的，在其他添加元素的方法里實現內我們都可以看到 ensureCapacityInternal 方法的調用，在真正操作底層數組前都會進行容量的確認，容量不夠則進行動態擴容。

序列化與反序列化

transient Object[] elementData;

在 ArrayList 源碼看到的 elementData 帶有關鍵字 transient，而通常 transient 關鍵字修飾了字段則表示該字段不會被序列化，但是 ArrayList 實現了序列化接口，并且提供的序列化方法 writeObject 與反序列化方法 readObject 的實現, 這是如何做到的呢？

我們首先來看下 ArrayList 進行序列化的代碼：

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
    int expectedModCount = modCount;
    s.defaultWriteObject();

    s.writeInt(size);

    for (int i = 0; i < size; i++) {
        s.writeObject(elementData[i]);
    }

    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

第4行代碼首先將當前對象的非 static 修飾，非 transient 修飾的字段寫出到流中；第6行將寫出元素的個數作為容量。

接下來就是通過循環將包含的所有元素寫出到流，在這一步可以看出 ArrayList 在自己實現的序列化方法中沒有將無存儲數據的內存空間進行序列化，節省了空間和時間。

同樣地，在反序列化中根據讀進來的流數據中獲取 size 屬性，然后進行數組的擴容，最后將流數據中讀到的所有元素數據存放到持有的對象數組中。

private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    s.defaultReadObject();

    s.readInt(); // ignored

    if (size > 0) {
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        ensureCapacityInternal(size);

        Object[] a = elementData;
        for (int i = 0; i < size; i++) {
            a[i] = s.readObject();
        }
    }
}

關于拷貝

針對列表元素的拷貝，ArrayList 提供自定義的 clone 實現如下：

public Object clone() {
  try {
    ArrayList<?> v = (ArrayList<?>) super.clone();
    v.elementData = Arrays.copyOf(elementData, size);
    v.modCount = 0;
    return v;
  } catch (CloneNotSupportedException e) {
    // this shouldn't happen, since we are Cloneable
    throw new InternalError(e);
  }
}

從上述代碼可以清楚看出執行的 copyOf 操作是一次淺拷貝操作，原 ArrayList 對象的元素不會被拷貝一份存到新的 ArrayList 對象然后返回，它們各自的字段 elementData 里各位置存放的都是一樣元素的引用，一旦哪個列表修改了數組中的某個元素，另一個列表也將受到影響。

JDK 1.8 后的 ArrayList

從源碼角度分析完 ArrayList 的特性之后，我們再來看下 JDK 1.8 之后在 ArrayList 類上有什么新的變化。

新增 removeIf 方法

removeIf 是 Collection 接口新增的接口方法，ArrayList 由于父類實現該接口，所以也有這個方法。removeIf 方法用于進行指定條件的從數組中刪除元素。

public boolean removeIf(Predicate<? super E> filter){...}

傳入一個代表條件的函數式接口參數 Predicate，也就是Lambda 表達式進行條件匹配，如果條件為 true， 則將該元素從數組中刪除，例如下方代碼示例：

List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
numbers.removeIf(i -> i % 2 == 0);
System.out.println(numbers); // [1, 3, 5, 7, 9]

新增 spliterator 方法

這個方法也是來自于 Collection 接口，ArrayList 對此方法進行了重寫。該方法會返回 ListSpliterator 實例，該實例用于遍歷和分離容器所存儲的元素。

@Override
public Spliterator<E> spliterator() {
    return new ArrayListSpliterator<>(this, 0, -1, 0);
}

在 ArrayList 的實現中，該方法返回一個內部靜態類對象 ArrayListSpliterator，通過它可以就可以集合元素進行操作。

它的主要操作方法有下面三種：

• tryAdvance 迭代單個元素，類似于 iterator.next()

• forEachRemaining 迭代剩余元素

• trySplit 將元素切分成兩部分并行處理,但需要注意的 Spliterator 并不是線程安全的。

雖然這個三個方法不常用，還是有必要了解，可以簡單看下方法的使用方式

ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(1,2,3,4,5,6));
Spliterator<Integer> numbers = numbers.spliterator();

numbers.tryAdvance( e -> System.out.println( e ) ); // 1

numbers.forEachRemaining( e -> System.out.println( e ) ); // 2 3 4 5 6

Spliterator<Integer> numbers2 = numbers.trySplit();

numbers.forEachRemaining( e -> System.out.println( 3 ) );      //4 5 6
numbers2.forEachRemaining( e -> System.out.println( 3 ) );      //1 2 3

必會的使用姿勢

接觸了 ArrayList 源碼和新API 之后，我們最后學習如何在平常開發中高效地使用 ArrayList。

高效的初始化

ArrayList 實現了三個構造函數, 默認創建時會分配到空數組對象 EMPTY_ELEMENTDATA；第二個是傳入一個集合類型數據進行初始化；第三個允許傳入集合長度的初始化值，也就是數組長度。由于每次數組長度不夠會導致擴容，重新申請更長的內存空間，并進行復制。而讓我們初始化 ArrayList 指定數組初始大小，可以減少數組的擴容次數，提供性能。

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 ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

元素遍歷

JDK 1.8前，ArrayList 只支持3種遍歷方式：迭代器遍歷，普通 for 循環，for-each 增強，在 JDK1.8 引入了 Stream API 之后，同屬于 Collection 集合的 ArrayList，可以使用 stream.foreach() 方法一個個地獲取元素：

ArrayList<String> names = new ArrayList<String>(Arrays.asList( "alex", "brian", "charles"));
names.forEach(name -> System.out.println(name)); // alex brian charles

轉換 Array

ArrayList 提供兩個方法用于列表向數組的轉換

public Object[] toArray();
public <T> T[] toArray(T[] a);

1. 第一個方法直接返回 Object 類型數組

2. 在第二個方法中，返回數組的類型為所傳入的指定數組的類型。 并且如果列表的長度符合傳入的數組，將元素拷貝后數組后，則在其中返回數組。 否則，將根據傳入數組的類型和列表的大小重新分配一個新數組，拷貝完成后再返回。

從上述描述可以看出使用第二個方法更加合適，能保留原先類型：

ArrayList<String> list = new ArrayList<>(4);
list.add("A");
list.add("B");
list.add("C");
list.add("D");

String[] array = list.toArray(new String[list.size()]);
System.out.println(Arrays.toString(array)); // [A, B, C, D]

應對多線程

在這里需要說明的是 ArrayList 本身是非線程安全的，如果需要使用線程安全的列表通常采用的方式是 java.util.Collections#synchronizedList(java.util.List<T>) 或者 使用 Vector 類代替。還有一種方式是使用并發容器類 CopyOnWriteArrayList 在多線程中使用，它底層通過創建原數組的副本來實現更新，添加等原本需同步的操作，不僅線程安全，減少了對線程的同步操作。

應對頭部結點的增刪

ArrayList是數組實現的，使用的是連續的內存空間，當有在數組頭部將元素添加或者刪除的時候，需要對頭部以后的數據進行復制并重新排序，效率很低。針對有大量類似操作的場景，出于性能考慮，我們應該使用 LinkedList 代替。由于LinkedList 是基于鏈表實現，當需要操作的元素位置位于List 前半段時，就從頭開始遍歷，馬上找到后將把元素在相應的位置進行插入或者刪除操作。

感謝各位的閱讀，以上就是“ArrayList的原理和使用方法”的內容了，經過本文的學習后，相信大家對ArrayList的原理和使用方法這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！