ArrayList源碼閱讀分析

番茄西紅柿發布于2019-05-23 16:08 / 2391人閱讀

摘要：實現接口通過源碼可以看到繼承自實現了接口接口接口接口。因此也說明類是線程不安全的類。插入指定位置插入元素，其邏輯如下校驗是否有效范圍，否則拋出數組越界異常擴容確保能有效插入。雙指針的思路，一個讀指針，一個寫指針。

ArrayList是最常用的一種集合類型。今天通過閱讀源碼的方式來加深對它的學習和理解。 ##實現接口

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

通過源碼可以看到ArrayList繼承自AbstractList,實現了List接口、RandomAccess接口、Cloneable接口、Serializable接口。說明它具備以下特點：

淺拷貝

序列化

常量

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

DEFAULT_CAPACITY 表示默認的容量是10個元素。

成員變量

transient Object[] elementData;
private int size;

elementData為實際存儲元素的數組，這里可以看到ArrayList的底層實際是一個數組。因此它具有數組的特點，隨機讀寫快，插入刪除慢。 transient關鍵字說明底層數組不能被序列化。？？

構造函數

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

無參構造函數，構造一個空的數組。

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(Collection<); {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

通過另外一個集合來構造。

添加元素方法 追加

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

這里可以看到add方法是線程不安全的，因為size++操作并非原子操作。因此也說明ArrayList類是線程不安全的類。 ensureCapacityInternal()方法保證數組容量可以容納新增的這個元素，不會出現數組越界的情況。

插入

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

指定index位置插入元素，其邏輯如下：

校驗index是否有效范圍，否則拋出數組越界異常.

擴容確保能有效插入。

將原數組index位置之后的元素全部后移一個位置。

將index位置設置為待插入元素。

添加集合方法 追加集合

public boolean addAll(Collection<); {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

和追加單個元素的原理類似，不同之處在于追加方式在于使用System.arraycopy方法。

插入集合

public boolean addAll(int index, Collection<); {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

和插入單個元素的原理類似，不同之處在于index之后的元素往后移的位置為插入集合的長度。

移除元素方法 根據索引移除

public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

邏輯如下：

校驗index是否合法，否則拋出數組越界異常

將index+1及以后的元素往前移一個位置

將最后一個元素置為null，同時size減一

返回刪除的元素值。

刪除元素

 public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

原理簡單，就是通過遍歷的方式。但是需要注意的是，只會移除第一個找到的元素。 fastRemove方法和remove(index) 方法作用相同，只是去掉了邊界校驗和返回值。

查詢 通過索引獲取元素

public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

原理就是通過數組獲取指定index的元素。

從前往后查找第一個出現的元素

public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

從后往前查找第一個出現的元素

public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

集合運算 并集

并集就是addAll方法

交集

 public boolean retainAll(Collection<); {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }

差集

public boolean removeAll(Collection<); {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

交集和差集都調用了batchRemove方法，通過一個boolean標記來表示要留下的是相同的一部分還是不同的一部分。 batchRemove方法的寫法還是值得學習。

batchRemove

private boolean batchRemove(Collection<);boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

雙指針的思路，一個讀指針，一個寫指針。讀指針每次往前增加一個位置，寫指針遇到要保留的元素時，再往前移動一個位置。最后，如果讀指針沒走到最后就異常了，那把剩下讀指針剩下的元素拷貝到寫指針之后。如果寫指針沒到最后，說明寫指針后面的元素都需要剔除，手動置為null，否則會內存泄露。如果寫指針走到了最后，說明一個元素都沒有移除掉，所以返回false。

GPU云服務器云服務器 ArrayList源碼源碼閱讀 webrtc源碼閱讀 hbase源碼閱讀

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/7112.html

ArrayList源碼閱讀分析

摘要：實現接口通過源碼可以看到繼承自實現了接口接口接口接口。因此也說明類是線程不安全的類。插入指定位置插入元素，其邏輯如下校驗是否有效范圍，否則拋出數組越界異常擴容確保能有效插入。雙指針的思路，一個讀指針，一個寫指針。ArrayList是最常用的一種集合類型。今天通過閱讀源碼的方式來加深對它的學習和理解。 ##實現接口 public class ArrayList extends Abstract...

番茄西紅柿 2019-05-23 16:08 評論0 收藏0
ArrayList源碼閱讀分析

摘要：實現接口通過源碼可以看到繼承自實現了接口接口接口接口。因此也說明類是線程不安全的類。插入指定位置插入元素，其邏輯如下校驗是否有效范圍，否則拋出數組越界異常擴容確保能有效插入。雙指針的思路，一個讀指針，一個寫指針。ArrayList是最常用的一種集合類型。今天通過閱讀源碼的方式來加深對它的學習和理解。 ##實現接口 public class ArrayList extends Abstract...

xiyang 2019-05-22 19:26 評論0 收藏0
源碼|jdk源碼-ArrayList與Vector源碼閱讀

摘要：畢業兩個星期了，開始成為一名正式的碼農了。將指定位置的數據移除。但是問題是，為時，并不是直接一個大小為的數組，而是使用靜態變量來代替。此外，函數還做了越界檢查。返回迭代器，與之有一個搭配的輔助類。畢業兩個星期了，開始成為一名正式的java碼農了。一直對偏底層比較感興趣，想著深入自己的java技能，看書、讀源碼、總結、造輪子實踐都是付諸行動的方法。說到看源碼，就應該由簡入難，逐漸加深，...

0x584a 2019-08-16 12:42 評論0 收藏0
ArrayList 源碼詳細分析

摘要：源碼分析構造方法有兩個構造方法，一個是無參，另一個需傳入初始容量值。所以我們可以把上面的代碼轉換一下，等價于下面形式這個時候，我們再去分析一下的迭代器源碼就能找出原因。原因是刪除元素后，元素計數器，而迭代器中的也等于，從而導致返回。 1.概述 ArrayList 是一種變長的集合類，基于定長數組實現。ArrayList 允許空值和重復元素，當往 ArrayList 中添加的元素數量大于...

W4n9Hu1 2019-08-15 13:51 評論0 收藏0
TOMCAT源碼閱讀總結（1）-TOMCAT的類加載體系

摘要：加載器之間父子關系不是通過類繼承的方式，而是通過對象變量的方式，來實現的。調用的方法，將設置為所有的獲取各個類加載器相應的資源配置文件這些是具體配置在配置文件中的。摘要一直以來想看一下tomcat的源碼，可以從頭到尾理解一遍在整個web請求的處理過程中，容器完成的功能，容器怎么把一個url的請求的處理遞交給了servlet，容器的pipeline是怎么設計的，容器的filter怎么...

ChanceWong 2019-08-15 12:13 評論0 收藏0