在我們的日常開發(fā)中，集合類是我們基本上每個人都會用經(jīng)常用到的東西，用著用著，突然有一天我心生好奇，那么java集合類的這些源碼是什么呢？那么我打算接下來一個一個的查看一些常用的類源碼爭取達到心中有數(shù)的水平~~本文源碼均來自Java 8

總體介紹

Collection接口是集合類的根接口，Java中沒有提供這個接口的直接的實現(xiàn)類。Set和List兩個類繼承于它。Set中不能包含重復(fù)的元素，也沒有順序來存放。而List是一個有序的集合，可以包含重復(fù)的元素。

而Map又是另一個接口，它和Collection接口沒有關(guān)系。Map包含了key-value鍵值對，同一個Map里key是不能重復(fù)的，而不同key的value是可以相同的。

在這里借用一張別人總結(jié)的對比圖進行總結(jié)

集合類對比

成員變量

首先我們來看看ArrayList的成員變量：

 /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
     * DEFAULT_CAPACITY when the first element is added.
     *
     * Package private to allow access from java.util.Collections.
     */
    transient Object[] elementData;

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

可以看到主要的幾個成員變量如上(跟進繼承的父類，父父類直到根父類都沒有成員變量)。我們來一一介紹一下。首先是一個常量DEFAULT_CAPACITY，根據(jù)注釋表示默認的長度為10。然后是一個EMPTY_ELEMENTDATA的常量object數(shù)組，只是空有其表沒有內(nèi)容。然后是一個object數(shù)組elementData。這個就是最重要的成員了，通過注釋我們可以看到這表示這個數(shù)組用來存儲我們的數(shù)據(jù)。也就是說，我們代碼中的add的數(shù)據(jù)都會放在這個數(shù)組里面。那么由此我們可知，ArrayList內(nèi)部是由數(shù)組實現(xiàn)。再看最后一個變量，int類型的size。第一眼還以為是elementData數(shù)組的長度。仔細看注釋，才發(fā)現(xiàn)它表示的是elementData數(shù)組里面包含的數(shù)據(jù)長度。

構(gòu)造函數(shù)

介紹完了成員變量，我們來看看構(gòu)造方法：

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

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

我們看到主要有三個構(gòu)造方法。

第一個構(gòu)造方法需要傳入一個int類型的變量。表示我們實例化一個ArrayList的時候想讓ArrayList的初始化長度為多少。然后如果該變量大于0，那么new一個長度為傳入值的對象數(shù)組。如果傳入為0，那么等于EMPTY_ELEMENTDATA。這個變量我們上面講過，就是實例化一個對象數(shù)組，內(nèi)容為空。如果小于0，那么拋出異常。

第二個構(gòu)造方法是無參構(gòu)造方法，直接等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA。沒有其他的好說的。

第三個則我們另外一種常見的使用方法，比如處理化AList的時候想把BList的值傳給AList。那么使用如下代碼：

List<Integer> AList = new ArrayList<>(BList);

我們看看構(gòu)造函數(shù)做了什么。我們看到首先調(diào)用了c.toArray()方法將我們傳入的集合元素變成一個數(shù)組來賦值給elementData數(shù)組。然后判斷elementData數(shù)組里面是否有數(shù)據(jù)元素，如果有，那么再判斷elementData數(shù)組類型是否為Object[]，不是的話，轉(zhuǎn)為Object[]類型。如果沒有元素，那么直接賦值為EMPTY_ELEMENTDATA。

至此三個構(gòu)造方法就已經(jīng)分析完了，基本上沒有什么難度。

常見方法

接下來我們來分析一些ArrayList的常見方法。

size()

  public int size() {
        return size;
    }

很簡單，就是將elementData數(shù)組中元素個數(shù)返回。

isEmpty()

 public boolean isEmpty() {
        return size == 0;
    }

也很簡單，就是判斷sizes是否等于0，即elementData數(shù)組中是否有元素。

add()

我們先來看add(E e) 方法：

 public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

