動態數組底層是如何實現的

来源:https://www.cnblogs.com/jiagooushi/archive/2022/08/04/16550477.html
-Advertisement-
Play Games

動態數組底層是如何實現的 引言: 提到數組,大部分腦海裡一下子想到了一堆東西 int long short byte float double boolean char String 沒錯,他們也可以定義成數組 但是,上面都是靜態的 不過,咱們今天學習的可是動態的(ArrayList 數組) 好接下 ...


動態數組底層是如何實現的

引言:
提到數組,大部分腦海裡一下子想到了一堆東西
int long short byte float double boolean char String
沒錯,他們也可以定義成數組
但是,上面都是靜態的
不過,咱們今天學習的可是動態的(ArrayList 數組)
好接下來,我們一起來下麵的內容

2.1 動態數組的位置

目標:

簡單認識下繼承關係

ArrayList繼承於AbstractList,實現了List, RandomAccess, Cloneable, java.io.Serializable這些介面

file

從繼承關係看功能

AbstractList類

AbstractList,實現了List。List介面我們都知道,提供了相關的添加、刪除、修改、遍歷等功能

RandmoAccess介面

ArrayList 實現了RandmoAccess介面,即提供了隨機訪問功能; 即list.get(i)

Cloneable介面

ArrayList 實現了Cloneable介面,即覆蓋了函數clone(),能被克隆

Serializable介面

ArrayList 實現java.io.Serializable介面,這意味著ArrayList支持序列化,能通過序列化去傳輸

2.2.動態數組與數據結構

目標:

圖解+面試題快速認識ArrayList

1) 概念介紹

ArrayList 是一個數組隊列,相當於動態(擴容)數組。

我們直接來看對象頭,對其有個簡單認識和猜想:(com.alist.InitialList)

package com.alist;

import org.openjdk.jol.info.ClassLayout;

import java.util.ArrayList;

public class ArrayListHeader {


    public static void main(String[] args) {
        int[] i = new int[8];
        ArrayList<Integer> list = new ArrayList(8);
        //將8個int類型依次放入數組和arrayList,註意,一個int占4個位元組
        for (int j = 0; j < 8; j++) {
            i[j] = j;
            list.add(j);
        }

        System.out.println(ClassLayout.parseInstance(i).toPrintable());
        System.out.println("=============");
        System.out.println(ClassLayout.parseInstance(list).toPrintable());
//        System.out.println(ClassLayout.parseClass(ArrayList.class));
    }
}

2) 執行結果分析:

file

從對象頭,我們大致可以看出ArrayList的數據結構:

  • ArrayList底層用一個數組存儲數據:elementData
  • 額外附加了幾組信息:modeCount(發生修改操作的次數)、size(當前數組的長度)

等會……

  • 為什麼長度不是數組裡的32,而是4個位元組?ArrayList的長度到底應該是多少???
  • 這個數組後面多出來倆null又是怎麼回事???

(下麵構造函數部分會得到詳細答案)

3) 結論 & 面試題

ArrayList外圍暴露出來的只是一些操作的表象,底層數據的存儲和操作都是基於數組的基礎上

這就意味著,它的特性和數組一樣:查詢快!刪除插入慢。

ArrayList訪問為什麼那麼快?

1、ArrayList底層是數組實現的

2、數組是一塊連續的記憶體空間

3、獲取數據可以直接拿地址偏移量(get(i))

file

因此:查詢(確切的說是訪問,而不是查找)的時間複雜度是O(1)

為什麼刪除和增加那麼慢?

增刪會帶來元素的移動,增加數據會向後移動,刪除數據會向前移動,所以影響效率

file

因此:插入、刪除的時間複雜度是O(N)

2.3 動態數組源碼深入剖析

接下來,我們從底層源碼層面看ArrayList的一系列操作

