摘要：集合之吃透增刪查改從源碼看初始化以及增刪查改，學(xué)習(xí)。一初始化無(wú)參的構(gòu)造器可以看到這個(gè)構(gòu)造器初始化了一個(gè)空數(shù)組。指定長(zhǎng)度的構(gòu)造器這個(gè)構(gòu)造器顯式的指明了數(shù)組的長(zhǎng)度，其實(shí)如果小于的話，在添加第一個(gè)元素的時(shí)候還是會(huì)擴(kuò)充到長(zhǎng)度為的數(shù)組。

從源碼看初始化以及增刪查改，學(xué)習(xí)ArrayList。

先來(lái)看下ArrayList定義的幾個(gè)屬性：

private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;  // 保存對(duì)象
private int size; // ArrayList的長(zhǎng)度

從這里可以看到ArrayList內(nèi)部使用數(shù)組實(shí)現(xiàn)的。

1. ArrayList()

無(wú)參的構(gòu)造器：

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

可以看到這個(gè)構(gòu)造器初始化了一個(gè)空數(shù)組。這里有個(gè)疑問(wèn)，就是注釋明明說(shuō)是構(gòu)造了一個(gè)長(zhǎng)度為10的數(shù)組，其實(shí)這是在添加第一個(gè)元素的時(shí)候才進(jìn)行的擴(kuò)充。

2. ArrayList(int initialCapacity)

指定長(zhǎng)度的構(gòu)造器：

    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    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);
        }
    }

這個(gè)構(gòu)造器顯式的指明了數(shù)組的長(zhǎng)度，其實(shí)如果小于10的話，在添加第一個(gè)元素的時(shí)候還是會(huì)擴(kuò)充到長(zhǎng)度為10的數(shù)組。

1. add(E e)

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return true (as specified by {@link Collection#add})
     * 添加指定的元素到List的末尾
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 擴(kuò)充數(shù)組長(zhǎng)度
        elementData[size++] = e;           // 最后一個(gè)賦值為e
        return true;
    }

那么它是如何擴(kuò)充數(shù)組長(zhǎng)度的呢？追蹤代碼來(lái)到grow(int minCapacity)方法:

/*
* 可以看到它是通過(guò)Arrays.copyOf方法將原數(shù)組拷貝到了一個(gè)數(shù)組長(zhǎng)度為newCapacity的新數(shù)組里面
*/
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);
    }

2. add(int index, E element)

    /**
     * 在指定的位置添加一個(gè)元素
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index); // 檢查index是否合法

        ensureCapacityInternal(size + 1);  // 擴(kuò)充數(shù)組長(zhǎng)度
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);  // 通過(guò)拷貝返回一個(gè)新數(shù)組
        elementData[index] = element;
        size++;
    }

這里用到了System類的arraycopy方法，它的用法如下：

System. arraycopy(Object src, int srcPos, Object dest, int destPos,int length)

src：原數(shù)組；

srcPos：源數(shù)組要復(fù)制的起始位置；

dest：目標(biāo)數(shù)組；

destPos：目標(biāo)數(shù)組放置的起始位置；

length：復(fù)制的長(zhǎng)度

這個(gè)方法也可以實(shí)現(xiàn)自身的復(fù)制。上面的就是利用了自身賦值的特性進(jìn)行數(shù)組的拷貝。相當(dāng)于將index后面的所有元素后移了一位，將新元素插入到index位置。

1. remove(int index)

     /*
     * 和add(int index, E element)類似，使用System.arraycopy進(jìn)行自身拷貝，相當(dāng)于將index后面的元素
     * 像前移動(dòng)了一位，覆蓋掉需要?jiǎng)h除的元素，將最后一個(gè)元素置位null，等待JVM自動(dòng)回收
     */
    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;
    }

2. remove(Object o)

    /*
    * 先通過(guò)for循環(huán)找到o所在的位置，再通過(guò)fastRemove(index)移除，實(shí)現(xiàn)方法和remove(int index)一樣
    */
    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;
    }

    /*
    * 查找元素就比較簡(jiǎn)單了，直接通過(guò)數(shù)組的下角標(biāo)進(jìn)行返回
    */
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    /*
    * 修改元素也比較簡(jiǎn)單，直接通過(guò)數(shù)組的下角標(biāo)進(jìn)行賦值
    */
    public E set(int index, E element) {
        rangeCheck(index);

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

從源碼可以看到，ArrayList以數(shù)組方式實(shí)現(xiàn)，查找和修改的性能比較好，增加和刪除的性能就比較差了。