面試官：換人！他連 ArrayList 的擴容機制都答不上來

聲明：為了邁向國際化，二哥把《教妹學(xué) Java》專欄的名字修改成了《Java 程序員進階之路》，英文全名叫 to be better javaer，怎么樣？是不是瞬間就高大上了點。

GitHub 地址：https://github.com/itwanger/toBeBetterJavaer

趕緊去 GitHub 上把該死 star 給安排下吧！文末附新版 PDF 的下載方式，想要的同學(xué)可以立馬拉到文末，emmm，順帶把點贊+在看悄悄地安排一下。

“二哥，聽說今天我們開講 ArrayList 了？好期待哦！”三妹明知故問，這個托配合得依然天衣無縫。

“是的呀，三妹。”我肯定地點了點頭，繼續(xù)說道，“ArrayList 可以稱得上是集合框架方面最常用的類了，可以和 HashMap 一較高下。”

從名字就可以看得出來，ArrayList 實現(xiàn)了 List 接口，并且是基于數(shù)組實現(xiàn)的。

數(shù)組的大小是固定的，一旦創(chuàng)建的時候指定了大小，就不能再調(diào)整了。也就是說，如果數(shù)組滿了，就不能再添加任何元素了。ArrayList 在數(shù)組的基礎(chǔ)上實現(xiàn)了自動擴容，并且提供了比數(shù)組更豐富的預(yù)定義方法（各種增刪改查），非常靈活。

Java 這門編程語言和 C語言的不同之處就在這里，如果是 C語言的話，就必須動手實現(xiàn)自己的 ArrayList，原生的庫函數(shù)里面是沒有的。

“二哥，如何創(chuàng)建一個 ArrayList 啊？”三妹問。

ArrayList<String> alist = new ArrayList<String>();

可以通過上面的語句來創(chuàng)建一個字符串類型的 ArrayList（通過尖括號來限定 ArrayList 中元素的類型，如果嘗試添加其他類型的元素，將會產(chǎn)生編譯錯誤），更簡化的寫法如下：

List<String> alist = new ArrayList<>();

由于 ArrayList 實現(xiàn)了 List 接口，所以 alist 變量的類型可以是 List 類型；new 關(guān)鍵字聲明后的尖括號中可以不再指定元素的類型，因為編譯器可以通過前面尖括號中的類型進行智能推斷。

如果非常確定 ArrayList 中元素的個數(shù)，在創(chuàng)建的時候還可以指定初始大小。

List<String> alist = new ArrayList<>(20);

這樣做的好處是，可以有效地避免在添加新的元素時進行不必要的擴容。但通常情況下，我們很難確定  ArrayList 中元素的個數(shù)，因此一般不指定初始大小。

“二哥，那怎么向 ArrayList 中添加一個元素呢？”三妹繼續(xù)問。

可以通過 add() 方法向 ArrayList 中添加一個元素，如果不指定下標的話，就默認添加在末尾。

alist.add("沉默王二");

“三妹，你可以研究一下 add() 方法的源碼（基于 JDK 8 會好一點），它在添加元素的時候會判斷需不需要進行擴容，如果需要的話，會執(zhí)行 grow() 方法進行擴容，這個也是面試官特別喜歡考察的一個重點。”我叮囑道。

下面是 add(E e) 方法的源碼：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

調(diào)用了私有的 ensureCapacityInternal 方法：

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

假如一開始創(chuàng)建 ArrayList 的時候沒有指定大小，elementData 就會被初始化成一個空的數(shù)組，也就是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

進入到 if 分支后，minCapacity 的值就會等于 DEFAULT_CAPACITY，可以看一下 DEFAULT_CAPACITY 的初始值：

private static final int DEFAULT_CAPACITY = 10;

也就是說，如果 ArrayList 在創(chuàng)建的時候沒有指定大小，默認可以容納 10 個元素。

接下來會進入 ensureExplicitCapacity 方法：

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

接著進入 grow(int minCapacity) 方法：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    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);
}

然后對數(shù)組進行第一次擴容 Arrays.copyOf(elementData, newCapacity)，由原來的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 擴容為容量為 10 的數(shù)組。

“那假如向 ArrayList 添加第 11 個元素呢？”三妹看到了問題的關(guān)鍵。

此時，minCapacity 等于 11，elementData.length 為 10，ensureExplicitCapacity() 方法中 if 條件分支就起效了：

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

會再次進入到 grow() 方法：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    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);
}

“oldCapacity 等于 10，oldCapacity >> 1 這個表達式等于多少呢？三妹你知道嗎？”我問三妹。

