起因

在Leetcode上做題寫了兩種暴力解法，但是執行效率上不太一樣。

時間上差很遠，記憶體雖然差不多但是前者擊敗30%，後者擊敗94%。這兩種解法區別是用一條ArrayList還是兩條來存數據，所以contains雖然執行次數一樣但是檢測的長度上不一樣，而且ArrayList的擴容次數也不一樣，所以學習一下。

contains(Object o)

直接翻(JDK8)源碼:

null和object區分開來還是因為equals有一方是null的話都會導致異常. 合併一起寫的話可以用Objects.equals(obj1, obj2)的寫法.
所以顯然暴力解法用到的contains的原理就是朴實無華的一遍遍搜索所以時間特別長.

ArrayList擴容機制

省流: 直接看最下麵的grow函數.

如果是預設的ArrayList, 添加元素時會先計算數組長度, 如果元素個數+1大於當前數組長度+1大於elementData.length時進行擴容，擴容後的數組大小是: oldCapacity + (oldCapacity >> 1) 可以理解成1.5倍擴容。

涉及到的源碼:

// 向指定索引位置插入元素
public void add(int index, E element) {
    // 檢查索引範圍
    rangeCheckForAdd(index);

    // 確保容量足夠
    ensureCapacityInternal(size + 1);  // 增加 modCount（用於支持併發修改的計數器）
    // 使用 System.arraycopy 將元素後移，為新元素騰出位置, 這是跟另一個add的區別⭐⭐⭐⭐⭐
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element; // 在指定位置插入新元素
    size++; // 更新列表大小
}

// 在列表末尾添加元素
public boolean add(E e) {
    // 確保容量足夠
    ensureCapacityInternal(size + 1);  // 增加 modCount
    elementData[size++] = e; // 在列表末尾添加新元素
    return true;
}

// 內部方法：確保容量足夠
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 內部方法：計算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 如果內部數組為空，返回預設容量或所需容量中的較大者
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity; // 否則返回所需容量
}

// 內部方法：確保容量足夠
private void ensureExplicitCapacity(int minCapacity) {
    modCount++; // 增加併發修改計數器

    // 檢查容量是否足夠，如果不夠則擴展
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 內部方法：擴展容量
private void grow(int minCapacity) {
    // 溢出安全的代碼
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量通常為舊容量的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity; // 如果新容量小於所需容量，使用所需容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity); // 處理可能的巨大容量情況
    // 使用 Arrays.copyOf 擴展數組容量
    elementData = Arrays.copyOf(elementData, newCapacity);
}

實際上Array.copyof底層調用的還是System.arraycopy.