ArrayList源碼分析

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

首先來總結一下，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     }

 


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

-Advertisement-
Play Games
更多相關文章
  • Anaconda中啟動Python時的錯誤：UnicodeDecodeError: 'gbk' codec can't decode byte 0xaf in position 553
    今天，在Anaconda prompt啟動python遇到瞭如下錯誤： UnicodeDecodeError: ‘gbk’ codec can’t decode byte 0xaf in position 553: illegal multibyte sequence 看了看出錯跟蹤，查看瞭如下位置 ...
  • 關於java中三種初始化塊的執行順序
    許多小伙伴對於java中的三種初始化塊的執行順序一直感到頭疼，接下來我們就來分析一下這三種初始化塊到底是怎麼運行的。有些公司也會將這個問題作為筆試題目。 下麵通過一段代碼來看看創建對象時這麼初始化塊是如何運行的 package com.hxy; public class CodeBlock{ pub ...
  • 揭秘String類型背後的故事——帶你領略彙編語言魅力
    字元串或串(String)是由數字、字母、下劃線組成的一串字元。一般記為 s=“a1a2···an”(n>=0)。它是編程語言中表示文本的數據類型。在程式設計中，字元串（string）為符號或數值的一個連續序列，如符號串（一串字元）或二進位數字串（一串二進位數字）。 String類型你一定不陌生，畢 ...
  • swoole中使用task進程非同步的處理耗時任務
    我們知道，swoole中有兩大進程，分別是 master 主進程和 manager 管理進程。 其中 master 主進程中會有一個主 reactor 線程和多個 reactor 線程，主要的作用就是用來維護TCP連接，處理網路IO，收發數據。 而 manager 管理進程，作用則是 fork 和管 ...
  • python基礎(19):random模塊、time模塊、sys模塊、os模塊
    1. random模塊 導入的是random模塊，格式是： import random 1.1 隨機小數 取隨機小數 : 數學計算。 print(random.random()) # 取0-1之間的小數print(random.uniform(1,2)) # 取1-2之間的小數 1.2 隨機整數 取 ...
  • Java阻塞隊列
    一、阻塞隊列：用於保存等待執行的任務。在阻塞隊列中，線程阻塞的兩種情況： 1.當隊列中沒有數據的情況下，消費者端的所有線程都會被自動阻塞（掛起），直到有數據放入隊列。 2.當隊列中填滿數據的情況下， 生產者端的所有線程都會被自動阻塞，知道隊列中有空位置，線程被自動喚醒。 二、阻塞隊列的主要方法 拋出 ...
  • 模擬處理器調度
    一、實習內容 選擇一個調度演算法，實現處理器調度。 二、實習目的 在採用多道程式設計的系統中，往往有若幹個進程同時處於就緒狀態。當就緒進程個數大於處理器數時，就必須依照某種策略來決定哪些進程優先占用處理器。本實習模擬在單處理器情況下的處理器調度，幫助學生加深瞭解處理器調度的工作。 三、實習題目 本實習 ...
  • Python實戰練習——列印日曆教程
    Python實戰教程，用Python做列印日曆的小程式，使用者可以通過輸入年月信息，程式將會輸出這個月的日曆 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類