“工欲善其事，必先利其器”。Java 容器就是我們開發(fā)中的利器。

然而，之前在開發(fā)中使用僅僅是容器的一小部分。這次從源碼的角度進(jìn)行深入的理解，一點(diǎn)總結(jié)分享給大家。

這里只列舉了非阻塞式的容器；阻塞式的容器，會(huì)在后面的并發(fā)篇補(bǔ)。

如果有什么理解不對(duì)的地方，歡迎大家在評(píng)論中指正～

ArrayList

實(shí)現(xiàn)： 數(shù)組實(shí)現(xiàn)

線程安全： 非線性安全，fail-fast 機(jī)制保護(hù)

容量： 初始容量為10；隨后每次增加都會(huì)變成之前的1.5倍(批量添加除外)。源碼如下：

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 這里是擴(kuò)容的關(guān)鍵
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 批量添加，也有可能會(huì)直接等于相加之后的容量
    if(newCapacity - minCapacity < 0) newCapacity = minCapacity;
    if(newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

效率：

除了模型中的操作外還有一些特殊的操作：

// 縮小容器的容量到元素的數(shù)量
public void trimToSize();
// 確保容量能覆蓋 minCapacity 個(gè)元素
public synchronized void ensureCapacity(int minCapacity) ;

Vector

實(shí)現(xiàn)： 數(shù)組

線程安全： 是；fast-fail 保護(hù)

容量： 初始容量為10；根據(jù)指定的擴(kuò)容數(shù)量或者*2(批量添加除外)；核心代碼：

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // capacityIncrement 是構(gòu)造函數(shù)中指定的值, 默認(rèn)為0
    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);
}

效率：

效率與ArrayList相似，但是每一個(gè)操作都需要獲取鎖，時(shí)間開銷要比ArrayList大。

Stack

實(shí)現(xiàn)： Vector

線程安全： 是；fast-fail保護(hù)

容量： 同Vector

效率：

LinkedList

實(shí)現(xiàn)： 雙指針鏈表

線程安全：否；fast-fail保護(hù)

容量： 有size()；無容量

效率：

作為 List 來說：

作為 Queue 來說：

作為 Deque 來說：

PriorityQueue

特征： 容器中元素的 出順序 不是元素的 插入順序，而是一個(gè)大小順序中的最值。

實(shí)現(xiàn)方式： 小頂堆

線程安全： 否；fail-fast保護(hù)

容量： 默認(rèn)初始容量11；容量小的時(shí)候*2，容量大的時(shí)候+50%。核心代碼如下：

