怎么深入理解ArrayList源碼

本篇內(nèi)容介紹了“怎么深入理解ArrayList源碼”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

創(chuàng)新互聯(lián)基于成都重慶香港及美國等地區(qū)分布式IDC機房數(shù)據(jù)中心構(gòu)建的電信大帶寬，聯(lián)通大帶寬，移動大帶寬，多線BGP大帶寬租用,是為眾多客戶提供專業(yè)服務(wù)器托管報價，主機托管價格性價比高，為金融證券行業(yè)四川主機托管，ai人工智能服務(wù)器托管提供bgp線路100M獨享，G口帶寬及機柜租用的專業(yè)成都idc公司。

ArrayList是最常見的集合類，顧名思義，ArrayList就是一個以數(shù)組形式實現(xiàn)的集合。它擁有List集合的特點：

  • 存取有序

  • 帶索引

  • 允許重復(fù)元素

它本身的特點是：

  • 查找元素快

  • 順序插入快

那ArrayList為什么會有這些特性的？其實從源碼中我們就能夠了解到它是如何實現(xiàn)的。

Resizable-array implementation of the {@code List} interface. Implements all optional list operations, and permits all elements, including {@code null}. In addition to implementing the {@code List} interface,this class provides methods to manipulate the size of the array that is used internally to store the list.

實現(xiàn)了List接口的，一個可調(diào)整大小的數(shù)組。可以存儲所有的元素，包括null，除了實現(xiàn)了List接口的方法外，還提供了一些方法用于操作內(nèi)部用于存儲元素的數(shù)組的大小。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

  • RandomAccess標(biāo)記接口 表示ArrayList支持隨機訪問。什么是隨機訪問呢？隨機訪問是說你可以隨意訪問該數(shù)據(jù)結(jié)構(gòu)中的任意一個節(jié)點，假設(shè)該數(shù)據(jù)結(jié)構(gòu)有10000個節(jié)點，你可以隨意訪問第1個到第10000個節(jié)點。因為ArrayList用數(shù)組來存數(shù)據(jù)，Java中給數(shù)組劃分內(nèi)存來存儲元素時，劃分的是一塊連續(xù)的內(nèi)存地址，這些相鄰元素是按順序連續(xù)存儲的。只要知道起始元素的地址First，直接first+N，便可以得到第N個元素的地址。這就是ArrayList查找快的原因。

  • Cloneable標(biāo)記接口 表示ArrayList是可以被克隆的。

  • java.io.Serializable標(biāo)記接口 表示ArrayList是可以被序列化的。

主要成員變量：

@java.io.Serial private static final long serialVersionUID = 8683452581122892189L;

用于標(biāo)明序列化時的版本號。

private static final int DEFAULT_CAPACITY = 10;

默認(rèn)初始化大小。

private static final Object[] EMPTY_ELEMENTDATA = {};

默認(rèn)空數(shù)組大小。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

默認(rèn)初始化空數(shù)組大小。

看到這可能有人會有疑問，同樣是空數(shù)組，為什么要有兩個引用變量來表示呢？且看后面的擴容機制說明。

transient Object[] elementData;

這就是ArrayList所維護的用于存儲數(shù)據(jù)的數(shù)組了，transient標(biāo)明這個存儲數(shù)據(jù)的數(shù)組不會被序列化，而ArrayList卻又打上了標(biāo)記接口java.io.Serializable說明是可序列化的，這不是自相矛盾了嗎？暫且按下不表，看看ArrayList的內(nèi)部機制再回頭說明。

private int size;

ArrayList的大?。ㄆ鋵嵰簿褪瞧渲邪脑貍€數(shù)）。

構(gòu)造方法：

//傳入了初始值的
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

//沒有傳入初始值的
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

//傳入一個Collection集合的
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

可以看到，如果傳入了初始值initialCapacity，就會按照這個值來初始化數(shù)組的大小。如果傳入0，則數(shù)組等于EMPTY_ELEMENTDATA，如果用了空參構(gòu)造，則數(shù)組等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

擴容機制：

我們知道，Java中數(shù)組一旦定義則長度是不允許改變的，那么ArrayList如何實現(xiàn)_Resizable-array implementation（可調(diào)整大小的數(shù)組實現(xiàn)）？_

答案就在擴容機制上：

//傳入最小所需要的容量
private Object[] grow(int minCapacity) {
        //當(dāng)前容量大小
        int oldCapacity = elementData.length;
    	//若當(dāng)前容量大小大于0且數(shù)組創(chuàng)建是不是通過空參構(gòu)造創(chuàng)建的
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //定義新的最小所需容量
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    //右移一位，類似于除以2
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

//傳入當(dāng)前容量，最小需要增加的容量，首選增長的容量
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        // assert oldLength >= 0
        // assert minGrowth > 0
		
    	//將最小所需要增加的容量與首選增長的容量比較，取較大的與當(dāng)前容量相加
        int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
        if (newLength - MAX_ARRAY_LENGTH <= 0) {
            return newLength;
        }
        return hugeLength(oldLength, minGrowth);
    }

