ArrayList相信大家都用過，那么今天就來聊聊ArrayList。

概述

ArrayList是一個相對來說比較簡單的數(shù)據(jù)結(jié)構(gòu)，底層是用數(shù)組實現(xiàn)的，它和數(shù)組最大的區(qū)別就是可以自動擴(kuò)容，即我們可以認(rèn)為ArrayList就是一個動態(tài)數(shù)組。

ArrayList 允許空值和重復(fù)元素，ArrayList 是非線程安全類，并發(fā)環(huán)境下，多個線程同時操作 ArrayList，會引發(fā)不可預(yù)知的錯誤。

源碼分析

構(gòu)造方法

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //transient 修飾，不參與序列化
    transient Object[] elementData;
    
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

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

ArrayList 有兩種構(gòu)造方法，一種有參，一種無參。邏輯都很簡單，目的就是初始化底層的數(shù)組elementData。默認(rèn)的構(gòu)造方法會初始化一個空的數(shù)組。

增加元素

    public boolean add(E e) {
        //檢查是否需要擴(kuò)容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //添加元素到末尾
        elementData[size++] = e;
        return true;
    }
    
    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++;
    }

add方法有兩種，一種是直接添加元素到末尾，一種是添加到指定位置。兩種步驟差不多，就是第二種會有一個將元素整體位移的操作。（第二種效率肯定較低，在大集合中應(yīng)該盡量避免調(diào)用）

從上面代碼中不難看出，擴(kuò)容的操作是在ensureCapacityInternal方法中完成的，那么我們來看看擴(kuò)容的具體過程。

    private static final int DEFAULT_CAPACITY = 10;
    
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    //邊界檢查，保證最小容量 >10 
    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);
    }
    
    //擴(kuò)容的核心方法
    private void grow(int minCapacity) {
    
        int oldCapacity = elementData.length;
        //擴(kuò)容為原來的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //仍然不夠就直接擴(kuò)容為需求值
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            // 如果最小容量超過 MAX_ARRAY_SIZE，則將數(shù)組容量擴(kuò)容至 Integer.MAX_VALUE
            newCapacity = hugeCapacity(minCapacity);
        
        //產(chǎn)生新的數(shù)組，并復(fù)制原有數(shù)組到新數(shù)組
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

代碼雖然不短，但是大部分操作都是邊界檢查。擴(kuò)容的核心方法是grow方法。它計算出新的容器大小（即newCapacity），并確保了newCapacity不會比minCapacity小，最后調(diào)用Arrays.copyOf()創(chuàng)建一個新的數(shù)組并將數(shù)據(jù)拷貝到新數(shù)組中，最后讓elementData進(jìn)行引用。默認(rèn)的擴(kuò)容大小是當(dāng)前數(shù)組大小的一半，即擴(kuò)容至當(dāng)前容量的1.5倍。

刪除元素

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

刪除操作也不是很復(fù)雜，就直接將刪除元素后面的所有元素向前移一位，這樣目標(biāo)元素就會被覆蓋，然后把最后的那個元素置空，同時將size變量減1。

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

remove方法還有另一種，用要刪除的Object作為參數(shù)。這種就是從前往后遍歷整個數(shù)組，找到第一個和目標(biāo)相等的對象，然后執(zhí)行刪除操作，刪除的過程和指定位置刪除沒有區(qū)別。如果刪除了元素會返回true，該元素不存在則返回false。

查詢及修改

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

        return elementData(index);
    }

get方法，直接返回目標(biāo)元素。

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

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

set方法，直接修改目標(biāo)元素。

總結(jié)

ArrayList是我們常用的集合類型，底層由數(shù)組實現(xiàn)，方法都非常簡單。在用無參構(gòu)造方法創(chuàng)建時會創(chuàng)建一個空數(shù)組，直到有元素放入后才會擴(kuò)容為10。默認(rèn)擴(kuò)容為原來的1.5倍，如果1.5倍仍不夠，則會直接擴(kuò)容到目標(biāo)值。由于擴(kuò)容操作會將原數(shù)組拷貝到創(chuàng)建出的新數(shù)組中，因此開銷較大，應(yīng)盡量在初始化時設(shè)置好數(shù)組的容量。

由于底層為數(shù)組實現(xiàn)，隨機(jī)讀寫開銷小，因此ArrayList適用于存儲訪問頻繁，但增刪較少的數(shù)據(jù)。