ArrayList類【JDK源碼分析】

Arrays類【JDK源碼分析】

前言
推薦
說明
ArrayList類

基本資訊
字段摘要
構造方法摘要
方法摘要
字段詳細資訊
構造方法詳細資訊
方法詳細資訊

trimToSize
ensureCapacity
add
remove
iterator

總結
最後

前言

2022/11/2

路漫漫其修遠兮,吾将上下而求索

本文是根據jdk學習所做筆記

僅供學習交流使用，轉載注明出處

說明

以下内容是結合很多資料進行編寫的

源碼為jdk1.8的

斜體樣式為自己的思考

下劃線為自己所畫的重點

ArrayList類

基本資訊

java.util

類 ArrayList< E>

java.lang.Object

繼承者 java.util.AbstractCollection< E>

繼承者 java.util.AbstractList< E>

繼承者 java.util.ArrayList< E>

所有已實作的接口：

Serializable, Cloneable, Iterable< E>, Collection< E>, List< E>, RandomAccess

直接已知子類：

AttributeList, RoleList, RoleUnresolvedList

public class ArrayList< E>

extends AbstractList< E>

implements List< E>, RandomAccess, Cloneable, SerializableList

接口的大小可變數組的實作。實作了所有可選清單操作，并允許包括 null 在内的所有元素。除了實作 List 接口外，此類還提供一些方法來操作内部用來存儲清單的數組的大小。（此類大緻上等同于 Vector 類，除了此類是不同步的。）

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定時間運作。add 操作以分攤的固定時間運作，也就是說，添加 n 個元素需要 O(n) 時間。其他所有操作都以線性時間運作（大體上講）。與用于 LinkedList 實作的常數因子相比，此實作的常數因子較低。

每個 ArrayList 執行個體都有一個容量。該容量是指用來存儲清單元素的數組的大小。它總是至少等于清單的大小。随着向 ArrayList 中不斷添加元素，其容量也自動增長。并未指定增長政策的細節，因為這不隻是添加元素會帶來分攤固定時間開銷那樣簡單。

在添加大量元素前，應用程式可以使用 ensureCapacity 操作來增加 ArrayList 執行個體的容量。這可以減少遞增式再配置設定的數量。

**注意，此實作不是同步的。**如果多個線程同時通路一個 ArrayList 執行個體，而其中至少一個線程從結構上修改了清單，那麼它必須保持外部同步。（結構上的修改是指任何添加或删除一個或多個元素的操作，或者顯式調整底層數組的大小；僅僅設定元素的值不是結構上的修改。）這一般通過對自然封裝該清單的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedList 方法将該清單“包裝”起來。這最好在建立時完成，以防止意外對清單進行不同步的通路：

List list = Collections.synchronizedList(new ArrayList(...));

此類的 iterator 和 listIterator 方法傳回的疊代器是快速失敗的：在建立疊代器之後，除非通過疊代器自身的 remove 或 add 方法從結構上對清單進行修改，否則在任何時間以任何方式對清單進行修改，疊代器都會抛出 ConcurrentModificationException。是以，面對并發的修改，疊代器很快就會完全失敗，而不是冒着在将來某個不确定時間發生任意不确定行為的風險。

注意，疊代器的快速失敗行為無法得到保證，因為一般來說，不可能對是否出現不同步并發修改做出任何硬性保證。快速失敗疊代器會盡最大努力抛出 ConcurrentModificationException。是以，為提高這類疊代器的正确性而編寫一個依賴于此異常的程式是錯誤的做法：疊代器的快速失敗行為應該僅用于檢測 bug。

此類是 Java Collections Framework 的成員。

從以下版本開始：

1.2

另請參見：

Collection, List, LinkedList, Vector, Collections.synchronizedList(List), 序列化表格

字段摘要

從類 java.util.AbstractList 繼承的字段

modCount

構造方法摘要

ArrayList()

構造一個初始容量為 10 的空清單。

ArrayList(Collection<? extends E> c)

構造一個包含指定 collection 的元素的清單，這些元素是按照該 collection 的疊代器傳回它們的順序排列的。

ArrayList(int initialCapacity)

