源碼解析 || ArrayList源碼解析

来源:https://www.cnblogs.com/hill1126/archive/2019/07/30/11261447.html
-Advertisement-
Play Games

前言 前言 這篇文章的ArrayList源碼是基於jdk1.8版本的源碼，如果與前後版本的實現細節出現不一致的地方請自己多加註意。先上一個它的結構圖 ArrayList作為一個集合工具，對於我而言它值得我們註意的地方有： 那麼我就由這四個細節對ArrayList進行分析。 ArrayList的參數細 ...


  • 前言

這篇文章的ArrayList源碼是基於jdk1.8版本的源碼，如果與前後版本的實現細節出現不一致的地方請自己多加註意。先上一個它的結構圖

ArrayList作為一個集合工具，對於我而言它值得我們註意的地方有：

  1. 參數的作用細節
  2. 擴容的細節
  3. 迭代的細節
  4. 特殊API的細節

那麼我就由這四個細節對ArrayList進行分析。

 

  • ArrayList的參數細節

ArrayList參數其實並不是特別多，值得我們拿出來講的那就更少了。下麵我通過一張圖的展示，同時列出一些值得我們談一談的參數：

  1. DEFAULT_CAPACITY、MAX_ARRAY_SIZE   兩個參數規定了ArrayList的預設長度和最大長度。但是，如果使用預設構造函數，在初始化ArrayList的時候，它的長度是0，只有第一次添加數據時，它才會擴容為10；
  2. EMPTY_ELEMENTDATA、DEFAULTCAPACITY_EMPTY_ELEMENTDATA 這兩個參數的值都是Object空數組，至於為什麼作者要寫兩個同樣的變數，那當然是為了區分不同方法當中的語義，使源碼更加易讀，當然這對於我們來說可以往後再關註。
  3. size   ArrayList中的大小，註意這也可以指已存放的數據的個數，和下麵elementData的長度也還有一定的區別。
  4.  elementData   Object數組，這個是整個ArrayList最核心的參數之一，ArrayList存放的數據都在這裡，對ArrayList的增刪改查都基於這個Object數組。同時，它是被transient關鍵字修飾的，這意味著ArrayList需要進行序列化的時候，會把它忽略。那麼我們會有一個問題，elementData 裡面的數據難道不用序列化了嗎？ 答案當然是需要的，但是它不是直接將一整個數組都序列化，而是通過方法writeObject()，把elementData 中有數據的位置序列化。通俗的話就是，它序列化elementData的前size個，而elementData的真實長度中，size後面的空間都認為是沒有數據的，如果也將它序列化會造成一定的流量浪費，影響傳輸性能。
  5. modCount 這個參數不是在ArrayList中聲明的，它是在父類AbstractList中聲明的，它的作用是記錄ArrayList的結構（增加或刪除）改變次數，以此來配合迭代器進行安全檢查，迭代器一旦發現modCount被修改了，則會拋出ConcurrentModificationException。

  •  擴容的細節

首先，為什麼不講增刪改查直接談擴容呢？因為ArrayList的查找和修改的實現細節其實和普通的數組操作一樣，並沒有什麼特別的地方。而添加和刪除涉及到數組的動態調整，也就是我現在寫的擴容，其它的其實和普通的數組操作差不多。

那麼，當ArrayList執行一次add()方法的時候，它會有什麼樣的操作呢？首先我們先來看一個圖。這是一個方法嵌套，執行到最後，就能確保list的空間是安全的。

上面是執行add方法後的一系列調用流程。可以看出方法內在調用完ensureCapacityInternal()後，空間是能確保數據的填充的。而往下調用的方法中，我們只關註grow()方法就行，這是個擴容方法，具體的代碼和意圖如下所示。

 1    /**
 2      * Increases the capacity to ensure that it can hold at least the
 3      * number of elements specified by the minimum capacity argument.
 4      *
 5      * @param minCapacity the desired minimum capacity
 6      */
 7     private void grow(int minCapacity) {
 8         int oldCapacity = elementData.length;
 9         //新容量暫時為舊容量的1.5倍
10         int newCapacity = oldCapacity + (oldCapacity >> 1);
11         //這一步是確保擴容的時候，擴容的空間儘量合理，避免頻繁擴容
12         if (newCapacity - minCapacity < 0)
13             newCapacity = minCapacity;
14         //假設參數大於MAX_VALUE，設定最大容量為Integer.MAX_VALUE
15         if (newCapacity - MAX_ARRAY_SIZE > 0)
16             newCapacity = hugeCapacity(minCapacity);
17         //調用數組工具把數據覆蓋並開闢記憶體空間
18         elementData = Arrays.copyOf(elementData, newCapacity);
19     }

  • 迭代的細節

