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
  • Dapr Outbox 執行流程
    Dapr Outbox 是1.12中的功能。 本文只介紹Dapr Outbox 執行流程，Dapr Outbox基本用法請閱讀官方文檔 。本文中appID=order-processor，topic=orders 本文前提知識：熟悉Dapr狀態管理、Dapr發佈訂閱和Outbox 模式。 Outbo ...
  • Advanced .Net Debugging 7：托管堆與垃圾收集
    引言 在前幾章我們深度講解了單元測試和集成測試的基礎知識，這一章我們來講解一下代碼覆蓋率,代碼覆蓋率是單元測試運行的度量值,覆蓋率通常以百分比表示，用於衡量代碼被測試覆蓋的程度，幫助開發人員評估測試用例的質量和代碼的健壯性。常見的覆蓋率包括語句覆蓋率（Line Coverage）、分支覆蓋率（Bra ...
  • C#S7.NET實現西門子PLCDB塊數據採集的完整步驟
    前言 本文介紹瞭如何使用S7.NET庫實現對西門子PLC DB塊數據的讀寫，記錄了使用電腦模擬，模擬PLC，自至完成測試的詳細流程，並重點介紹了在這個過程中的易錯點，供參考。 用到的軟體： 1.Windows環境下鏈路層網路訪問的行業標準工具（WinPcap_4_1_3.exe）下載鏈接：http ...
  • WPF控制項：密碼框綁定MVVM
    從依賴倒置原則（Dependency Inversion Principle, DIP）到控制反轉（Inversion of Control, IoC）再到依賴註入（Dependency Injection, DI）的演進過程，我們可以理解為一種逐步抽象和解耦的設計思想。這種思想在C#等面向對象的編 ...
  • Python中的私有屬性與私有方法
    關於Python中的私有屬性和私有方法 Python對於類的成員沒有嚴格的訪問控制限制，這與其他面相對對象語言有區別。關於私有屬性和私有方法，有如下要點： 1、通常我們約定，兩個下劃線開頭的屬性是私有的（private）。其他為公共的（public）； 2、類內部可以訪問私有屬性（方法）； 3、類外 ...
  • C++ 訪問說明符詳解：封裝數據，控制訪問，提升安全性
    C++ 訪問說明符 訪問說明符是 C++ 中控制類成員（屬性和方法）可訪問性的關鍵字。它們用於封裝類數據並保護其免受意外修改或濫用。 三種訪問說明符： public：允許從類外部的任何地方訪問成員。 private：僅允許在類內部訪問成員。 protected：允許在類內部及其派生類中訪問成員。 示 ...
  • static_cast與dynamic_cast到底是什麼？
    寫這個隨筆說一下C++的static_cast和dynamic_cast用在子類與父類的指針轉換時的一些事宜。首先，【static_cast，dynamic_cast】【父類指針，子類指針】，兩兩一組，共有4種組合：用 static_cast 父類轉子類、用 static_cast 子類轉父類、使用 ...
  • C語言數據結構：雙向鏈表的增刪操作
    /******************************************************************************************************** * * * 設計雙向鏈表的介面 * * * * Copyright (c) 2023-2 ...
  • @ComponentScan註解的實現，Spring掃描包的過程
    相信接觸過spring做開發的小伙伴們一定使用過@ComponentScan註解 @ComponentScan("com.wangm.lifecycle") public class AppConfig { } @ComponentScan指定basePackage，將包下的類按照一定規則註冊成Be ...
  • opensips開啟python支持
    操作系統 ：CentOS 7.6_x64 opensips版本： 2.4.9 python版本：2.7.5 python作為腳本語言，使用起來很方便，查了下opensips的文檔，支持使用python腳本寫邏輯代碼。今天整理下CentOS7環境下opensips2.4.9的python模塊筆記及使用 ...
所有分類