天天看點
傳回

基于jdk1.8的ArrayList源碼分析

前言
ArrayList作為一個常用的集合類，這次我們簡單的根據源碼來看看AarryList是如何使用的。

ArrayList擁有的成員變量      
1 public class ArrayList<E> extends AbstractList<E>
 2         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
 3 {
 4     private static final long serialVersionUID = 8683452581122892189L;
 5 
 6     /**
 7      * Default initial capacity.
 8      */
 9     private static final int DEFAULT_CAPACITY = 10;
10 
11     /**
12      * Shared empty array instance used for empty instances.
13      */
14     private static final Object[] EMPTY_ELEMENTDATA = {};
15 
16     /**
17      * Shared empty array instance used for default sized empty instances. We
18      * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
19      * first element is added.
20      */
21     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
22 
23     /**
24      * The array buffer into which the elements of the ArrayList are stored.
25      * The capacity of the ArrayList is the length of this array buffer. Any
26      * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
27      * will be expanded to DEFAULT_CAPACITY when the first element is added.
28      */
29     transient Object[] elementData; // non-private to simplify nested class access
30 
31     /**
32      * The size of the ArrayList (the number of elements it contains).
33      *
34      * @serial
35      */
36     private int size;      
根據源碼顯示
1. 實作的接口看出，支援随機通路，克隆，序列化；
2. 第9行代碼表示預設初始的容器大小DEFAULT_CAPACITY為10;
3. 第29行代碼中的elementData存儲數組資料，是 Object[] 類型的數組；
4. size為實際數組大小；

構造函數      
1 /**
 2      * 構造一個指定初始容量的空清單
 3      * @param  initialCapacity  ArrayList的初始容量
 4      * @throws IllegalArgumentException 如果給定的初始容量為負值
 5      */
 6     public ArrayList(int initialCapacity) {
 7         if (initialCapacity > 0) {
 8             this.elementData = new Object[initialCapacity];
 9         } else if (initialCapacity == 0) {
10             this.elementData = EMPTY_ELEMENTDATA;
11         } else {
12             throw new IllegalArgumentException("Illegal Capacity: "+
13                                                initialCapacity);
14         }
15     }
16 
17     // 構造一個預設的空清單，但是沒有配置設定大小，直到第一次添加元素的時候才給數組賦初始大小為10
18     public ArrayList() {
19         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
20     }
21 
22     /**
23      * 構造一個包含指定collection的元素的清單，這些元素按照該collection的疊代器傳回的順序排列的
24      * @param c 包含用于去構造ArrayList的元素的collection
25      * @throws NullPointerException 如果指定的collection為空
26      */
27     public ArrayList(Collection<? extends E> c) {
28         elementData = c.toArray();
29         if ((size = elementData.length) != 0) {
30             // c.toArray()可能不會正确地傳回一個 Object[]數組，那麼使用Arrays.copyOf()方法
31             if (elementData.getClass() != Object[].class)
32                 //Arrays.copyOf()傳回一個 Object[].class類型的，大小為size，元素為elementData[0,...,size-1]
33                 elementData = Arrays.copyOf(elementData, size, Object[].class);
34         } else {
35             // replace with empty array.
36             this.elementData = EMPTY_ELEMENTDATA;
37         }
38     }

添加元素源碼解析   

執行add方法

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

ensureCapacityInternal(size + 1)方法表示是一個擴容操作，進入方法顯示

1 　　private void ensureCapacityInternal(int minCapacity) {
 2         ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
 3     }
 4 
 5     private void ensureExplicitCapacity(int minCapacity) {
 6         modCount++;
 7 
 8         // overflow-conscious code
 9         if (minCapacity - elementData.length > 0)
10             grow(minCapacity);
11     }

modCount用于記錄ArrayList的結構性變化的次數，add()、remove()、addall()、removerange()及clear()方法都會讓modCount增長。這個參數暫時可以忽略，主要是用在集合的Fail-Fast機制(即快速失敗機制)的判斷中使用的，限于篇幅原因就不展開了

進入calculateCapacity方法可看到以下代碼段

1 private static int calculateCapacity(Object[] elementData, int minCapacity) {
2         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
3             return Math.max(DEFAULT_CAPACITY, minCapacity);
4         }
5         return minCapacity;
6     }

