我們經常使用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的源碼。
注意 非常有必要在集合初始化時聲明容量。