構造一個具有指定初始容量的空清單。

方法摘要

boolean add(E e)

将指定的元素添加到此清單的尾部。

void add(int index, E element)

将指定的元素插入此清單中的指定位置。

boolean addAll(Collection<? extends E> c)

按照指定 collection 的疊代器所傳回的元素順序，将該 collection 中的所有元素添加到此清單的尾部。

boolean addAll(int index, Collection<? extends E> c)

從指定的位置開始，将指定 collection 中的所有元素插入到此清單中。

void clear()

移除此清單中的所有元素。

Object clone()

傳回此 ArrayList 執行個體的淺表副本。

boolean contains(Object o)

如果此清單中包含指定的元素，則傳回 true。

void ensureCapacity(int minCapacity)

如有必要，增加此 ArrayList 執行個體的容量，以確定它至少能夠容納最小容量參數所指定的元素數。

E get(int index)

傳回此清單中指定位置上的元素。

int indexOf(Object o)

傳回此清單中首次出現的指定元素的索引，或如果此清單不包含元素，則傳回 -1。

boolean isEmpty()

如果此清單中沒有元素，則傳回 true

int lastIndexOf(Object o)

傳回此清單中最後一次出現的指定元素的索引，或如果此清單不包含索引，則傳回 -1。

E remove(int index)

移除此清單中指定位置上的元素。

boolean remove(Object o)

移除此清單中首次出現的指定元素（如果存在）。

protected void removeRange(int fromIndex, int toIndex)

移除清單中索引在 fromIndex（包括）和 toIndex（不包括）之間的所有元素。

E set(int index, E element)

用指定的元素替代此清單中指定位置上的元素。

int size()

傳回此清單中的元素數。

Object[] toArray()

按适當順序（從第一個到最後一個元素）傳回包含此清單中所有元素的數組。

T[]

toArray(T[] a)

按适當順序（從第一個到最後一個元素）傳回包含此清單中所有元素的數組；傳回數組的運作時類型是指定數組的運作時類型。

void trimToSize()

将此 ArrayList 執行個體的容量調整為清單的目前大小。

從類 java.util.AbstractList 繼承的方法

equals, hashCode, iterator, listIterator, listIterator, subList

從類 java.util.AbstractCollection 繼承的方法

containsAll, removeAll, retainAll, toString

從類 java.lang.Object 繼承的方法

finalize, getClass, notify, notifyAll, wait, wait, wait

從接口 java.util.List 繼承的方法

containsAll, equals, hashCode, iterator, listIterator, listIterator, removeAll, retainAll, subList

字段詳細資訊

java.util.AbstractList

modCount

protected transient int modCount已從結構上修改此清單的次數。從結構上修改是指更改清單的大小，或者打亂清單，進而使正在進行的疊代産生錯誤的結果。

此字段由 iterator 和 listIterator 方法傳回的疊代器和清單疊代器實作使用。如果意外更改了此字段中的值，則疊代器（或清單疊代器）将抛出 ConcurrentModificationException 來響應 next、remove、previous、set 或 add 操作。在疊代期間面臨并發修改時，它提供了快速失敗行為，而不是非确定性行為。

子類是否使用此字段是可選的。如果子類希望提供快速失敗疊代器（和清單疊代器），則它隻需在其 add(int, E) 和 remove(int) 方法（以及它所重寫的、導緻清單結構上修改的任何其他方法）中增加此字段。對 add(int, E) 或 remove(int) 的單個調用向此字段添加的數量不得超過 1，否則疊代器（和清單疊代器）将抛出虛假的 ConcurrentModificationExceptions。如果某個實作不希望提供快速失敗疊代器，則可以忽略此字段。

/**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 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.
     */
    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

public ArrayList(int initialCapacity)構造一個具有指定初始容量的空清單。

參數：

initialCapacity - 清單的初始容量

抛出：

IllegalArgumentException - 如果指定的初始容量為負

ArrayList

public ArrayList()構造一個初始容量為 10 的空清單。

ArrayList

public ArrayList(Collection<? extends E> c)構造一個包含指定 collection 的元素的清單，這些元素是按照該 collection 的疊代器傳回它們的順序排列的。

