ArrayList源碼分析

来源:https://www.cnblogs.com/HuiH/archive/2019/11/08/11822925.html

首先來總結一下,ArrayList的一些特點: 1.arraylist本質上就是一個elementData數組,它允許對元素進行快速隨機訪問,可以存放null值; 2.arraylist區別於數組的地方在於能夠自動擴展大小,其中關鍵就是grow() 方法,每次擴充後數組為原來數組的1.5倍; 3.a ...


首先來總結一下,ArrayList的一些特點:

  1.arraylist本質上就是一個elementData數組,它允許對元素進行快速隨機訪問,可以存放null值;

  2.arraylist區別於數組的地方在於能夠自動擴展大小,其中關鍵就是grow() 方法,每次擴充後數組為原來數組的1.5倍;

  3.arraylist由於本質是數組,所以它在數據的查詢方面會很快,而在插入刪除方面,性能會下降很多,要移動很多數據才能達到應有的效果;

  4.arraylist中的removeAll(collection c)和clear() 的區別就是removeAll可以刪除批量指定的元素,而clear是全部刪除集合中的元素;

  5.arraylist實現了RandomAccess,所以在遍歷時推薦使用for迴圈;

  6.arraylist是線程不安全的;

一、繼承結構和層次關係

  

  

  由圖可以看出,ArrayList 繼承於AbstractList;AbstractList 繼承於AbstractCollection;所有類都繼承於Object。

1.為什麼要先繼承AbstractList,讓AbstractList先實現List<E>,而不是讓ArrayList直接實現List<E>?

  介面中全都是抽象的方法,而抽象類中可以有抽象方法,還可以有具體的實現方法,讓AbstractList實現介面中一些通用的方法,而具體的類,如ArrayList就繼承這個AbstractList類,拿到一些通用的方法,然後自己再實現一些自己特有的方法。

2.ArrayList實現了那些介面?

  List<E>介面

  RandomAccedd介面:是一個標記性介面,作用是用來快速隨機存取。若實現了該介面,使用普通的for迴圈來遍歷,性能更高,例如arraylist。而沒有實現該方法的介面,使用iterator來迭代,這樣性能更高,例如LinkedList。

  Cloneable介面:實現了該介面,就可以使用Object.Clone()方法。

  Serializable介面:實現該序列化介面,表明該類可以被序列化。

二、構造方法

  

1.無參構造方法

1 //這裡就說明瞭預設會給10的大小,所以說一開始arrayList的容量是10.
2      //ArrayList中儲存數據的其實就是一個數組,這個數組就是elementData,在123行定義的 private transient Object[] elementData;
3    public ArrayList() {  
4             super();        //調用父類中的無參構造方法,父類中的是個空的構造方法
5             this.elementData = EMPTY_ELEMENTDATA;    //EMPTY_ELEMENTDATA:是個空的Object[], 將elementData初始化,elementData也是個Object[]類型。空的Object[]會給預設大小10。
6         }

2.有參構造方法1

1   public ArrayList(int initialCapacity) {
2         super(); //父類中空的構造方法
3         if (initialCapacity < 0)    //判斷如果自定義大小的容量小於0,則報非法數據異常
4             throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
5             this.elementData = new Object[initialCapacity]; //將自定義的容量大小當成初始化elementData的大小
6     }

3.有參構造方法2(不常用)

1  //我還有一個Collection<Student>、由於這個Student繼承了Person,那麼根據這個構造方法,我就可以把這個Collection<Student>轉換為ArrayList<Sudent>這就是這個構造方法的作用 
2      public ArrayList(Collection<? extends E> c) {
3         elementData = c.toArray();    //轉換為數組
4         size = elementData.length;   //數組中的數據個數
5         if (elementData.getClass() != Object[].class) //每個集合的toarray()的實現方法不一樣,所以需要判斷一下,如果不是Object[].class類型,那麼就需要使用ArrayList中的方法去改造一下。
6             elementData = Arrays.copyOf(elementData, size, Object[].class);
7     }

 

三、常用方法

1.add方法

  

boolean add(E);//預設直接在末尾添加元素

1 public boolean add(E e) {    
2     //確定內部容量是否夠了,size是數組中數據的個數,因為要添加一個元素,所以size+1,先判斷size+1的這個數數組能否放得下,就在這個方法中去判斷是否數組.length是否夠用了。
3         ensureCapacityInternal(size + 1);  
4         //在數據中正確的位置上放上元素e,並且size++
5         elementData[size++] = e;
6         return true;
7     }

ensureCapacityInternal(xxx);

1 private void ensureCapacityInternal(int minCapacity) {
2         if (elementData == EMPTY_ELEMENTDATA) { //判斷初始化的elementData是不是空的數組,也就是沒有長度。因為如果是空的話,minCapacity=size+1;其實就是等於1,空的數組沒有長度就存放不了,所以就將minCapacity變成10,也就是預設大小,但是在這裡,還沒有真正的初始化這個elementData的大小。
3             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
4         }
5         //確認實際的容量,上面只是將minCapacity=10,這個方法就是真正的判斷elementData是否夠用
6         ensureExplicitCapacity(minCapacity);
7     }

