Java集合源碼ArrayList的可視化操作過程示例詳解

更新時間：2025年06月09日 08:53:08 作者：持行非就

這篇文章主要介紹了Java集合源碼ArrayList的可視化操作過程示例詳解,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧

??1. 底層數(shù)據(jù)結(jié)構(gòu)

基于動態(tài)數(shù)組實現(xiàn)，內(nèi)部維護一個Object[]數(shù)組。本質(zhì)是數(shù)組數(shù)據(jù)結(jié)構(gòu)，底層通過拷貝擴容使得數(shù)組具備了動態(tài)增大的特性。

數(shù)組所具備的一些特性，ArrayList也同樣具備，比如、插入元素的有序性、訪問元素的地址計算等。ArrayList與普通數(shù)組的本質(zhì)區(qū)別就在于它的動態(tài)擴容特性。

集合內(nèi)可以保存什么類型元素？保存的是什么？ 這點必須明確知道集合必須保存引用類型的元素，對于基本類型是無法保存的，比如、int、long類型，但可以保持對應(yīng)的基本類型的封裝類，比如，Integer、Long。集合內(nèi)保存的是對象的引用，而非對象本身。

1.1. ArrayList的特性

有底層數(shù)據(jù)結(jié)構(gòu)所決定的特性

插入元素的有序性，而非排序，不會自動根據(jù)值排序；
元素訪問：通過數(shù)組“首地址+下標”來計算元素的存儲地址，再通過元素地址直接訪問，時間復雜度都是O(1)；
數(shù)組一但申請空間就確定不可變，所以ArrayList需要在添加元素操作時，實現(xiàn)自動擴容。

1.2. 如何設(shè)計的數(shù)據(jù)結(jié)構(gòu)

以下是ArrayList類結(jié)構(gòu)與字段

public class ArrayList<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, Serializable {
    private static final long serialVersionUID = 8683452581122892189L;
    /** 默認初始容量 */ 
    private static final int DEFAULT_CAPACITY = 10;
    /** 空實例數(shù)組（無延遲擴容） */
    private static final Object[] EMPTY_ELEMENTDATA = {};
    /** 默認構(gòu)造后首次擴容使用的空數(shù)組 */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    /** 閾值：最大數(shù)組大小 */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    /** 真正存儲元素的數(shù)組；構(gòu)造時或賦予 EMPTY_* 共享數(shù)組 */
    transient Object[] elementData;
    /** 當前元素個數(shù) */
    private int size;
    /** 用于 Fail-Fast 的修改計數(shù)器 */
    protected transient int modCount;
    // …
}

真正存儲元素的成員變量Object[] elementData和保存數(shù)組大小的size，其它字段多半服務(wù)于動態(tài)擴容。

MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 為什么減8？因為數(shù)組頭需要占用一些空間，8位剛好一個字節(jié)，故最小減8，使得ArrayList盡可能存儲更多數(shù)據(jù)，但正常開發(fā)不可能保存這么大數(shù)據(jù)集合，Integer.MAX_VALUE可以保持十億級了，你減個1024都沒問題。

modCount用于記錄擴容次數(shù)，在迭代器中若存在并發(fā)修改，則快速失效拋出異常。

我們從本質(zhì)去學習技術(shù)：集合的作用是什么？

集合的作用是將數(shù)據(jù)以特定結(jié)構(gòu)存儲在內(nèi)存中，并且方便開發(fā)者進行操作。

存儲：開辟內(nèi)存空間，寫入數(shù)據(jù)；在Java語言中無需開發(fā)者手動申請內(nèi)存空間，只需要關(guān)注數(shù)據(jù)寫入即可；
操作：無非就是增刪查改，只不過現(xiàn)在操作的是內(nèi)存中的數(shù)據(jù)罷了。

??2. 元素插入（增）

方法分類

ArrayList 的 add 方法有兩個重載版本，對應(yīng)不同的用法：

add(E e) —— 在數(shù)組末尾插入；
add(int index, E element) —— 在指定索引下標插入。

2.1. 在數(shù)組末尾插入

使用方法 add(E e)，以下是jdk8的源碼

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

插入數(shù)據(jù)的過程

調(diào)用 ensureCapacityInternal 確保數(shù)組足夠大；
將元素寫入 elementData[size]；
size++ 并返回。

