引言
ArrayList是基于數(shù)組所實現(xiàn)的徘铝。
眾所周知，數(shù)組是不能進行擴容操作的泵琳，而我們調(diào)用ArrayList的add()等方法時卻可以實現(xiàn)擴容操作哗总。
源碼
其內(nèi)部源碼主要經(jīng)歷以下步驟：
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
- 當我們調(diào)用
add()時，系統(tǒng)會先調(diào)用ensureCapacityInternal(size+1)來確認ArrayList的內(nèi)部數(shù)組elementData是否有足夠空間容納size+1大小的數(shù)據(jù)脸候。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
- 在
ensureCapacityInternal()中穷娱，首先系統(tǒng)會先判定內(nèi)部數(shù)組elementData是否等于默認的空數(shù)組，如果是的話运沦，則取DEFAULT_CAPACITY(默認容量為10)與minCapacity的最大值(即ArrayList默認構造一個容量為10的空數(shù)組)泵额，然后調(diào)用ensureExplicitCapacity()確認是否需要擴容。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
- 在
ensureExplicitCapacity()中携添，首先增加modCount數(shù)量(modCount是用來記錄ArrayList元素數(shù)目被修改的次數(shù))嫁盲，其次進行判定minCapacity是否超過了當前數(shù)組elementData的長度，超過了則調(diào)用grow()方法薪寓，進行數(shù)組擴容操作亡资。未超過則進行elementData[size++] = e賦值操作。
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
- 在
grow()方法中向叉，可以看到newCapacity = oldCapacity + (oldCapacity >> 1)锥腻，即是新的數(shù)組長度為原數(shù)組長度的1.5倍，再與傳入的minCapacity大小進行比較母谎，取最大值瘦黑，如果超過了MAX_ARRAY_SIZE大小(值為Interger.MAX_VALUE - 8)，調(diào)用hugeCapacity()方法奇唤，然后調(diào)用Arrays.copyOf()將數(shù)組擴容并復制到新數(shù)組幸斥。
總結
ArrayList實現(xiàn)擴容操作的機制，就是在超過elementData數(shù)組長度時咬扇，將數(shù)組擴容1.5倍甲葬，并調(diào)用Arrays.copyOf復制到新數(shù)組。而至于1.5倍的擴容懈贺，是因為不會導致每次進行add操作時就要頻繁進行擴容數(shù)組長度经窖，也不會過于浪費內(nèi)存空間。當然梭灿，如果我們能預知ArrayList的大小時画侣，我們應該調(diào)用ensureCapacity()方法來事先擴容數(shù)組長度，避免頻繁擴容影響性能堡妒。
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
? 0
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
擴展知識
- 數(shù)組也不能進行刪除操作配乱，而ArrayList中可以調(diào)用
remove()等方法來實現(xiàn)刪除操作，實際上是先遍歷查找出對應的position，然后調(diào)用System.arraycopy()方法將數(shù)據(jù)復制到新數(shù)組搬泥，然后再將原position位置的數(shù)據(jù)置空桑寨，使gc回收其資源。 - 由于ArrayList上述擴容機制佑钾，ArrayList的
size()方法并不是返回其內(nèi)部數(shù)組elementData的長度西疤，而是返回size變量，size變量在調(diào)用add休溶、remove等方法的時候增加或減小其值，例如在add方法中扰她，在賦值操作中elementData[size++] = e;使size值加一兽掰。addAll、remove等方法同理徒役。
