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     }

 


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

更多相關文章
  • 今天,在Anaconda prompt啟動python遇到瞭如下錯誤: UnicodeDecodeError: ‘gbk’ codec can’t decode byte 0xaf in position 553: illegal multibyte sequence 看了看出錯跟蹤,查看瞭如下位置 ...
  • 許多小伙伴對於java中的三種初始化塊的執行順序一直感到頭疼,接下來我們就來分析一下這三種初始化塊到底是怎麼運行的。有些公司也會將這個問題作為筆試題目。 下麵通過一段代碼來看看創建對象時這麼初始化塊是如何運行的 package com.hxy; public class CodeBlock{ pub ...
  • 字元串或串(String)是由數字、字母、下劃線組成的一串字元。一般記為 s=“a1a2···an”(n>=0)。它是編程語言中表示文本的數據類型。在程式設計中,字元串(string)為符號或數值的一個連續序列,如符號串(一串字元)或二進位數字串(一串二進位數字)。 String類型你一定不陌生,畢 ...
  • 我們知道,swoole中有兩大進程,分別是 master 主進程和 manager 管理進程。 其中 master 主進程中會有一個主 reactor 線程和多個 reactor 線程,主要的作用就是用來維護TCP連接,處理網路IO,收發數據。 而 manager 管理進程,作用則是 fork 和管 ...
  • 1. random模塊 導入的是random模塊,格式是: import random 1.1 隨機小數 取隨機小數 : 數學計算。 print(random.random()) # 取0-1之間的小數print(random.uniform(1,2)) # 取1-2之間的小數 1.2 隨機整數 取 ...
  • 一、阻塞隊列:用於保存等待執行的任務。在阻塞隊列中,線程阻塞的兩種情況: 1.當隊列中沒有數據的情況下,消費者端的所有線程都會被自動阻塞(掛起),直到有數據放入隊列。 2.當隊列中填滿數據的情況下, 生產者端的所有線程都會被自動阻塞,知道隊列中有空位置,線程被自動喚醒。 二、阻塞隊列的主要方法 拋出 ...
  • 一、實習內容 選擇一個調度演算法,實現處理器調度。 二、實習目的 在採用多道程式設計的系統中,往往有若幹個進程同時處於就緒狀態。當就緒進程個數大於處理器數時,就必須依照某種策略來決定哪些進程優先占用處理器。本實習模擬在單處理器情況下的處理器調度,幫助學生加深瞭解處理器調度的工作。 三、實習題目 本實習 ...
  • Python實戰教程,用Python做列印日曆的小程式,使用者可以通過輸入年月信息,程式將會輸出這個月的日曆 ...
一周排行
  • C 語法糖——持續更新 1. return的switch寫法 ...
  • 0. 前言 繼上一篇,以及上上篇,我們對SqlSugar有了一個大概的認識,但是這並不完美,因為那些都是理論知識,無法描述我們工程開發中實際情況。而這一篇,將帶領小伙伴們一起試著寫一個能在工程中使用的模板類。 1. 創建一個Client SqlSugar在操作的時候需要一個Client,用來管理數據 ...
  • 1 class Program 2 { 3 static void Main(string[] args) 4 { 5 //數組:長度不可變,類型單一 6 //ArrayList集合:長度可以任意改變,類型可以不單一 7 8 //創建一個ArrayList對象 9 ArrayList mylist ...
  • .NET 程式下銳浪報表 (Grid++ Report) 的綠色發佈指南 在銳浪報表官方為 CSharp 編寫的開發文檔:“在C#與VB.NET中開始使用說明.txt” 中,關於發佈項目是這麼描述的: ★發佈你的項目,用VS.NET製作安裝程式:1、先創建安裝項目:在解決方案資源管理器的根節點上點右 ...
  • 執行代碼清理時,可以點擊那個掃把小圖片,會按照預設的第一種配置文件來自動修複。也可以點擊下拉三角符合,選擇不同的配置文件,然後進行修複。或者快捷鍵Ctrl+K,Ctrl+E。 針對每一項配置的說明: 刪除不必要的using 儘可能將私有欄位設置為只讀 刪除不必要的類型轉換(針對強類型轉換),像Con ...
  • 1.概念簡述 (1)AR模型 AR 模型(auto regressive model)自回歸模型,模型參量法高解析度譜分析方法之一,也是現代譜估計中常用的模型。 用AR模型法求信具體作法是: ①選擇AR模型,在輸入是衝激函數或白雜訊的情況下,使其輸出等於所研究的信號,至少,應是對該信號的一個好的近似 ...
  • 4.元組 元組的主要特性為: 1.元組在創建之後,具有不可以更改的特性,因此不能直接給元組的元素賦值 2.元組的元素類型可以為任意類型,如字典、字元串、列表等 3.元組常用於在程式的整個生命周期中都不變的場景中 4.1 常用方法 元組大小和內容在定義賦值之後,就不可更改,常用的方法如下所示: cou ...
  • 老孟導讀:今天分享一個類似“孔雀開屏”的動畫效果,打開新的頁面時,新的頁面從屏幕右上角以圓形逐漸打開到全屏。 先來看下具體的效果 不知道這種效果大家叫什麼名字?如果有更合適的名字可以在評論處告訴我,下麵來說下如何實現此效果。 在使用Navigator進入一個新的頁面時,通常用法如下: 就包含了切換頁 ...
  • hashCode() 和equals() 方法的重要性體現在什麼地方? Java中的HashMap使用hashCode()和equals()方法設置值,根據鍵獲取值的時候也會用到這兩個方法。 怎樣 設置 的值? hashCode()獲得 hash值。而hash值用來確定hashmap中內部 Node ...
  • IDEA一些不錯的插件分享 目錄 IDEA一些不錯的插件分享 插件集合 CamelCase Translation LiveEdit MarkDown Navigator Jrebel CheckStyle IDEA Alibaba Java Coding Guidelines Ideavim Ma ...