我們每次添加元素的時候，都會去確認(rèn)一下當(dāng)前ArrayList所維護的數(shù)組存儲的元素是否已經(jīng)達到上限(元素個數(shù)等于數(shù)組長度)？如果是的話，就會觸發(fā)擴容機制grow()去創(chuàng)建一個新的更大的數(shù)組來轉(zhuǎn)移數(shù)據(jù)。

可以看到，若是我們通過傳入?yún)?shù)0來構(gòu)造ArrayList，grow()就會判斷出來這個是一個長度為0的自定義空數(shù)組，那么就會按照最小的所需要的容量擴容。

如果沒有傳入?yún)?shù)，就用默認(rèn)初始容量10，來創(chuàng)建初始的數(shù)組。

怎么深入理解ArrayList源碼

而且我們可以看到，擴容的時候會判斷所需要的最小容量是不是比當(dāng)前數(shù)組的1.5倍還大？不是就按照當(dāng)前數(shù)組長度的1.5倍來擴容，否則就按傳進來的最小所需容量來擴容。

為什么是1.5倍呢？

1.如果一次性擴容擴得太大，必然造成內(nèi)存空間的浪費。

2.如果一次性擴容擴得不夠，那么下一次擴容的操作必然比較快地會到來，這會降低程序運行效率，要知道擴容還是比較耗費性能的一個操作，因為會新建數(shù)組移動數(shù)據(jù)。

所以擴容擴多少，是JDK開發(fā)人員在時間、空間上做的一個權(quán)衡，提供出來的一個比較合理的數(shù)值。

添加元素：

//添加單個元素，默認(rèn)添加到集合尾    
public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

//實際調(diào)用的方法
private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

//添加另一個集合，默認(rèn)添加到集合尾 
public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        modCount++;
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);
        //5個參數(shù)的意思分別是：源數(shù)組，源數(shù)組開始復(fù)制的位置，目標(biāo)數(shù)組，目標(biāo)數(shù)組開始接收的位置，接收的長度
        System.arraycopy(a, 0, elementData, s, numNew);
        size = s + numNew;
        return true;
    }

基本上很淺顯易懂，只要容量夠就能直接添加，否則得擴容。

其中modCount是用于快速失敗的一種機制，因為基本集合在多線程環(huán)境下是不安全的，這個以后再討論。

刪除元素：

//按元素刪除  
public boolean remove(Object o) {
        final Object[] es = elementData;
        final int size = this.size;
        int i = 0;
        //標(biāo)簽舊方法，用于跳出多個循環(huán)
        found: {
            if (o == null) {
                for (; i < size; i++)
                    if (es[i] == null)
                        break found;
            } else {
                for (; i < size; i++)
                    if (o.equals(es[i]))
                        break found;
            }
            return false;
        }
        fastRemove(es, i);
        return true;
    }

//按索引刪除
public E remove(int index) {
        Objects.checkIndex(index, size);
        final Object[] es = elementData;

        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
        fastRemove(es, index);

        return oldValue;
    }

//實際執(zhí)行方法
private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
    }

分兩種情況，一種是按照傳入的元素去刪除，這樣得從數(shù)組開頭遍歷過去并且逐一調(diào)用equals方法比較，只要找到第一個符合的就將其刪除。

第二種是按照傳入的索引去刪除，這個可以直接定位。另外需要注意的一點是當(dāng)ArrayList里存儲的是Integer包裝類的時候，依然是選擇索引刪除。

刪除的意思是將數(shù)組此位置的元素的引用設(shè)置為null，如果沒有另外的引用指向此元素，那么此元素就會被標(biāo)記為垃圾被回收。

如果刪除的元素在最后就不用移動元素了，如果不在就需要移動元素。

怎么深入理解ArrayList源碼

插入元素：

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        elementData[index] = element;
        size = s + 1;
    }

先判斷容量是否足夠，再去將此位置以及后面的元素全部向后移動一位，最后將傳入的元素插入此位置。

最后說明：

了解了ArrayList的各種機制，我們就能知道為什么存儲元素的elementData用transient修飾了

//序列化
@java.io.Serial
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioral compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

//反序列化
 @java.io.Serial
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // like clone(), allocate array based upon size not capacity
            SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
            Object[] elements = new Object[size];

            // Read in all elements in the proper order.
            for (int i = 0; i < size; i++) {
                elements[i] = s.readObject();
            }

            elementData = elements;
        } else if (size == 0) {
            elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new java.io.InvalidObjectException("Invalid size: " + size);
        }
    }

其實主要是看里邊的兩個循環(huán)的方法，涉及到的是size。我們已經(jīng)了解了存放元素的數(shù)組會動態(tài)的改變，因此里邊未必就存滿了元素。真正有多少個元素是size負(fù)責(zé)的。所以我們序列化的時候僅僅去遍歷size個對象就能完成序列化了。這樣就能避免序列化太多不需要的東西，加快序列化速度以及減小文件大小。

“怎么深入理解ArrayList源碼”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！

本文標(biāo)題：怎么深入理解ArrayList源碼
標(biāo)題網(wǎng)址：http://bm7419.com/article24/pcccje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供靜態(tài)網(wǎng)站、自適應(yīng)網(wǎng)站、定制網(wǎng)站、品牌網(wǎng)站設(shè)計、網(wǎng)站內(nèi)鏈、網(wǎng)頁設(shè)計公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

商城網(wǎng)站建設(shè)