Java集合源碼剖析之ArrayList

1 ArrayList概括
- 1.1 特性
- 1.2 資料結構
2 ArrayList源碼剖析
- 2.1 繼承關系
- 2.2 成員屬性
- 2.3 構造方法
- 2.4 核心方法
- - 2.4.1 添加元素
  - 2.4.2 查詢元素
  - 2.4.3 修改元素
  - 2.4.4 删除元素
  - 2.4.5 數組擴容
  - 2.4.6 其它方法

1 ArrayList概括

1.1 特性

ArrayList是基于數組實作的有序集合，它的容量可以動态的增長和縮減，預設容量為10，最大容量為Integer.MAX_VALUE。

ArrayList實作了RandomAccess接口，查找元素時可以通過數組下标快速的随機查找，但插入或删除元素時通常需要移動元素，是以，ArrayList更适合需要頻繁的查找或修改的應用場景，而不太适合需要頻繁的插入或删除的應用場景。如果想在ArrayList中添加大量元素，可通過ensureCapacity()方法指定合适的容量，進而減少擴容的次數以達到提高性能的目的。

ArrayList是非線程安全的，隻能在單線程環境下使用，多線程環境下可以使用concurrent并發包下的CopyOnWriteArrayList類。

ArrayList中的元素可以重複，且可以為null值。

特性總結：有序、動态擴容、随機通路、非線程安全、元素可重複。

1.2 資料結構

ArrayList是使用Object數組實作的，其資料結構圖如下圖所示：

Java集合源碼剖析之ArrayList1 ArrayList概括2 ArrayList源碼剖析

2 ArrayList源碼剖析

2.1 繼承關系

ArrayList的層次結構如處圖所示：

Java集合源碼剖析之ArrayList1 ArrayList概括2 ArrayList源碼剖析

ArrayList的繼承關系下所示：

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

2.2 成員屬性

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 數組的預設容量
     */
    private static final int DEFAULT_CAPACITY = 10;
    
    /**
     * 數組的預設最大容量
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 空數組
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 預設空數組
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * ArrayList用于存儲資料元素的數組
     */
    transient Object[] elementData;

    /**
     * ArrayList中實際資料元素的個數
     */
    private int size;
}

2.3 構造方法

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

    /**
     * 無參構造方法：不指定容量時，為預設空數組，預設容量為10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * 有參構造方法：指定容量時，為指定容量的數組
     */
    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(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;
        }
    }
}

2.4 核心方法

2.4.1 添加元素

/**
 * 在ArrayList中添加一個元素
 */
public boolean add(E e) {
	// 容量檢查，必要時進行擴容
    ensureCapacityInternal(size + 1);
    // 添加元素，修改實際元素的個數
    elementData[size++] = e;
    return true;
}

/**
 * 在ArrayList中指定位置添加一個元素
 */
public void add(int index, E element) {
	// 下标合法性檢查
    rangeCheckForAdd(index);
    // 容量檢查，必要時進行擴容
    ensureCapacityInternal(size + 1);
    // 移動index位置後面的元素
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    // 添加元素
    elementData[index] = element;
    // 修改實際元素的個數
    size++;
}

/**
 * 在ArrayList中批量添加元素
 */
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    // 容量檢查，必要時進行擴容
    ensureCapacityInternal(size + numNew);
    // 批量添加元素
    System.arraycopy(a, 0, elementData, size, numNew);
    // 修改實際元素的個數
    size += numNew;
    return numNew != 0;
}

/**
 * 在ArrayList中指定位置批量添加元素
 */
public boolean addAll(int index, Collection<? extends E> c) {
    // 下标合法性檢查
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    // 容量檢查，必要時進行擴容
    ensureCapacityInternal(size + numNew);
    // 計算需要移動元素的個數
    int numMoved = size - index;
    if (numMoved > 0) {
    	// 移動元素
        System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
	}
	// 批量添加元素
    System.arraycopy(a, 0, elementData, index, numNew);
    // 修改實際元素的個數
    size += numNew;
    return numNew != 0;
}

當調用add方法後，實際上會調用一系列方法，調用流程如下圖所示：

Java集合源碼剖析之ArrayList1 ArrayList概括2 ArrayList源碼剖析

上圖所示的調用流程實際上是與擴容有關，這一部分在2.4.5節中專門講解。

2.4.2 查詢元素

/**
 * 查詢指定位置的元素
 */
public E get(int index) {
	// 下标合法性檢查
    rangeCheck(index);
    // 擷取并傳回元素
    return elementData(index);
}

