一、集合的大體架構圖

希望大家能牢牢記住下面這張框架圖，一旦面試官讓你“說說集合吧”，希望大家能立馬給他畫出來，邊畫邊逐一介紹每個集合的特點，以及彼此的差異。重點是要從底層源代碼的角度來給面試官分析。

一說到底層代碼，可能很多人就頭疼了，總認為知道和不知道對開發根本沒多大實用價值，會應用就行了。這個觀點，我暫不做評論。但是大家很慶幸的是，看到了本篇博客，博主將會帶大家，來分析一些在面試中一定會用到的集合底層實現原理。

二、List

1.ArrayList和Vector的區別

第一句話：ArrayList和Vector底層都是數組實現的，初始容量都為10；在ArrayList的底層，是通過定義一個DEFAULT_CAPACITY的常量來指定的，而Vector的底層，是直接在空參構造中，通過寫死了一個this(10)來指定的；

   （PS:標黑色的部分，估計學過Java的人都會說，人云亦云，但是你要是在面試中，說出了后面標紅的部分，雖然意思一樣，但是，你這樣一講，絕對瞬間提升了一個檔次，立馬就能夠脫穎而出。后面的解析同理：黑色是眾人皆知的常識，紅色字體才是精髓）

ArrayList源碼片段：

    /**
     * Default initial capacity.默認初始容量
     */
private static final int DEFAULT_CAPACITY = 10;=

Vector源碼片段：

   /**
     * Constructs an empty vector so that its internal data array
     * has size {@code 10} and its standard capacity increment is
     * zero.空參構造,其內部數據數組的大小為10，并且它的標準容量增量為零
     */
    public Vector() {
        this(10);
    }

   第二句話：Vector大部分方法的底層實現,都加了 synchronized關鍵字，所以Vector是線程同步的，而 ArrayList不是；

Vector源碼片段：

   /**
     * Returns the number of components in this vector.
     */
    public synchronized int size() {
        return elementCount;
    }
    /**
     * Tests if this vector has no components.
     */
    public synchronized boolean isEmpty() {
        return elementCount == 0;
    }

第三句話：在查看API時，發現Vector有4個構造方法，比 ArrayList多了一個。而多的這個構造方法，是跟擴容有關的。ArrayList默認的擴容，在JDK1.6時，是按照新容量 =（原容量*3）/2+1來計算的，大約50%左右；而在JDK1.7以后，是按照新容量 = 原容量 +（原容量 >> 1）來計算的，大約也在50%左右，所以都不是很多資料上說的就是50%,同時由于位運算的速度比快，所以ArrayList在JDK1.7之后效率更高，也可以看出來，；而在Vector中，默認情況下，是100%增長的，但是我們可以通過比ArrayList多的那個構造方法，來指定它增容的大小。

ArrayList源碼片段：

    /**
     * jdk1.6中：int newCapacity = (oldCapacity * 3)/2 + 1;
     */
    public void ensureCapacity(int minCapacity) {
     modCount++;
     int oldCapacity = elementData.length;
     if (minCapacity >oldCapacity) {
         Object oldData[] = elementData;
         int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity <minCapacity)
        newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
             elementData = Arrays.copyOf(elementData, newCapacity);
     }
    }

    /**
     * jdk1.7之后：int newCapacity = oldCapacity + (oldCapacity >> 1);
     */
    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);
    }

Vector源碼片段：

    /**
     * Vector中int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
     */  
    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);
    }

2.ArrayList與LinkedList

第一句話：ArrayList是實現了基于動態數組的數據結構，LinkedList基于鏈表的數據結構，它繼承于AbstractSequentialList的雙向鏈表，由于AbstractSequentialList 實現了get(i)、set()、add() 和 remove()這些骨干性函數，這也降低了List接口的復雜程度。

LinkedList源碼片段：

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

第二句話：ArrayList與LinkedList都是不是同步的。如果多個線程同時訪問一個鏈接列表，而其中至少一個線程從結構上修改了該列表，則它必須保持外部同步。同步的方法就是使用Collections.synchronizedList(Collection<T> c)來“包裝”該列表。

static <T> Collection<T>  synchronizedCollection(Collection<T> c) 
返回指定 collection 支持的同步（線程安全的）

第三句話：對于隨機訪問get和set，ArrayList絕對優于LinkedList，因為從源碼可以看出，ArrayList想要get(int index)元素時，直接返回index位置上的元素；而LinkedList需要通過for循環進行查找，雖然LinkedList已經在查找方法上做了優化，比如index < size / 2，則從左邊開始查找，反之從右邊開始查找，但是還是比ArrayList（隨機查找）要慢。

ArrayList源碼片段：

    public E get(int index) {
        rangeCheck(index); 
        checkForComodification();
        return ArrayList.this.elementData(offset +index); //直接返回索引
    }

LinkedList源碼片段：

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item; //get()方法會調用node()方法，
}
//node()方法需要循環遍歷查找索引;
    Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {  //加速機制
            Node<E> x = first;
            for (int i = 0;i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i =size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
}

第四句話：從源碼來看，ArrayList想要在指定位置插入或刪除元素時，主要耗時的是System.arraycopy動作，會移動index后面所有的元素；LinkedList主耗時的是要先通過for循環找到index，然后直接插入或刪除。這就導致了兩者并非一定誰快誰慢！

具體情況，可參看如下測試數據（數據來源于網絡）：

#在index=1000出插入結果：
  array time:4
  linked time:240
  array insert time:20
  linked insert time:18
#在index=5000處插入結果： 
  array time:4
  linked time:229
  array insert time:13
  linked insert time:90
#在index=9000處插入結果：
  array time:4
  linked time:237
  array insert time:7
  linked insert time:92

    所以，不是很多資料中說得那樣簡單：以為ArrayList查詢快，增刪慢，因為它是集合實現的，要改角標；而LinkedList是鏈表實現的，所以查詢慢，增刪快??！
         結論：當插入的數據量很小時，兩者區別不太大；當插入的數據量大時，大約在容量的1/10之前，LinkedList會優于ArrayList；在其后就完全劣于ArrayList，且越靠近后面越差。所以個人覺得，一般首選用ArrayList，因為LinkedList還可以實現棧、隊列以及雙端隊列等數據結構。