可視化感受下：無參構(gòu)造創(chuàng)建ArrayList集合，然后插入五個元素，首次add需要擴容數(shù)組為10（詳細的擴容流程看后面章節(jié)），效果如圖

2.2. 指定索引下標插入

使用方法： add(int index, E element)

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++;
}

插入數(shù)據(jù)的過程

檢查是否越界；
調(diào)用 ensureCapacityInternal 確保數(shù)組足夠大；
將坐標index后的元素都往后移動一位；
將元素寫入 elementData[size]；
size++ 。

演示在索引下標插入元素，效果如圖：

2.3. ensureCapacityInternal 與 grow 擴容流程

為了好查閱源碼，簡單調(diào)整了下，jdk源碼基本如下

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 延遲初始化：第一次調(diào)用 ensureCapacity 時，將容量至少設(shè)置為 DEFAULT_CAPACITY（10）
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++; // 用于迭代時快速失敗
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // 舊容量
    int oldCapacity = elementData.length;
    // 新容量 = 舊容量 + 舊容量>>1 （1.5 倍擴容）
    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);
}

延遲初始化：無參構(gòu)造后 elementData 引用一個長度為 0 的共享常量數(shù)組。
modCount：每次結(jié)構(gòu)修改（如擴容、增刪）都會自增，配合迭代器檢查并發(fā)修改。
擴容策略：oldCapacity + (oldCapacity >> 1)，右移一位等于除于2，所以newCapacity為原來的1.5 倍，以權(quán)衡空間和拷貝成本。

ArrayList如果不指定大小初始大小為0，首次add才進行首次擴容，擴容大小為10，這個默認的初始容量DEFAULT_CAPACITY在首層插入數(shù)據(jù)才會使用到。故此，在創(chuàng)建ArrayList時最好指定大小，最佳情況是創(chuàng)建時就知道集合的大小。

詳細可見構(gòu)造方法源碼

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // 指定初始容量大于0時
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
// 無參構(gòu)造方法
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

擴容可視化過程：插入第11個元素的擴容過程

2.4. 擴容時才對modCount 自增合理嗎？

不合理。因為你插入新的數(shù)據(jù)沒有擴容的情況下，集合申請的內(nèi)存空間不變，但是集合保存元素的大小發(fā)生了變化，這和移除元素一樣，集合也是發(fā)生了變化的，所以在后續(xù)的jdk版本中，add操作加入了modCount++;。

以下是jdk11的add源碼：首行就對modCount做了自增

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

2.5. 允許null和可重復插入？

ArrayList集合內(nèi)保存的是對象的引用，在Java語言中，引用是可以指向null的，故ArrayList集合可以保存null。在元素插入時并沒有對元素進行重復檢查，故可以保存重復數(shù)據(jù)，包括重復的null。

List 接口在 javadoc 里就明確說了：

允許所有元素（包括 null），允許重復插入；
如果你需要“元素唯一”或“禁止空值”，Java 提供了其他集合類型（如實現(xiàn)了 Set 接口的 HashSet/LinkedHashSet/TreeSet，或者在 Java 9+ 可以用 List.of(...) 構(gòu)造的不可空、不可變的列表）

實現(xiàn)簡單高效ArrayList 底層用一塊連續(xù)的 Object[] 數(shù)組存儲元素：

插入 null 只不過是往數(shù)組里賦一個 null，跟存任何其他對象沒區(qū)別；
重復插入只是把同一個引用賦給不同索引，也沒有額外開銷；
如果強行在 add() 里做“非空檢查”或“去重”，不僅會增加每次插入的開銷，還會破壞它作為通用、輕量列表的設(shè)計初衷。

??3. 修改元素（改）

根據(jù)指定索引進行覆蓋E set(int index, E element)

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

這個很簡單，檢查是否越界，暫存舊值，覆蓋數(shù)組對應(yīng)下標的值，返回舊值。

修改索引元素可視化過程：

??4. 移除元素（刪）

方法分類

ArrayList 的 remove 方法有兩個重載版本，對應(yīng)不同的用法：

remove(int index) —— 按索引刪除；
remove(Object o) —— 按對象值刪除。

4.1. 指定索引刪除

使用到的方法：remove(int index)

