重識 ArrayList

来源:https://www.cnblogs.com/one12138/archive/2019/09/03/11456147.html
-Advertisement-
Play Games

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


前言

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 的實現和常見使用，作為基礎容器集合，越是多些瞭解，對我們日常使用越順手。由於上文提到了另一個列表集合 LinkedList，它與 ArrayList 實現方式不同，使用場景也不同，將作為下一篇文章分析的集合登場，感興趣的小伙伴歡迎關註我的微信公眾號，期待更新。

參考

  • https://www.cnblogs.com/skywang12345/p/3308556.html
  • https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
  • https://yuqirong.me/2018/01/21/ArrayList%E5%86%85%E9%83%A8%E5%8E%9F%E7%90%86%E8%A7%A3%E6%9E%90/
  • https://juejin.im/post/5a58aa62f265da3e4d72a51b
  • https://howtodoinjava.com/java-arraylist/
  • http://cmsblogs.com/?p=4727

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 演算法：線性查找（重點isFlag標誌）
    package com.atguigu;public class Main { public static void main(String[] args) { String[] arr=new String[]{"JJ","DD","MM","BB","GG","AA"}; //線性查找 Stri ...
  • ArrayList擴容
    ArrayList有三種初始化方式： 1.指定大小初始化 public ArrayList(int initialCapacity) 2.傳入一個Collection對象初始化，並將對象中的數據添加到ArrayList中 public ArrayList(Collection<? extends E ...
  • 演算法：數組的反轉
    package com.atguigu;public class Fanzhuan { public static void main(String[] args) { //數組的反轉 //方法一 String[] arr=new String[]{"JJ","DD","MM","BB","GG", ...
  • goroutine,channel
    Go語言中有個概念叫做goroutine, 這類似我們熟知的線程，但是更輕。 以下的程式，我們串列地去執行兩次loop函數: go package main import "fmt" func main() { loop() loop() } func loop() { for i := 0; i ...
  • 07-常用內置對象
    數組Array 1.數組的創建方式 字面量方式創建： 使用構造函數的方式創建（使用new關鍵字對構造函數進行創建對象） 2.數組的賦值 3.數組的常用方法 3.1 concat：把幾個數組合併成一個數組 3.2 join：將數組中的元素使用指定的字元串連接起來，他會形成一個新的字元串 3.3 將數組 ...
  • GIL(全局解釋器鎖)
    來一道GIL面試題 描述python GIL的概念，以及他對python多線程的影響，編寫一個多線程抓取網頁的程式，並闡明多線程抓取程式是否比單線程有所提升，並解釋原因。 參考答案： 1.python語言和GIL沒有關係，僅僅是由於歷史原因在CPython虛擬機（解釋器），難以移除GIL 2.GIL ...
  • 演算法：array1和array2地址值相同，都指向堆空間的唯一的一個數組實體（不是數組的複製）
    package com.atguigu;public class fuzhi { public static void main(String[] args) { int[] array1=new int[]{2,3,5,7,11,13,17,19};//靜態初始化 int[] array2; fo ...
  • Java基礎知識點總結
    1.源文件聲明規則2.JAVA基本類型void3.數據類型預設值4.自動類型轉換5.Java變數類型6.Java局部變數7.訪問控制修飾符8.父類與子類的訪問控制9.instanceof運算符 1.源文件聲明規則 一個源文件中只能有一個public類 一個源文件中可以有多個非public類 源文件名 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類