快捷導(dǎo)航

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

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

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

簡介

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

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

之所以是動態(tài)數(shù)組，是因?yàn)樵谑褂脽o參構(gòu)造函數(shù)創(chuàng)建ArrayList之后，默認(rèn)為空數(shù)組

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

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

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

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

Fast-Fail機(jī)制

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

Fast-Fail是一種機(jī)制，用于檢測在迭代過程中是否有其他線程對集合進(jìn)行了修改。當(dāng)一個線程在迭代 ArrayList 時，如果其他線程對 ArrayList 進(jìn)行了結(jié)構(gòu)性修改（如添加、刪除元素），那么迭代器會立即拋出 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)

造成快速失敗的常見操作包括：

在迭代過程中，使用 ArrayList 的 add、remove、clear 等方法修改集合的結(jié)構(gòu)。
多個線程同時對 ArrayList 進(jìn)行修改操作。

為了避免快速失敗，可以采取以下措施：

在迭代過程中，不要修改集合的結(jié)構(gòu)。如果需要修改，可以使用迭代器的 remove 方法，對應(yīng)上面的例子也就是iterator.remove()。
在多線程環(huán)境下，對于需要并發(fā)修改的情況，可以使用線程安全的集合類，如 CopyOnWriteArrayList。

如果使用語法糖 for (String next : list) {
System.out.println(next);
list.remove(next);
} 這樣的遍歷方式，其實(shí)內(nèi)部也是使用的迭代器，所以會存在同樣的問題

到此這篇關(guān)于Java動態(tài)數(shù)組ArrayList實(shí)現(xiàn)動態(tài)原理的文章就介紹到這了,更多相關(guān)Java ArrayList實(shí)現(xiàn)動態(tài)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: