讀古今文學網 > 編寫高質量代碼:改善Java程序的151個建議 > 建議63:在明確的場景下,為集合指定初始容量 >

建議63:在明確的場景下,為集合指定初始容量

我們經常使用ArrayList、Vector、HashMap等集合,一般都是直接用new跟上類名聲明出一個集合來,然後使用add、remove等方法進行操作,而且因為它是自動管理長度的,所以不用我們特別費心超長的問題,這確實是一個非常好的優點,但也有我們必須要注意的事項。

下面以ArrayList為例深入瞭解一下Java是如何實現長度的動態管理的,先從add方法的閱讀開始,代碼如下。


public boolean add(E e){

//擴展長度

ensureCapacity(size+1);

//追加元素

elementData[size++]=e;

return true;

}


我們知道ArrayList是一個大小可變的數組,但它在底層使用的是數組存儲(也就是elementData變量),而且數組是定長的,要實現動態長度必然要進行長度的擴展,ensureCapacity方法提供了此功能,代碼如下:


public void ensureCapacity(int minCapacity){

//修改計數器

modCount++;

//上次(原始)定義的數組長度

int oldCapacity=elementData.length;

//當前需要的長度超過了數組長度

if(minCapacity>oldCapacity){

Object oldData=elementData;

//計算新數組長度

int newCapacity=(oldCapacity*3)/2+1;

if(newCapacity<minCapacity)

newCapacity=minCapacity;

//數組拷貝,生成新數組

elementData=Arrays.copyOf(elementData, newCapacity);

}

}


注意看新數組的長度計算方法,並不是增加一個元素,elementData的長度就加1,而是在達到elementData長度的臨界點時,才將elementData擴容1.5倍,這樣實現有什麼好處呢?好處是避免了多次調用copyOf方法的性能開銷,否則每加一個元素都要擴容一次,那性能豈不是非常糟糕?!

可能有讀者要問了,這裡為什麼是1.5倍,而不是2.5倍、3.5倍?這是一個好問題,原因是一次擴容太大(比如擴容2.5倍),佔用的內存也就越大,浪費的內存也就越多(1.5倍擴容,最多浪費33%的數組空間,而2.5倍則最多可能浪費60%的內存);而一次擴容太小(比如每次擴容1.1倍),則需要多次對數組重新分配內存,性能消耗嚴重。經過測試驗證,擴容1.5倍即滿足了性能要求,也減少了內存消耗。

現在我們知道了ArrayList的擴容原則,那還有一個問題:elementData的默認長度是多少呢?答案是10,如果我們使用默認方式聲明ArrayList,如new ArrayList(),則elementData的初始長度就是10。我們來看ArrayList的無參構造:


//無參構造,我們通常用得最多的就是這個

public ArrayList(){

//默認是長度為10的數組

this(10);

}

//指定數組長度的有參構造

public ArrayList(int initialCapacity){

super();

if(initialCapacity<0)

throw new IllegalArgumentException(\"Illegal Capacity:\"+initialCapacity);

//聲明指定長度的數組,容納element

this.elementData=new Object[initialCapacity];

}


默認初始化時聲明了一個長度為10的數組,在通過add方法增加第11個元素時,ArrayList類就自動擴展了,新的elementData數組長度是(10×3)/2+1,也就是16,當增加到第17個元素時再次擴容為(16×3)/2+1,也就是25,依此類推,實現了ArrayList的動態數組管理。

從這裡我們可以看出,如果不設置初始容量,系統就按照1.5倍的規則擴容,每次擴容都是一次數組的拷貝,如果數據量很大,這樣的拷貝會非常耗費資源,而且效率非常低下。如果我們已經知道一個ArrayList的可能長度,然後對ArrayList設置一個初始容量則可以顯著提高系統性能。比如一個班級的學生,通常也就是50人左右,我們就聲明ArrayList的默認容量為50的1.5倍(元素數量小,直接計算,避免數組拷貝),即new ArrayList<Studeng>(75),這樣在使用add方法增加元素時,只要在75以內都不用做數組拷貝,超過了75才會按照默認規則擴容(也就是1.5倍擴容)。如此處理,對我們的開發邏輯並不會有任何影響,而且還可以提高運行效率(在大數據量下,是否指定容量會使性能相差5倍以上)。

弄明白了ArrayList的長度處理方式,那其他集合類型呢?我們先來看Vector,它的處理方式與ArrayList相似,只是數組的長度計算方式不同而已,代碼如下:


private void ensureCapacityHelper(int minCapacity){

int oldCapacity=elementData.length;

if(minCapacity>oldCapacity){

ObjectoldData=elementData;

//若有遞增步長,則按照步長增長;否則,擴容2倍

int newCapacity=(capacityIncrement>0)?(oldCapacity+capacityIncrement)

:(oldCapacity*2);

//越界檢查,否則超過int最大值

if(newCapacity<minCapacity){

newCapacity=minCapacity;

}

elementData=Arrays.copyOf(elementData, newCapacity);

}

}


Vector與ArrayList不同的地方是它提供了遞增步長(capacityIncrement變量),其值代表的是每次數組拓長時要增加的長度,不設置此值則是容量翻倍(默認是不設置遞增步長的,可以通過構造函數來設置遞增步長)。其他集合類的擴容方式與此相似,如HashMap是按照倍數增加的,Stack繼承自Vector,所採用的也是與其相同的擴容原則等,讀者有興趣可以自行研讀一下JDK的源碼。

注意 非常有必要在集合初始化時聲明容量。