ArrayList擴容機制以及底層實作-有解無憂

簡介

　　ArrayList動態陣列，是 java 中比較常用的資料結構，繼承自 AbstractList，實作了 List 介面，底層基于陣列實作容量大小動態變化，本隨筆主要講述ArrayList的擴容機制以及它的底層實作，

成員變數

 1    private static final int DEFAULT_CAPACITY = 10;  //默認的初始容量為10
 2     
 3     private static final Object[] EMPTY_ELEMENTDATA = https://www.cnblogs.com/qinjunlin/archive/2020/09/25/{};  //空陣列
 4     
 5     /**
 6      *與默認的初始容量DEFAULT_CAPACITY區分開來，
 7      *簡單來講就是第一次添加元素時知道該 elementData 
 8      *從空的建構式還是有參建構式被初始化的，以便確認如何擴容，
 9      **/
10     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = https://www.cnblogs.com/qinjunlin/archive/2020/09/25/{};//空陣列，與EMPTY_ELEMENTDATA空陣列區分
11     
12      /**
13     * 存盤ArrayList元素的陣列緩沖區，
14     * ArrayList的容量是這個陣列緩沖區的長度，
15     *任何空的ArrayList 即 elementData =https://www.cnblogs.com/qinjunlin/archive/2020/09/25/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA
16     *當添加第一個元素時，將擴展為DEFAULT_CAPACITY，
17      **/
18     transient Object[] elementData; 
19     
20     private int size;  //實際元素個數

建構式

有參構造

1 /**
2      * 構造一個初始容量為10的空ArrayList
3      */
4     public ArrayList() {
5         this.elementData =https://www.cnblogs.com/qinjunlin/archive/2020/09/25/ DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
6     }

這里需要注意，注釋（是我翻譯后的）是說構造一個容量大小為 10 的空的 list 集合，但這里建構式了只是給 elementData 賦值了一個空的陣列，實際上并未開始擴容，真正開始擴容其實是在第一次添加元素時才容量擴大至 10 的，

有參建構式

下面的代碼是構造一個大小為 initialCapacity 的 ArrayList

 1 public ArrayList(int initialCapacity) {
 2     if (initialCapacity > 0) {  //當 initialCapacity 大于零時初始化一個大小為 initialCapacity 的 object 陣列并賦值給 elementData
 3         this.elementData = https://www.cnblogs.com/qinjunlin/archive/2020/09/25/new Object[initialCapacity];
 4     } else if (initialCapacity == 0) {  //當 initialCapacity 為零時則是把 空陣列EMPTY_ELEMENTDATA 賦值給 elementData
 5         this.elementData =https://www.cnblogs.com/qinjunlin/archive/2020/09/25/ EMPTY_ELEMENTDATA;
 6     } else {
 7         throw new IllegalArgumentException("Illegal Capacity: "+
 8                                        initialCapacity);
 9     }
10 }

使用指定 Collection 來構造 ArrayList 的建構式，將 Collection 轉化為陣列并賦值給 elementData，

 1 public ArrayList(Collection<? extends E> c) {
 2     elementData =https://www.cnblogs.com/qinjunlin/archive/2020/09/25/ c.toArray();
 3     if ((size = elementData.length) != 0) {
 4         // c.toArray might (incorrectly) not return Object[] (see 6260652)
 5         if (elementData.getClass() != Object[].class) //判斷 elementData 的 class 型別是否為 Object[]，不是的話則做一次轉換
 6         elementData = https://www.cnblogs.com/qinjunlin/archive/2020/09/25/Arrays.copyOf(elementData, size, Object[].class);//
 7     } else {
 8         // size 為零，則將空陣列賦給elementData，相當于new ArrayList(0)
 9         this.elementData =https://www.cnblogs.com/qinjunlin/archive/2020/09/25/ EMPTY_ELEMENTDATA;
10     }
11 }

產生擴容的操作

