深入了解學習ArrayList

概述
擴容原理
面試常問

概述

ArrayList 使用動态數組來存儲元素。用MSDN(面向開發人員和技術專業人員的 Microsoft 文檔和學習首頁)中的說法，就是Array的複雜版本，它提供了動态的增加和減少元素，實作了Collection和List接口，靈活的設定數組的大小等好處。

動态數組是指在聲明時沒有确定數組大小的數組，即忽略圓括号中的下标；當要用它時，可随時用ReDim(為數組變量重新配置設定存儲空間)語句重新指出數組的大小。使用動态數組的優點是可以根據使用者需要，有效利用存儲空間

繼承關系圖

Java集合-ArrayList深入學習概述擴容原理面試常問

1>.ArrayList繼承了AbstractList，實作了List，提供了添加、修改、删除、周遊等功能。

2>.ArrayList實作了RandomAccess接口，提供了随機通路的功能。在ArrayList中，通過元素下标快速擷取到元素。實際RandomAccess是沒有任何代碼的，但ArrayList底層是數組，是以快速随機通路是肯定的。

3>.ArrayList實作了Cloneable接口，即覆寫了clone()方法，可以被克隆(淺克隆)。

4>.ArrayList實作了Serializable接口，即支援序列化(将對象的狀态資訊轉換為可以存儲或傳輸的形式的過程)。

5>.ArrayList是非線程安全的，根據場景需要可以使用線程安全的替換ArrayList，例如Vector或CopyOnWriteArrayList。

擴容原理

了解ArrayList的屬性

// 預設數組長度
    private static final int DEFAULT_CAPACITY = 10;
	// 空數組
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 空數組，不同于EMPTY_ELEMENTDATA，該空數組主要用于無參建立ArrayList時擴容
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 存儲元素的數組，transient修飾不存于序列化
    transient Object[] elementData; 
    // 數組長度，實際數組裡元素的數量
    private int size;

了解ArrayList的構造方法，不同的構造方法影響着擴容機制的判斷

// 無參構造，elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

	// 指定初始容量構造，當initialCapacity為0，elementData = 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);
        }
    }

	// 包含指定集合有參構造，指定集合的length為0時，elementData = EMPTY_ELEMENTDATA
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

擴容，發生在add添加元素方法中，隻有添加才會涉及容量不足而産生擴容。後續分析擴容以無參構造建立的ArrayList，且第一次添加元素作為主要分析依據。看下兩個主要添加方法的具體邏輯：

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

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

可以看到兩個方法都調用了ensureCapacityInternal(size + 1)方法，把數組長度加1以確定能存下下一個資料。

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

此方法會先調用calculateCapacity方法，參數有elementData、minCapacity。無參構造時elementData為DEFAULTCAPACITY_EMPTY_ELEMENTDATA；minCapacity為size + 1，size為0，即minCapacity為1；

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

此方法會判斷目前數組是否為DEFAULTCAPACITY_EMPTY_ELEMENTDATA，剛才提到無參構造時才會傳回這個數組。是以，若建立ArrayList時調用的是無參構造，此方法會傳回DEFAULT_CAPACITY（值為10）和 minCapacity的之間最大值，是以，最終會傳回固定值10；若建立ArrayList時調用了有參構造，則第一次調此方法會傳回1，注意這個minCapacity變量隻是第一次調用add方法時值為1，此後的調用需要根據實際的數組長度size + 1。

再調用ensureExplicitCapacity方法

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

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

modCount++用到了快速失敗機制，此處先不做讨論；

繼續向下走，如果minCapacity大于elementData.length，則會調用grow方法，注意這個elementData.length傳回的是目前數組的容量，而不是數組實際的長度size。如果調用了有參構造，例如傳入的容量為5，則此時elementData.length值即為5，而此時第一次調用add時，size值為0，是以minCapacity為1，不滿足條件，此情況不需要擴容調用grow方法；如果調用了無參構造傳回數組DEFAULTCAPACITY_EMPTY_ELEMENTDATA，注意這個數組隻是一個空數組，是以此時elementData.length為0，滿足條件，需要擴容調用grow方法。

通俗來講，就是如果ArrayList給定了特定初始容量，則此處需要根據實際情況确定是否調用grow方法，即有可能不需要擴容。如果沒有指定初始容量，第一次調用add則此處一定需要調用grow方法。

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
	
    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);
    }

int newCapacity = oldCapacity + (oldCapacity >> 1)此行代碼即為擴容的核心，oldCapacity為原來的容量，右移一位，即除以2，是以這句的意思就是新的容量newCapacity = oldCapacity+oldCapacity / 2，即原來的1.5倍。

然後判斷newCapacity如果小于傳入的minCapacity，則直接讓newCapacity等于minCapacity（當無參構造時，elementData.length為0，是以oldCapacity也為0，minCapacity為10，是以最終newCapacity為10）。

然後判斷newCapacity是否大于設定的MAX_ARRAY_SIZE，此處

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

如果大于，則調用hugeCapacity方法

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

如果minCapacity大于MAX_ARRAY_SIZE，則傳回Integer的最大值，否則傳回MAX_ARRAY_SIZE。最後，通過Arrays.copyOf方法把原數組的内容放到更大容量的數組裡面。

面試常問

ArrayList 是什麼？常用來做什麼？底層是什麼實作的？

ArrayList是有序動态數組，顧名思義底層是數組實作的，實作了List接口，提供了基本的增、删、改、查等功能。常用來裝載資料的。
ArrayList 和 LinkedList 有什麼差別？各自優缺點？

ArrayList 查找和通路速度較快(底層是數組)，添加和删除相較慢些(例如指定中間位置添加元素，該下标後的元素全部後移一位，删除同理，該下标後的元素全部前移一位)

LinkedList 查找和通路速度較慢(底層是連結清單)，添加和删除相較快些。

都是非線程安全的。

當遇到通路元素比較頻繁時，建議使用ArrayList；當遇到在某個特定索引中，删除或添加元素比較頻繁時，建議使用LinkedList。
ArrayList 是否是線程安全的？

ArrayList是非線程安全的，可以使用線程安全的集合例如Vector或CopyOnWriteArrayList。
ArrayList 動态擴容機制是什麼？

1.擴容是發生在調用add方法的時候

2.在add方法中，會先判斷存儲元素的數組elementData是否等于ArrayList一個特殊的空數組，隻有無參構造才會等于，minCapacity才會為預設長度10

有參構造不會等于，minCapacity為size + 1，size為目前數組的元素數量。再判斷minCapacity是否大于elementData.length，大于則表明需要擴容。

指定兩個變量，oldCapacity = element.length，newCapacity = oldCapacity + oldCapacity / 2，即新數組長度為之前數組長度的1.5倍。判斷

newCapacity < minCapacity，小于則newCapacity = minCapacity；再判斷newCapacity > MAX_ARRAY_SIZE，大于則最大指派Integer.MAX_VALUE。

最後通過Arrays.copyOf建立新長度的數組，包含原數組元素。

擴容參考文章：https://blog.csdn.net/qq_26542493/article/details/88873168

Java集合-ArrayList深入學習概述擴容原理面試常問

深入了解學習ArrayList

概述

擴容原理

面試常問

繼續閱讀

關于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