摘要：畢業(yè)兩個星期了，開始成為一名正式的碼農(nóng)了。將指定位置的數(shù)據(jù)移除。但是問題是，為時，并不是直接一個大小為的數(shù)組，而是使用靜態(tài)變量來代替。此外，函數(shù)還做了越界檢查。返回迭代器，與之有一個搭配的輔助類。

畢業(yè)兩個星期了，開始成為一名正式的java碼農(nóng)了。
一直對偏底層比較感興趣，想著深入自己的java技能，看書、讀源碼、總結(jié)、造輪子實踐都是付諸行動的方法。
說到看源碼，就應(yīng)該由簡入難，逐漸加深，那就從jdk的源碼開始看起吧。

ArrayList和Vector是java標(biāo)準(zhǔn)庫提供的一種比較簡單的數(shù)據(jù)結(jié)構(gòu)，也是最常用的一種。

表這種抽象概念指的是一種存放數(shù)據(jù)的容器，其中數(shù)據(jù)A1, A2, A3, ..., A_i, ... A_N有序排列。

那么在表這一抽象的數(shù)據(jù)結(jié)構(gòu)模型中：

數(shù)據(jù)是有序排列的，有前后之分。

表中每個數(shù)據(jù)都有一個索引，A1元素的索引為0, A_i元素的索引為i - 1。至于索引從0開始還是從1開始編號這個不是重點。

表的大小為即為數(shù)據(jù)的個數(shù)，即N。

它的操作有：

獲取表的大小。

取出表中給定索引的數(shù)據(jù)。

給表中給定索引的位置放入數(shù)據(jù)。

向指定位置插入數(shù)據(jù)。

將指定位置的數(shù)據(jù)移除。

表有兩種實現(xiàn)方式，數(shù)組實現(xiàn)和鏈表實現(xiàn)。這兩種實現(xiàn)方式各有優(yōu)劣，其中這里所說的ArrayList是數(shù)組實現(xiàn)方式。

線性表的實現(xiàn)中是將元素放到數(shù)組中的。如果是C的數(shù)組，那其實是一塊連續(xù)的內(nèi)存。
在java中也是java的原生數(shù)組，內(nèi)存布局中邏輯上是連續(xù)的，物理上不一定。印象中有的jvm實現(xiàn)為了解決內(nèi)存碎片搞類似邏輯內(nèi)存的這種操作。

往線性表取出數(shù)據(jù)或拿出元素都能很直接對應(yīng)到原生數(shù)組中去。
但是，線性表插入數(shù)據(jù)的這一操作要求表是能夠動態(tài)增長的，但是原生數(shù)組的大小是固定的。

線性表實現(xiàn)的一大重點是實現(xiàn)表動態(tài)增長這一要求，將其轉(zhuǎn)換、化歸到固定大小的原生數(shù)據(jù)上去。思路是，當(dāng)線性表內(nèi)部保存數(shù)據(jù)的數(shù)組如果不夠用了，就申請一個更大的數(shù)組，將原來數(shù)組的數(shù)據(jù)拷貝進去。

由于線性表用數(shù)組實現(xiàn)，因此定位元素實際上只需要計算內(nèi)存偏移量即可訪問得到，取出和放入元素的時間復(fù)雜度為O(1)。

由于數(shù)組中的元素是緊密排列的，因此在中間插入一個元素或移除一個元素需要移動后面一排數(shù)據(jù)，所以往指定位置插入或移除數(shù)據(jù)的平均時間復(fù)雜度為O(n)。

如果是往表末尾插入元素，情況比較復(fù)雜因為這可能觸發(fā)擴容操作。不觸發(fā)擴容就是O(1)，如果觸發(fā)了擴容，假設(shè)是2倍擴容，我們可以把擴容的時間均攤到前面每一個元素的插入操作上，平均來說，也是O(1)。

如上圖所示，在設(shè)計上，它的結(jié)構(gòu)應(yīng)該理解成 ArrayList --> List --> Collection --> Iterable：

List接口表示抽象的表，也就是上面所說的表。

Collection接口表示抽象的容器，能放元素的都算。

Iterable接口表示可迭代的對象。也即該容器內(nèi)的元素都能夠通過迭代器迭代。

但是在繼承結(jié)構(gòu)上，ArrayList繼承了AbstractList。這是java中通用的一種技巧，由于java8之前的接口無法指定默認(rèn)方法，如果你要實現(xiàn)List接口，你需要實現(xiàn)其中的所有方法。
但是，List接口中的所有方法是大而全的，有大量方法是為了方便調(diào)用者使用而設(shè)計的衍生方法，并非實現(xiàn)該接口的必須方法。比如說，isEmpty方法就可以化歸到size方法上。
所以，java對于List接口會提供一個AbstractList抽象類，里面提供了部分方法的默認(rèn)實現(xiàn)，而繼承該類的只需要實現(xiàn)一組最小的必須方法即可。
總而言之一句話，AbstractList的作用是給List接口提供某些方法的默認(rèn)實現(xiàn)。

先看ArrayList內(nèi)部保存的屬性和狀態(tài)。

    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData; // non-private to simplify nested class access
    private int size;

其中，最關(guān)鍵的為elementData和size。 elementData也即真正存儲元素的java原生數(shù)組。
由于ArrayList中實際保存的元素個數(shù)是少于elementData數(shù)組的大小的，也即會有部分空間的浪費，因此size屬性是用來保存ArrayList存儲的元素個數(shù)。

值得注意的是，elementData沒有訪問修飾符，我們知道默認(rèn)是對包內(nèi)可見的。這樣做的目的是：

即能保證使用者（包外）無法訪問到這個屬性，保證了數(shù)據(jù)隱藏；

另外一方面，實現(xiàn)ArrayList需要一些輔助作用的嵌套類，它們需要知道部分ArrayList的實現(xiàn)細(xì)節(jié)。由于它們和ArrayList在同一個包下，這樣輔助類能夠訪問到它們。

構(gòu)造函數(shù)一共有三個，下面是其中兩個。第三個是從其它容器初始化，沒什么好看的地方。

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

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

第一個帶參數(shù)的構(gòu)造函數(shù)，行為上這個都知道，創(chuàng)建出來的依然是個空表，看代碼也可發(fā)現(xiàn)執(zhí)行完后size屬性為0。initialCapacity的含義是指定內(nèi)部存儲數(shù)據(jù)的原生數(shù)組的初始化大小。
代碼邏輯很簡單，initialCapacity大于0時對elementData分配該大小的原生數(shù)組。但是問題是，initialCapacity為0時，并不是直接new一個大小為0的數(shù)組，而是使用靜態(tài)變量EMPTY_ELEMENTDATA來代替。
為什么？EMPTY_ELEMENTDATA是靜態(tài)變量，所有實例共享，個人猜測應(yīng)該是為了省點內(nèi)存吧?？墒沁@個占不了多大的內(nèi)存啊，這個理由可能說服力不太強。

第二個默認(rèn)構(gòu)造函數(shù)，這個函數(shù)行為上也是創(chuàng)建空表。但是會預(yù)先將存儲數(shù)據(jù)的原生數(shù)組的大小設(shè)置為DEFAULT_CAPACITY，也就是默認(rèn)值10。這樣，能避免在大小較小時頻繁擴容帶來性能損耗。

按照這個思路，代碼應(yīng)該長這樣才對：

    public ArrayList() {
        this.elementData = new Object[DEFAULT_CAPACITY];
    }

但是實際上，我們發(fā)現(xiàn)DEFAULTCAPACITY_EMPTY_ELEMENTDATA其實是個空表，也是靜態(tài)變量，多實例共享的。
這實際上也可以認(rèn)為是一種優(yōu)化手段，因為很多場景都是直接默認(rèn)構(gòu)造的一個空表在哪里放著，為了節(jié)約內(nèi)存，jdk實現(xiàn)先不實際分配空間，僅僅做一個類似標(biāo)記作用的操作，之后真正使用了才會分配空間，達(dá)到一個類似“延遲分配”的效果。這些思路在擴容相關(guān)的代碼中有所體現(xiàn)。

get和set沒什么好說的，實際上是直接操作內(nèi)部的原生數(shù)組。
不過，從下面的代碼中可以看到，在get和set之前，會做越界檢查。

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

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

        return elementData(index);
    }

    E elementData(int index) {
        return (E) elementData[index];
    }

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

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

下面再來看插入元素。插入有兩種：

第一種是在末尾插入。

第二種是在中間插入。

    public boolean add(E e) {
        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++;
    }

    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

思路都特別顯然，主要是在操作之前，調(diào)用了ensureCapacityInternal函數(shù)，這個函數(shù)調(diào)用完畢后會保證內(nèi)部數(shù)組的空間能存儲下這么多元素。
此外，void add(int, E)函數(shù)還做了越界檢查。

接下來看ensureCapacityInternal函數(shù)，相關(guān)實現(xiàn)涉及到四個函數(shù)。
這個函數(shù)的目的是保證執(zhí)行完后，內(nèi)部的原生數(shù)組至少能容納minCapacity個元素。
之前所說的那種“延遲分配”操作在這里就體現(xiàn)出來了。分析代碼流程不難發(fā)現(xiàn)，當(dāng)elementData為DEFAULTCAPACITY_EMPTY_ELEMENTDATA，也即前面所說到的那個標(biāo)記，那么之后擴容后的原生數(shù)組空間一定不小于DEFAULT_CAPACITY，也就是前面定義處的10。

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_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;
    }

再看具體的擴容邏輯，也即grow函數(shù)。邏輯還不單一。首先擴容嘗試按照原來大小的1.5倍擴容，為了性能，這里除以2優(yōu)化成了右移運算。
如果1.5倍不夠怎么辦？如果是我，我可能會優(yōu)雅的遞歸再擴大，然而，jdk的做法是如果1.5倍不夠的話直接按照需要的大小擴容。
最后，如果實在太大，也要做一下限制，最大可達(dá)到的大小為Integer.MAX_VALUE，否則就超過了int的范圍，溢出了。

下面是移除相關(guān)的函數(shù)，有兩個：

E remove(int)是通過索引移除。

boolean remove(Object)是通過元素移除。

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

按索引移除的的思路很簡單，首先把需要移除的元素拿出來，然后后面的都往前挪一個，通過數(shù)據(jù)拷貝實現(xiàn)。
但是，有個 特別需要注意的地方是，假設(shè)刪除之后的表大小為N，往前挪一個后，elementData[N - 1]和elementData[N]都指向了最后一個元素。這時elementData[N]仍然持有對該元素的引用。如果之后試圖移除表中最后一個元素，它可能不會及時的被gc干掉，造成無意義的額外內(nèi)存占用。

按元素移除的思路也很顯然，先是找到該元素的索引，然后按索引移除。fastRemove的代碼幾乎和remove(int)一模一樣，不知道為什么復(fù)用一下。。。

最后，從代碼可以看到一點，表內(nèi)元素會被移除，但是jdk對ArrayList的實現(xiàn)只會擴容表，而不會縮小表以減小內(nèi)存占用。不過，它提供了一個trimToSize方法，將表中原生數(shù)組的空閑空間去掉：

    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

很明顯，它重新分配一個正好合適的原生數(shù)組，然后拷貝過去。

這兩個函數(shù)很好理解：

removeAll是移除所有c中的元素

retainAll是保留所有c中的元素

這兩個函數(shù)算法幾乎一模一樣，因此抽象出一個函數(shù)batchRemove來實現(xiàn)。

    public boolean removeAll(Collection c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

    public boolean retainAll(Collection c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }

    private boolean batchRemove(Collection c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

核心在于try中的那三行代碼。這個算法簡化了就是這樣：

有兩個數(shù)組data和isRemove，isRemove[i]為true表示data[i]應(yīng)該被移除。
要求在O(n)時間復(fù)雜度，O(1)空間復(fù)雜度，將data中isRemove[i]為true的元素移除。

算法這種東西，思路我能在腦子里想象出來畫面，但是說不清楚。。。 大學(xué)里學(xué)習(xí)算法時候都寫過，就不多說了。

感覺寫的有點多。。。以上是和ArrayList操作密切相關(guān)的，其它的簡單總結(jié)下吧。

subList. subList返回的是一個List，代表著該ArrayList的中間一段。這個subList實際上返回的是類似視圖的對象，它本身不存儲數(shù)據(jù)，所有的對subList的操作最終會反映到原來的那個ArrayList上來。實現(xiàn)在輔助類SubList中。

iterator. 返回迭代器，與之有一個搭配的輔助類Itr?；径际且恍┌b代碼。

sort. 排序是通過調(diào)用Arrays.sort實現(xiàn)的，所以，具體的排序算法要看Arrays.sort。

還有一個沒有看懂的問題，即在AbstractList中有一個modCount字段，ArrayList的實現(xiàn)中多次操作該字段。但是仍然沒有理解該字段的作用。

Vector提供的容器模型和ArrayList幾乎一模一樣，只不過它是線程安全的。
它的代碼思路上和ArrayList差不多，但是有一些實現(xiàn)細(xì)節(jié)上的小區(qū)別。

首先，它有一個參數(shù)capacityIncrement，能夠控制擴容的細(xì)節(jié)，看構(gòu)造函數(shù)：

    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

如果不指定的話，這個initialCapacity默認(rèn)值為0。在內(nèi)部使用屬性capacityIncrement保存。

其次，再看控制擴容的核心函數(shù)grow，研究下擴容邏輯是不是有什么差異:

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

可以發(fā)現(xiàn)，capacityIncrement控制的是擴容的步長。
如果沒有指定步長，那么則是按照兩倍擴容，這是與ArrayList不同的地方。

總體上，它相當(dāng)于synchronized同步過的ArrayList，也即它對線程安全的實現(xiàn)非常暴力，并未用到太多的技巧。很顯然，在并發(fā)環(huán)境下，對vector的操作直接鎖住整個vector，相當(dāng)于操作vector的線程是串行操作vector，性能不高。