/**
 * 擷取指定位置的元素
 */
E elementData(int index) {
    return (E) elementData[index];
}

2.4.3 修改元素

/**
 * 修改指定位置的元素
 */
public E set(int index, E element) {
	// 下标合法性檢查
    rangeCheck(index);
    // 擷取舊元素
    E oldValue = elementData(index);
    // 設定新元素
    elementData[index] = element;
    return oldValue;
}

2.4.4 删除元素

/**
 * 删除指定位置的元素
 */
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;
    return oldValue;
}

/**
 * 删除指定元素
 */
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;
}

/*
 * 批量删除元素
 */
public boolean removeAll(Collection<?> c) {
	// 合法性檢查
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

/**
 * 清空所有元素
 */
public void clear() {
    modCount++;
    for (int i = 0; i < size; i++) {
        elementData[i] = null;
	}
    size = 0;
}

/*
 * 批量删除元素
 * @param complement 指明c中的元素是要保留的元素還是要删除的元素，true則為要保留的元素，false則為要删除的元素
 */
private boolean batchRemove(Collection<?> c, boolean complement) {
  
    final Object[] elementData = this.elementData;
    // w是批量删除後的實際元素個數
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++) {
        	// 周遊每個元素，并保留希望保留的元素
            if (c.contains(elementData[r]) == complement) {
                elementData[w++] = elementData[r];
            }
        }
    } finally {
    	// 如果還有元素沒有周遊，則把後面的元素全部向前移動
        if (r != size) {
            System.arraycopy(elementData, r, elementData, w, size - r);
            w += size - r;
        }
        // 如果有元素被删除了
        if (w != size) {
        	// 清空後面的元素
            for (int i = w; i < size; i++) {
                elementData[i] = null;
            }
            modCount += size - w;
            // 修改批量删除之後的實際元素的個數
            size = w;
            modified = true;
        }
    }
    return modified;
}



/*
 * 快速移動元素
 */
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;
}

2.4.5 數組擴容

/**
 * 容量檢查，必要時進行擴容
 * @param minCapacity 此次操作後的實際元素個數
 */
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

/**
 * 計算完成此次操作之後的容量
 * @param minCapacity 此次操作後的實際元素個數
 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果存儲資料元素的數組為空數組，則此次操作後的容量應該為max(DEFAULT_CAPACITY, minCapacity)
    // 如果存儲資料元素的數組不為空數組，則此次操作後的容量應該為minCapacity
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

/**
 * 查檢是否要進行擴容
 * @param minCapacity 此次操作後的實際容量
 */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 如果此次操作之後的實際容量比目前容量要大，則進行擴容，否則不擴容
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

/**
 * 擴容
 * @param minCapacity 此次操作後的實際容量
 */
private void grow(int minCapacity) {
    // 儲存現有的資料
    int oldCapacity = elementData.length;
    // 計算的新容量 = 目前容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 計算的新容量 = max(計算的新容量 , 此次操作後的實際容量)
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    // 如果計算的新容量比預設的最大容量還要大，則計算的新容量 = 允許的最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        newCapacity = hugeCapacity(minCapacity);
    }
    // 按照計算的新容量進行擴容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

/**
 * 計算允許的最大容量
 * @param minCapacity 此次操作後的實際容量
 */
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) {
        throw new OutOfMemoryError();
    }
    // 如果此次操作後的實際容量比預設最大容量要大，則允許的最大容量為Integer.MAX_VALUE，否則為MAX_ARRAY_SIZE
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

擴容總結：正常情況下擴容為原來的1.5倍，否則擴容為最大值（Integer.MAX_VALUE 或 MAX_ARRAY_SIZE）

2.4.6 其它方法

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

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

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

public <T> T[] toArray(T[] a) {
    if (a.length < size) {
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    }
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size) {
        a[size] = null;
    }
    return a;
}

如果覺得本文對您有幫助，請關注部落客的微信公衆号，會經常分享一些Java和大資料方面的技術案例！

Java集合源碼剖析之ArrayList1 ArrayList概括2 ArrayList源碼剖析

Java集合源碼剖析之ArrayList1 ArrayList概括2 ArrayList源碼剖析

Java集合源碼剖析之ArrayList

1 ArrayList概括

1.1 特性

1.2 資料結構

2 ArrayList源碼剖析

2.1 繼承關系

2.2 成員屬性

2.3 構造方法

2.4 核心方法

2.4.1 添加元素

2.4.2 查詢元素

2.4.3 修改元素

2.4.4 删除元素

2.4.5 數組擴容

2.4.6 其它方法

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method