一、集合的大體架構(gòu)圖

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

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

二、List

1.ArrayList和Vector的區(qū)別

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

   （PS:標黑色的部分，估計學(xué)過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.空參構(gòu)造,其內(nèi)部數(shù)據(jù)數(shù)組的大小為10，并且它的標準容量增量為零
     */
    public Vector() {
        this(10);
    }

   第二句話：Vector大部分方法的底層實現(xiàn),都加了 synchronized關(guān)鍵字，所以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時，發(fā)現(xiàn)Vector有4個構(gòu)造方法，比 ArrayList多了一個。而多的這個構(gòu)造方法，是跟擴容有關(guān)的。ArrayList默認的擴容，在JDK1.6時，是按照新容量 =（原容量*3）/2+1來計算的，大約50%左右；而在JDK1.7以后，是按照新容量 = 原容量 +（原容量 >> 1）來計算的，大約也在50%左右，所以都不是很多資料上說的就是50%,同時由于位運算的速度比快，所以ArrayList在JDK1.7之后效率更高，也可以看出來，；而在Vector中，默認情況下，是100%增長的，但是我們可以通過比ArrayList多的那個構(gòu)造方法，來指定它增容的大小。

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是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)，它繼承于AbstractSequentialList的雙向鏈表，由于AbstractSequentialList 實現(xiàn)了get(i)、set()、add() 和 remove()這些骨干性函數(shù)，這也降低了List接口的復(fù)雜程度。

LinkedList源碼片段：

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

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

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

第三句話：對于隨機訪問get和set，ArrayList絕對優(yōu)于LinkedList，因為從源碼可以看出，ArrayList想要get(int index)元素時，直接返回index位置上的元素；而LinkedList需要通過for循環(huán)進行查找，雖然LinkedList已經(jīng)在查找方法上做了優(yōu)化，比如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()方法會調(diào)用node()方法，
}
//node()方法需要循環(huán)遍歷查找索引;
    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循環(huán)找到index，然后直接插入或刪除。這就導(dǎo)致了兩者并非一定誰快誰慢！

具體情況，可參看如下測試數(shù)據(jù)（數(shù)據(jù)來源于網(wǎng)絡(luò)）：

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

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