ArrayList概述

ArrayList就是動(dòng)態(tài)數(shù)組邪锌，用MSDN中的說法芒炼，就是Array的復(fù)雜版本批狐，它提供了動(dòng)態(tài)的增加和減少元素，實(shí)現(xiàn)了ICollection和IList接口鸳谜，靈活的設(shè)置數(shù)組的大小等好處,其繼承關(guān)系如下

ArrayList繼承關(guān)系.png

ArrayList是線程不安全的,如果在多線程中使用,建議用CopyOnWriteArrayList或者用Collections中的synchronizedList方法將其包裝成一個(gè)線程安全的List

預(yù)熱

System.arraycopy()和Arrays.copyOf()

  //System.arraycopy()
   @FastNative
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);
//Arrays.copyOf()
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;
    }

• 從源碼可以看出
  • arraycopy()需要目標(biāo)數(shù)組膝藕，將原數(shù)組拷貝到你自己定義的數(shù)組里，而且可以選擇拷貝的起點(diǎn)和長(zhǎng)度以及放入新數(shù)組中的位置
  • copyOf()是系統(tǒng)自動(dòng)在內(nèi)部新建一個(gè)數(shù)組咐扭，調(diào)用arraycopy()將original內(nèi)容復(fù)制到copy中去芭挽，并且長(zhǎng)度為newLength懒棉。返回copy; 即將原數(shù)組拷貝到一個(gè)長(zhǎng)度為newLength的新數(shù)組中，并返回該數(shù)組览绿。
  • Array.copyOf()可以看作是受限的System.arraycopy(),它主要是用來將原數(shù)組全部拷貝到一個(gè)新長(zhǎng)度的數(shù)組，適用于數(shù)組擴(kuò)容穗慕。

看看源碼怎么說

/*******************************ArrayList中重要的常量*********************************************/
    //序列化id
    private static final long serialVersionUID = 8683452581122892189L;
    //容器默認(rèn)初始化大小 
    private static final int DEFAULT_CAPACITY = 10;
    //一個(gè)空對(duì)象
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //一個(gè)空對(duì)象饿敲，如果使用默認(rèn)構(gòu)造函數(shù)創(chuàng)建ArrayList，則默認(rèn)對(duì)象內(nèi)容是該值
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //ArrayList存放對(duì)象的容器逛绵，后面的添加怀各、刪除等操作都是基于該屬性來進(jìn)行操作
    transient Object[] elementData; 
    //當(dāng)前列表已使用的長(zhǎng)度
    private int size;
    //數(shù)組最大長(zhǎng)度（2147483639），這里為什么是Integer.MAX_VALUE - 8是因?yàn)橛行┨摂M機(jī)在數(shù)組中保留了一些頭部信    息术浪，防止內(nèi)存溢出
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    //這個(gè)是從AbstractList繼承過來的瓢对，代表ArrayList集合修改的次數(shù)
    protected transient int modCount = 0;   

transient^xr1關(guān)鍵字，變量修飾符胰苏，如果用transient聲明一個(gè)實(shí)例變量硕蛹，當(dāng)對(duì)象存儲(chǔ)時(shí)，它的值不需要維持硕并。換句話來說就是法焰，用transient關(guān)鍵字標(biāo)記的成員變量不參與序列化過程。

作用

Java的serialization提供了一種持久化對(duì)象實(shí)例的機(jī)制倔毙。當(dāng)持久化對(duì)象時(shí)埃仪，可能有一個(gè)特殊的對(duì)象數(shù)據(jù)成員，我們不想用serialization機(jī)制來保存它陕赃。為了在一個(gè)特定對(duì)象的一個(gè)域上關(guān)閉serialization卵蛉，可以在這個(gè)域前加上關(guān)鍵字transient。當(dāng)一個(gè)對(duì)象被序列化的時(shí)候么库，transient型變量的值不包括在序列化的表示中傻丝，然而非transient型的變量是被包括進(jìn)去的

構(gòu)造函數(shù)

    //1.我們常用的無參構(gòu)造 
    public ArrayList() {
        //構(gòu)造一個(gè)空數(shù)組
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    //2.帶初始長(zhǎng)度的ArrayList構(gòu)造函數(shù)
    public ArrayList(int initialCapacity) {
        //創(chuàng)建指定長(zhǎng)度的數(shù)組
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //創(chuàng)建空數(shù)組
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    //3.帶Collection對(duì)象的構(gòu)造函數(shù)
    public ArrayList(Collection<? extends E> c) {
        //把Collection轉(zhuǎn)為數(shù)組對(duì)ArrayList初始容器進(jìn)行數(shù)組地址的拷貝
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            //把Collection對(duì)象的內(nèi)容copy(可以理解為深拷貝)到elementData中，并且這些元素是按照該collection的              迭代器返回它們的順序排列的
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 替換成空數(shù)組
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

構(gòu)造函數(shù)總結(jié)

1. 如果不傳遞參數(shù) 默認(rèn)會(huì)構(gòu)建一個(gè)空數(shù)組,

2. 傳遞int值表示創(chuàng)建初始的數(shù)組長(zhǎng)度

3. 傳遞collection對(duì)象,默認(rèn)會(huì)把這個(gè)對(duì)象轉(zhuǎn)為數(shù)組,如果這個(gè)collection對(duì)象不是object類型,就會(huì)進(jìn)行一次深拷貝

增加元素Add

• boolean add(E e);

//將指定的元素附加到此列表的末尾
public boolean add(E e) {
        //判斷是否需要對(duì)數(shù)組進(jìn)行擴(kuò)容
        ensureCapacityInternal(size + 1);  
        //進(jìn)行元素賦值
        elementData[size++] = e;
        return true;
}
//獲取Arraylist最小容量 
private void ensureCapacityInternal(int minCapacity) {
        //如果原來的數(shù)組是空數(shù)組
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //minCapacity =(0+1) DEFAULT_CAPACITY默認(rèn)是10
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //先進(jìn)行數(shù)組的擴(kuò)容
        ensureExplicitCapacity(minCapacity);
}
//判斷是否滿足擴(kuò)容條件
private void ensureExplicitCapacity(int minCapacity) {
      //擴(kuò)容次數(shù)
        modCount++;
      //對(duì)數(shù)組的最小容量和ArrayList存放對(duì)象的數(shù)組長(zhǎng)度進(jìn)行比較
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}
//進(jìn)行數(shù)組擴(kuò)容
private void grow(int minCapacity) {
        //的到ArrayList的長(zhǎng)度
        int oldCapacity = elementData.length;
        //新的數(shù)組長(zhǎng)度=原始長(zhǎng)度+原始長(zhǎng)度/2 右移一位就相當(dāng)于除以2的一次方
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //處理數(shù)組長(zhǎng)度溢出 
            newCapacity = hugeCapacity(minCapacity);
        //對(duì)數(shù)組長(zhǎng)度進(jìn)行一次深拷貝
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
//這里并不會(huì)到MAX_ARRAY_SIZE,這個(gè)值取決于虛擬機(jī)內(nèi)存
 private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

關(guān)于add(E e)總結(jié)

1. 確保數(shù)組已使用長(zhǎng)度（size）加1后可以存入下一個(gè)元素诉儒。
2. 修改次數(shù)modCount標(biāo)識(shí)自增1桑滩，如果當(dāng)前數(shù)組已使用長(zhǎng)度+1后大于當(dāng)前數(shù)組長(zhǎng)度，則調(diào)用grow()方法允睹，擴(kuò)容數(shù)組运准，grow()會(huì)將當(dāng)前數(shù)組的長(zhǎng)度變?yōu)樵瓉砣萘康?.5倍
3. 確保新加的元素有地方存儲(chǔ)后，則將新元素添加到位于size++的位置上缭受。
4. 返回添加成功的布爾值胁澳。

• void add(int index, E element);

  //指定位置添加數(shù)據(jù)
public void add(int index, E element) {
        //step1: 索引檢測(cè)
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //step2:判斷是否需要擴(kuò)容
        ensureCapacityInternal(size + 1);  
        //step3:對(duì)源數(shù)組進(jìn)行復(fù)制處理（位移），從index + 1到size - index
        System.arraycopy(elementData, index, elementData, index + 1,size - index);
        //step4:數(shù)組指定的位置進(jìn)行賦值
        elementData[index] = element;
        size++;
    }

• boolean addAll(Collection<? extends E> c);

 public boolean addAll(Collection<? extends E> c) {
        //把Collection對(duì)象轉(zhuǎn)為數(shù)組
        Object[] a = c.toArray();
        //得到數(shù)組長(zhǎng)度
        int numNew = a.length;
        //擴(kuò)容檢測(cè)
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //對(duì)源數(shù)組進(jìn)行復(fù)制處理 從原數(shù)組的末尾進(jìn)行追加
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

• boolean addAll(Collection<? extends E> c);

public boolean addAll(int index, Collection<? extends E> c) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew); 
        //得到需要移動(dòng)到的位置
        int numMoved = size - index;
        //將當(dāng)前索引等于index和大于index的元素往后移numMoved個(gè)位置
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        //將數(shù)組添加到列表尾部
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

• E set(int index, E element);

public E set(int index, E element) {
    //判斷插入位置是否正確米者，如果大于列表長(zhǎng)度會(huì)拋出異常
    if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //獲取插入位置的當(dāng)前元素
        E oldValue = elementData(index);
        //將新的元素替換當(dāng)前插入位置的元素
        elementData[index] = element;
        //返回插入位置老的值
        return oldValue;
    }

刪除元素

• boolean remove(Object o);

//刪除對(duì)象
public boolean remove(Object o) {
        //空對(duì)象
        if (o == null) {
            //遍歷出所有的的null
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    //刪除這個(gè)元素
                    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 fastRemove(int index) {
        modCount++;
        //得到被刪除元素的位置
        int numMoved = size - index - 1;
        if (numMoved > 0)
            //如果不是最后一個(gè)位置將刪除位置后的元素向左移numMoved個(gè)位置進(jìn)行復(fù)制
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //置空最后一個(gè)位置元素
        elementData[--size] = null; 
 }

• E remove(int index);

public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //擴(kuò)充++
        modCount++;
        //得到原數(shù)組
        E oldValue = (E) elementData[index];
        //得到移除元素后的位置
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        //將元素最后一個(gè)位置置空
        elementData[--size] = null; 
        return oldValue;
    }

• boolean removeAll(Collection<?> c);

 //刪除傳遞過來的對(duì)象 
public boolean removeAll(Collection<?> c) {
        //判斷傳遞的對(duì)象是否為空
        Objects.requireNonNull(c);
        //刪除對(duì)象
        return batchRemove(c, false);
    }
//保留傳遞對(duì)來的對(duì)象,如果ArrayList中有這個(gè)對(duì)象之外的數(shù)據(jù)將會(huì)被刪除
public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        //保留對(duì)象刪除
        return batchRemove(c, true);
    }
//進(jìn)行批量刪除
 private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            //遍歷數(shù)組韭畸，并檢查這個(gè)集合是否包含對(duì)應(yīng)的值宇智，移動(dòng)要保留的值到數(shù)組前面，w最后值為要保留的元素的數(shù)量
            //若保留胰丁，就將相同的元素移動(dòng)到前段随橘；不刪除，就將不同元素移動(dòng)到前段
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // 確保異常拋出前的部分可以完成期望的操作锦庸，而被遍歷的部分會(huì)被接到后面
            //r不等于size表示可能出錯(cuò)了
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
              //如果w等于size机蔗，表示全部元素都保留了，所以也就沒有刪除操作發(fā)生甘萧，所以會(huì)返回false萝嘁；反之，返true扬卷，并更改數(shù)組
            //而w不等于size的時(shí)候牙言，即使try塊拋出異常，也能正確處理異常拋出前的操作怪得，因?yàn)閣始終為要保留的前段部分的長(zhǎng)度咱枉，數(shù)組也不會(huì)因此亂序
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

關(guān)于iterator遍歷ArrayList

public Iterator<E> iterator() {
        return new Itr();
    }
 private class Itr implements Iterator<E> {
     ...
         public E next() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            int i = cursor;
            if (i >= limit)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
         ...
 }

一般的話，調(diào)用完iterator之后徒恋，我們會(huì)使用iterator做遍歷庞钢，這里使用next做遍歷的時(shí)候有個(gè)需要注意的地方，就是調(diào)用next的時(shí)候因谎，可能會(huì)引發(fā)ConcurrentModificationException基括，當(dāng)修改次數(shù)，與期望的修改次數(shù)（調(diào)用iterator方法時(shí)候的修改次數(shù)）不一致的時(shí)候财岔，會(huì)發(fā)生該異常风皿，

expectedModCount這個(gè)值是在用戶調(diào)用ArrayList的iterator方法時(shí)候確定的，但是在這之后用戶add匠璧，或者remove了ArrayList的元素桐款，那么modCount就會(huì)改變，那么這個(gè)值就會(huì)不相等夷恍，將會(huì)引發(fā)ConcurrentModificationException異常魔眨，這個(gè)是在多線程使用情況下，比較常見的一個(gè)異常酿雪。

解決辦法

• 多線程中使用Iterator來遍歷時(shí)候,可以在線程中給ArrayList加一個(gè)同步鎖,鎖住ArrayList來保證modCount變量的同步

• 使用CopyOnWriteArrayList本質(zhì)上是對(duì)array數(shù)組的一個(gè)封裝遏暴，一旦CopyOnWriteArrayList對(duì)象發(fā)生任何的修改都會(huì)new一個(gè)新的Object[]數(shù)組newElement，在newElement數(shù)組上執(zhí)行修改操作指黎，修改完成后將newElement賦值給array數(shù)組（array=newElement）朋凉。因?yàn)?code>array是volatile的，因此它的修改對(duì)所有線程都可見

 //CopyOnWriteArrayList
private transient volatile Object[] array;
//ArrayList
transient Object[] elementData; 

<a id="url1">

為什么說ArrayList線程不安全

</a>
在給ArrayList添加數(shù)據(jù)的時(shí)候有一段代碼elementData[size++] = e; 賦值的過程可以分為兩個(gè)步驟1.elementData[size] = e; 2.size++;我們分別使用兩個(gè)線程來模擬插入過程.例如有兩個(gè)線程,分別加入數(shù)字1與2.這里會(huì)出現(xiàn)三種情況

• 輸出值為null; 此處導(dǎo)致了某些值為null的問題.因?yàn)樵?code>size=1, 但是因?yàn)榫€程1與線程2都將值賦值給了element[1],導(dǎo)致了element[2]內(nèi)沒有值,被跳過了.指針index指向了3.所以,導(dǎo)致了某些情況下值為null的情況