ensureExplicitCapacity(xxx);

1 private void ensureExplicitCapacity(int minCapacity) {
2         modCount++;
3 //minCapacity如果大於了實際elementData的長度,那麼就說明elementData數組的長度不夠用,不夠用那麼就要增加elementData的length。
4 /*第一種情況:由於elementData初始化時是空的數組,那麼第一次add的時候,minCapacity=size+1;也就minCapacity=1,在上一個方法(確定內部容量ensureCapacityInternal)就會判斷出是空的數組,就會將minCapacity=10,到這一步為止,還沒有改變elementData的大小,
5  第二種情況:elementData不是空的數組了,那麼在add的時候,minCapacity=size+1;也就是minCapacity代表著elementData中增加之後的實際數據個數,拿著它判斷elementData的length是否夠用,如果length不夠用,那麼肯定要擴大容量,不然增加的這個元素就會溢出。
6 */
7         if (minCapacity - elementData.length > 0)
8             grow(minCapacity); //arrayList能自動擴展大小的關鍵方法就在這裡了
9     }

grow(xxx);  //arraylist核心的方法,能擴展數組大小的關鍵。

 1 private void grow(int minCapacity) {
 2         int oldCapacity = elementData.length;  //將擴充前的elementData大小給oldCapacity
 3         int newCapacity = oldCapacity + (oldCapacity >> 1);    //newCapacity就是1.5倍的oldCapacity
 4         if (newCapacity - minCapacity < 0)//這句話就是適應於elementData為空數組的時候,length=0,那麼oldCapacity=0,newCapacity=0,所以這個判斷成立,在這裡就是真正的初始化elementData的大小了,就是為10。
 5             newCapacity = minCapacity;
 6         if (newCapacity - MAX_ARRAY_SIZE > 0)//如果newCapacity超過了最大的容量限制,就調用hugeCapacity,也就是將能給的最大值給newCapacity
 7             newCapacity = hugeCapacity(minCapacity);
 8         //新的容量大小已經確定好了,就copy數組,改變容量大小。
 9         elementData = Arrays.copyOf(elementData, newCapacity);
10     }

hugeCapacity();

1 //這個就是上面用到的方法,就是用來賦最大值。
2     private static int hugeCapacity(int minCapacity) {
3         if (minCapacity < 0) 
4             throw new OutOfMemoryError();
5 //如果minCapacity都大於MAX_ARRAY_SIZE,那麼就Integer.MAX_VALUE返回,反之將MAX_ARRAY_SIZE返回。因為maxCapacity是三倍的minCapacity,可能擴充的太大了,就用minCapacity來判斷了。
6 //Integer.MAX_VALUE:2147483647   MAX_ARRAY_SIZE:2147483639  也就是說最大也就能給到第一個數值。還是超過了這個限制,就要溢出了。相當於arraylist給了兩層防護。
7         return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE : MAX_ARRAY_SIZE;
8     }

 

void add(int ,E);  //在特定的位置添加元素,也就是插入元素

 1 public void add(int index, E element) {
 2         rangeCheckForAdd(index);//檢查index也就是插入的位置是否合理。
 3 //跟上面的分析一樣,具體看上面
 4         ensureCapacityInternal(size + 1); 
 5 //這個方法就是用來在插入元素之後,要將index之後的元素都往後移一位,
 6         System.arraycopy(elementData, index, elementData, index + 1,  size - index);  // System.arraycopy(...):就是將elementData在插入位置後的所有元素往後面移一位
 7 //在目標位置上存放元素
 8         elementData[index] = element;
 9         size++;    //size增加1
10     }

rangeCheckForAdd(index)

1   private void rangeCheckForAdd(int index) {
2         if (index > size || index < 0)   //插入的位置肯定不能大於size 和小於0
3      //如果是,就報這個越界異常
4             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
5     }

 

