Java的ArrayList擴容源碼解析

更新時間：2024年01月11日 10:02:56 作者：好奇的7號

這篇文章主要介紹了Java的ArrayList擴容源碼解析,通過動態(tài)擴容,ArrayList能夠在添加元素時保持高效的性能,擴容操作是有一定開銷的,但由于擴容的時間復雜度為O(n),其中n是當前元素個數(shù),所以平均情況下,每次添加元素的時間復雜度仍然是O(1),需要的朋友可以參考下

ArrayList擴容源碼

1、擴容原理概括

ArrayList的擴容原理如下：

初始容量：在創(chuàng)建ArrayList對象時，默認會分配一個初始容量。初始容量可以通過構(gòu)造函數(shù)進行指定，若未指定，則默認為10。例如，ArrayList<String> list = new ArrayList<>();會創(chuàng)建一個初始容量為10的ArrayList。
添加元素：當向ArrayList中添加元素時，會先檢查當前元素個數(shù)是否已經(jīng)達到了數(shù)組的容量上限。如果元素個數(shù)等于或超過了容量上限，就需要進行擴容。
擴容機制：擴容時，ArrayList會創(chuàng)建一個更大的新數(shù)組，并將原有的元素復制到新數(shù)組中。默認情況下，新數(shù)組的大小是原來容量的1.5倍（即增長50%）。例如，如果當前容量為10，那么擴容后的新容量為15。
數(shù)組復制：在擴容時，ArrayList使用System.arraycopy()方法將原始數(shù)組中的元素復制到新的數(shù)組中。這是一個底層的高效數(shù)組復制方法，可以快速地將原有的數(shù)據(jù)移動到新數(shù)組中。
更新引用：在完成數(shù)組復制后，ArrayList會更新內(nèi)部的引用，指向新的數(shù)組。這樣，原先的數(shù)組就會被垃圾回收器回收。

通過動態(tài)擴容，ArrayList能夠在添加元素時保持高效的性能。擴容操作是有一定開銷的，但由于擴容的時間復雜度為O(n)，其中n是當前元素個數(shù)，所以平均情況下，每次添加元素的時間復雜度仍然是O(1)。

同時，擴容的增長因子（即容量的增加比例）也可以被修改，以滿足特定需求。

2、源碼解析

例如，對于如下list進行添加元素，初始容量設置為5，添加6個元素：

ArrayList<String> list = new ArrayList<>(5);
list.add("1");
list.add("2");
list.add("3");
list.add("777");
list.add("888");
list.add("999");

對于一開始的前五個元素而言：

public boolean add(E e) {
        modCount++;
        add(e, elementData, size);//e是“1”，size是0，即目前元素數(shù)量，也可以理解為數(shù)組的索引
        return true;
}
 
//add源碼：
private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)//當元素數(shù)量等于arraylist數(shù)組長度，才grow擴容
            elementData = grow();
        elementData[s] = e;//否則直接在索引位置賦值
        size = s + 1;//并將索引右移
}

但在第6個元素“999”添加進去的時候，要進入grow方法進行擴容：

private void add(E e, Object[] elementData, int s) { //e是“999”，s為5
        if (s == elementData.length)//已經(jīng)相等
            elementData = grow();//步入grow
        elementData[s] = e;
        size = s + 1;
}
 
//grow源碼：輸入size + 1
private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;//舊的數(shù)組大小
 
//接下來，檢查當前數(shù)組是否為空，或者不是使用默認初始容量的空數(shù)組（即DEFAULTCAPACITY_EMPTY_ELEMENTDATA）。如果是空數(shù)組，則說明是第一次添加元素，使用默認初始容量。
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);//計算新數(shù)組大小
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
}
 
//ArraysSupport.newLength源碼：
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        // assert oldLength >= 0
        // assert minGrowth > 0
//minGrowth就是6 - 5 = 1，即，至少需要增大的容量
//prefGrowth為數(shù)組的舊容量的1/2
//求其max，一般為1/2。加上oldlength，所以為1.5倍
        int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
        if (newLength - MAX_ARRAY_LENGTH <= 0) {
            return newLength;
        }
        return hugeLength(oldLength, minGrowth);
    }
 
//最后調(diào)用Arrays.copyOf，內(nèi)部使用System.arraycopy()方法將原始數(shù)組中的元素復制到新的數(shù)組中

實現(xiàn)擴容后，添加元素步驟同上，結(jié)束，return true

到此這篇關于Java的ArrayList擴容源碼解析的文章就介紹到這了,更多相關ArrayList擴容源碼內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: