JDK1.8中ArrayList是如何擴容的

Posted on by

ArrayList簡介：

ArrayList實現瞭List接口它是一個可調整大小的數組可以用來存放各種形式的數據。並提供瞭包括CRUD在內的多種方法可以對數據進行操作但是它不是線程安全的，外ArrayList按照插入的順序來存放數據。

在講擴容機制之前，我們需要瞭解一下ArrayList中最主要的幾個變量：

private static final int DEFAULT_CAPACITY = 10;//數組默認初始容量

private static final Object[] EMPTY_ELEMENTDATA = {};//定義一個空的數組實例以供其他需要用到空數組的地方調用 

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//定義一個空數組，跟前面的區別就是這個空數組是用來判斷ArrayList第一添加數據的時候要擴容多少。默認的構造器情況下返回這個空數組 

transient Object[] elementData;//數據存的地方它的容量就是這個數組的長度，同時隻要是使用默認構造器（DEFAULTCAPACITY_EMPTY_ELEMENTDATA ）第一次添加數據的時候容量擴容為DEFAULT_CAPACITY = 10 

private int size;//當前數組的長度

本題的所有的講解都是基於JDK8

在這裡插入圖片描述

這道題考察瞭ArrayList的構造器和對擴容機制的瞭解，本篇博客基於此出發講解ArrayList的擴容機制

想要做出這道題必須瞭解ArrayList的構造函數，ArrayList的構造函數總共有三個：

  • ArrayList()構造一個空的數組。JDK7中構造一個初始容量為10的空列表但是JDK8中隻是構造一個空的數組
  • ArrayList(Collection<? extends E> c)構造一個包含指定 collection 的元素的數組，這些元素是按照該 collection 的迭代器返回它們的順序排列的。
  • ArrayList(int initialCapacity)構造一個具有指定初始容量的空數組。

我們重點來看這兩個ArrayList(int initialCapacity)，ArrayList()構造函數

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

初始化一個空數組，這是JDK8不同於之前版本的地方

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

對於形參initialCapacity判斷，如果大於0那麼就聲明一個和形參一樣大小的數組。瞭解到這裡似乎這道題的正確答案也出來瞭即選擇A，並沒有發生擴容

但是作為一名合格的程序員要有探索精神，題目提到瞭擴容，既然ArrayList底層是一個數組，那麼就肯定會滿，什麼時候發生擴容呢？

//1.add方法為添加元素在數組末尾
public boolean add(E e) {
    //確保數組容量 size指向數組的末尾
    ensureCapacityInternal(size + 1);
    //在完成添加之前要確保數組長度足夠
    elementData[size++] = e;
    return true;
}
//3.elementData為ArrayList底層維護的數組，minCapacity為此時數組的大小
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果數組為初始化的值，就初始化數組容量為10(空參的構造方法下首次添加)
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
//2.minCapacity表示此時數組的大小
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//4.minCapacity表示此時數組的大小
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //如果此時數組容量的大小不夠就擴容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

源碼讀到這裡，我們明白瞭，當我們每次向ArrayList添加元素的時候，都會首先確保數組容量夠放下元素如果不夠就會 grow(minCapacity)調用擴容函數，那麼秉承著探索的精神，原本大小的數組擴容之後變成多大瞭呢？還得繼續看源碼

//擴容源碼
private void grow(int minCapacity) {
    //獲取當前數組的長度
    int oldCapacity = elementData.length;
    //>>右移相當於整除2，新容量相當於就舊容量的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);
}

源碼大致讀完後，我們明白瞭ArrayList的自動擴容機制，每次新添加元素的時候都會判斷是否能夠容下，如果不夠就會發生擴容，擴容的大小為原大小的1.5倍數，明白這些以後讓我們看看下面這段程序擴容瞭幾次呢？？容量是多少呢？

ArrayList<Integer> arrayList = new ArrayList<Integer>(20);
for(int i=1;i<=50;i++) {
     arrayList.add(i);
}

前20次添加不會發生擴容，當21元素添加時數組容量從20擴容到30，當添加31元素時數組容量從30擴容到45，當添加46元素時數組容量從45擴容到67

到此這篇關於JDK1.8中ArrayList是如何擴容的的文章就介紹到這瞭,更多相關JDK1.8 ArrayList擴容內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：