2.刪除方法

  

  

  

 remove(int) 方法:通過刪除指定位置上的元素

 1 public E remove(int index) {
 2         rangeCheck(index);//檢查index的合理性
 3         modCount++;//這個作用很多,比如用來檢測快速失敗的一種標誌。
 4         E oldValue = elementData(index);//通過索引直接找到該元素
 5         int numMoved = size - index - 1;//計算要移動的位數。
 6         if (numMoved > 0)
 7 //這個方法也已經解釋過了,就是用來移動元素的。
 8             System.arraycopy(elementData, index+1, elementData, index, numMoved);
 9 //將--size上的位置賦值為null,讓gc(垃圾回收機制)更快的回收它。
10             elementData[--size] = null; 
11 //返回刪除的元素。
12 return oldValue;
13     }

 remove(Object):這個方法可以看出來,arraylist是可以存放null值的。

 1 //就是通過元素來刪除該元素,就依次遍歷,如果有這個元素,就將該元素的索引傳給fastRemobe(index),使用這個方法來刪除該元素,fastRemove(index)方法的內部跟remove(index)的實現幾乎一樣,這裡最主要是知道arrayList可以存儲null值。
 2      public boolean remove(Object o) {
 3         if (o == null) {
 4             for (int index = 0; index < size; index++)
 5                 if (elementData[index] == null) {
 6                     fastRemove(index);
 7                     return true;
 8                 }
 9         } else {
10             for (int index = 0; index < size; index++)
11                 if (o.equals(elementData[index])) {
12                     fastRemove(index);
13                     return true;
14                 }
15         }
16         return false;
17     }

clear():將elementData中每個元素都賦值為null,等待垃圾回收將這個給回收掉,所以叫clear;

1 public void clear() {
2         modCount++;
3         for (int i = 0; i < size; i++)
4             elementData[i] = null;
5         size = 0;
6     }

removeAll(collection c)

1  public boolean removeAll(Collection<?> c) {
2          return batchRemove(c, false);//批量刪除
3      }

  其中的batchRemove(xx,xx):用於兩個方法,一個removeAll():它只清楚指定集合中的元素,retainAll() 用來測試兩個集合是否有交集。

 1 //這個方法,用於兩處地方,如果complement為false,則用於removeAll;如果為true,則給retainAll()用
 2    private boolean batchRemove(Collection<?> c, boolean complement) {
 3         final Object[] elementData = this.elementData; //將原集合,記名為A
 4         int r = 0, w = 0;   //r用來控制迴圈,w是記錄有多少個交集
 5         boolean modified = false;  
 6         try {
 7             for (; r < size; r++)
 8 //參數中的集合C一次檢測集合A中的元素是否有,
 9                 if (c.contains(elementData[r]) == complement)
10 //有的話,就給集合A
11                     elementData[w++] = elementData[r];
12         } finally {
13 //如果contains方法使用過程報異常
14             if (r != size) {
15 //將剩下的元素都賦值給集合A,
16                 System.arraycopy(elementData, r, elementData, w, size - r);
17                 w += size - r;
18             }
19             if (w != size) {
20 //這裡有兩個用途,在removeAll()時,w一直為0,就直接跟clear一樣,全是為null。
21 //retainAll():沒有一個交集返回true,有交集但不全交也返回true,而兩個集合相等的時候,返回false,所以不能根據返回值來確認兩個集合是否有交集,而是通過原集合的大小是否發生改變來判斷,如果原集合中還有元素,則代表有交集,而元集合沒有元素了,說明兩個集合沒有交集。
22           
23                 for (int i = w; i < size; i++)
24                     elementData[i] = null;
25                 modCount += size - w;
26                 size = w;
27                 modified = true;
28             }
29         }
30         return modified;
31     }

 


您的分享是我們最大的動力!

更多相關文章
  • 前言 array,顧名思義,數組,就是存儲數字、處理數字的一種數據結構。今天在將list轉換為array時,遇到了一個問題,數據量比較大,剛開始怎麼都不知道問題出在哪裡。直到我用一個3 3的小數據測試時,才發現問題的本質所在。浪費了半天的時間,不過總算搞明白了。 學的不夠踏實,以此警戒所有的初學者: ...
  • Python 3最重要的新特性之一是對字元串和二進位數據流做了明確的區分。文本總是Unicode,由str類型表示,二進位數據則由bytes類型表示。Python 3不會以任意隱式的方式混用str和bytes,你不能拼接字元串和位元組流,也無法在位元組流里搜索字元串(反之亦然),也不能將字元串傳入參數為 ...
  • Python編寫類的時候,每個函數參數第一個參數都是self,一開始我不管它到底是幹嘛的,只知道必須要寫上。後來對Python漸漸熟悉了一點,再回頭看self的概念,似乎有點弄明白了。 首先明確的是self只有在類的方法中才會有,獨立的函數或方法是不必帶有self的。self在定義類的方法時是必須有 ...
  • php中有很多排序的函數,sort,rsort,ksort,krsort,asort,arsort,natcasesort,這些函數用來對數組的鍵或值進行這樣,或那樣的排序。 可以終究有時候還需要一些函數來隨機獲取數組的元素。 array_rand()函數 隨機獲取數組中的一個函數,可以通過第二個參 ...
  • 雖然之前已經學了2個月python,但仍然感覺學的很亂,沒有系統性;或者說自學的沒有條例,只是追求進度,沒有保證知識點的全面與準確。 從今天開始,從python的基礎變數開始重新整理知識點,梳理忽略的內容。願所學即所會,所會即能用。 1、變數名遵循的規則 只能包含字母、數字和下劃線。需要以字母或下劃 ...
一周排行
x