• 數(shù)組越界異常;

  • 線程1 賦值 element[1] = 1; 隨后因?yàn)闀r(shí)間片用完而中斷;

  • 線程2 賦值 element[1] = 2; 隨后因?yàn)闀r(shí)間片用完中斷;

• 某些線程沒有輸出值

  • 線程1 自增 size++; (size=2)

  • 線程2 自增 size++; (size=3)

解決方案

• 使用Vector類進(jìn)行替換

• 使用Collections.synchronizedList(List)

• 使用CopyOnWriteArrayList

總結(jié)

1. ArrayList自己實(shí)現(xiàn)了序列化和反序列化醋安，因?yàn)樗鼘?shí)現(xiàn)了writeObject和readObject方法杂彭。

2. ArrayList基于數(shù)組實(shí)現(xiàn)墓毒，會(huì)自動(dòng)擴(kuò)容。

3. 添加元素時(shí)會(huì)自己判斷是否需要擴(kuò)容亲怠，最好指定一個(gè)大概的大小所计，防止后面多次擴(kuò)容帶來的內(nèi)存消耗；刪除元素時(shí)不會(huì)減少容量团秽，刪除元素時(shí)主胧，將刪除掉的位置元素置為null，下次gc就會(huì)自動(dòng)回收這些元素所占的空間徙垫。

4. ArrayList是線程不安全的。

5. 使用iterator遍歷可能會(huì)引發(fā)多線程異常

transient關(guān)鍵字