ArrayList的迭代器採用的是fast-fail方式，也就是我們的快速失敗方式。這是什麼意思呢？我們直接貼出源碼的註釋來解釋。

在創建迭代器之後，除非通過迭代器自身的 remove 或 add 方法從結構上對列表進行修改，否則在任何時間以任何方式對列表進行修改，迭代器都會拋出 ConcurrentModificationException。因此，面對併發的修改，迭代器很快就會完全失敗，而不是冒著在將來某個不確定時間發生任意不確定行為的風險。

那麼 ，iterator通過什麼方式判斷列表被修改了呢？答案是在ArrayList內部還有一個內部 Iterator的實現類，裡面有一個參數expectedModCount，這個值與modCount 比較，若兩個值不相等，則拋出異常。

1  //源碼方法
2 final void checkForComodification() {
3             if (modCount != expectedModCount)
4                 throw new ConcurrentModificationException();
5         }

註意！我所說的迭代要註意的細節，指的是在迴圈過程中，伴隨著ArrayList結構上的修改，例如添加或刪除。如果只是簡單的迴圈遍歷輸出，其實各種方法沒有太大的區別。

下麵例舉集中常見的錯誤使用方式：

這種情況通常是迭代用迭代器，而對於修改則是用ArrayList的方法引起的，要解決這個問題只需要利用iterator的remove()方法即可。

 1  ArrayList<Integer> list = new ArrayList<>(3);
 2         list.add(111);
 3         list.add(222);
 4         list.add(333);
 5 
 6         Iterator<Integer> iterator = list.iterator();
 7         while(iterator.hasNext()){
 8             Integer next = iterator.next();
 9             if (next.equals(111)){
10                 //錯誤的使用，在創建迭代器後使用list方法來remove,會拋出ConcurrentModificationException
11                 list.remove(new Integer(111));
12             }
13             System.out.println(next);
14         }
15     }

下麵這種情況如果你只是想要找到一個目標值，同時將這個值刪除並break退出是可以的。但是，如果你還要繼續遍歷下去，這種情況則會導致ArrayList集合遍歷的不完整。

 1 ArrayList<Integer> list = new ArrayList<>(3);
 2         list.add(111);
 3         list.add(222);
 4         list.add(333);
 5         for (int i=0;i<list.size();i++){
 6             if (list.get(i).equals(222)){
 7                 //執行這一步，size的值為2，導致333這個值沒有輸出就結束迴圈。
 8                 list.remove(i);
 9                 continue;
10             }
11             System.out.println(list.get(i));  //輸出結果：111
12         }
13 
14     }

 

一般來說，當我們迭代有對ArrayList進行remove的需求的時候，可以利用迭代器來遍歷ArrayList的結構，這樣比較安全規範的且不會產生錯誤。

 1 import java.util.ArrayList;
 2 import java.util.Iterator;
 3 
 4 public class ArrayListDemo {
 5     public static void main(String[] args) {
 6         ArrayList<Integer> list = new ArrayList<>();
 7         list.add(111);
 8         list.add(222);
 9         list.add(333);
10         Iterator<Integer> iterator = list.iterator();
11         while (iterator.hasNext()){
12             Integer next = iterator.next();
13             if(next.equals(222)){
14                 iterator.remove();
15                 continue;
16             }
17             System.out.println(next);
18         }
19     }
20 }

  • 特殊API的細節

  1. remove方法參數的不確定性。

就在我剛纔的示例代碼中就有一種隱藏的危險，當你的ArrayList存放的是Integer類型的時候，有一種場景下你需要移除一個值。你會理所當然的調用list.remove(222);這個方法來移除222這個值。但是，這個時候其實它是指移除索引位置在222上的值。這個時候就會有刪除錯誤或者範圍異常的發生。

1  Integer next = iterator.next();
2      if (next.equals(222)){
3                
4         list.remove(222);
5    }

　　 2. subList方法的實現及返回類型

下麵先列出subList方法返回在SubList內部類的繼承關係和構造方法。

 1  private class SubList extends AbstractList<E> implements RandomAccess {
 2         private final AbstractList<E> parent;
 3         private final int parentOffset;
 4         private final int offset;
 5         int size;
 6         
 7         SubList(AbstractList<E> parent,
 8                 int offset, int fromIndex, int toIndex) {
 9             this.parent = parent;
10             this.parentOffset = fromIndex;
11             this.offset = offset + fromIndex;
12             this.size = toIndex - fromIndex;
13             this.modCount = ArrayList.this.modCount;
14         }
15 }

