Java動態(tài)數(shù)組ArrayList實現(xiàn)動態(tài)原理

更新時間：2023年08月10日 08:48:44 作者：很閑很快樂

ArrayList是一種動態(tài)數(shù)組,它可以在運行時自動調(diào)整大小以適應元素的添加和刪除,在Java中,你可以使用ArrayList類來實現(xiàn)動態(tài)數(shù)組,本文將給大家介紹一下ArrayList動態(tài)數(shù)組,是怎么實現(xiàn)動態(tài)的

簡介

ArrayList是一個動態(tài)數(shù)組，可以通過泛型來決定數(shù)據(jù)中存放的元素類型

怎么實現(xiàn)的動態(tài)

之所以是動態(tài)數(shù)組，是因為在使用無參構造函數(shù)創(chuàng)建ArrayList之后，默認為空數(shù)組

public ArrayList() {  
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  
}

在你每次去add一個元素的時候，通過ensureCapacityInternal方法去檢查添加后元素的個數(shù)是否會超出當前數(shù)組的長度，如果超出，數(shù)組將會進行擴容，以滿足添加數(shù)據(jù)的需求

public boolean add(E e) {
	// size為當前數(shù)據(jù)存放元素的數(shù)量
    ensureCapacityInternal(size + 1);
    // elementData為ArrayList內(nèi)部存放數(shù)據(jù)的數(shù)組
    elementData[size++] = e;  
    return true;
}
private void ensureCapacityInternal(int minCapacity) { 
	// 判斷數(shù)組是否為空，為空則將最小容量設置為默認值10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  
    }  
	// 判斷當前容量是否滿足最小容量
    ensureExplicitCapacity(minCapacity);  
}
private void ensureExplicitCapacity(int minCapacity) {
	// modCount用于記錄修改次數(shù)，作用于fast-fail機制
	// 如果在迭代的時候發(fā)現(xiàn)modCount被修改了，則會拋出異常來避免可能會出現(xiàn)的不確定行為
    modCount++;  
    // 如果當前容量小于最小容量，則進行擴容
    if (minCapacity - elementData.length > 0)  
        grow(minCapacity);  
}
private void grow(int minCapacity) {  
    int oldCapacity = elementData.length;  
    // 計算新的容量，擴大為原容量的1.5倍, oldCapacity >> 1 運算表示右移一位，也就是相當于除以二并取整
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)  
        newCapacity = minCapacity; 
    // 如果新容量超過了數(shù)組的最大容量,調(diào)用hugeCapacity方法來獲取一個更大的容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)  
        newCapacity = hugeCapacity(minCapacity);  
    // 拷貝原數(shù)組，將原數(shù)組的元素復制到新數(shù)組中 
    elementData = Arrays.copyOf(elementData, newCapacity);  
}
private static int hugeCapacity(int minCapacity) {  
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
	// 如果最小容量大于最大容量，則將容量設置為Integer.MAX_VALUE
    return (minCapacity > MAX_ARRAY_SIZE) ?  
        Integer.MAX_VALUE :  
        MAX_ARRAY_SIZE;  
}

從上面的源碼解釋可以看到，如果新建數(shù)據(jù)沒有給定初始值，ArrayList是每次在進行add操作的時候去進行擴容的，擴容則會涉及到Arrays.copyOf深拷貝，會造成內(nèi)存和性能的消耗，所以在生產(chǎn)項目中，推薦大家盡量在創(chuàng)建ArrayList對象的時候就指定其容量。

Fast-Fail機制

大家肯定注意到了上面提到的通過modCount實現(xiàn)的Fast-Fail機制

Fast-Fail是一種機制，用于檢測在迭代過程中是否有其他線程對集合進行了修改。當一個線程在迭代 ArrayList 時，如果其他線程對 ArrayList 進行了結構性修改（如添加、刪除元素），那么迭代器會立即拋出 ConcurrentModificationException 異常，以避免出現(xiàn)不確定的行為。例子：

public class Example1 {  
    public static void main(String[] args) {  
        ArrayList<String> list = new ArrayList<>(3);  
        list.add("qwe");  
        list.add("asd");  
        list.add("zxc");  
        Iterator<String> iterator = list.iterator();  
        while (iterator.hasNext()){  
            String next = iterator.next();  
            System.out.println(next);  
            list.remove(next);  
        }  
    }  
}
輸出：
qwe
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
	at java.util.ArrayList$Itr.next(ArrayList.java:851)
	at com.example.lepractice.collection.Example1.main(Example1.java:21)