文章首發(fā)csdn博客地址：https://blog.csdn.net/u013277209?viewmode=contents

前言

本篇作為吃透Java集合系列第三篇笛臣，我們來(lái)看一下ArrayList个曙，通過(guò)本篇我們要明白如下問(wèn)題：
1茬底、ArrayList擴(kuò)容機(jī)制
2钠龙、ArrayList迭代器實(shí)現(xiàn)
3吹缔、fail-fast機(jī)制
4捺信、ArrayList序列化反序列化機(jī)制
5岳瞭、ArrayList clone實(shí)現(xiàn)

ArrayList內(nèi)部是使用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的狂票，換句話說(shuō)候齿，ArrayList封裝了對(duì)內(nèi)部數(shù)組的操作，比如向數(shù)組中添加闺属、刪除慌盯、插入新的元素或者數(shù)據(jù)的擴(kuò)展和重定向。

• 繼承了AbstractList,此類提供 List 接口的骨干實(shí)現(xiàn)掂器，以最大限度地減少實(shí)現(xiàn)”隨機(jī)訪問(wèn)”數(shù)據(jù)存儲(chǔ)（如數(shù)組）支持的該接口所需的工作.對(duì)于連續(xù)的訪問(wèn)數(shù)據(jù)（如鏈表）亚皂，應(yīng)優(yōu)先使用 AbstractSequentialList，而不是此類国瓮。
• 實(shí)現(xiàn)了List接口,意味著ArrayList元素是有序的,可以重復(fù)的,可以有null元素的集合.
• 實(shí)現(xiàn)了RandomAccess接口標(biāo)識(shí)著其支持隨機(jī)快速訪問(wèn),實(shí)際上,我們查看RandomAccess源碼可以看到,其實(shí)里面什么都沒(méi)有定義.因?yàn)锳rrayList底層是數(shù)組,那么隨機(jī)快速訪問(wèn)是理所當(dāng)然的,訪問(wèn)速度O(1)灭必。
• 實(shí)現(xiàn)了Cloneable接口,標(biāo)識(shí)著可以它可以被復(fù)制.注意,ArrayList里面的clone()復(fù)制其實(shí)是淺復(fù)制匠楚。
• 實(shí)現(xiàn)了Serializable 標(biāo)識(shí)著集合可被序列化。

一：ArrayList擴(kuò)容機(jī)制

初始化：
ArrayList提供了三個(gè)構(gòu)造函數(shù)來(lái)對(duì)elementData數(shù)組初始化：
無(wú)參構(gòu)造函數(shù)：初始化一個(gè)空的數(shù)組厂财，添加元素時(shí)再對(duì)數(shù)組elementData擴(kuò)容芋簿。
指定容量的構(gòu)造函數(shù)：直接初始化數(shù)組為指定的大小。
帶有一個(gè)集合參數(shù)的構(gòu)造函數(shù)：把指定集合中的數(shù)據(jù)通過(guò)Arrays.copyOf拷貝到elementData中璃饱，容量和指定集合容量相同与斤。

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
//無(wú)參構(gòu)造函數(shù)直接賦值一個(gè)空的數(shù)組
 public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }
//指定大小的構(gòu)造函數(shù)
public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
//構(gòu)造一個(gè)包含指定*集合的元素的列表。
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

擴(kuò)容：
添加元素時(shí)使用 ensureCapacityInternal() 方法來(lái)保證容量足夠荚恶，如果不夠時(shí)撩穿，需要使用 grow() 方法進(jìn)行擴(kuò)容，新容量的大小為 oldCapacity + (oldCapacity >> 1)谒撼，也就是舊容量的 1.5 倍食寡。

擴(kuò)容操作需要調(diào)用 Arrays.copyOf() 把原數(shù)組整個(gè)復(fù)制到新數(shù)組中，這個(gè)操作代價(jià)很高廓潜，因此最好在創(chuàng)建 ArrayList 對(duì)象時(shí)就指定大概的容量大小抵皱，減少擴(kuò)容操作的次數(shù)。

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

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

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(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);
    }
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

二：ArrayList迭代器實(shí)現(xiàn)

如果對(duì)Iterable和Iterator接口不是很清楚的辩蛋，請(qǐng)先移步到第一篇文章：
吃透Java集合系列一：Iterable和Iterator
ArrayList通過(guò)內(nèi)部類實(shí)現(xiàn)Iterator接口來(lái)實(shí)例化迭代器類呻畸，通過(guò)Iterator我們可以實(shí)現(xiàn)對(duì)elementData中的元素迭代遍歷。而ArrayList又實(shí)現(xiàn)了一種功能更為強(qiáng)大的ListIterator來(lái)實(shí)現(xiàn)迭代遍歷悼院。ListIterator繼承于Iterator接口伤为，對(duì)Iterator接口做了擴(kuò)展，支持向前向后遍歷据途、迭代過(guò)程中去修改集合等

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;

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

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

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

