動態數組底層是如何實現的 引言： 提到數組，大部分腦海裡一下子想到了一堆東西 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這些介面
從繼承關係看功能
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) 執行結果分析：
從對象頭，我們大致可以看出ArrayList的數據結構：
- ArrayList底層用一個數組存儲數據：elementData
- 額外附加了幾組信息：modeCount（發生修改操作的次數）、size（當前數組的長度）
等會……
- 為什麼長度不是數組裡的32，而是4個位元組？ArrayList的長度到底應該是多少？？？
- 這個數組後面多出來倆null又是怎麼回事？？？
（下麵構造函數部分會得到詳細答案）
3) 結論 & 面試題
ArrayList外圍暴露出來的只是一些操作的表象，底層數據的存儲和操作都是基於數組的基礎上
這就意味著，它的特性和數組一樣：查詢快！刪除插入慢。
ArrayList訪問為什麼那麼快？
1、ArrayList底層是數組實現的
2、數組是一塊連續的記憶體空間
3、獲取數據可以直接拿地址偏移量（get（i））
因此：查詢（確切的說是訪問，而不是查找）的時間複雜度是O(1)
為什麼刪除和增加那麼慢？
增刪會帶來元素的移動，增加數據會向後移動，刪除數據會向前移動，所以影響效率
因此：插入、刪除的時間複雜度是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構造器意味著，你可以使用以下一攬子集合對象：
總結：
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());
}
}
結果分析：
原理：
//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增加與擴容調用流程圖
增加源碼（簡單）
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流程圖解：
因為基於數組，所以極其簡單
public E get(int index) { //返回list中指定位置的元素
rangeCheck(index);//越界檢查
return elementData(index);//返回list中指定位置的元素，數組訪問，賊快~
}
總結：
和java的數組用法相近
2.3.5 源碼分析之remove方法
目標：
源碼分析ArrayList的remove方法
數組拷貝是重點，可以藉助單步調試debug查看過程
移除回顧
remove方法執行流程
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
總結：
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的大小並沒有回縮！
2.4 動態數組常見面試題
1、哪些集合實現了List介面和Collection介面，各自的優缺點是什麼
通過上面類圖可用看出，List介面下有4個實現類，分別為：LinkedList、ArrayList、Vector和Stack。
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插入刪除一定慢麽？
取決於你刪除的元素離數組末端有多遠
本文由傳智教育博學谷 - 狂野架構師教研團隊發佈
如果本文對您有幫助，歡迎關註和點贊；如果您有任何建議也可留言評論或私信，您的支持是我堅持創作的動力
轉載請註明出處！