“不知道啊，>> 是什么意思呢？”三妹很疑惑。

“>> 是右移運算符，oldCapacity >> 1 相當于 oldCapacity 除以 2。”我給三妹解釋道，“在計算機內(nèi)部，都是按照二進制存儲的，10 的二進制就是 1010，也就是 0*2^0 + 1*2^1 + 0*2^2 + 1*2^3=0+2+0+8=10 。。。。。。”

還沒等我解釋完，三妹就打斷了我，“二哥，能再詳細解釋一下到底為什么嗎？”

“當然可以啊。”我拍著胸脯對三妹說。

先從位全的含義說起吧。

平常我們使用的是十進制數(shù)，比如說 39，并不是簡單的 3 和 9，3 表示的是 3*10 = 30，9 表示的是 9*1 = 9，和 3 相乘的 10，和 9 相乘的 1，就是位權(quán)。位數(shù)不同，位權(quán)就不同，第 1 位是 10 的 0 次方（也就是 10^0=1），第 2 位是 10 的 1 次方（10^1=10），第 3 位是 10 的 2 次方（10^2=100），最右邊的是第一位，依次類推。

位權(quán)這個概念同樣適用于二進制，第 1 位是 2 的 0 次方（也就是 2^0=1），第 2 位是 2 的 1 次方（2^1=2），第 3 位是 2 的 2 次方（2^2=4），第 34 位是 2 的 3 次方（2^3=8）。

十進制的情況下，10 是基數(shù)，二進制的情況下，2 是基數(shù)。

10 在十進制的表示法是 0*10^0+1*10^1=0+10=10。

10 的二進制數(shù)是 1010，也就是 0*2^0 + 1*2^1 + 0*2^2 + 1*2^3=0+2+0+8=10。

然后是移位運算，移位分為左移和右移，在 Java 中，左移的運算符是 <<，右移的運算符 >>。

拿 oldCapacity >> 1 來說吧，>> 左邊的是被移位的值，此時是 10，也就是二進制 1010；>> 右邊的是要移位的位數(shù)，此時是 1。

1010 向右移一位就是 101，空出來的最高位此時要補 0，也就是 0101。

“那為什么不補 1 呢？”三妹這個問題很尖銳。

“因為是算術(shù)右移，并且是正數(shù)，所以最高位補 0；如果表示的是負數(shù)，就需要補 1。”我慢吞吞地回答道，“0101 的十進制就剛好是 1*2^0 + 0*2^1 + 1*2^2 + 0*2^3=1+0+4+0=5，如果多移幾個數(shù)來找規(guī)律的話，就會發(fā)現(xiàn)，右移 1 位是原來的 1/2，右移 2 位是原來的 1/4，諸如此類。”

也就是說，ArrayList 的大小會擴容為原來的大小+原來大小/2，也就是差不多 1.5 倍。

除了 add(E e) 方法，還可以通過 add(int index, E element) 方法把元素添加到指定的位置：

alist.add(0, "沉默王三");

add(int index, E element) 方法的源碼如下：

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
            size - index);
    elementData[index] = element;
    size++;
}

該方法會調(diào)用到一個非常重要的本地方法 System.arraycopy()，它會對數(shù)組進行復(fù)制（要插入位置上的元素往后復(fù)制）。

“三妹，注意看，我畫幅圖來表示下。”我認真地做起了圖。

“二哥，那怎么更新 ArrayList 中的元素呢？”三妹繼續(xù)問。

可以使用 set() 方法來更改 ArrayList 中的元素，需要提供下標和新元素。

alist.set(0, "沉默王四");

假設(shè)原來 0 位置上的元素為“沉默王三”，現(xiàn)在可以將其更新為“沉默王四”。

來看一下 set() 方法的源碼：

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

該方法會先對指定的下標進行檢查，看是否越界，然后替換新值并返回舊值。

“二哥，那怎么刪除 ArrayList 中的元素呢？”三妹繼續(xù)問。

remove(int index) 方法用于刪除指定下標位置上的元素，remove(Object o) 方法用于刪除指定值的元素。

alist.remove(1);
alist.remove("沉默王四");

先來看 remove(int index) 方法的源碼：

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;
}

該方法會調(diào)用 System.arraycopy() 對數(shù)組進行復(fù)制移動，然后把要刪除的元素位置清空 elementData[--size] = null。

再來看 remove(Object o) 方法的源碼：

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

該方法通過遍歷的方式找到要刪除的元素，null 的時候使用 == 操作符判斷，非 null 的時候使用 equals() 方法，然后調(diào)用 fastRemove() 方法；有相同元素時，只會刪除第一個。

既然都調(diào)用了 fastRemove() 方法，那就繼續(xù)來跟蹤一下源碼：

private void fastRemove(int index) {
    modCount++;
    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
}

同樣是調(diào)用 System.arraycopy() 方法對數(shù)組進行復(fù)制和移動。

“三妹，注意看，我畫幅圖來表示下。”我認真地做起了圖。

“二哥，那怎么查找 ArrayList 中的元素呢？”三妹繼續(xù)問。

如果要正序查找一個元素，可以使用 indexOf() 方法；如果要倒序查找一個元素，可以使用 lastIndexOf() 方法。

alist.indexOf("沉默王二");
alist.lastIndexOf("沉默王二");

來看一下 indexOf() 方法的源碼：

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

如果元素為 null 的時候使用“==”操作符，否則使用 equals() 方法。

lastIndexOf() 方法和 indexOf() 方法類似，不過遍歷的時候從最后開始。

contains() 方法可以判斷 ArrayList 中是否包含某個元素，其內(nèi)部調(diào)用了 indexOf() 方法：

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

如果 ArrayList 中的元素是經(jīng)過排序的，就可以使用二分查找法，效率更快。

Collections 類的 sort() 方法可以對 ArrayList 進行排序，該方法會按照字母順序?qū)?String 類型的列表進行排序。如果是自定義類型的列表，還可以指定 Comparator 進行排序。

List<String> copy = new ArrayList<>(alist);
copy.add("a");
copy.add("c");
copy.add("b");
copy.add("d");

Collections.sort(copy);
System.out.println(copy);

輸出結(jié)果如下所示：

[a, b, c, d]

排序后就可以使用二分查找法了：

int index = Collections.binarySearch(copy, "b");

“最后，三妹，我來簡單總結(jié)一下 ArrayList 的時間復(fù)雜度吧，方便后面學(xué)習(xí) LinkedList 時對比。”我喝了一口水后補充道。

1）通過下標（也就是 get(int index)）訪問一個元素的時間復(fù)雜度為 O(1)，因為是直達的，無論數(shù)據(jù)增大多少倍，耗時都不變。

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

2）默認添加一個元素（調(diào)用 add() 方法時）的時間復(fù)雜度為 O(1)，因為是直接添加到數(shù)組末尾的，但需要考慮到數(shù)組擴容時消耗的時間。

3）刪除一個元素（調(diào)用 remove(Object) 方法時）的時間復(fù)雜度為 O(n)，因為要遍歷列表，數(shù)據(jù)量增大幾倍，耗時也增大幾倍；如果是通過下標刪除元素時，要考慮到數(shù)組的移動和復(fù)制所消耗的時間。

4）查找一個未排序的列表時間復(fù)雜度為 O(n)（調(diào)用 indexOf() 或者 lastIndexOf() 方法時），因為要遍歷列表；查找排序過的列表時間復(fù)雜度為 O(log n)，因為可以使用二分查找法，當數(shù)據(jù)增大 n 倍時，耗時增大 logn 倍（這里的 log 是以 2 為底的，每找一次排除一半的可能）。

ArrayList，如果有個中文名的話，應(yīng)該叫動態(tài)數(shù)組，也就是可增長的數(shù)組，可調(diào)整大小的數(shù)組。動態(tài)數(shù)組克服了靜態(tài)數(shù)組的限制，靜態(tài)數(shù)組的容量是固定的，只能在首次創(chuàng)建的時候指定。而動態(tài)數(shù)組會隨著元素的增加自動調(diào)整大小，更符合實際的開發(fā)需求。

學(xué)習(xí)集合框架，ArrayList 是第一課，也是新手進階的重要一課。要想完全掌握 ArrayList，擴容這個機制是必須得掌握，也是面試中經(jīng)常考察的一個點。

要想掌握擴容機制，就必須得讀源碼，也就肯定會遇到 oldCapacity >> 1，有些初學(xué)者會選擇跳過，雖然不影響整體上的學(xué)習(xí)，但也錯過了一個精進的機會。

計算機內(nèi)部是如何表示十進制數(shù)的，右移時又發(fā)生了什么，靜下心來去研究一下，你就會發(fā)現(xiàn)，哦，原來這么有趣呢？

好了，點擊下方的名片，回復(fù)關(guān)鍵字「03」 就可以獲取《Java 程序員進階之路》的 PDF 版了。

希望大家能點贊+在看下，給二哥注入一點點更新的動力。我也會不斷地提升品質(zhì)，更大家?guī)砀埠说募夹g(shù)文章，筆芯~