創(chuàng)建ArrayList

創(chuàng)建 ArrayList 時窿给，一般是直接創(chuàng)建覆获，或者是直接將實現(xiàn)了 Collection 接口的集合類傳入進行初始化創(chuàng)建

// 1 直接new
ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
System.out.println(Arrays.toString(list.toArray()));

// 2 創(chuàng)建時直接添加元素 實現(xiàn)了collection接口的類
ArrayList<String> list1 = new ArrayList<>(list);
System.out.println(Arrays.toString(list1.toArray()));
HashSet<String> hashSet = new HashSet<>();
hashSet.add("C");
ArrayList<String> list2 = new ArrayList<>(hashSet);
System.out.println(Arrays.toString(list2.toArray()));

添加元素 -> ArrayList 的擴容機制

首先看 ArrayList 的 add 方法，當添加元素時贸弥，首先是通過 ensureCapacityInternal 方法進行

增量判斷窟坐，判斷后進行賦值以及返回添加元素成功。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!這里是增量機制
    elementData[size++] = e;
    return true;
}

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

private static final int DEFAULT_CAPACITY = 10;

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

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++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

而對于 ensureCapacityInternal 方法來說绵疲，首先通過 calculateCapacity 方法來計算容量哲鸳。

如果 elementData(存儲數(shù)據(jù)的數(shù)組) 為 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 數(shù)組，

則說明 ArrayList 是無參剛創(chuàng)建的盔憨，所以使用默認的容量(10)與實際數(shù)量 minCapacity(size + 1)

中最大值徙菠。通過 ensureExplicitCapacity 方法驗證容量與 elementData 實際長度的大小情況，

通過 grow 方法進行擴容郁岩。同理 addAll 方法也是同樣的機制婿奔。只不過多了復制數(shù)組的一步。

成員變量 modCount 則是后面再說问慎，下面先說 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);
}

grow 方法增容詳解。首先根據(jù) ArrayList 中元素的數(shù)量 + (數(shù)量 >> 1)也就大約是容量的1.5倍如叼，

所以 newCapacity - minCapacity < 0 這個條件只有空數(shù)據(jù)第一次添加的時候能成立冰木，

讓 elementData 初始化為長度10的數(shù)組，之后都不成立笼恰。在上面的 ensureExplicitCapacity

方法中 minCapacity 是 size + 1踊沸，所以只有當 size == elementData.length 時，才會

調(diào)用 grow 方法進行擴容社证，將容量 增擴為 oldCapacity + (oldCapacity >> 1)逼龟，約是1.5倍。

刪除元素 -> ArrayList 刪除元素時所需考慮問題

刪除方法一般使用 remove 方法猴仑，其他較為特殊的方法暫不討論审轮。

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

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

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

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
}

通過 index 刪除時先進行下標范圍檢查肥哎，然后獲取到刪除元素，移動原數(shù)組疾渣。

為什么是 size - 1 - index篡诽，是因為 index 從0開始。numMoved 不判斷=0的情況

則是因為=0時榴捡，刪除元素是末尾元素杈女，直接置 null 就好。elementData[--size] = null

就是末尾元素置 null吊圾。其他情況則移動元素通過 object 刪除時則涉及到 fastRemove 方法达椰，

原理和刪除 index 的情況一致。這里判斷了 o == null是因為 o 為 null 時調(diào)用

equals 方法時報 NPE项乒，所以要判斷啰劲。而 equals 方法判斷相等時，為了實現(xiàn)現(xiàn)實中的

‘相等概念’需要重寫 equals 和 hashCode 方法檀何。否則 equals 只是判斷是否為同一對象蝇裤。

ArrayList<String> list = new ArrayList<>();
list.add("張三");
list.add("張三");
list.add("趙四");
list.add("王五");

for (int i = 0; i < list.size(); i++) {
    if ("張三".equals(list.get(i))) {
        list.remove(list.get(i));
        System.out.println("張三已被刪除");
    }
}

for (String str : list) {
    if ("張三".equals(str)) {
        list.remove(str);
        System.out.println("張三已被刪除1");
    }
}

/*
    張三已被刪除
    張三已被刪除1
    Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:911)
    at java.util.ArrayList$Itr.next(ArrayList.java:861)
    at com.wuhaitao.base.collection.List.ArrayListInfo.main(ArrayListInfo.java:62)
*/

一般情況下，集合中刪除元素時频鉴，我們都是通過遍歷去刪除元素栓辜。所以這里存在一些問題。

由于有fail-fast 機制垛孔，這個機制意思是：一旦檢測到可能會發(fā)生錯誤藕甩，就立馬拋出異常，

程序?qū)⒉辉偻聢?zhí)行周荐。這個機制并不是集合中特有的狭莱，只是在集合中很容易實現(xiàn)，在這里

介紹很方便概作。比如上面的例子贩毕，看著沒有任何問題，但是一旦運行起來就會報錯仆嗦，拋出了

ConcurrentModificationException 異常。并且還調(diào)用了911行的checkForComodification

方法先壕。明明我們只調(diào)用了 remove 方法瘩扼，remove 方法中也沒有調(diào)用

checkForComodification方法，那么這些情況是為什么呢垃僚？另外集绰，為什么 fori 沒有

問題的刪除了第一個‘張三’，但是為什么后面不再刪除了谆棺？在 fori 的情況下栽燕，

當?shù)谝粋€元素被刪除時罕袋，集合本身元素位置發(fā)生變化，刪除完第一個‘張三’后：i = 1碍岔，但是

