【Java】- 源碼解析——ArrayList

一、ArrayList簡介

　　由于ArrayList底層是通過數組進行實現的，所以我們在說ArrayList之前我們先說下數組

　　數組：

　　　　優點： a、有序 ---- > 存儲的順序位置和訪問取出的順序一致

　　　　　　　　b、查詢取值速度快 ---- > 　根據索引可以直接查詢定位索要的value值

　　　　缺點： a、數組長度定義后不可改變，即不可擴容

　　　　　　　　b、數組由于是有序，所以在中間進行插入刪除值時會很慢

　　ArrayList：

　　　　a、由于ArrayList底層時通過數組來實現的List類，ArrayList集合滿足了數組的所有有點，同時改善了數據的部分缺點，比如可以自動擴容

　　　　b、該類定義了一個Object[]的數組，來達到存儲任何值的效果，并且類中通過capacity屬性來記錄數組的長度，若是在數組中添加數據，

　　那么capacity就會自動增長來統計Object[]的數組長度

　　　　c、若是該類有大量數據存儲，可以在創建對象時傳入capacity值，來定義集合的長度(內部Object[])數組的長度，從而建少擴容次數，減少

　　重分配的次數，提高性能

　　　　d、ArrayList 和 vector 提供了一模一樣的方法，唯一的缺點就是 vector 類是線程安全的，而 ArrayList 是線程非安全的，所以效率來說

　　ArrayList 比 Vector 更快

二、ArrayList繼承關系

1 public class ArrayList<E> extends AbstractList<E>
2         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
3 
4 public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

　　有代碼可知：

　　　　ArrayList 繼承 AbstractList 繼承 AbstractCollection

　　　　　　　　實現 List RandomAccess Cloneable Serializable

三、源碼講解

　　1、類屬性講解

 1 public class ArrayList<E> extends AbstractList<E>
 2         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
 3 {
 4     // 版本號用于序列反序列化時版本匹配
 5     private static final long serialVersionUID = 8683452581122892189L;
 6     // 缺省容量
 7     private static final int DEFAULT_CAPACITY = 10;
 8     // 空對象數組
 9     private static final Object[] EMPTY_ELEMENTDATA = {};
10     // 缺省空對象數組
11     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
12     // 元素數組用例存儲arraylist的value值
13     transient Object[] elementData;
14     // 實際元素大小，默認為0
15     private int size;
16     // 最大數組容量
17     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
18 }

　　2、構造方法

　　　　2.1、無參構造方法

1 /**
2 * 無參構造方法， 同時為 elementData 進行初始化，類型為Object[]，
3 * 且數組長度為空，后面會進行賦默認值10
4 */
5 public ArrayList() {
6     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
7 }

　　　　2.2、自定義數組長度構造方法

 1 public ArrayList(int initialCapacity) {
 2     if (initialCapacity > 0) {  // 自定義容量大小>0時,將自定義容量作為數組初始化容量大小
 3         this.elementData = new Object[initialCapacity];
 4     } else if (initialCapacity == 0) {// 自定義容量大小=0時,通過空對象數組EMPTY_ELEMENTDATA來初始化數組
 5         this.elementData = EMPTY_ELEMENTDATA;
 6     } else {  // 自定義容量大小<0時, 拋出IllegalArgumentException不合法的參數異常
 7         throw new IllegalArgumentException("Illegal Capacity: "+
 8                                            initialCapacity);
 9     }
10 }

　　　　　2.3、通過一個集合來調用構造函數

 1 public ArrayList(Collection<? extends E> c) { // 傳參為繼承Collection的數組
 2     // object[] toArray() 從第一個到最后一個返回數組來初始化elementData 轉換為數組
 3     elementData = c.toArray();  
 4     if ((size = elementData.length) != 0) {// 若是elementData.length不為0且將elementData.length賦值給size
 5         // 通過反射判斷若是elementData對象不是Object[].class的對象
 6         if (elementData.getClass() != Object[].class) 
 7         // 通過Arrays.copyOf來處理,返回新數組對象，且數組類型為Object[]
 8             elementData = Arrays.copyOf(elementData, size, Object[].class); 
 9     } else {
10         this.elementData = EMPTY_ELEMENTDATA; // 通過空對象數組EMPTY_ELEMENTDATA來初始化數組
11     }
12 }

　　總結：arrayList的構造方法就做一件事情，就是初始化一下儲存數據的容器，其實本質上就是一個數組，在其中就叫elementData。

　　2.4、提供的核心方法

　　　　2.4.1、add()方法：

　　　　　　add(E e) ：將指定的元素追加到此列表的末尾。

　　　　　　add(int index, E element) ：在此列表中的指定位置插入指定的元素。

　　　　　　addAll(Collection<? extends E> c) : 按指定集合的Iterator返回的順序將指定集合中的所有元素追加到此列表的末尾。

　　　　　　addAll(int index, Collection<? extends E> c) : 將指定集合中的所有元素插入到此列表中，從指定的位置開始。

　　　　a、 add(E e) ：將指定的元素追加到此列表的末尾。

1 // 在末尾添加元素<E>類型元素
2 public boolean add(E e) {
3     ensureCapacityInternal(size + 1);  // 判斷數組容量是否夠用 size代表數組中的元素個數
4     elementData[size++] = e; // 將原則添加在數組中，且size自增1
5     return true; 
6 }

　　　　數組容量判定方法解析一

 1 private void ensureCapacityInternal(int minCapacity) { // minCapacity=size+1 size代表數組中的元素個數
 2     // 若是elementData為空：
 3         // 1、無參函數創建 new ArrayList()
 4         // 2、有參自定義值為0，調用構造函數 new ArrayList(0)
 5         // 3、傳入集合，但集合為空，new ArrayList(new LinkList(0))
 6     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
 7         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 將 minCapacity  賦值為10 默認值
 8     }
 9     // 具體判定容量方法
10     ensureExplicitCapacity(minCapacity);
11 }

　　　　數組容量判定方法解析二

1 private void ensureExplicitCapacity(int minCapacity) {
2     modCount++;
3     // minCapacity 解析：(minCapacity代表elementData數組存儲數組所需的最小容量)
4         //若是數組初始化后第一次調用 由ensureCapacityInternal()方法中判斷可知minCapacity賦值為10
5         //而elementData.length=0
6         //若是數組初始化后非第一次調用 由ensureCapacityInternal()方法中判斷可知minCapacity = size+1
7     if (minCapacity - elementData.length > 0)
8         grow(minCapacity);
9 }

　　　　數組擴容方法解析

 1 private void grow(int minCapacity) {
 2     // 獲取elementData數組原長度 放入oldCapacity變量中
 3     int oldCapacity = elementData.length; 
 4     // 擴容elementData.lenth*1.5倍后的值放入變量newCapacity中， oldCapacity >> 1 有位移相當于oldCapacity/2
 5     int newCapacity = oldCapacity + (oldCapacity >> 1); 
 6     if (newCapacity - minCapacity < 0) // 擴容后的容量值<最小所需容量值 適用于elementData為空數組時
 7         newCapacity = minCapacity; // 就直接用最小容量進行擴容
 8     //private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 9     if (newCapacity - MAX_ARRAY_SIZE > 0) // 原數組擴容1.5倍后的值>最大數組容量
10         newCapacity = hugeCapacity(minCapacity); // 將最大容量賦值給newCapacity
11     elementData = Arrays.copyOf(elementData, newCapacity);// 通過newCapacity進行擴容
12 }

　　　　hugeCapacity()方法解析

1 private static int hugeCapacity(int minCapacity) {
2     if (minCapacity < 0) // overflow 拋出OutOfMemoryError堆內存溢出
3         throw new OutOfMemoryError();
4    // Integer.MAX_VALUE：2147483647   MAX_ARRAY_SIZE：2147483639
5    // 若是minCapacity > MAX_ARRAY_SIZE則返回Integer.MAX_VALUE 否則返回MAX_ARRAY_SIZE
6     return (minCapacity > MAX_ARRAY_SIZE) ?
7         Integer.MAX_VALUE :
8         MAX_ARRAY_SIZE;
9 }

　　　　Arrays.copyOf() 方法說明

 1     //方法傳回的數組是新的數組對象，改變傳回數組中的元素值，不會影響原來的數組。
 2     // copyOf()的第二個自變量指定要建立的新數組長度，如果新數組的長度超過原數組的長度，則保留數組默認值
 3     // copyOf()的第二個自變量指定要建立的新數組長度，如果新數組的長度小于原數組的長度，則舍棄多出值
 4     public static void main(String[] args) {
 5     int[] arr1 = {1, 2, 3, 4, 5};
 6     int[] arr2 = Arrays.copyOf(arr1, 5);
 7     int[] arr3 = Arrays.copyOf(arr1, 10);
 8     int[] arr4 = Arrays.copyOf(arr1, 4);
 9     System.out.print("原數組為：");
10     for(int i : arr1){
11         System.out.print(i+" ");
12    }
13     System.out.print("\n");
14     System.out.print("等于原數組為：");
15     for(int i : arr2){
16         System.out.print(i+" ");
17     }
18     System.out.print("\n");
19     System.out.print("多于原數組為：");
20     for(int i : arr3){
21         System.out.print(i+" ");
22     }
23     System.out.print("\n");
24     System.out.print("少于原數組為：");
25     for(int i : arr4){
26         System.out.print(i+" ");
27     }
28 }

　　　　b、add(int index, E element) ：在此列表中的指定位置插入指定的元素。

1 public void add(int index, E element) {
2     rangeCheckForAdd(index);  //校驗索引有效性
3     ensureCapacityInternal(size + 1);  // 校驗數組容量是否需要擴容  參考以上詳細講解
4     System.arraycopy(elementData, index, elementData, index + 1,
5                      size - index);
6     elementData[index] = element;
7     size++;
8 }

　　　　rangeCheckForAdd()方法分析

1 public void add(int index, E element) {
2     rangeCheckForAdd(index);  //校驗索引有效性
3     ensureCapacityInternal(size + 1);  // 校驗數組容量是否需要擴容  參考以上詳細講解
4     System.arraycopy(elementData, index, elementData, index + 1,
5                      size - index);
6     elementData[index] = element;
7     size++;
8 }

　　　　rangeCheckForAdd()方法分析

1 private void rangeCheckForAdd(int index) {
2     //若是索引信息>數組的容量或著索引信息<0 則拋出異常IndexOutOfBoundsException數組越界異常
3     if (index > size || index < 0)
4         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
5 }

　　　　2.4.2、刪除方法：

　　　　　　remove(int index) : 刪除該列表中指定位置的元素。

　　　　　　remove(Object o) : 從列表中刪除指定元素的第一個出現（根據值來刪除，且僅刪除第一個出現的值)

　　　　　　removeAll(Collection<?> c) : 從此列表中刪除指定集合中包含的所有元素。

　　　　　　removeIf(Predicate<? super E> filter) ：刪除滿足給定謂詞的此集合的所有元素。

　　　　　　removeRange(int fromIndex, int toIndex) ：從這個列表中刪除所有索引在 fromIndex （含）和 toIndex之間的元素。

　　　　　　由于刪除代碼功能相似，僅挑選常用的進行說明

　　　　a、remove(int index) : 刪除該列表中指定位置的元素

 1 public E remove(int index) {
 2     rangeCheck(index); // 索引校驗  當index索引值>size數組容量時 IndexOutOfBoundsException 拋出數組越界異常
 3     modCount++;
 4     E oldValue = elementData(index);   // 取出數組索引對應的value值
 5     int numMoved = size - index - 1;  // 計算需要數組往前移動的位數
 6     if (numMoved > 0)
 7         System.arraycopy(elementData, index+1, elementData, index,
 8                          numMoved);  // 此方法為System類靜態方法且native修飾，作用將刪除索引位置后的所有元素，往前移動一位
 9     elementData[--size] = null; // size數組真實容量-1 且 將數組最后一位置為null 等待GC回收器刪除
10     return oldValue; // 返回被remove指定索引的值
11 }

　　　　b、remove(Object o) : 從列表中刪除指定元素的第一個出現（根據值來刪除，且僅刪除第一個出現的值)

 1 // 該方法不用解釋，簡單來說就是通過傳參Object o 值來循環遍歷數組，
 2 // 若是存在這個元素就將該元素的索引傳給fastRemove(index)來進行刪除
 3 // 通過此方法 remove(Object o)可以知道 ArrayList可以存儲null值
 4 public boolean remove(Object o) {
 5     if (o == null) {
 6         for (int index = 0; index < size; index++)
 7             if (elementData[index] == null) {
 8                 fastRemove(index);
 9                 return true;
10             }
11     } else {
12         for (int index = 0; index < size; index++)
13             if (o.equals(elementData[index])) {
14                 fastRemove(index);
15                 return true;
16             }
17     }
18     return false;
19 }

　　　　fastRemove(index)分析

1 // 此方法不做過多介紹，和 remove(int index) 幾乎相同，只不過remove(int index) 獲取了index對應的元素
2 private void fastRemove(int index) {
3     modCount++;
4     int numMoved = size - index - 1;
5     if (numMoved > 0)
6         System.arraycopy(elementData, index+1, elementData, index,
7                          numMoved);
8     elementData[--size] = null; // clear to let GC do its work
9 }

　　　　c、removeAll(Collection<?> c) : 從此列表中刪除指定集合中包含的所有元素

1 public boolean removeAll(Collection<?> c) {
2     Objects.requireNonNull(c);  // 校驗集合不能為null 否則拋出空指針異常
3     return batchRemove(c, false);
4 }

　　　　batchRemove(c, false)解析

 1 private boolean batchRemove(Collection<?> c, boolean complement) {
 2     // complement 為false 則為removeAll()調用使用 為true 則為retainAll()用 
 3     // retainAll() 是用來檢測兩個集合是否有交集的
 4     final Object[] elementData = this.elementData;   //將原集合，記名為 elementData
 5     int r = 0, w = 0; //r用來控制循環，w是記錄有多少個交集/差集  removeAll 調用記錄差集  retainAll()記錄交集
 6     boolean modified = false;
 7     try {
 8         for (; r < size; r++)
 9             if (c.contains(elementData[r]) == complement) // 校驗c集合元素是否在elementData中是否為false/true
10                 // 若是 complement = true 則將 c中包含elementData中的元素 替換 elementData[w++]位置值 達到元素前移效果
11                 // 若是 complement = false則將 c中不包含elementData中的元素 存入 elementData[w++]位置值 達到元素前移效果
12                 elementData[w++] = elementData[r]; 
13     } finally {
14          if (r != size) { //  r ！= size 只會在 c.contains()直接報錯，否則r==size 一直不走此段邏輯
15             System.arraycopy(elementData, r,
16                              elementData, w,
17                              size - r);
18             w += size - r;
19         }
20         if (w != size) { // 將 自 elementData[w] 到 elementData[size-1]的值全部置為null
21             for (int i = w; i < size; i++)
22                 elementData[i] = null;
23             modCount += size - w; // 標記elementData數組修改次數
24             size = w; // 修改 size 實例容量
25             modified = true;
26         }
27     }
28     return modified;
29 }

　　　　2.4.3、clear方法

　　　　　　從列表中刪除所有元素。

1 // 循環遍歷數組將數組元素全部置為null 等等GC回收機制回收
2 public void clear() {
3     modCount++;
4     // clear to let GC do its work
5     for (int i = 0; i < size; i++)
6         elementData[i] = null;
7 
8     size = 0;
9 }

　　　　2.4.4、ensureCapacity(int minCapacity)方法

　　　　　　增加此 ArrayList實例的容量，以確保它可以至少保存最小容量參數指定的元素數。

public void ensureCapacity(int minCapacity) {
    // 如果elementData不為DEFAULTCAPACITY_EMPTY_ELEMENTDATA(常量{})那么minExpand =0否則minExpand = DEFAULT_CAPACITY(常量10)
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        ? 0
        : DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
        // 修改elementData容量
        ensureExplicitCapacity(minCapacity);
    }
}

　　　　ensureExplicitCapacity(minCapacity)解析

1 private void ensureExplicitCapacity(int minCapacity) {
2     modCount++;
3     if (minCapacity - elementData.length > 0) // 若是 minCapacity>當前數組的容量 則進行擴容
4         grow(minCapacity);
5 }

　　　　　　用指定的元素替換此列表中指定位置的元素

 1 public E set(int index, E element) {
 2     // 檢驗索引是否合法
 3     rangeCheck(index);
 4     // 舊值
 5     E oldValue = elementData(index);
 6     // 賦新值
 7     elementData[index] = element;
 8     // 返回舊值
 9     return oldValue;
10 }

四、ArrayList 總結：

　　 1、arrayList可以存放null。

　　2、arrayList本質上就是一個elementData數組。

　　3、arrayList區別于數組的地方在于能夠自動擴展大小，其中關鍵的方法就是gorw()方法。

　　4、arrayList中removeAll(collection c)和clear()的區別就是removeAll可以刪除批量指定的元素，而clear是全部刪除集合中的元素。

　　5、arrayList由于本質是數組，所以它在數據的查詢方面會很快，而在插入刪除這些方面，性能下降很多，有移動很多數據才能達到應有的效果

　　6、arrayList實現了RandomAccess，所以在遍歷它的時候推薦使用for循環。

感謝?。。。?br>

posted on 2021-02-10 02:44 一夢三千年閱讀(113) 評論(0) 收藏舉報

刷新頁面返回頂部

一夢三千年

導航

公告

【Java】- 源碼解析——ArrayList

一、ArrayList簡介

數組：

ArrayList：

二、ArrayList繼承關系

三、源碼講解

1、類屬性講解

2、構造方法

2.1、無參構造方法

2.2、自定義數組長度構造方法

2.3、通過一個集合來調用構造函數

2.4、提供的核心方法

2.4.1、add()方法：

2.4.2、刪除方法：

2.4.3、clear方法

2.4.4、ensureCapacity(int minCapacity)方法

四、ArrayList 總結：

一夢三千年

導航

公告

【Java】- 源碼解析——ArrayList

一、ArrayList簡介

數組：

ArrayList：

二、ArrayList繼承關系

三、源碼講解

1、類屬性講解

2、構造方法

2.1、無參構造方法

2.2、自定義數組長度構造方法

2.3、通過一個集合來調用構造函數

2.4、提供的核心方法

2.4.1、add()方法：

2.4.2、刪除方法：

2.4.3、clear方法

2.4.4、ensureCapacity(int minCapacity)方法

四、ArrayList 總結：

一、ArrayList簡介

　　數組：

　　ArrayList：

二、ArrayList繼承關系

三、源碼講解

　　1、類屬性講解

　　2、構造方法

　　　　2.1、無參構造方法

　　　　2.2、自定義數組長度構造方法

　　　　　2.3、通過一個集合來調用構造函數

　　2.4、提供的核心方法

　　　　2.4.1、add()方法：

　　　　2.4.2、刪除方法：

　　　　2.4.3、clear方法

　　　　2.4.4、ensureCapacity(int minCapacity)方法

四、ArrayList 總結：