先準備測試代碼,下麵debug用(com.alist.AList

public class AList {

    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<String>(2);
        //斷點跟蹤add
        arrayList.add("100");
        arrayList.add("200");
        arrayList.add("300");
        arrayList.add("400");


        //斷點跟蹤get
//        for (int i = 0; i <arrayList.size() ; i++) {
//            arrayList.get(i);//Random
//
//        }


//        //斷點跟蹤remove
//        arrayList.remove(1);
//        //arrayList.remove("100");//和上面邏輯一樣remove
//        System.out.println(arrayList);


//         //斷點跟蹤set
//        arrayList.set(1,"2000000");
//        System.out.println(arrayList);


//        //斷點跟蹤clear
//        arrayList.clear();
//        System.out.println(arrayList);

    }

2.3.1 源碼分析之全局變數

目標:

先認識下類變數和成員變數,方便講解源碼的時候能快速理解

 private static final int DEFAULT_CAPACITY = 10;//預設的初始化容量
 private static final Object[] EMPTY_ELEMENTDATA = {};//空,對象數組,註意static,所有空arraylist共用,那不會出問題嗎???(秘密在add數據時的擴容操作里……)
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//空,無參構造使用(1.8才有)
 transient Object[] elementData; // 當前數據對象存放的地方,註意是transient,雖然數組實現了serializable介面,但是它的數據不會被預設的ObjectOutputStream序列化,想做網路傳輸,自己改寫writeObject和readObject方法!
 private int size;//當前數據的個數
 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//數組最大長度?(擴容部分有彩蛋)

小問題:

  • ArrayList可以無限大嗎?到底最大是多少?
  • elementData好理解,放數據,又為啥定義兩個空數組?啰嗦不?

上面的定義看似明明白白,其實背地裡藏著很多不為人知的事,我們接著往下看……

2.3.2 源碼分析之構造器

目標:

源碼查看ArrayList的3個構造器

1)無參構造函數

如果不傳入參數,則使用預設無參構建方法創建ArrayList對象,如下:

    public ArrayList() {
        //預設構造函數,很簡單,就是把default empty數組賦給了data
      	//jdk8里才有DEFAULTCAPACITY_EMPTY_ELEMENTDATA這貨,並且僅僅被用在了這個構造函數里
      	//官方的解釋是,為了區分判斷第一次add的時候,數組初始化的容量
      	//這個秘密藏在calculateCapacity里(下文會講)
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

2)帶int類型的構造函數

如果傳入參數,則代表指定ArrayList的初始數組長度,傳入參數如果是大於等於0,則使用用戶的參數初始化,如果用戶傳入的參數小於0,則拋出異常,構造方法如下:

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //以指定容量初始化Object數組
            this.elementData = new Object[initialCapacity];//初始化容量
        } else if (initialCapacity == 0) {
            //如果指定0的話,用empty數組
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //否則,如果是負數的話,扔一個異常出來(哪有長度為負數的??)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

3)帶Collection對象的構造函數

    public ArrayList(Collection<? extends E> c) {
        //集合轉換成數組
        elementData = c.toArray();
        //將data長度賦值給size屬性
        if ((size = elementData.length) != 0) {
            // 官方註釋:c.toArray might (incorrectly) not return Object[] (see 6260652)
            // 翻譯:toArray不一定會返回Object數組,參考jdk的bug號……汗!
            // 如果不是Object數組,轉成Object[]
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);//數組賦值,類型轉換
        } else {
            // 如果數據為空,將empty賦給data
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

Collection構造器意味著,你可以使用以下一攬子集合對象:

file

總結:

1、構造器一 啥也沒乾,只是聲明瞭一個空數組

2、構造器二 通過自定義的初始化容量創建數組

3、**構造器三 **接受Collection的參數,如果有數據,就轉換成一個新的elementData,否則還是一個空數組

事情有這麼簡單嗎???接著往下看!

問題來了:無參構造和0長度構造有什麼區別?

用代碼說話,我們把對象結構給他打出來:

package com.alist;

import org.openjdk.jol.info.ClassLayout;

import java.util.ArrayList;

public class InitialList {
    public static void main(String[] args) {
        //兩種方式構建list,有什麼區別?
        ArrayList list1 = new ArrayList();
        ArrayList list2 = new ArrayList(0);

        //列印對象頭
        System.out.println(ClassLayout.parseInstance(list1).toPrintable());
        System.out.println(ClassLayout.parseInstance(list2).toPrintable());

        System.out.println("========");

        //add一個元素之後再來列印試試
        list1.add(1);
        list2.add(1);

        System.out.println(ClassLayout.parseInstance(list1).toPrintable());
        System.out.println(ClassLayout.parseInstance(list2).toPrintable());
    }
}

結果分析:
file

原理:

		//calculateCapacity
		//每次元素變動,比如add,會調用該函數判斷容量情況
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
      	//定義default empty數組的意義就在這裡!用於擴容時判斷當初採用的是哪種構造函數
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          	//如果是無參的構造函數,用的就是該default empty
          	//那麼第一次add時候,容量取default和min中較大者
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
      	//如果是另外兩個構造函數,比如指定容量為5,或者初始參數collection為5
      	//那就直接返回5,一定程度上,節約了記憶體空間
        return minCapacity;
    }

結論:

  • 剛構造時,都是空的!add時才初始化(這裡容易誤解,以為預設構造器data初始化就是10)
  • 雖然list可以自動擴容,但儘量初始就預估並定義list的容量,少用無參的構造器,尤其小於10的時候
  • default empty存在的意義:判斷那種構造函數來的,初始階段節約了擴容的空間占用

2.3.3 源碼分析之增加與擴容

目標:

源碼分析ArrayList的增加、擴容方法

add增加與擴容調用流程圖

file

增加源碼(簡單)

public boolean add(E e) {
  //確認容量,不夠則擴容
  ensureCapacityInternal(size + 1);
  //將元素追加到數組的末尾去,同時計數增size++
  elementData[size++] = e;
  return true;
}

擴容源碼(重點)

    private void grow(int minCapacity) {
        //minCapacity:我需要的最小長度,也就是上面的size+1
        int oldCapacity = elementData.length;//先取出舊數組大小
        int newCapacity = oldCapacity + (oldCapacity >> 1);//擴容為舊數組的1.5倍;右移一位(除以2)
        if (newCapacity - minCapacity < 0)//如果擴容1.5後還不夠
            newCapacity = minCapacity;//取需求量為新長度,數組的擴容還是比較保守和吝嗇!
        if (newCapacity - MAX_ARRAY_SIZE > 0)//新長度大於數組最大長度,彩蛋來了!
            newCapacity = hugeCapacity(minCapacity);//看下麵的huge方法 ↓
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);//返回一個新的數組對象
    }



    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // 負數說明超出了Integer的範圍,溢出了,拋異常
            throw new OutOfMemoryError();
      	//否則:返回Integer的最大值,而不是最大值-8!驚不驚奇?意不意外?
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }



    //這是為什麼呢?我們一開始integer-8還有啥意義?
    //讓我們返回去,看這個變數的註釋:
		//翻譯:有些VM會在array頭上預留信息,企圖大於這個值也行,但是不保證安全性,可能會溢出報錯!

    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

擴容總結:

1、按1.5倍擴容,如果1.5還不夠,取你想要的容量(總之保證夠你用的)

2、數組最大容量是integer的max_value,但是達到這個值的時候,arraylist不保證穩定可靠!

2.3.4 源碼分析之get方法、

目標:

源碼分析ArrayList的get方法

get流程圖解:

file

因為基於數組,所以極其簡單

public E get(int index) { //返回list中指定位置的元素
    rangeCheck(index);//越界檢查

    return elementData(index);//返回list中指定位置的元素,數組訪問,賊快~
}

總結:

和java的數組用法相近

2.3.5 源碼分析之remove方法

目標:

源碼分析ArrayList的remove方法

數組拷貝是重點,可以藉助單步調試debug查看過程

移除回顧

file
remove方法執行流程

file

remove源碼解釋(重點)

    public E remove(int index) {
        rangeCheck(index);//數組越界檢查

        modCount++;//結構性修改次數+1
        E oldValue = elementData(index);//將要移除的元素

        int numMoved = size - index - 1;//刪除指定元素後,需要左移的元素個數(graph)
        if (numMoved > 0)//如果有需要左移的元素,就移動(移動後,要刪除的元素就已經被覆蓋了)
          	//參數:src、src   dest、dest、移動的長度
          	//從data的index+1到data的index,也就是元素挨個前移一格,一共移動num個
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
      	//左移後,最後一個位置還有值,給他搞成null,下一步gc會把對象收走,size計數減少
      	//(藉助斷點查看data數組的最後一個元素的值)
        elementData[--size] = null; 

        return oldValue;//返回剛纔要刪除的值
    }

不好理解的地方

數組變化過程(左移個數,數組合併)

   int numMoved = size - index - 1;//刪除指定元素後,需要左移的元素個數(graph)
        if (numMoved > 0)//如果有需要左移的元素,就移動(移動後,該刪除的元素就已經被覆蓋了)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);//參數:src、src   dest、dest、移動的長度
        elementData[--size] = null; //左移後,最後一個位置就為空了;size減一,為了讓GC起作用,設置為null

file

總結:

1、移除後 ,後面的節點通過數組拷貝的方式需要左移

2、需要註意的是:如果末端太長,remove是非常耗費性能的

2.3.6 源碼分析之set方法

    public E set(int index, E element) {
      rangeCheck(index);//越界檢查
      E oldValue = elementData(index);//修改前的原素質
      elementData[index] = element;//新元素賦值
      return oldValue;//返回舊的元素
    }

2.3.7 源碼分析之clear方法

目標:

源碼分析ArrayList的clear方法

public void clear() { //從列表中刪除所有元素。該調用返回後,數組將為空    
  modCount++;//修改測試自增    
  // clear to let GC do its work    
  for (int i = 0; i < size; i++)        
    elementData[i] = null;//清除表元素    
  size = 0;//大小為0
}

總結:

清除就是設置為null、大小設置為0;設置null,方便gc

需要註意的是:

clear過後,size=0,但是table的大小並沒有回縮!

file

2.4 動態數組常見面試題

1、哪些集合實現了List介面和Collection介面,各自的優缺點是什麼

file

通過上面類圖可用看出,List介面下有4個實現類,分別為:LinkedList、ArrayList、Vector和Stack

file

List只是個介面,介面也就是定義了一組規範或者api

具體的實現甚至底層存儲可以是完全不同的,比如數組,鏈表

2、ArrayList提供了幾種查詢方式、效率如何?

  • Iterator迭代器遍歷方式
 Integer value = null;
 Iterator iter = list.iterator();
 while (iter.hasNext()) {
     value = (Integer)iter.next();
	 }
  • 隨機訪問 通過索引值遍歷
 Integer value = null;
 for (int i=0; i<list.size(); i++) {
     value = (Integer)list.get(i);        
 }
  • for-each迴圈遍歷
public   void show(List<Object> list){
   list.forEach( s -> System.out.println(s));
}

關於性能:

1、數據量不大的時候,以上三種方式差不多

2、數據量不斷上升的情況下for each表現不錯

3、ArrayList可以存放null嗎?

可以。

4、ArrayList是如何擴容的?

  • 在用無參構造來創建對象的時候其實就是創建了一個空數組,長度為0。add時先分配一個預設大小10,後續擴容,每次擴容都是原容量的1.5倍。
  • 在有參構造中,傳入的參數是正整數就按照傳入的參數來確定創建數組的大小。再進行擴容,每次擴容都是原容量的1.5倍

5、ArrayList是線程安全的嗎?

不是

6、ArrayList插入刪除一定慢麽?

取決於你刪除的元素離數組末端有多遠

本文由傳智教育博學谷 - 狂野架構師教研團隊發佈
如果本文對您有幫助,歡迎關註和點贊;如果您有任何建議也可留言評論或私信,您的支持是我堅持創作的動力
轉載請註明出處!


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

-Advertisement-
Play Games
更多相關文章
  • 一、簡介Spring Cloud Feign Client 是一個方便的聲明式 REST 客戶端,我們用它來實現微服務之間的通信。 在這個簡短的教程中,我們將展示如何設置自定義的 Feign 客戶端連接超時,包括全局和每個客戶端。 2. 預設值Feign Client 是相當可配置的。 在超時方面, ...
  • 目錄 一.簡介 二.效果演示 三.源碼下載 四.猜你喜歡 零基礎 OpenGL (ES) 學習路線推薦 : OpenGL (ES) 學習目錄 >> OpenGL ES 基礎 零基礎 OpenGL (ES) 學習路線推薦 : OpenGL (ES) 學習目錄 >> OpenGL ES 轉場 零基礎 O ...
  • “生產環境伺服器變慢?如何診斷處理” 這是最近一些工作5年以上的粉絲反饋給我的問題,他們去一線大廠面試,都被問到了這一類的問題。 今天給大家分享一下,面試過程中遇到這個問題,我們應該怎麼回答。 這個問題高手部分的回答,我整理到了一個10W字的文檔裡面,大家可以在我的主頁加V領取。 來看看高手的回答。 ...
  • 1、jsp表達式和EL標簽 1.1 獲取值的區別 1.用法el表達式更加簡潔 2.獲取參數不存在時,jsp表達式時null,el表達式是空; <% request.setAttribute("userName", "kh96"); %> <p>獲取作用域中存在的值:userName_jsp = <% ...
  • SpringBoot 2.7.2 學習系列,本節通過實戰內容講解如何集成 MyBatisPlus 本文在前文的基礎上集成 MyBatisPlus,並創建資料庫表,實現一個實體簡單的 CRUD 介面。 MyBatis Plus 在 MyBatis 做了增強,內置了通用的 Mapper,同時也有代碼生成 ...
  • 最近在研究所做網路終端測試的項目,包括一些嵌入式和底層數據幀的封裝調用。之前很少接觸對二進位原始數據的處理與封裝,所以在此進行整理。 ...
  • 跨域指的是瀏覽器不能執行其他網站的腳本。它是由瀏覽器的同源策略造成的,是瀏覽器對JavaScript施加的安全限制。在做前後端分離項目的時候就需要解決此問題。 ...
  • 在眾多編程語言中,Python的社區生態是其中的佼佼者之一。幾乎所有的技術痛點,例如優化代碼提升速度,在社區內都有很多成功的解決方案。本文分享的就是一份可以令 Python 變快的工具清單,值得瞭解下。 一、序言 這篇文章會提供一些優化代碼的工具。會讓代碼變得更簡潔,或者更迅速。 當然這些並不能代替 ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...