public E remove(int index) {
    rangeCheck(index); // 檢查索引是否合法
    modCount++;        // 修改次數(shù)+1，支持 fail-fast
    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;
}

分析：

使用 System.arraycopy() 將后面所有元素向前移動一位；
最壞情況是刪除索引 0，移動 n-1 個元素；
修改 size，清除最后一個元素引用。

刪除索引元素的可視化過程：

4.2. 按照對象值刪除

使用到的方法：remove(Object o)

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;
}

配套的 fastRemove(int index) 實現(xiàn)如下：

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;
}

分析：

先線性查找目標元素，最多比較 n 次；
然后移除元素，最多移動 n-1 個；
所以總操作是一次“線性查找 + 線性移動”。

避免在大列表中頻繁刪除中間元素（尤其在循環(huán)中刪除），否則容易退化為 O(n²)。

對比按照索引刪除，多了一步元素查找對比，其它基本一致。

按照對象值刪除元素的可視化過程：

??5. 獲取和檢索元素（查）

5.1. 獲取元素

根據(jù)索引獲取元素：get(int index)

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

檢查是否越界，然后根據(jù)下標索引獲取元素。

5.2. 檢索元素

在 ArrayList 中，檢索某個元素（不是通過索引，而是查找某個值是否存在，或其位置）主要通過以下兩個方法完成：

1) 判斷是否包含某個元素

根據(jù)對象值判斷集合中是否存在：contains(Object o)

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

這個方法內(nèi)部調(diào)用了 indexOf 方法。它返回一個布爾值，表示某個元素是否存在于列表中。

2) 返回元素首次出現(xiàn)的索引

根據(jù)對象值檢索首次出現(xiàn)的位置：indexOf(Object o)

跟按照對象值刪除的檢索過程一致，可查看上面的可視化過程動圖。

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;
}

如果查找的是 null，就用 == 比較；如果是非 null 對象，則用 equals() 方法逐個比較。從頭遍歷，找到第一個匹配項的索引。

3) 返回元素最后一次出現(xiàn)的索引

根據(jù)對象值檢索最后出現(xiàn)的位置：lastIndexOf(Object o)

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size - 1; i >= 0; i--)
            if (elementData[i] == null)
                return i;
    } else {
        for (int i = size - 1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

與 indexOf 類似，但從尾部開始向前查找。

6. ArrayList 的迭代器（Iterator）

6.1. 什么是迭代器？

迭代器（Iterator）是 Java 集合框架中用于遍歷集合元素的工具。
ArrayList 提供了兩種主要的迭代方式：

Iterator<E>：基礎(chǔ)的迭代器接口（只支持單向遍歷）
ListIterator<E>：是 Iterator 的子接口，支持雙向遍歷、修改元素、獲取索引等高級功能

6.2. iterator迭代器

源碼（位于 ArrayList.java）：

public Iterator<E> iterator() {
    return new Itr();
}

這會返回一個內(nèi)部類 Itr 的實例。

1) Itr 內(nèi)部類的核心源碼（簡化版）：

private class Itr implements Iterator<E> {
    int cursor = 0;       // 下一個要返回的元素索引
    int lastRet = -1;     // 上一個返回的元素索引，若沒有則為 -1
    int expectedModCount = modCount;  // 用于檢測并發(fā)修改
    public boolean hasNext() {
        return cursor != size;
    }
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    }
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

2) `modCount` 與并發(fā)修改檢查（fail-fast）

modCount 是 ArrayList 中用于記錄結(jié)構(gòu)性修改（如添加、刪除元素）次數(shù)的字段。
迭代器創(chuàng)建時保存了當前的 modCount 到 expectedModCount。
如果在迭代期間集合發(fā)生結(jié)構(gòu)性修改，modCount != expectedModCount，就會拋出 ConcurrentModificationException。

這就是所謂的 fail-fast機制。

3) 示例代碼

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    System.out.println(s);
}

6.3. ListIterator更強大的雙向迭代器

1) 增強版迭代器簡述

通過 list.listIterator() 或者listIterator(int index)來獲取，本質(zhì)都是返回new ListItr(index)對象。ListItr是Itr的子類）private class ListItr extends Itr implements ListIterator<E>，是增強版迭代器。

ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
    System.out.println(it.next());
}
while (it.hasPrevious()) {
    System.out.println(it.previous());
}

