ArrayList 底層原理和重點代碼分析

ArrayList 相關類圖

ArrayList 是 Java 中常用的一種資料結構，底層使用數組實作。

它的特點是支援動态擴容和随機通路，但是對于往中間插入或者删除，效率相對較低。

下面我們來詳細講解一下 ArrayList 的底層原理。

在建立 ArrayList 對象時，會先建立一個空數組，用來存放元素。

預設情況下，這個數組的大小為 10(DEFAULT_CAPACITY)，可以通過構造函數傳入容量大小進行初始化。

//預設大小的集合
 private static final int DEFAULT_CAPACITY = 10;
 
 //通過有參構造，建立一個指定大小的集合
 public ArrayList(int initialCapacity) {
   if (initialCapacity > 0) {
   this.elementData = new Object[initialCapacity];
   } else if (initialCapacity == 0) {
   this.elementData = EMPTY_ELEMENTDATA;
   } else {
   throw new IllegalArgumentException("Illegal Capacity: "+
   initialCapacity);
   }
 }           

當需要添加元素時，如果目前數組已滿，則會建立一個新的數組，将原數組的元素複制到新數組中，并将新元素添加到新數組的末尾。是以，ArrayList 的添加操作是一個比較耗時的操作，特别是在數組長度很大時。

關鍵代碼如下：

private void grow(int minCapacity) {
         // overflow-conscious code
         int oldCapacity = elementData.length;
       //容量擴容為原來的 1.5 倍
         int newCapacity = oldCapacity + (oldCapacity >> 1);
         if (newCapacity - minCapacity < 0)
             newCapacity = minCapacity;
         if (newCapacity - MAX_ARRAY_SIZE > 0)
             newCapacity = hugeCapacity(minCapacity);
         // 複制
         elementData = Arrays.copyOf(elementData, newCapacity);
     }
 
 
     public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
         @SuppressWarnings("unchecked")
         T[] copy = ((Object)newType == (Object)Object[].class)
             ? (T[]) new Object[newLength]
             : (T[]) Array.newInstance(newType.getComponentType(), newLength);
         System.arraycopy(original, 0, copy, 0,
                          Math.min(original.length, newLength));
         return copy;
     }
            

随機通路 ArrayList 中的元素時，隻需要根據元素的下标計算出在數組中的索引，然後直接通路該位置的元素即可。由于數組的記憶體是連續的，是以通路數組元素的速度非常快，時間複雜度為 O(1)。

public E get(int index) {
         rangeCheck(index);
 
         return elementData(index);
     }
 
 
     //越界校驗
     private void rangeCheck(int index) {
         if (index >= size)
             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
     }           

上邊你可以看到，這裡有個 size 這個size是數組中實際的元素個數！而 elementData包含了元素，并且還有一部分的空餘空間！

當需要删除 ArrayList 中的元素時，會将該元素從數組中删除，并将後面的元素往前移動。這個過程也是比較耗時的，特别是删除數組中靠前的元素時。

關鍵代碼如下：

public E remove(int index) {
       //越界檢查
         rangeCheck(index);
 
         modCount++;//資料修改的次數（可以當做是資料的版本号，并發修改的時候，當做校驗條件）
         E oldValue = elementData(index);
 
         int numMoved = size - index - 1;
         if (numMoved > 0)
             System.arraycopy(elementData, index+1, elementData, index,
                              numMoved);
         elementData[--size] = null; // clear to let GC do its work
 
         return oldValue;
     }
 
            

當 ArrayList 中的元素數量變得很少時，我們可以使用 trimToSize 方法将容量縮小到實際元素數量，這樣可以減小記憶體的開銷。

public void trimToSize() {
         modCount++;
         if (size < elementData.length) {
             elementData = (size == 0)
               ? EMPTY_ELEMENTDATA
               : Arrays.copyOf(elementData, size);
         }
     }           

總結一下，ArrayList 的優點是支援随機通路，支援動态擴容；缺點是添加和删除元素比較耗時，特别是在數組長度很大時。在實際應用中，我們需要根據具體的業務場景，選擇合适的資料結構來存儲和操作資料