動態陣列底層是如何實作的

引言：
提到陣列，大部分腦海里一下子想到了一堆東西
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 = https://www.cnblogs.com/jiagooushi/archive/2022/08/04/{};//空，物件陣列，注意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 = https://www.cnblogs.com/jiagooushi/archive/2022/08/04/DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

2）帶int型別的建構式

如果傳入引數，則代表指定ArrayList的初始陣列長度，傳入引數如果是大于等于0，則使用用戶的引數初始化，如果用戶傳入的引數小于0，則拋出例外，構造方法如下：

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            //以指定容量初始化Object陣列
            this.elementData = https://www.cnblogs.com/jiagooushi/archive/2022/08/04/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 = https://www.cnblogs.com/jiagooushi/archive/2022/08/04/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 =https://www.cnblogs.com/jiagooushi/archive/2022/08/04/= 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 = https://www.cnblogs.com/jiagooushi/archive/2022/08/04/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 = https://www.cnblogs.com/jiagooushi/archive/2022/08/04/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 = https://www.cnblogs.com/jiagooushi/archive/2022/08/04/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 = https://www.cnblogs.com/jiagooushi/archive/2022/08/04/null;
 Iterator iter = list.iterator();
 while (iter.hasNext()) {
     value = (Integer)iter.next();
	 }

隨機訪問通過索引值遍歷

 Integer value = https://www.cnblogs.com/jiagooushi/archive/2022/08/04/null;
 for (int i=0; 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插入洗掉一定慢么？
取決于你洗掉的元素離陣列末端有多遠

本文由傳智教育博學谷 - 狂野架構師教研團隊發布

如果本文對您有幫助，歡迎關注和點贊；如果您有任何建議也可留言評論或私信，您的支持是我堅持創作的動力

轉載請注明出處！






        
      轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/500959.html
      標籤：其他 
      上一篇：編譯型與解釋型編程語言的區別
下一篇：這份工具清單，令Python 提速N倍，簡直太好用了