額外支持：

hasPrevious(), previous()
add(E e), remove(), set(E e)
nextIndex(), previousIndex()

2) 示例代碼

反序遍歷案例

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class ListIteratorReverseDemo {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("Dog");
        list.add("Cat");
        list.add("Bird");
        list.add("Fish");
        System.out.println("原始列表: " + list);
        ListIterator<String> iterator = list.listIterator(list.size()); // 從末尾開始
        while (iterator.hasPrevious()) {
            String animal = iterator.previous();
            // 替換元素
            if (animal.equals("Cat")) {
                iterator.set("Tiger"); // 將 Cat 替換為 Tiger
            }
            // 刪除元素
            if (animal.equals("Bird")) {
                iterator.remove(); // 刪除 Bird
            }
            // 在 Fish 前插入一個元素
            if (animal.equals("Fish")) {
                iterator.add("Whale"); // 插入 Whale（在 Fish 之前）
            }
        }
        System.out.println("修改后的列表: " + list);
    }
}

6.4. 時間復雜度

每個迭代器的 next()、hasNext() 操作時間復雜度都是 O(1)。
但是若在 remove() 中觸發(fā) ArrayList 的 remove(index)，那是 O(n)，因為后面的元素要移動。

6.5. 注意事項

在使用 for-each 或 iterator 遍歷時，不要直接修改原始集合（如調(diào)用 add()、remove()），否則會拋出 ConcurrentModificationException。
如果需要在遍歷中安全地修改集合，可以使用 ListIterator 的 remove() 或 add() 方法，它是支持修改的。

7. 線程安全問題

ArrayList是線程不安全的。

舉個例子

List<Integer> list = new ArrayList<>();
Runnable task = () -> {
    for (int i = 0; i < 1000; i++) {
        list.add(i);  // 非線程安全
    }
};
Thread t1 = new Thread(task);
Thread t2 = new Thread(task);
t1.start();
t2.start();
t1.join();
t2.join();
System.out.println("最終大小: " + list.size()); // 不一定是 2000

不過只有 ArrayList 作為共享變量時，才需要考慮線程安全問題，當 ArrayList 集合作為方法內(nèi)的局部變量時，無需考慮線程安全的問題。

解決安全問題的一些方法

類注釋中推薦我們使用 Collections#synchronizedList 來保證線程安全，SynchronizedList 是通過在每個方法上面加上鎖來實現(xiàn)，雖然實現(xiàn)了線程安全，但是性能大大降低。

使用方式

List<Integer> syncList = Collections.synchronizedList(new ArrayList<>());
// 遍歷時手動加鎖
synchronized(syncList) {
    for (Integer i : syncList) {
        // 安全遍歷
    }
}

也可以使用這個集合：CopyOnWriteArrayList（推薦用于讀多寫少）

List<String> cowList = new CopyOnWriteArrayList<>();

特性：

所有寫操作（add/remove/set）都會復制一份數(shù)組再修改；
不會拋出 ConcurrentModificationException；
非常適合讀多寫少的場景。

缺點：

寫操作開銷大，性能比 ArrayList 差很多。

8. 時間復雜度匯總

操作	時間復雜度	備注
插入元素	O(1)，擴容單次為 O(n)	`add(E)`
隨機插入	O(n)，元素拷貝	`add(index,E)`
指定索引刪除	O(n)，指定索引刪除	`remove(index)`
指定對象值刪除	O(n)，查找 + 移動	`remove(Object)`
指定索引修改	O(1)	`set(index,E)`
獲取元素	O(1)	`get(index)`
檢索元素	都為`O(n)`	`indexOf(Object)`/ `lastIndexOf(Object)`

9. 總結(jié)

在使用ArrayList集合時，需要關(guān)注以下特性：隨機獲取/修改快、插入/刪除慢、擴容性能問題、并發(fā)線程安全問題。

關(guān)于元素插入、檢索、修改、刪除、擴容過程等操作過程，完整的視頻鏈接：https://www.bilibili.com/video/BV1KET2zGEm4/

到此這篇關(guān)于Java集合源碼--ArrayList的可視化操作過程的文章就介紹到這了,更多相關(guān)Java集合源碼--ArrayList的可視化操作過程內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线