add方法

 1 public boolean add(E e) {
 2     ensureCapacityInternal(size + 1);  //每次添加元素到集合中時都會先確認下集合容量大小
 3     elementData[size++] = e;  //size 自增 +1，
 4     return true;
 5 }
 6     
 7 //確認容量大小
 8 private void ensureCapacityInternal(int minCapacity) {
 9     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
10 }
11 
12 //回傳容量大小
13 private static int calculateCapacity(Object[] elementData, int minCapacity) {
14     if (elementData =https://www.cnblogs.com/qinjunlin/archive/2020/09/25/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
15         return Math.max(DEFAULT_CAPACITY, minCapacity); //這里其實才是真正的開始初始化陣列的容量大小為10
16     }
17     return minCapacity;
18 }
19 
20 //根據確認的容量的大小判斷是否進行擴容
21 private void ensureExplicitCapacity(int minCapacity) {
22     modCount++;  //記錄操作次數
23 
24     // overflow-conscious code
25     if (minCapacity - elementData.length > 0)
26         grow(minCapacity);  //呼叫擴容方法
27 }

由上面的源代碼可知陣列的容量大小的初始化是在第一次添加元素的時候才開始的，calculateCapacity方法中有一個判斷elementData =https://www.cnblogs.com/qinjunlin/archive/2020/09/25/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA ，在第一次添加元素的時候，集合本身就是空的，所以會就取 DEFAULT_CAPACITY 和 minCapacity 的最大值也就是 10，

初始化完容量后，之后的每次添加元素都會走一遍上面代碼的流程，就是每次添加元素前都會確認容量，然后根據minCapacity是否大于 elementData 的長度來決定是否對集合進行擴容，

grow擴容

 1 //根據確認的容量的大小判斷是否進行擴容
 2 private void ensureExplicitCapacity(int minCapacity) {
 3     modCount++;  //記錄操作次數
 4 
 5     // overflow-conscious code
 6     if (minCapacity - elementData.length > 0)
 7         grow(minCapacity);  //呼叫擴容方法
 8 }
 9 
10 //擴容函式
11 private void grow(int minCapacity) {
12     // overflow-conscious code
13     int oldCapacity = elementData.length;
14     int newCapacity = oldCapacity + (oldCapacity >> 1);
15     if (newCapacity - minCapacity < 0)
16         newCapacity = minCapacity;
17     if (newCapacity - MAX_ARRAY_SIZE > 0)
18         newCapacity = hugeCapacity(minCapacity);
19     // minCapacity is usually close to size, so this is a win:
20     elementData =https://www.cnblogs.com/qinjunlin/archive/2020/09/25/ Arrays.copyOf(elementData, newCapacity);
21 }

1 //擴容過大，或者所需容量過大則呼叫此方法 
2 private static int hugeCapacity(int minCapacity) {
3         if (minCapacity < 0) // overflow
4             throw new OutOfMemoryError();
5         return (minCapacity > MAX_ARRAY_SIZE) ?
6             Integer.MAX_VALUE :
7             MAX_ARRAY_SIZE;
8     }

有代碼可知，這里的擴容是擴容至原來容量的 1.5 倍，為什么是1.5倍呢？可以看看下面的這個

int oldCapacity = elementData.length; //原容量為10，二進制表示為1010

int newCapacity = oldCapacity + (oldCapacity >> 1); //此處將原來的1010右移一位，變成101，即10進制的5

所以 newCapacity = 10 + 5，即是15 ，所以1.5倍是這樣來的，

其次，擴容1.5并不一定是最終的容量大小，因為還有兩個判斷，

1、如果1.5倍太小的話，則將我們所需的容量大小賦值給newCapacity

2、1.5倍太大或者我們需要的容量太大，則呼叫 hugeCapacity方法，

太大究竟是多大？請看下面

hugeCapacity方法，中的引數分析

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //ArrayList的成員變數
Integer.MAX_VALUE的大小為2的31次-1，即2147483647

所以你說大不大？嘻嘻

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/125490.html

標籤：其他

上一篇：虛擬機系列 | 執行引擎和垃圾回收

下一篇：c++ builder 呼叫com組件的dll 有沒有一個實體讓我看一下糾結了好久還是不會