參數：

c - 其元素将放置在此清單中的 collection

抛出：

NullPointerException - 如果指定的 collection 為 null

方法詳細資訊

trimToSize

public void trimToSize()

将此 ArrayList 執行個體的容量調整為清單的目前大小。應用程式可以使用此操作來最小化 ArrayList 執行個體的存儲量。

/**
     * Trims the capacity of this <tt>ArrayList</tt> instance to be the
     * list's current size.  An application can use this operation to minimize
     * the storage of an <tt>ArrayList</tt> instance.
     */
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

ensureCapacity

public void ensureCapacity(int minCapacity)

如有必要，增加此 ArrayList 執行個體的容量，以確定它至少能夠容納最小容量參數所指定的元素數。

參數：

minCapacity - 所需的最小容量

/**
     * Increases the capacity of this <tt>ArrayList</tt> instance, if
     * necessary, to ensure that it can hold at least the number of elements
     * specified by the minimum capacity argument.
     *
     * @param   minCapacity   the desired minimum capacity
     */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

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

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

/**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
     * 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;
        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:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

add

public boolean add(E e)

将指定的元素添加到此清單的尾部。

指定者：

接口 Collection 中的 add

指定者：

接口 List 中的 add

覆寫：

類 AbstractList 中的 add

參數：

e - 要添加到此清單中的元素

傳回：

true（按照 Collection.add(E) 的指定）

/**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

remove

public boolean remove(Object o)

移除此清單中首次出現的指定元素（如果存在）。如果清單不包含此元素，則清單不做改動。更确切地講，移除滿足 (o==null ? get(i)==null : o.equals(get(i))) 的最低索引的元素（如果存在此類元素）。如果清單中包含指定的元素，則傳回 true（或者等同于這種情況：如果清單由于調用而發生更改，則傳回 true）。

指定者：

接口 Collection 中的 remove

指定者：

接口 List 中的 remove

覆寫：

類 AbstractCollection 中的 remove

參數：

o - 要從此清單中移除的元素（如果存在）

傳回：

如果此清單包含指定的元素，則傳回 true

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

/**
     * Checks if the given index is in range.  If not, throws an appropriate
     * runtime exception.  This method does *not* check if the index is
     * negative: It is always used immediately prior to an array access,
     * which throws an ArrayIndexOutOfBoundsException if index is negative.
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

iterator

public Iterator iterator()傳回以恰當順序在此清單的元素上進行疊代的疊代器。

此實作傳回 iterator 接口的一個直接實作，具體取決于底層實作清單的 size()、get(int) 和 remove(int) 方法。

注意，除非重寫清單的 remove(int) 方法，否則此方法傳回的疊代器将抛出一個 UnsupportedOperationException 來響應其 remove 方法。

根據 (protected) modCount 字段規範中的描述，在面臨并發修改時，可以使此實作抛出運作時異常。

指定者：

接口 Iterable 中的 iterator

指定者：

接口 Collection 中的 iterator

指定者：

接口 List 中的 iterator

指定者：

類 AbstractCollection 中的 iterator

傳回：

在此 collection 中的元素上進行疊代的疊代器。

另請參見：

modCount

/**
     * Returns an iterator over the elements in this list in proper sequence.
     *
     * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
     *
     * @return an iterator over the elements in this list in proper sequence
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

/**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;//用于檢查快速失敗

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();//檢測快速失敗
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();//檢測快速失敗

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        //檢查快速失敗
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

總結

ensureCapacity

不同步的

public ArrayList()

構造一個初始容量為 10 的空清單。

add
remove
iterator

快速失敗

ArrayList類【JDK源碼分析】

Arrays類【JDK源碼分析】

前言

推薦

說明

ArrayList類

基本資訊

字段摘要

構造方法摘要

方法摘要

字段詳細資訊

構造方法詳細資訊

方法詳細資訊

trimToSize

ensureCapacity

add

remove

iterator

總結

最後

繼續閱讀

資料結構與算法（27）——排序（二）

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使用文檔

Dijkstra--簡易版（最短路徑）

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

hdu7108哈希