1、ArrayList源碼解析

来源:https://www.cnblogs.com/knowledgeispower/archive/2022/11/22/16915407.html
-Advertisement-
Play Games

1 概述 ArrayList實現了List介面,是 順序容器,允許放入null元素 有一個容量(capacity),表示底層數組的實際大小。如果容量不足,容器會 自動增大底層數組的大小 支持泛型,泛型擦除後,容器的元素都是 Object類型 ArrayList沒有實現同步(synchronized) ...


目錄

1 概述

  1. ArrayList實現了List介面,是 順序容器,允許放入null元素
  2. 有一個容量(capacity),表示底層數組的實際大小。如果容量不足,容器會 自動增大底層數組的大小
  3. 支持泛型,泛型擦除後,容器的元素都是 Object類型
  4. ArrayList沒有實現同步(synchronized),因此它是 線程不安全的。(vector線程安全)
  5. 關於數組:一旦數組初始化完成,則長度不可改變 因此ArrayList擴容時會涉及數組的拷貝

2 底層數據結構

兩個重要成員變數

  1. Object[] elementData

存儲列表元素的數組;該數組的長度就是列表的容量
列表的容量是指它所能存儲元素的最大個數

  1. size

列表的大小。指當前列表包含的元素個數,跟容量不是一個概念

size 跟 elementData數組長度是不一樣的。elementData 允許長度大於元素的個數

    transient Object[] elementData; //存儲列表元素的數組
    private int size;//元素的數量
    protected transient int modCount = 0; //list的修改次數

3 構造函數

有三個構造函數:

  • 指定初始容量大小時,創建一個容量為參數的Object數組,並賦值給數據數組
  • 不指定初始容量大小時,數據數組賦值為一個無限容量的空數組
  • 構造參數為集合類型,將參數轉換成Object類型數組,並賦值給數據數組
  • 註意,只有當第一次add元素時,才會指定數組的長度

參照源碼:

    //指定初始容量大小時,創建一個容量為參數的Object數組,並賦值給數據數組
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
// 不指定初始容量大小時,數據數組賦值為一個無限容量的空數組
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
// 構造參數為集合類型,將參數轉換成Object類型數組,並賦值給數據數組
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

4 自動擴容

  1. 添加元素時,會判斷添加後是否超出當前數組長度,超出則會執行數組擴容;
  2. 數組擴容時,會將老數組中的元素重新 拷貝一份到新的數組中。(因為數組長度不可變,因此需要創建新數組)
  3. 數組執行擴容,擴容後的容量為擴容前的 1.5倍
  4. 儘可能評估所需要容量的大小,避免擴容。(因為擴容占用更多的記憶體)

參考源碼:

重點!!!!!:添加前,都判斷是否需要擴容:(如果size+1後,超過elementData的長度,則執行擴容,擴容為原來的1.5倍


public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // size 初始化時是0,
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//計算所需容量:第一次添加時,容量為10;反則,容量為當前長度+1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY = 10,即第一次添加時,數組長度變為10
    }
    return minCapacity;//如果數組不為空時,最小長度是當前長度+1
}

//再次計算數組所需容量
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;//列表修改次數遞增
    //所需容量大於數組的長度,則執行擴容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
//擴容,數組的記憶體狀態已經發生變化了
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//  新的長度為舊長度的1.5倍  【右移1位(除以2)】
    if (newCapacity - minCapacity < 0)  // 如果擴容後的長度小於所需要的最小長度,則使用最小長度(基本不會發生)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)  //這裡是極限的情況,即逼近數組分配的最大記憶體空間
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);  // 執行數組拷貝
}

5 set() get() remove()

  • set()方法也就變得非常簡單,直接對數組的指定位置賦值即可。
public E set(int index, E element) {
    rangeCheck(index);//下標越界檢查
    E oldValue = elementData(index);
    elementData[index] = element;//賦值到指定位置,複製的僅僅是引用
    return oldValue;//返回原先位置上的元素
}
  • get()方法同樣很簡單,唯一要註意的是由於底層數組是Object[],得到元素後需要進行類型轉換。
public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];//註意類型轉換
}
  • remove()方法也有兩個版本,一個是remove(int index)刪除指定位置的元素,另一個是remove(Object o)刪除第一個滿足o.equals(elementData[index])的元素。刪除操作是add()操作的逆過程,需要將刪除點之後的元素向前移動一個位置。需要註意的是為了讓GC起作用,必須顯式的為最後一個位置賦null值
public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; //清除該位置的引用,讓GC起作用
    return oldValue;
}

6 Fail-Fast機制

ArrayList也採用了快速失敗的機制,通過記錄 modCount 參數來實現。在面對併發的修改時,迭代器很快就會完全失敗,而不是冒著在將來某個不確定時間發生任意不確定行為的風險。


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