第二個‘張三’被移動到了 index = 0 的位置浴讯，所以下一次 get(i) 時，獲取到的是被移動到

index = 1 的‘趙四’第二個‘張三’蔼啦，因此被巧妙地跳過了榆纽。所以，當使用 fori 進行刪除時捏肢，

雖然可以進行刪除操作奈籽，但存在數(shù)據(jù)問題。我們接著來看增強 for鸵赫。

String[] arr = new String[]{"張三", "張三", "趙四", "王五"};
String[] var2 = arr;
int i = arr.length;

for(int var4 = 0; var4 < i; ++var4) {
    String s = var2[var4];
    System.out.println(s);
}

List<Integer> list = new ArrayList();

for(i = 0; i < 5; ++i) {
    list.add(i);
}

Iterator var7 = list.iterator();

while(var7.hasNext()) {
    Integer integer = (Integer)var7.next();
    if ("張三".equals(str)) {
        list.remove(str);
    }
}

增強for是一個語法糖衣屏。所以在編譯代碼時，它會被解析成基礎(chǔ)代碼辩棒。如果是數(shù)組使用增強for

則解析過后就是 fori 的形式狼忱。如果是實現(xiàn)了 Iterable 的集合，則會解析成 iterator

迭代器的形式遍歷集合盗温。所以藕赞，在之前 ArrayList 的增強 for 中，會被解析成 iterator

迭代器形式遍歷卖局。所以會調(diào)用 iterator斧蜕，hasNext 方法以及 next 方法。但是呢砚偶！

這里有一個我們非常需要注意的地方批销，刪除方法我們是調(diào)用的 ArrayList 的 remove 方法。

我們接下來看下 Itr 源碼染坯。(注意：泛型也是語法糖均芽，也會被解析成基礎(chǔ)代碼，但這里不做講解)

public Iterator<E> iterator() {
    return new Itr();
}

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

在 ArrayList 實現(xiàn)的 iterator 方法中单鹿，返回了內(nèi)部類 Itr 實例對象掀宋。Itr 則實現(xiàn)了

Iterator 接口，所以會重寫 hasNext仲锄，next 方法劲妙。在 hasNext 中判斷了指針是否還指向元素。

而在 next 方法中掉了用我們前面提到的報錯方法 checkForComodification儒喊，這個方法拋出了

ConcurrentModificationException 異常镣奋。而這個異常是根據(jù) modCount != expectedModCount

這個條件達成的。好怀愧，現(xiàn)在我們就要來聊聊這個一開始就提到的 modCount 了侨颈。

protected transient int modCount = 0;
// add 方法調(diào)用
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
// remove 方法調(diào)用
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
}

首先 modCount 并不在 ArrayList 中定義的余赢，而是在 AbstractList 中定義的，其記錄的是

集合被修改的次數(shù)哈垢。所以妻柒，在 add，remove 等方法中會見到 modCount++ 這個操作温赔。在‘張三’

的例子增強for中蛤奢，創(chuàng)建 Itr 內(nèi)部類時 int expectedModCount=modCount，expectedModCount

這個內(nèi)部類成員變量已被賦值陶贼，因為做了四次 add啤贩、一次 remove 操作， 所以

expectedModCount = modCount = 5拜秧。當增強 for第一次遍歷時痹屹，checkForComodification

方法判斷成功，刪除第二個‘張三’(第一個‘張三’是 fori 中刪除)上面說過枉氮，增強 for 中調(diào)用的是

ArrayList的刪除方法志衍。所以這時modCount++變成了6，所以在下一次刪除時聊替，

checkForComodification 方法判斷失敗楼肪，所以報了 ConcurrentModificationException 異常。

那么我們來看正常的 iterator 迭代器遍歷惹悄。

List<String> list = new ArrayList<>();
list.add("張三");
list.add("張三");
list.add("趙四");
list.add("王五");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String next = iterator.next();
    if ("張三".equals(next)) {
        iterator.remove();
        System.out.println("張三已被刪除1");
    }
}
// itr 的刪除源碼
public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();
    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

在迭代器遍歷刪除時春叫，我們調(diào)用的時 Itr 內(nèi)部類的刪除方法，我們明顯看到了

expectedModCount = modCount泣港，這也就解釋了為什么迭代器遍歷不會報錯而增強 for 會報錯

最后暂殖，阿里守則中，也明確提到了当纱，不要在 foreach 循環(huán)里刪除元素呛每。若需刪除元素，

請使用 Iterator 方式坡氯。在并發(fā)操作時晨横，需對 Iterator 對象加鎖。

查找元素 -> 如果有序箫柳，可以二分查找提高效率

如果要正序查找一個元素颓遏，可以使用 indexOf 方法；如果要倒序查找一個元素滞时，可以使用

lastIndexOf 方法contains方法可以判斷 ArrayList 中是否包含某個元素，內(nèi)部調(diào)用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;
}
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

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

ArrayList<String> copy = new ArrayList<>(alist);
copy.add("1");
copy.add("2");
copy.add("2");
copy.add("4");
Collections.sort(copy);
System.out.println(copy);

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

更新元素

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

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

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

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

更新元素時曼玩，先對指定的下標進行檢查，看是否越界窒百，然后替換新值并返回舊值

(????)??嗨黍判！如果這篇文章小小幫助到你，可以幫小弟我點個贊呀篙梢。點贊是對我最大的支持與認可顷帖，感謝！