ArrayList中有一個subList方法可以用於對ArrayList的切割。一般我們要用List介面來接收返回的集合，但是其實它返回的具體類型是一個內部類SubList。與ArrayList肯定不是同一個類型，因此，如果你把它強制轉換為ArrayList則會發生錯誤。

1  public static void main(String[] args) {
2         ArrayList<Integer> list = new ArrayList<>(3);
3         list.add(111);
4         list.add(222);
5         list.add(333);
6         List<Integer> subList = list.subList(0, 1);
7         //編譯不報錯，運行時報錯
8         ArrayList worngList = (ArrayList)subList;
9     }

同時，從構造函數可以看出。SubList類中的集合其實是從ArrayList中直接賦值來的，它只是通過修改邊界範圍和size來構成一個新集合。也就是說，實質上SubList和ArrayList用的是同一個elementData數組。因此，當對SubList進行增刪改的時候，也會影響到ArrayList的存放的數據。示例代碼如下：

1  public static void main(String[] args) {
2         ArrayList<Integer> list = new ArrayList<>(3);
3         list.add(111);
4         list.add(222);
5         list.add(333);
6         List<Integer> subList = list.subList(0, 1);
7         subList.add(444);
8         subList.add(555);
9     }

我們通過debug可以看到，當添加到444,555的時候，兩個對象都出現了這兩個數據。

 


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

-Advertisement-
Play Games
更多相關文章
  • PHP中發送qq郵件
    SMTPDebug = 1; //設置郵件使用SMTP $mail->isSMTP(); // 設置郵件程式以使用SMTP $mail->Host = 'smtp.qq.com'; $mail->isSMTP(); /... ...
  • Java學習第六天
    1.構造函數的作用： 實現屬性的初始化 使用構造函數實現成員變數的初始化 非靜態成員變數 隨著對象的常見才開闢空間，所以只能使用對象來訪問 靜態成員變數，隨著類的載入而開闢空間，可以通過類直接訪問 2.static關鍵字： static修飾成員變數的特點： 1：static修飾的成員變數是隨著類的加 ...
  • 第一章、Go安裝與Goland破解
    1.1.安裝Go 安裝包下載：https://studygolang.com/dl 一直點下一步安裝即可，預設是安裝在“C:\Go”，如果自己換成其它目錄則需添加環境變數。 1.2.Liteide liteide是一款免費的IDE 安裝包下載：https://sourceforge.net/proj ...
  • 畢業了，聊一聊電腦實驗室的脫坑指南
    前文已經說過，你可以提前通過學長學姐咨詢實驗室的情況，來選擇自己心儀的實驗室，避免進入自己不喜歡的實驗室。那麼如果已經不小心進入到了自己不喜歡的實驗室怎麼辦，這裡提供一些有用的建議。 1.離開你所在的項目組或者離開你所在的實驗室 對，你沒看錯，就是離開。很多人可能會有疑問，我都已經進來了，怎麼出去啊 ...
  • Python基礎總結之第九天開始【python之OS模塊對目錄的操作、以及操作文件】（新手可相互督促）
    年薪20萬的夢想。。。 python對文件、目錄能做什麼？或者說我們需要python替我們做什麼？最經常的操作就是對文件的：打開、關閉、讀取、寫入、修改、保存等等對目錄的操作，無非就是：創建目錄、刪除目錄、更改目錄名字等等。我們先認識一下OS模塊，os模塊以及子模塊path中包含了獲取系統信息、以及 ...
  • javaweb入門-----request與response的作用
    request對象和request對象的原理 1.request和response對象request對象和request對象的原理時由伺服器創建的，我們來使用它們 2.request對象是來獲取請求消息，response對象是來設置響應消息 requset對象繼承體繫結構： ServletReque ...
  • SpringBoot讀取配置值的方式
    SpringBoot讀取配置值的方式 方法一： @Value註解的方式取值 設定appliction.properties的配置信息 使用@Value取值 頁面展示 小明==》性別：boy 年齡：18 分數：98 方法二： 使用@ConfigurationProperties賦值給實體類 設定app ...
  • SpringCloud微服務(01)：Eureka組件，管理服務註冊與發現
    一、Eureka基本架構 1、Eureka角色結構圖 角色職責如下： 1）、Register：服務註冊中心，它是一個Eureka Server ，提供服務註冊和發現功能。 2）、Provider：服務提供者，它是一個Eureka Client ，提供服務。 3）、Consumer：服務消費者，它是一 ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類