-Advertisement-
Play Games
更多相關文章
  • 最小生成樹(貪心演算法) 概念 一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖,且包含原圖中的所有 n 個結點,並且有保持圖連通的最少的邊。 連通圖有多種連接方式,而其中最小的連通圖,就是最小生成樹 連通圖分為:無向、有向 無向連通圖:所以頂點相連,但各個邊都沒有方向 有向連通圖:邊有方向 1 ...
  • 學習:SQL 語句到結構體的轉換 | Go 語言編程之旅 (eddycjy.com) 目標:SQL表轉換為Go語言結構體 可以線上體驗這個過程:SQL生成GO語言結構體 - 支持批量處理 (tl.beer) MySQL資料庫中的表結構,本質上是SQL語句。 CREATE TABLE `USER`( ...
  • 規則引擎 Drools 全套代碼及資料全部完整提供,點此處下載 1. 問題引出 現有一個線上申請信用卡的業務場景,用戶需要錄入個人信息,如下圖所示: 通過上圖可以看到,用戶錄入的個人信息包括姓名、性別、年齡、學歷、電話、所在公司、職位、月收入、是否有房、是否有車、是否有信用卡等。錄入完成後點擊申請按 ...
  • 1、static修飾局部變數 在函數體內,只初始化一次,被static聲明過的局部變數在調用過程中值不變。原因:在任意函數內定義局部變數,存儲線上程中的棧區,出函數時自動摧毀,所以在每次調用這個函數時,局部變數的初始值都為定義的值在進行運算。static在修飾局部變數時,存儲在靜態區,函數返回時值保 ...
  • 前面幾篇文章對 Yarn 基本架構、程式基礎庫、應用設計方法等進行了介紹。之後幾篇將開始對 Yarn 核心組件進行剖析。 ResourceManager(RM)是 Yarn 的核心管理服務,負責集群管理、任務調度、狀態機管理等,本篇將對 RM 總體架構進行介紹。 ...
  • 哈夫曼編碼應用 問題描述 ​ 給定字元串,將每個不同的字元的哈夫曼編碼表示並輸出其哈夫曼編碼,並再將其哈夫曼編碼還原回字元串 分析一下 構建哈夫曼樹 ​ 使用靜態鏈表,先將所有的結點關係全部清零,再進行結點和相應權值的賦值,遍歷後n-1個結點 (新根),從n個結點中選兩個最小的權值了合成一棵樹,並將 ...
  • 一.小結 1.一個boolean變數可以存儲值true或false 2.關係運算符(<,<=,==,!=,>,>=)和數值及字元一起運算 3.布爾運算符&&,|| ,| 和 ^對布爾值和布爾變數進行計算 4.當對p1&&p2求值時,java先求p1的值,如果p1為true,再對p2求值;如果p1為f ...
  • 迭代器的功能: 提供一種統一的方式,來透明的遍歷容器 理解 begin()方法,end()方法, ++ , * 的用處 其中 C++11 中提供的foreach的方式,其底層還是通過迭代器來進行遍歷的. #include <iostream> using namespace std; class M ...
一周排行
    -Advertisement-
    Play Games
  • 簡介 本文的初衷是希望幫助那些有其它平臺視覺演算法開發經驗的人能快速轉入Halcon平臺下,通過文中的示例開發者能快速瞭解一個Halcon項目開發的基本步驟,讓開發者能把精力完全集中到演算法的開發上面。 首先,你需要安裝Halcon,HALCON 18.11.0.1的安裝包會放在文章末尾。安裝包分開發和 ...
  • 本文是對Datawhale的動手學數據分析課程的學習總結,記錄了整體的學習過程、答案以及個人感想,代碼較為詳細。 ...
  • JZ7重建二叉樹 描述 給定節點數為 n 的二叉樹的前序遍歷和中序遍歷結果,請重建出該二叉樹並返回它的頭結點。 例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6} 提示: 1.vin.length == pre.length 2.pre 和 vin ...
  • 我們都知道在Java編程中多線程的同步使用synchronized關鍵字來標識,那麼這個關鍵字在JVM底層到底是如何實現的呢。 我們先來思考一下如果我們自己實現的一個鎖該怎麼做呢: 首先肯定要有個標記記錄對象是否已經上鎖,執行同步代碼之前判斷這個標誌,如果對象已經上鎖線程就阻塞等待鎖的釋放。 其次要 ...
  • 目錄 一.OpenGL 色階 1.Windows OpenGL ES 版本 2.Windows OpenGL 版本 二.OpenGL 色階 GLSL Shader 三.猜你喜歡 零基礎 OpenGL ES 學習路線推薦 : OpenGL ES 學習目錄 >> OpenGL ES 基礎 零基礎 Ope ...
  • 1. 查看Linux伺服器版本信息 # cat /etc/redhat-release CentOS Linux release 7.4.1708 (Core) 2. 禪道開源版安裝包下載 wget http://dl.cnezsoft.com/zentao/9.8.2/ZenTaoPMS.9.8. ...
  • Spring 框架可以為 Java 應用程式開發提供全面的基礎設施支持,它是現在非常流行的 Java 開源框架,對於一個 Java 開發人員來說,熟練掌握 Spring 是必不可少的。 ...
  • 前言 本篇是c++總結的第二篇,關於c++的對象模型,在構造、拷貝虛函數上重點分析,也包含了c++11class的新用法和特性,如有不當,還請指教! c++三大特性 訪問許可權 ​ 在c++中通過public、protected、private三個關鍵字來控製成員變數和成員函數的訪問許可權,它們分別表示 ...
  • 一.小結 1.使用二維數組來存儲表格 2.可以使用以下語法來聲明二維數組變數: 元素類型[ ] [ ]數組變數 3.可以使用以下語法來創建二維數組變數: new 元素類型 [行的個數][列的個數] 4.使用下麵的語法表示二維數組中的每個元素: 數組變數[行下標][列的個數] 5.可使用數組初始化語法 ...
  • typimg是一款為typora編輯器提供圖像自定義上傳服務的工具,該工具將在typora中輸入的網路圖片、本地圖片、剪貼板圖片/截圖上傳到博客園,支持在MacOS、Windiws、Linux三個平臺上運行。 ...