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ì)!

0 人點(diǎn)贊