App下載

揭秘ArrayList初始容量與擴容機制——90%的人都不知道

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

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

ArrayList的初始容量

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

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

       源碼如下:

// 默認容量大小
private static final int DEFAULT_CAPACITY = 10;

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

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

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

// 數(shù)組中元素個數(shù),默認是0
private int size;

// 無參初始化,默認是空數(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)建一個指定初始容量的ArrayList,這樣可以根據(jù)預(yù)期的元素數(shù)量來優(yōu)化內(nèi)存分配和擴容次數(shù)。例如,如果我們知道要存儲100個元素,我們可以這樣創(chuàng)建一個ArrayList:

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

       這樣就可以避免多次擴容的開銷,同時也不會浪費太多的空間。

ArrayList的擴容機制

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

ArrayList的擴容策略也可能因為不同的Java實現(xiàn)而有所差異,但通常有以下幾個特點:

  • 擴容的時機是在添加元素之前,檢查當前的容量是否足夠,如果不夠,就進行擴容。例如,在Java 1.8中,ArrayList的add()方法的源碼如下:

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

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

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

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

其中,ensureCapacityInternal方法會判斷是否需要擴容,如果需要,就調(diào)用grow方法進行擴容。

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

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

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

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

總結(jié)

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

1698630578111788

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

0 人點贊