可以看到add()方法還是比較簡短的，接下面我們一步一步的分析,第一行是調(diào)用了一個方法，第二行是常見的數(shù)組賦值，將下標為size處的數(shù)組元素賦值為e，然后size自加1。如果有意識的話，會想到，咦？這么做的話，不怕數(shù)組越界？？那么我們?nèi)サ谝恍写a的方法里看看：

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

首先第一個方法中先判斷elementData是否是沒有元素的數(shù)組(但并不是elemetData為null)。如果是，那么取我們傳入的值(也就是size + 1)和默認的數(shù)組長度(長度為10)中的最大值。然后調(diào)用了ensureExplicitCapacity()方法。我們繼續(xù)看這個方法：

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

首先是一個int類型的成員變量modCount自加，這個變量是ArrayList的父類AbstractList的一個成員，用來表示List的修改次數(shù)。接下來有一個判斷，用傳入的值減去當(dāng)前elementData的長度，如果大于0，調(diào)用grow()方法(我個人理解為擴展的意思)，這里其實也能猜出大概意思。如果我們所需的最小數(shù)組長度已經(jīng)比當(dāng)前數(shù)組長度大了，那么就需要我們擴展數(shù)組了。我們接著看grow()方法:

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

我們接著看代碼，首先保存當(dāng)前數(shù)組長度到oldCapacity，然后定義一個newCapacity，新長度為舊長度的3/2,也就是增加一半的容量。然后用新長度減去所需最小長度，如果小于0，意味著新長度比所需長度還要小，那么就直接將新長度改為所需最小長度。然后新長度如果超過了允許的數(shù)組最大長度，調(diào)用hugeCapacity()方法進行調(diào)整。最后處理完畢后，調(diào)用Arrays.copyOf()方法賦值給elementData。至此就把elementData數(shù)組擴展完畢。然后回到add方法中直接賦值 elementData[size++] = e即可。
我們來看第二個add()方法:

public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

上面的方法也是我們常用的，將指定的下標處元素賦值為我們設(shè)定的值。最開始我用這個方法的時候一直很擔(dān)心假設(shè)我把指定位置設(shè)置了值，那原來的值會不會被覆蓋呢？

我們看一下實現(xiàn)代碼解惑一下，也很簡單。首先檢查index索引是否比elementData中擁有元素的數(shù)量大或者小于0。有問題則拋出異常。負責(zé)又調(diào)用ensureCapacityInternal()方法來確認數(shù)組長度是否足夠。然后調(diào)用System.arraycopy()方法，我們來看看：

 public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

可以看到是個native方法，我們就不跟源碼了，看看參數(shù)含義就明白了。src就是源數(shù)組，srcPos就是表明從源數(shù)組的下標多少開始復(fù)制，dest和destPos就是對應(yīng)的目的數(shù)組，復(fù)制源數(shù)組的數(shù)據(jù)到從目的數(shù)組的下標開始存放，length就是打算復(fù)制多少個源數(shù)組的值。說了半天有點繞口，看看上面的調(diào)用例子，我們用具體例子來講解。首先源數(shù)組是elementData，假設(shè)有6個元素(即size為6，但是elementData的長度大于6)，index假設(shè)為3，length為size - index為3。而dest也為elementData，destPos為index + 1 等于4。所以整體就是從index(3)下標處即elementData[3]處開始往后拿3個值，復(fù)制到elementDatadestPos開始往后3個值。

其實解釋了半天就是將我們要插入的位置開始的元素全部往后移了一個位置。然后把值插入到指定的位置。（我真聰明）所以之前的擔(dān)心就多余啦。我們插入到指定位置，指定位置的舊值會往后移，并不會被覆蓋。

clear

    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

clear()方法也很簡單，首先modCount自加，表示我們對list進行了操作。然后for循環(huán)置空即可，最后設(shè)置size等于0。

remove()

remove()也有兩個方法，我們來看第一個：

   public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) 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;
    }