當elementData為空時，也就是我們在第一次添加添加元素的時候，預設賦給容器的大小為DEFAULT_CAPACITY，也就是我們前面說的初始大小為10

新增元素後的大小minCapacity是否超過目前集合的容量elementData.length，如果超過，則調用grow方法進行擴容。我們進入該方法進行檢視:

1 private void grow(int minCapacity) {
 2         // overflow-conscious code
 3         int oldCapacity = elementData.length;
 4         int newCapacity = oldCapacity + (oldCapacity >> 1);
 5         if (newCapacity - minCapacity < 0)
 6             newCapacity = minCapacity;
 7         if (newCapacity - MAX_ARRAY_SIZE > 0)
 8             newCapacity = hugeCapacity(minCapacity);
 9         // minCapacity is usually close to size, so this is a win:
10         elementData = Arrays.copyOf(elementData, newCapacity);
11     }

擴容操作比較簡單，基本的思路就是新加入元素後所需的的容器大小與原先容器的大小相比，小了則擴容oldCapacity + (oldCapacity >> 1)，也就是1.5倍，右移相當于除以2，然後将老容器的資料指派到新容器上，多次的擴容比較消耗性能，是以如果一開始知道資料量比較大可以先賦一個合适的初始容量

其他向某個位置插入元素與addAll方法都與上面add方法類似，基本思路都是先比較容量大小，或者增加一個索引越界判斷，然後将資料插入适當的位置，對後面的資料進行移位操作。

remove方法源碼解析

根據索引删除

1 public E remove(int index) {
 2         rangeCheck(index);
 3 
 4         modCount++;
 5         E oldValue = elementData(index);
 6 
 7         int numMoved = size - index - 1;
 8         if (numMoved > 0)
 9             System.arraycopy(elementData, index+1, elementData, index,
10                              numMoved);
11         elementData[--size] = null; // clear to let GC do its work
12 
13         return oldValue;
14     }

remove方法原理add方法類似

1.查找相應位置的資料

2.将index後面的資料向前移動一位，也就是把原先索引在index位置的對象覆寫

3.第11行代碼将多出的一位置為null，clear to let GC do its work，讓回收器能夠回收對象資料

4.傳回删除的對象

根據對象删除

1 public boolean remove(Object o) {
 2         if (o == null) {
 3             for (int index = 0; index < size; index++)
 4                 if (elementData[index] == null) {
 5                     fastRemove(index);
 6                     return true;
 7                 }
 8         } else {
 9             for (int index = 0; index < size; index++)
10                 if (o.equals(elementData[index])) {
11                     fastRemove(index);
12                     return true;
13                 }
14         }
15         return false;
16     }

1.循環查詢list中的對象是否與傳入的對象相同

2.相同則執行fastRemove(index)方法

3.fastRemove方法與根據索引删除的方法一緻，簡單的指派移位。

private void fastRemove(int index) {
        modCount++;
        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
    }

contain方法源碼解析

public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

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;
    }

1.便利查詢是否有該對象，有則傳回對應索引，否則傳回-1

在上述的删除操作中，常用到以下方法

1 public static native void arraycopy(Object src,  int  srcPos,
2                                         Object dest, int destPos,
3                                         int length);

這是一個native關鍵字修飾的本地方法本地方法和其它方法不一樣，本地方法意味着和平台有關，是以使用了native的程式可移植性都不太高。另外native方法在JVM中運作時資料區也和其它方法不一樣，它有專門的本地方法棧。native方法主要用于加載檔案和動态連結庫，由于Java語言無法通路作業系統底層資訊（比如：底層硬體裝置等），這時候就需要借助C語言來完成了。被native修飾的方法可以被C語言重寫。

參數 說明
src 源數組
srcPos 源數組索引，也就是說要從哪裡開始複制
dest 目标數組
destPos 目标數組索引，從第幾個位置放置新複制過來的數組
length　 要複制的數組長度

轉載于:https://www.cnblogs.com/xiguadadage/p/10097995.html

java C/C++ 作業系統
上一篇: LinkedList源碼分析——基于jdk1.8
下一篇: String 記憶體位址對比

繼續閱讀