private void grow(int minCapacity) {
int oldCapacity = queue.length;
// 小于64的時(shí)候增倍；大于64的時(shí)候增加50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1));
if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
// queue是存放元素的數(shù)組
queue = Arrays.copyOf(queue, newCapacity);

效率：

如果只是用到確定數(shù)量個(gè)元素的情況下，它是比列表排序的效率要高的。隨機(jī)數(shù)列的排序平均都要O(n*log(n))了，而它最高的復(fù)雜度僅為O(log(n))

但是，如果所有元素都要遍歷一次取出來，那效率與就跟堆排序是一樣的O(n*log(n))。

HashSet

特征： 高效率的集合容器

實(shí)現(xiàn)： HashMap

線程安全： 否；failfast保護(hù)

容量： 同HashMap

效率：同HashMap

LinkedHashSet

特征： 高效率的集合容器，能保存插入順序

實(shí)現(xiàn)：LinkedHashMap

線程安全：否； failfast保護(hù)

容量： 同LinkedHashMap

效率： 同LinkedHashMap

TreeSet

特征： 帶全排序的集合容器

實(shí)現(xiàn)：TreeMap

線程安全：否；failfast保護(hù)

容量：無

效率：同TreeMap

HashMap

特征：高效率的映射表

實(shí)現(xiàn)： 開散列

線程安全：否；fail-fast保護(hù)

是否支持null： 是

容量： 默認(rèn)初始容量16；容量總是2的冪；默認(rèn)加載因子0.75；擴(kuò)容后的容量由當(dāng)前容量和加載因子決定，這里的擴(kuò)容代碼不是很直接，需要聯(lián)系幾個(gè)方法來看：

// 添加一組映射的時(shí)候
void addEntry(int hash, K key, V value, int bucketIndex) {
    // 容量超過threshold并且對(duì)應(yīng)的hash值存在在沖突的時(shí)候，開始擴(kuò)容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 擴(kuò)展為之前的2倍
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

// 這個(gè)方法的作用在于將數(shù)組擴(kuò)展到相應(yīng)的容量，
// 并把原數(shù)組中的元素全部重新計(jì)算位置，轉(zhuǎn)移到新數(shù)組中
// 重新計(jì)算下一個(gè)threshold
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

// 這個(gè)方法在容器第一次添加元素的時(shí)候調(diào)用，使用toSize做參數(shù)的目的是避免第一次添加元素的時(shí)候多次擴(kuò)容
private void inflateTable(int toSize) {
    int capacity = roundUpToPowerOf2(toSize);
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

效率：

LinkedHashMap

特征： 在HashMap的基礎(chǔ)上添加了，特定規(guī)則的順序保存

實(shí)現(xiàn)：開散列 + 雙指針鏈表環(huán)

線程安全： 否；fast-fail保護(hù)

是否支持null： 是

容量： 同HashMap

特征：它在HashMap的基礎(chǔ)上，對(duì)Entry的封裝中加了兩個(gè)指針記錄順序。也就是說，這里既有散列保證隨機(jī)訪問效率，又有鏈表記錄順序。

這里的順序不是指大小順序。而是插入順序，或者訪問次數(shù)的順序。所以它可以用來做LRU緩存容器，不過在此之前需要對(duì)他做一些封裝，需要定義緩存的體積和重寫一些方法：

//這里的accessOrder要設(shè)置為true
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
}
// 緩存容量
private static final int MAX_ENTRIES = 100;
// 設(shè)置為超容量即刪除
protected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > MAX_ENTRIES;
}

TreeMap

特征： 全排序的映射表

實(shí)現(xiàn)：紅黑樹

線程安全： 否，fastfail保護(hù)

是否支持null：是

容量：無

特征：訪問的時(shí)候根據(jù)二叉查找樹來查找，插入，刪除的時(shí)候需要根據(jù)紅黑樹的規(guī)則來平衡樹。

效率：

Hashtable

特征：線程安全的高效映射表

實(shí)現(xiàn)： 開散列

線程安全： 是；fail-fast保護(hù)

是否支持null：否

容量：默認(rèn)初始容量11；加載因子0.75；由加載因子決定擴(kuò)容時(shí)機(jī)，默認(rèn)size超過容量的0.75需要擴(kuò)容。核心代碼如下：

public synchronized V put(K key, V value) {
    // ...
    // 容器中元素?cái)?shù)量超過threshold時(shí)，擴(kuò)容并重新計(jì)算hash，然后再添加元素
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();
        tab = table;
        hash = hash(key);
        index = (hash & 0x7FFFFFFF) % tab.length;
    }
    // ...
}

protected void rehash() {
    int oldCapacity = table.length;
    Entry<K,V>[] oldMap = table;
    // 新容量是舊容量的2倍
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<K,V>[] newMap = new Entry[newCapacity];
    modCount++;
    // 這里計(jì)算新的閾值
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    boolean rehash = initHashSeedAsNeeded(newCapacity);
    table = newMap;
    // 然后重新計(jì)算hash對(duì)應(yīng)的位置
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;
            if (rehash) {
                e.hash = hash(e.key);
            }
            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = newMap[index];
            newMap[index] = e;
        }
    }
}

效率：

WeakHashMap

特征：
它的Map.Entry類設(shè)計(jì)的比較特殊繼承了弱引用類。key是作為弱引用持有的對(duì)象。這意味著容器中的對(duì)象在沒有外部引用持有的時(shí)候隨時(shí)都有可能被GC回收。所以它可以被用來做緩存。

    private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
        V value;
        int hash;
        Entry<K,V> next;

        /**
         * Creates new entry.
         */
        Entry(Object key, V value,
              ReferenceQueue<Object> queue,
              int hash, Entry<K,V> next) {
            // key是弱引用持有的對(duì)象
            super(key, queue);
            this.value = value;
            this.hash  = hash;
            this.next  = next;
        }
    }

實(shí)現(xiàn)： 開散列 + WeakReference + ReferenceQueue

線程安全： 否； fast-fail保護(hù)

是否支持null：是

容量：默認(rèn)初始容量16；默認(rèn)加載因子0.75；容量總是2的冪，每次擴(kuò)容都*2；如果在擴(kuò)容過程中發(fā)現(xiàn)大量的元素被回收，可能會(huì)終止擴(kuò)容，繼續(xù)使用之前的容量。核心代碼如下：

public V put(K key, V value) {
    // ...
    tab[i] = new Entry<>(k, value, queue, h, e);
    if (++size >= threshold)
        resize(tab.length * 2);
}

void resize(int newCapacity) {
    Entry<K,V>[] oldTable = getTable();
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry<K,V>[] newTable = newTable(newCapacity);
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;
    transfer(oldTable, newTable, rehash);
    table = newTable;
    /*
     * 如果在擴(kuò)容過程中刪除的元素非常的多，填充數(shù)不到閾值的一半的時(shí)候
     * 使用回之前容量的數(shù)組
     */
    if (size >= threshold / 2) {
        threshold = (int)(newCapacity * loadFactor);
    } else {
        expungeStaleEntries();
        transfer(newTable, oldTable, false);
        table = oldTable;
    }
}

/** Transfers all entries from src to dest tables */
private void transfer(Entry<K,V>[] src, Entry<K,V>[] dest, boolean rehash) {
    for (int j = 0; j < src.length; ++j) {
        Entry<K,V> e = src[j];
        src[j] = null;
        while (e != null) {
            Entry<K,V> next = e.next;
            Object key = e.get();
            // 注意，這里在轉(zhuǎn)移元素的過程中會(huì)刪除一些已經(jīng)被垃圾回收的元素
            if (key == null) {
                e.next = null;  // Help GC
                e.value = null; //  "   "
                size--;
            } else {
                if (rehash) {
                    e.hash = hash(key);
                }
                int i = indexFor(e.hash, dest.length);
                e.next = dest[i];
                dest[i] = e;
            }
            e = next;
        }
    }
}

效率：

IdentityHashMap

特征： 使用“引用相等”而非equals相等。只有兩個(gè) key 完全是同一個(gè)對(duì)象的時(shí)候才判定為相等。

實(shí)現(xiàn)： 閉散列；沒有用Map.Entry類，數(shù)組偶數(shù)位置放 key，奇數(shù)位置放 value

線程安全： 否；fast-fail保護(hù)

是否支持null：是

容量：默認(rèn)初始容量32；加載因子2/3；容量一定為2的冪；核心代碼：

    public V put(K key, V value) {
        // ...
        // 超過閾值，擴(kuò)容
        if (++size >= threshold)
            resize(len); // len == 2 * current capacity.
        // ...
    }

    private void resize(int newCapacity) {
        // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
        // 原容量*2
        int newLength = newCapacity * 2;

        Object[] oldTable = table;
        int oldLength = oldTable.length;
        // 這里重新計(jì)算閾值
        if (oldLength == 2*MAXIMUM_CAPACITY) { // can't expand any further
            if (threshold == MAXIMUM_CAPACITY-1)
                throw new IllegalStateException("Capacity exhausted.");
            threshold = MAXIMUM_CAPACITY-1;  // Gigantic map!
            return;
        }
        if (oldLength >= newLength)
            return;

        Object[] newTable = new Object[newLength];
        threshold = newLength / 3;
        // 重新計(jì)算位置， 由于這是閉散列，需要對(duì)所有元素重新計(jì)算
        for (int j = 0; j < oldLength; j += 2) {
            Object key = oldTable[j];
            if (key != null) {
                Object value = oldTable[j+1];
                oldTable[j] = null;
                oldTable[j+1] = null;
                int i = hash(key, newLength);
                while (newTable[i] != null)
                    i = nextKeyIndex(i, newLength);
                newTable[i] = key;
                newTable[i + 1] = value;
            }
        }
        table = newTable;
    }

效率：