根據(jù)傳入?yún)?shù)我們也能猜到意思，就是移除指定下標的元素。
首先還是檢查index是否有效。然后modCount++,表示我們對list又進行一次操作。然后將指定下標的元素取出。然后計算出我們需要移動多少個元素，指的是從刪除位置往后的元素，不包括刪除位置的元素。如果個數(shù)大于0，那么調(diào)用 System.arraycopy()方法將刪除位置后的一個元素開始到最后的元素往前移動一個位置。然后將size立馬自減，然后將最后一個位置置為null(因為元素往前移動一位，那么最后一個元素往前移后，原來的最后一個位置值還存在沒有被覆蓋)。
最后返回舊的刪除位置的元素值。

接下來我們來看第二個remove()方法：

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

很明顯看參數(shù)也猜得出是直接移除掉我們某個元素。首先判斷我們傳入的object是否為空，如果為空，那么就for循環(huán)找到第一個數(shù)組中值為null的元素，調(diào)用fastRemove()方法，我們?nèi)タ纯矗?/p>

 /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    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()方法的簡化版，取消了越界檢查，并且設(shè)置返回類型為void，不再返回刪除的舊值。這里就不再分析。

接著上面說，如果remove()中如果傳入的對象不為null，那么就是for循環(huán)找到這個值然后移除即可。整個函數(shù)返回類型為boolean，true表示有這個對象刪除成功。沒有表示數(shù)組里沒有這個對象，沒有進行刪除操作。

contains()

public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

contains()也是我們經(jīng)常使用的方法，用來查詢當(dāng)前ArrayList是否包含某個對象。我們看調(diào)用了一個indexOf()方法然后把返回值和0進行比較(乍一看還是很奇怪的，返回布爾值不好嗎)，我們來看看indexOf()方法：

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

我們來看看代碼，首先是對傳入對象的判空。如果對象為空，還是一樣的，for循環(huán)來查找elementData中第一個為null的元素，然后返回下標。如果傳入對象不為空，那么一樣for循環(huán)查找第一個匹配元素，然后返回第一個匹配元素的下標。如果都找不到，那么就返回-1。

看完這個方法，就明白了為啥不用返回值布爾類型了，原來是返回下標來和0進行判斷是否包含。但是我們可以看到其實contains()方法并沒有返回元素下標。所以本人第一次看完代碼覺得這是多此一舉。后來突然想到indexOf()方法是一個public方法，也是我們經(jīng)常使用的方法?？赡芫驮谶@里java編寫者進行方法重用就不必再重復(fù)寫新方法來判斷。順帶著我們就把indexOf()方法介紹，方法就是返回第一個匹配傳入對象的元素下標。如果數(shù)組中沒有匹配元素那么返回-1。

get()

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

        return elementData(index);
    }

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

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

這個方法可以說是最最常用的方法了，但是其實我們看到非常簡單，就是進行一個下標的越界判斷，然后返回elementData[index]元素。

set()

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

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

set方法也是，其實set(int index, E element)和add(int index, E element)方法很相似。只是set是將指定位置的值直接覆蓋掉，而add()則是將指定位置開始的元素往后全部后移一位，舊值不會被覆蓋掉。set()方法沒有什么可以多分析的代碼。

至此我們常見的ArrayList的方法源碼分析就已經(jīng)完了，其他的一些方法要么不怎么用，要么非常簡單只有一兩行簡單代碼，讀者一跟進去就能明白。

最后我們再來總結(jié)一下：

• 首先ArrayList內(nèi)部是由數(shù)組來實現(xiàn)的。而且在存放數(shù)據(jù)的數(shù)組長度不夠時，會進行擴容，即增加數(shù)組長度。在Java 8中是默認擴展為原來的1.5倍。
• 既然是數(shù)組，那么優(yōu)點就是查找某個元素很快?？梢酝ㄟ^下標查找元素，查找效率高。但是由此也看出缺點，每次刪除元素，都會進行大量的數(shù)組元素移動，復(fù)制新的數(shù)組等等。增加元素的話如果長度不夠，還要進行擴容。因此刪除效率低。如果我們在實際開發(fā)中能夠清楚知道我們的數(shù)據(jù)量，建議創(chuàng)建ArrayList的時候指定長度，這樣無需頻繁增加數(shù)據(jù)時不斷進行擴容。