private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

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

        public void set(E e) {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.set(lastRet, e);
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        public void add(E e) {
            checkForComodification();

            try {
                int i = cursor;
                ArrayList.this.add(i, e);
                cursor = i + 1;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    }

三： Fail-Fast機(jī)制

modCount 用來(lái)記錄 ArrayList 結(jié)構(gòu)發(fā)生變化的次數(shù)绞愚。結(jié)構(gòu)發(fā)生變化是指添加或者刪除至少一個(gè)元素的所有操作，或者是調(diào)整內(nèi)部數(shù)組的大小颖医，僅僅只是設(shè)置元素的值不算結(jié)構(gòu)發(fā)生變化位衩。

在進(jìn)行序列化或者迭代等操作時(shí)，需要比較操作前后 modCount 是否改變便脊，如果改變了需要拋出 ConcurrentModificationException蚂四。如下例子

public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
        Iterator<Integer> iterator = list.listIterator();
        while (iterator.hasNext()) {
            Integer i = iterator.next();
            if (i == 1) {
                list.remove(i);
            }
        }
    }

運(yùn)行后會(huì)拋出異常：

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:886)
    at java.util.ArrayList$Itr.next(ArrayList.java:836)
    at MyTest.main(MyTest.java:12)

當(dāng)我們調(diào)用list.remove的方法來(lái)刪除元素后，此時(shí)modCount會(huì)+1哪痰，導(dǎo)致modCount和迭代器里面的expectedModCount 不相等遂赠，當(dāng)遍歷下一個(gè)元素調(diào)用next方法時(shí)，會(huì)先調(diào)用checkForComodification()方法晌杰，當(dāng)expectedModCount跷睦！=modCount時(shí)會(huì)拋出ConcurrentModificationException，這就是Fail-Fast機(jī)制肋演。

那我們要如何避免此問(wèn)題呢抑诸？Iterator已經(jīng)為我們提供了remove方法烂琴，所以我們只需要調(diào)用迭代器里面的remove方法就可以了，Iterator中的remove方法移除元素后會(huì)把modCount重寫賦值給expectedModCount蜕乡，下一個(gè)循環(huán)時(shí)expectedModCount與modCount相等就避免此問(wèn)題奸绷。如下例子：

public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
        Iterator<Integer> iterator = list.listIterator();
        while (iterator.hasNext()) {
            Integer i = iterator.next();
            if (i == 1) {
                iterator.remove();
            }
        }
    }

四： ArrayList序列化機(jī)制

我們看到ArrayList實(shí)現(xiàn)了Serializable接口，那么證明可以是被序列化的层玲，但是elementData數(shù)組又被transient關(guān)鍵字修飾号醉，我們知道被transient修飾的成員屬性變量不被序列化，那么我們先看一個(gè)例子辛块，ArrayList是否能被序列化成功呢畔派？

public static void main(String[] args) throws IOException, ClassNotFoundException {
        List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
        ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
        ObjectOutputStream objectOutputStream = new ObjectOutputStream(byteArrayOutputStream);
        objectOutputStream.writeObject(list);

        ByteArrayInputStream byteArrayInputStream = new ByteArrayInputStream(byteArrayOutputStream.toByteArray());
        ObjectInputStream objectInputStream = new ObjectInputStream(byteArrayInputStream);
        List<Integer> newList = (List<Integer>) objectInputStream.readObject();
        System.out.println(Arrays.toString(newList.toArray()));
    }

運(yùn)行輸出結(jié)果：

[1, 2, 3]

結(jié)果是序列化和反序列化成功？润绵？這是為什么呢线椰？
其實(shí)細(xì)心的我們?cè)诓榭丛创a時(shí)發(fā)現(xiàn)，ArrayList重寫了readObject和writeObject來(lái)自定義的序列化和反序列化策略尘盼。什么是自定義序列化和反序列化呢憨愉？

• 在序列化過(guò)程中，如果被序列化的類中定義了writeObject 和 readObject 方法悔叽，虛擬機(jī)會(huì)試圖調(diào)用對(duì)象類里的 writeObject 和 readObject 方法莱衩，進(jìn)行用戶自定義的序列化和反序列化爵嗅。
• 如果沒(méi)有這樣的方法娇澎，則默認(rèn)調(diào)用是 ObjectOutputStream 的 defaultWriteObject 方法以及 ObjectInputStream 的 defaultReadObject 方法。
• 用戶自定義的 writeObject 和 readObject 方法可以允許用戶控制序列化的過(guò)程睹晒，比如可以在序列化的過(guò)程中動(dòng)態(tài)改變序列化的數(shù)值趟庄。

那么我們來(lái)看一下ArrayList源碼是怎么來(lái)自定義序列化和反序列化的：

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }
private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

可以看到通過(guò)writeObject方法和readObject方法來(lái)遍歷elementData數(shù)組把數(shù)組中的元素寫入ObjectOutputStream ，ObjectInputStream 中的伪很。那么為什么ArrayList要用這種方式來(lái)實(shí)現(xiàn)序列化呢戚啥？

ArrayList實(shí)際上是動(dòng)態(tài)數(shù)組，每次在放滿以后自動(dòng)增長(zhǎng)設(shè)定的長(zhǎng)度值锉试，如果數(shù)組自動(dòng)增長(zhǎng)長(zhǎng)度設(shè)為100猫十，而實(shí)際只放了一個(gè)元素，那就會(huì)序列化99個(gè)null元素呆盖。為了保證在序列化的時(shí)候不會(huì)將這么多null同時(shí)進(jìn)行序列化拖云，ArrayList把元素?cái)?shù)組設(shè)置為transient。

五： ArrayList clone機(jī)制

ArrayList的clone實(shí)現(xiàn)应又，其實(shí)是通過(guò)數(shù)組元素拷貝來(lái)實(shí)現(xiàn)的淺拷貝宙项，很簡(jiǎn)單，我們看一下源碼就行了：

public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }