App下載

揭秘ArrayList初始容量與擴(kuò)容機(jī)制——90%的人都不知道

孫尚香 2023-11-30 11:00:59 瀏覽數(shù) (2018)
反饋

在Java編程中，ArrayList是一種常用的數(shù)據(jù)結(jié)構(gòu)，它提供了便捷的動(dòng)態(tài)數(shù)組功能。然而，了解ArrayList的內(nèi)部機(jī)制對(duì)于優(yōu)化代碼性能和避免不必要的資源浪費(fèi)至關(guān)重要。本文將深入探討ArrayList的兩個(gè)關(guān)鍵問題：初始容量和擴(kuò)容機(jī)制。我們將揭示ArrayList的初始容量到底是0還是10，并詳細(xì)解析ArrayList的擴(kuò)容機(jī)制，包括何時(shí)觸發(fā)擴(kuò)容、擴(kuò)容的策略以及如何提高代碼的效率和性能。通過對(duì)ArrayList的深入了解，我們能夠更好地理解和利用這一重要的數(shù)據(jù)結(jié)構(gòu)，為我們的Java編程提供更強(qiáng)大的工具。

ArrayList的初始容量

ArrayList的初始容量是指創(chuàng)建一個(gè)空的ArrayList時(shí)，它內(nèi)部數(shù)組的大小。這個(gè)大小會(huì)影響到ArrayList的內(nèi)存占用和擴(kuò)容次數(shù)。不同的版本的Java實(shí)現(xiàn)可能有不同的初始容量設(shè)置，但通常有兩種方式來指定或修改它：

  • 使用無參構(gòu)造函數(shù)創(chuàng)建一個(gè)默認(rèn)的ArrayList，它的初始容量由實(shí)現(xiàn)決定。例如，在Java 1.6中，它的初始容量為10，而在Java 1.7和1.8中，它的初始容量為0，只有在添加第一個(gè)元素時(shí)才分配10個(gè)對(duì)象空間。

       源碼如下：

// 默認(rèn)容量大小
private static final int DEFAULT_CAPACITY = 10;

// 空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默認(rèn)容量的數(shù)組對(duì)象
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 存儲(chǔ)元素的數(shù)組
transient Object[] elementData;

// 數(shù)組中元素個(gè)數(shù)，默認(rèn)是0
private int size;

// 無參初始化，默認(rèn)是空數(shù)組
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);
    }
}

  • 使用帶有int參數(shù)的構(gòu)造函數(shù)創(chuàng)建一個(gè)指定初始容量的ArrayList，這樣可以根據(jù)預(yù)期的元素?cái)?shù)量來優(yōu)化內(nèi)存分配和擴(kuò)容次數(shù)。例如，如果我們知道要存儲(chǔ)100個(gè)元素，我們可以這樣創(chuàng)建一個(gè)ArrayList：

ArrayList<Integer> list = new ArrayList<>(100);

       這樣就可以避免多次擴(kuò)容的開銷，同時(shí)也不會(huì)浪費(fèi)太多的空間。

ArrayList的擴(kuò)容機(jī)制

ArrayList的擴(kuò)容機(jī)制是指當(dāng)ArrayList的內(nèi)部數(shù)組已經(jīng)滿了，無法再容納新的元素時(shí)，它會(huì)自動(dòng)創(chuàng)建一個(gè)更大的數(shù)組，并將原來的數(shù)組的內(nèi)容復(fù)制到新的數(shù)組中，以實(shí)現(xiàn)動(dòng)態(tài)增長的功能。這個(gè)過程會(huì)影響到ArrayList的性能和內(nèi)存使用，因?yàn)閿?shù)組的創(chuàng)建和復(fù)制都是耗時(shí)的操作，而且會(huì)產(chǎn)生額外的垃圾對(duì)象。

ArrayList的擴(kuò)容策略也可能因?yàn)椴煌腏ava實(shí)現(xiàn)而有所差異，但通常有以下幾個(gè)特點(diǎn)：

  • 擴(kuò)容的時(shí)機(jī)是在添加元素之前，檢查當(dāng)前的容量是否足夠，如果不夠，就進(jìn)行擴(kuò)容。例如，在Java 1.8中，ArrayList的add()方法的源碼如下：

// 添加元素
public boolean add(E e) {
  // 確保數(shù)組容量夠用，size是元素個(gè)數(shù)
  ensureCapacityInternal(size + 1);
  // 直接在下個(gè)位置賦值
  elementData[size++] = e;
  return true;
}

// 確保數(shù)組容量夠用
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 計(jì)算所需最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
  	// 如果數(shù)組等于空數(shù)組，就設(shè)置默認(rèn)容量為10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

// 確保容量夠用
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
  	// 如果所需最小容量大于數(shù)組長度，就進(jìn)行擴(kuò)容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

其中，ensureCapacityInternal方法會(huì)判斷是否需要擴(kuò)容，如果需要，就調(diào)用grow方法進(jìn)行擴(kuò)容。

  • 擴(kuò)容的幅度是按照一定的比例增加，而不是固定的值，這樣可以保證擴(kuò)容的次數(shù)是對(duì)數(shù)級(jí)別的，而不是線性級(jí)別的，從而降低平均的時(shí)間復(fù)雜度。例如，在Java 1.8中，ArrayList的grow方法的源碼如下：

// 擴(kuò)容，就是把舊數(shù)據(jù)拷貝到新數(shù)組里面
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  // 計(jì)算新數(shù)組的容量大小，是舊容量的1.5倍
  int newCapacity = oldCapacity + (oldCapacity >> 1);

  // 如果擴(kuò)容后的容量小于最小容量，擴(kuò)容后的容量就等于最小容量
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;

  // 如果擴(kuò)容后的容量大于Integer的最大值，就用Integer最大值
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
 
  // 擴(kuò)容并賦值給原數(shù)組
  elementData = Arrays.copyOf(elementData, newCapacity);
}

總結(jié)

ArrayList是一種靈活和高效的動(dòng)態(tài)列表，它可以根據(jù)需要自動(dòng)調(diào)整容量，以存儲(chǔ)任意數(shù)量的元素。但是，它的初始容量和擴(kuò)容機(jī)制也會(huì)影響到它的性能和內(nèi)存使用，因此，在使用ArrayList時(shí)，我們應(yīng)該根據(jù)實(shí)際的場景和需求，合理地選擇或指定它的初始容量，以避免不必要的開銷和浪費(fèi)。

1698630578111788

如果你對(duì)Java工程師職業(yè)和編程技術(shù)感興趣，不妨訪問編程獅官網(wǎng)（http://m.hgci.cn/）。編程獅官網(wǎng)提供了大量的技術(shù)文章、編程教程和資源，涵蓋了Java工程師、編程、職業(yè)規(guī)劃等多個(gè)領(lǐng)域的知識(shí)。無論你是初學(xué)者還是有經(jīng)驗(yàn)的開發(fā)者，編程獅官網(wǎng)都為你提供了有用的信息和資源，助你在編程領(lǐng)域取得成功。不要錯(cuò)過這個(gè)寶貴的學(xué)習(xí)機(jī)會(huì)！

Java

0 人點(diǎn)贊