小白也能看懂的ArrayList的擴容機制
- 2020 年 10 月 5 日
- 筆記
來，話不多說進入正題！我們下面用最簡單的代碼創建ArrayList並添加11個元素，並 一 一 講解底層源碼；在說之前，給大家先普及一些小知識：
》ArrayList底層是用數組來實現的
》數組一旦創建後，大小就是固定的，如果超出了數組大小後，就會創建一個新的數組
》接下來所謂數組的擴容實質上是重新創建一個大小更大的新數組
@Test public void testArrayList() { //創建一個泛型為String的ArrayList(這裡泛型是什麼不重要) ArrayList<String> list = new ArrayList<String>(); //依次添加11個元素 list.add("1"); list.add("2"); list.add("3"); list.add("4"); list.add("5"); list.add("6"); list.add("7"); list.add("8"); list.add("9"); list.add("10"); list.add("11"); }
上面的代碼中，我們就只調用了add（），在看add()源碼前，我必須給你們先介紹一些在ArrayList的常量和變量，因為在接下來的源碼中會涉及到這些，怕你們到時一臉蒙
private static final int DEFAULT_CAPACITY = 10; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; private int size; private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
》DEFAULT_CAPACITY：default_capcity，默認的容量大小，也就是當你第一次創建數組並往裏面添加第一個元素時，數組的默認容量大小
》DEFAULTCAPACITY_EMPTY_ELEMENTDATA：defaultcapacity_empty_elementdata是默認的空數組，他的作用是當elementData為{}，即空數組時，把它賦值給elementData，要是理解不了，請你往下繼續看！
》elementData：表示的就是當前存儲元素的數組
》size：他表示當前還沒有添加新元素前的數組中有效的元素個數，比如說數組長度為10，只保存了5個元素，那有效長度就是5
》MAX_ARRAY_SIZE：最大數組長度，它用來標識當前數組可保存元素的最大長度，值為Integer_MAX_VALUE -8，即2147483647 – 8 ，這裡的 8 代表8位元組用來保存數組本身的內存大小。
現在我們進入到add（）裏面看他們具體如何實現的，如下代碼：
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
》ensureCapacityInternal(size + 1)：這個方法意為「確保內部變量」，什麼意思呢？他是用來判斷當前數組的容量是否足夠，不足就擴容；等下我們會進入這個方法來看他如何具體實現的，size表示當前還未添加新元素前的數組有效元素個數，而size+1表示傳入當前數組的最小容量（有效長度）
》elementData[size++] = e：這段語句意思是給數組做賦值操作，簡單說就是給數組添加元素；比如說當前數組已經有3個元素了，那現在再添加一個元素a，則這一步為elementData[3]=a;
》return true：代表添加成功；
現在我們就進入到ensureCapacityInternal()，如下代碼：
private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
這裏面涉及兩個方法ensureExplicitCapacity（）和calculateCapacity（）：
》calculateCapacity（）：計算容量，它用來計算當前的數組所需的最小容量minCapacity， 你可以理解為當前數組的有效長度；源碼如下：
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//若傳入的是個空數組，則返回的是最小容量 是 默認容量（10） 和 當前最小容量（0）之間的最大值 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; }
PS：第一次添加元素時calculateCapacity返回的最小容量minCapacity是10，從第二次開始minCapacity為2，第三次為3，依次類推..在這裡第一次返回10大家不要糾結它的意義，重點在第二次及之後表示的意思
》ensureExplicitCapacity（）：判斷是否需要擴容；查看它的源碼：
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code當最小容量大於當前的數組大小時 if (minCapacity - elementData.length > 0)
//計算擴容後的數組大小 grow(minCapacity); }
我們第一次list.add（），最小容量minCapacity是10，elementData.length長度為0，所以條件成立，進入grow()（第二次minCapacity是2，elementData.length為10，條件不成立就不再擴容了；當第11次時，11>10，又可以擴容了）
private void grow(int minCapacity) { // 得到當前數組的大小，即老數組大小 int oldCapacity = elementData.length;
//將舊數組大小+舊數組/2，即舊數組的1.5倍是新數組的大小（先不要在意>>1的意思，你只要知道oldCapacity >> 1表示oldCapacity/2就行） int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果擴容後的是數組大小還是小於最小所需容量，直接讓minCapacity賦值到新容量 if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
//若新容量大小大於數組長度的最大預設值；由於擴容後是原數組的1.5倍，則非常有可能會溢出這個預設值 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win: //上面都是為了確定最終的新容量的大小，這個方法是真正的擴容實現 elementData = Arrays.copyOf(elementData, newCapacity); }
相信大家這上面大部分都能夠理解，可能就一個地方不太清楚：當newCapacity > MAX_ARRAY_SIZE（新容量大於預設值較特殊的情況，一般數組長度不會擴容到這麼大）時調用hugeCapacity有啥用？我們看下hugeCapacity()的源碼：
private static int hugeCapacity(int minCapacity) { //若最小容量小於0的情況，拋出異常 if (minCapacity < 0) // overflow throw new OutOfMemoryError(); //若最小容量>最大預設值，返回Integer.Max_VALUE,否則是MAX_ARRAY_SIZE（Integer.Max_VALUE-8） return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
hugeCapacity()是用來限制新容量的大小的，是不能超出Integer.MAX_VALUE值的，最後說一點，數組的最大長度並不是MAX_ARRAY_SIZE，而是Integer.MAX_VALUE。
》Arrays.copyOf(elementData, newCapacity)，就不看源碼了，簡單說一下：它這個方法能返回一個擴容後的數組，將舊數組elementData的數據複製到長度為newCapacity的新數組中。
好的，就介紹到這裡吧，覺得可以的點給贊哦！
