摘要：三系列用于保存鍵值對，無論是，還是已棄用的或者線程安全的等，都是基于紅黑樹。是完全基于紅黑樹的，并在此基礎(chǔ)上實現(xiàn)了接口?？梢钥吹?，只有紅黑樹，且紅黑樹是通過內(nèi)部類來實現(xiàn)的。

閱讀JDK源碼有段時間了，準備以博客的形式記錄下來，也方便復(fù)習(xí)時查閱，本文參考JDK1.8源碼。

Collection是所有容器的基類，定義了一些基礎(chǔ)方法。List、Set、Map、Queue等子接口都繼承于它，并根據(jù)各自特性添加了額外的方法。

ArrayList是使用頻率較高的容器，實現(xiàn)較為簡單。內(nèi)部主要靠一個可自動擴容的對象數(shù)組來維持，

transient Object[] elementData;

可以通過構(gòu)造函數(shù)指定數(shù)組的初始容量，也可以不指定，當(dāng)首次通過add加入元素時，會通過內(nèi)部擴容機制新建一個容量為10的數(shù)組（JDK1.7前在構(gòu)造函數(shù)中直接新建數(shù)組）：

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

從上面代碼可以看出，當(dāng)容量不夠時，ArrayList每次擴容1.5倍，然后將原對象數(shù)組中的元素拷貝至新的對象數(shù)組。Arrays.copyOf(Object[],int)方法先是根據(jù)傳入的新容量新建數(shù)組，然后將元素拷貝到新數(shù)組，拷貝操作是通過System.arrayCopy方法來完成的，這是native方法。這兩個方法在容器類中經(jīng)常使用，用以拷貝數(shù)組。

ArrayList支持指定位置的賦值，通過set(int,E)和add(int,E)方法，在執(zhí)行這些操作時都需要對范圍進行檢查，同理還有獲取和移除指定位置的元素。

上面發(fā)現(xiàn)elementData數(shù)組是transient的，這表明系統(tǒng)默認序列化執(zhí)行時跳過該數(shù)組。取而代之的是，ArrayList提供了writeObject和readObject方法來自定義寫入和讀取該數(shù)組的方式。

最后，作為容器類的共性，ArrayList實現(xiàn)了Iterable接口，并通過內(nèi)部類定義了Itr、ListItr這兩個迭代器。spliterator是為了并行遍歷，會在后面統(tǒng)一分析。

LinkedList其實與Arraylist有很多相似地方，只不過底層實現(xiàn)一個是通過數(shù)組，一個是通過鏈表而已。由于這兩種實現(xiàn)的不同，也導(dǎo)致的它們不同的使用場合。ArrayList是用數(shù)組實現(xiàn)的，那么在查的方面肯定優(yōu)于基于鏈表的LinkedList，與之相對的是LinkedList在增刪改上優(yōu)于ArrayList。
LinkedList的核心數(shù)據(jù)結(jié)構(gòu)如下：

transient Node first;
transient Node last;

private static class Node {
     E item;
     Node next;
     Node prev;

     Node(Node prev, E element, Node next) {
         this.item = element;
         this.next = next;
         this.prev = prev;
     }
}

可以看到，Node節(jié)點其實就是雙向鏈表，由于是用鏈表實現(xiàn)，自然不用考慮擴容，只需對其修改時更新節(jié)點即可。LinkedList方法大多是跟鏈表相關(guān)，選取addFirst分析一下：

public void addFirst(E e) {
    linkFirst(e);
}
private void linkFirst(E e) {
    final Node f = first;//用f保存之前頭節(jié)點
    final Node newNode = new Node<>(null, e, f);//以f作為后置節(jié)點創(chuàng)建新節(jié)點
    first = newNode;//將新節(jié)點作為頭節(jié)點
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;//將新節(jié)點設(shè)為f的前置節(jié)點
    size++;
    modCount++;
}

另外，LinkedList還有一些類似棧的操作函數(shù)：peek、pop、push(E)等。其他方法與ArrayList大同小異。

Vector就是在ArrayList的基礎(chǔ)上增加了同步機制，對可能改變?nèi)萜骷皟?nèi)部元素的方法都加了同步鎖，Vector的加鎖機制是用Synchronized。這樣雖然安全且方便，但Synchronized是重量級鎖，同步塊在已進入的線程執(zhí)行完之前會阻塞其他線程的進入，Java的線程是映射到操作系統(tǒng)原生線程上的，如果要阻塞或喚醒一個線程，都需要操作系統(tǒng)從用戶態(tài)轉(zhuǎn)為核心態(tài)，需要消耗很多處理器時間，甚至超過用戶代碼執(zhí)行時間。這點需要注意！

Stack繼承自Vector，在此基礎(chǔ)上添加了一些棧操作，也是加了同步的。

Map用于保存鍵值對，無論是HashMap，TreeMap還是已棄用的HashTable或者線程安全的ConcurrentHashMap等，都是基于紅黑樹。我們知道，JDK1.7以前的HashMap是基于數(shù)組加鏈表實現(xiàn)的，這樣一般情況下能有不錯的查找效率，但是當(dāng)hash沖突嚴重時，整個數(shù)組趨向一個單鏈表，這時查找的效率就會下降的很明顯，而紅黑樹通過其不錯的平衡性保證在hash沖突嚴重的情況下仍然又不錯的查找效率。這里優(yōu)先介紹一下紅黑樹，具體實現(xiàn)會多帶帶介紹。

紅黑樹是在普通二叉查找樹和AVL樹之間的平衡，既能保證不錯的平衡性，維護平衡的成本又比AVL低，定義如下：

性質(zhì)一：節(jié)點為紅色或者黑色；

性質(zhì)二：根節(jié)點是黑色；

性質(zhì)三：每個葉節(jié)點是黑色；

性質(zhì)四：每個紅色節(jié)點的兩個子節(jié)點都是黑色；

性質(zhì)五：從任一節(jié)點到其沒個葉節(jié)點的所有路徑都包含相同數(shù)目的黑色節(jié)點

紅黑樹是Map系列容器的底層實現(xiàn)細節(jié)，關(guān)于具體的對紅黑樹的操作在Map的分析中會涉及。

HashMap是很常用的Map結(jié)構(gòu)，JDK1.7是由Entry數(shù)組實現(xiàn)，JDK1.8改為Node數(shù)組加TreeNode紅黑樹結(jié)合實現(xiàn)。

static final class TreeNode extends LinkedHashMap.Entry {
    TreeNode parent;  // red-black tree links
    TreeNode left;
    TreeNode right;
    TreeNode prev;    // needed to unlink next upon deletion
    boolean red;
    ...
}
static class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next;
    ...
}

transient Node[] table;//Node數(shù)組
int threshold;//臨界值
final float loadFactor;//填充因子
transient int size;//元素個數(shù)

HashMap有四個重載的構(gòu)造函數(shù)：

public HashMap();
public HashMap(int initialCapacity);
public HashMap(int initialCapacity, float loadFactor);
public HashMap(Map m);

需要注意的是，傳入的initialCapacity并不是實際的初始容量，HashMap通過tableSize函數(shù)將initialCapacity調(diào)整為大于等于該值的最小2次冪

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;//確保第一次出現(xiàn)1的位及其后一位都是1
    n |= n >>> 2;//確保前兩次出現(xiàn)的1及其后兩位都是1
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

以此類推，最后能夠得到一個2的冪。剛開始減1是為了避免當(dāng)cap剛好等于2的整次冪時經(jīng)過調(diào)整會變成原來的2倍。

HashMap能夠擁有良好的性能很大程度依賴于它的擴容機制，從put方法放置元素開始分析整個擴容機制會比較清晰：

首先看一下hash函數(shù)，獲取key的hashCode，這個值與具體系統(tǒng)硬件有關(guān)，然后將hashCode值無符號右移16位后與原值異或得到hash值，這其實是簡化了JDK1.7的擾動函數(shù)。有興趣可以看一下JDK1.7的擾動函數(shù)。擾動函數(shù)是為了避免hashCode只取后幾位時碰撞嚴重，因為我們算數(shù)組的下標(biāo)時是用(n-1)&hash,一般情況下n不大，下標(biāo)值就是hashCode的后幾位，這時擾動函數(shù)就可以發(fā)揮作用。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

我們調(diào)用put函數(shù)往hashMap里填充元素時，會調(diào)用putVal函數(shù)，會有以下幾種情況：

數(shù)組為空則新建數(shù)組；

判斷table[i]首個元素是否為空，是則直接插入新節(jié)點；

如果對應(yīng)位置存在節(jié)點，判斷首個元素是否和key一樣，是則覆蓋value；

如果首節(jié)點為TreeNode，則直接在紅黑樹中插入鍵值對；

否則遍歷鏈表，如果存在節(jié)點與key相等，那么退出循環(huán)，為對應(yīng)鍵賦值，否則在鏈表后添加一個節(jié)點，判斷鏈表長度是否超過臨界值，是則轉(zhuǎn)為紅黑樹；

插入完成后判斷是否擴容。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node[] tab; Node p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)//數(shù)組為空新建數(shù)組
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)//table[i]為空直接插入新節(jié)點
        tab[i] = newNode(hash, key, value, null);
    else {
        Node e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))//對應(yīng)位置首個節(jié)點key相同
            e = p;
        else if (p instanceof TreeNode)//首節(jié)點為TreeNode，直接在紅黑樹中插入
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        else {//遍歷鏈表，插入后判斷是否擴容
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

數(shù)組為空時新建數(shù)組調(diào)用了resize方法，resize方法其實包括兩個部分，建立新數(shù)組和移動元素到新數(shù)組:

final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {//數(shù)組已存在，不為空
        if (oldCap >= MAXIMUM_CAPACITY) {//容量已經(jīng)超過最大值時，不會再改動數(shù)組，只會調(diào)整臨界值
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&//擴容兩倍
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) //只有臨界值時，將臨界值設(shè)為數(shù)組容量
        newCap = oldThr;
    else {//否則使用默認值              
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //計算新的臨界值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    //新建Node數(shù)組
        Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    
    //將舊數(shù)組元素填充至新數(shù)組
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)//該位置鏈表只有一個節(jié)點，計算下標(biāo)并移至新數(shù)組
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)//該位置為紅黑樹，則通過樹操作分解至新數(shù)組
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                else { // 將鏈表分為兩部分整體位移至新數(shù)組
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                        //新的下標(biāo)值等于舊的下標(biāo)值的元素
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                        //新的下標(biāo)值等于舊的下標(biāo)值加oldCap的元素
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    //對兩條鏈的整體移動
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

最后整體移動至新數(shù)組是JDk1.8對resize的優(yōu)化。因為我們每次擴容是原來容量的兩倍，那么每次計算得到的下標(biāo)hash&(newCap-1)會有一定規(guī)律，因為newCap-1比oldCap多了一個高的1位，因此新的下標(biāo)要么等于舊的下標(biāo)，要么等于舊的下標(biāo)加上oldCap，取決于hash值對應(yīng)位是0還是1，即e.hash&oldCap是0還是1.

接下來看一下hashMap中的紅黑樹操作,hashMap中的紅黑樹操作還是很多的，這里以上面插入節(jié)點后鏈表長度超過8時轉(zhuǎn)為紅黑樹調(diào)用的treeify方法為例：

final void treeifyBin(Node[] tab, int hash) {
    int n, index; Node e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {//首節(jié)點不為空，樹化
        TreeNode hd = null, tl = null;//頭尾節(jié)點
        do {
            //用樹節(jié)點代替鏈表節(jié)點
            TreeNode p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        //頭節(jié)點不為空轉(zhuǎn)為紅黑樹
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

treeify函數(shù)是一個雙層循環(huán)，外層循環(huán)從首節(jié)點開始遍歷所有節(jié)點，如果紅黑樹根節(jié)點為空，將當(dāng)前節(jié)點設(shè)為根節(jié)點；否則進入內(nèi)層循環(huán)，內(nèi)層循環(huán)類似二叉查找樹的插入，通過比較hash值的大小逐層尋找新節(jié)點的插入位置，這里有個細節(jié)需要注意：

//當(dāng)節(jié)點的鍵沒有實現(xiàn)Comparable接口，或者兩個鍵通過conpareTo比較相等的時候，通過tieBreakOrder來比較大小，tieBreakOrder本質(zhì)上比較hashCode。
else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||
         (dir = compareComparables(kc, k, pk)) == 0)
    dir = tieBreakOrder(k, pk);

插入完成后會調(diào)用balanceInsertion來保證紅黑樹的平衡性：

static  TreeNode balanceInsertion(TreeNode root,
                                            TreeNode x) {
    //新插入節(jié)點默認為紅節(jié)點
    x.red = true;
    for (TreeNode xp, xpp, xppl, xppr;;) {
        //x即為根節(jié)點
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
    //x為根節(jié)點的子節(jié)點或者父節(jié)點為黑節(jié)點
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
    //父節(jié)點為祖父節(jié)點的左孩子
        if (xp == (xppl = xpp.left)) {
            //叔節(jié)點為紅節(jié)點
            if ((xppr = xpp.right) != null && xppr.red) {
                //顏色轉(zhuǎn)換：祖父節(jié)點的兩個字節(jié)點由紅轉(zhuǎn)黑，祖父節(jié)點由黑轉(zhuǎn)紅
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                //繼續(xù)調(diào)整祖父節(jié)點
                x = xpp;
            }
            //叔節(jié)點為黑節(jié)點
            else {
                //x節(jié)點為父節(jié)點的右節(jié)點，左旋
                if (x == xp.right) {
                    root = rotateLeft(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                //右旋
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        //父節(jié)點為祖父節(jié)點的右孩子，與上面類似
        else {
            if (xppl != null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            else {
                if (x == xp.left) {
                    root = rotateRight(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

類似操作不再分析，其實就是紅黑樹的操作，包括插入，刪除。
最后分析一下keySet()這個方法：

public Set keySet() {
    Set ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

public final Iterator iterator()     { return new KeyIterator(); }
final class KeyIterator extends HashIterator

可以看到，當(dāng)調(diào)用keySet的iterator()時，就持有了hashIterator，也就可以訪問hashMap的內(nèi)部數(shù)組，獲得key的集合Set。

TreeMap是完全基于紅黑樹的，并在此基礎(chǔ)上實現(xiàn)了NavigableMap接口。所以它的特點是可排序，該Map根據(jù)其鍵的自然順序(a.compareTo(b))進行排序，或者根據(jù)創(chuàng)建時提供的Comparator(comparactor.compare(a,b))進行排序，具體取決于使用的構(gòu)造方法。

private final Comparator comparator;
private transient Entry root;
private transient int size = 0;
private transient int modCount = 0;
static final class Entry implements Map.Entry {
    K key;
    V value;
    Entry left;
    Entry right;
    Entry parent;
    boolean color = BLACK;
    ...
}

可以看到，TreeMap只有紅黑樹，且紅黑樹是通過內(nèi)部類Entry來實現(xiàn)的。接下來重點查看一下put函數(shù)：

public V put(K key, V value) {
    Entry t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry parent;
    // split comparator and comparable paths
    Comparator cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable k = (Comparable) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

可以看到，先是判斷根結(jié)點的情況，然后無非是根據(jù)是否有比較器分別討論，都是按二叉查找樹的規(guī)則插入。在插入完成之后再調(diào)用fixAfterInsertion，這個方法與HashMap的balanceInsertion基本類似。

TreeMap有一個構(gòu)造函數(shù)是根據(jù)有序序列構(gòu)建的：

public TreeMap(SortedMap m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}

buildFromSorted通過重載方法完成紅黑樹的構(gòu)建：

if (hi < lo) return null;

int mid = (lo + hi) >>> 1;

Entry left  = null;
if (lo < mid)
    left = buildFromSorted(level+1, lo, mid - 1, redLevel,
                           it, str, defaultVal);

// extract key and/or value from iterator or stream
K key;
V value;
if (it != null) {
    if (defaultVal==null) {
        Map.Entry entry = (Map.Entry)it.next();
        key = (K)entry.getKey();
        value = (V)entry.getValue();
    } else {
        key = (K)it.next();
        value = defaultVal;
    }
} else { // use stream
    key = (K) str.readObject();
    value = (defaultVal != null ? defaultVal : (V) str.readObject());
}

Entry middle =  new Entry<>(key, value, null);

// color nodes in non-full bottommost level red
if (level == redLevel)
    middle.color = RED;

if (left != null) {
    middle.left = left;
    left.parent = middle;
}

if (mid < hi) {
    Entry right = buildFromSorted(level+1, mid+1, hi, redLevel,
                                       it, str, defaultVal);
    middle.right = right;
    right.parent = middle;
}

return middle;

從上面代碼可以看出，首先以序列中間節(jié)點為根節(jié)點，將序列分為左右兩個部分，并分別建立成根節(jié)點的左右子樹，然后用同樣的方法，在子序列中尋找中間節(jié)點作為子樹的根節(jié)點，以此遞歸下去。最終構(gòu)建成一棵二叉樹。葉子節(jié)點以上是一棵滿二叉樹，而葉子節(jié)點則不一定，所以葉子節(jié)點都是紅節(jié)點，滿足紅黑樹的性質(zhì)。至于如何判斷葉子節(jié)點是通過節(jié)點的深度，首先通過computeRedLevel方法計算出葉子節(jié)點應(yīng)該在的深度，然后每層遞歸深度加1，再判斷是否等于葉子深度，以此決定是否為紅節(jié)點。

private static int computeRedLevel(int sz) {
    int level = 0;
    for (int m = sz - 1; m >= 0; m = m / 2 - 1)
        level++;
    return level;
}

LinkedHashMap繼承自HashMap，它的內(nèi)部類Entry也繼承自HashMap.Node。它重寫了一些HashMap的方法，在hashMap的基礎(chǔ)上，將所有元素連成一個雙向鏈表。

static class Entry extends HashMap.Node {
    Entry before, after;
    Entry(int hash, K key, V value, Node next) {
        super(hash, key, value, next);
    }
}

transient LinkedHashMap.Entry head;
transient LinkedHashMap.Entry tail;
final boolean accessOrder;//在構(gòu)造函數(shù)中初始化，用來指定迭代順序，true為訪問順序，false為插入順序

accessOrder是一個比較重要的標(biāo)志位，如果為true，每次訪問元素都要及時調(diào)整鏈表。

HashTable跟JDk1.7以前的HashMap一樣，是基于數(shù)組加鏈表的，不過它的方法都是同步的，HashTable效率很低，因為每次訪問修改都會對整個數(shù)組加鎖，我們需要更細粒度的鎖以提高效率。ConcurrentHashMap相比而言擁有更高的效率，因為它不是對整個數(shù)組加鎖，這涉及到一些并發(fā)知識，具體的分析會在另外一篇多帶帶展開。

Set其實就是Map的鍵集合，查看源碼得知Set內(nèi)部都保存著一個Map，對Set的訪問實際轉(zhuǎn)換為對Map的訪問。

HashSet通過內(nèi)部的HashMap保存數(shù)據(jù)：

private transient HashMap map;
public HashSet() {
    map = new HashMap<>();
}

再來看一下HashSet的幾個方法：

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
public int size() {
    return map.size();
}
public Iterator iterator() {
    return map.keySet().iterator();
}

可以看到，HashSet的方法都是訪問內(nèi)部的map，而鍵值對的值都是PRESENT，只有鍵是有意義的。

TreeSet內(nèi)部通過NavigableMap的鍵保存數(shù)據(jù)，方法也都是轉(zhuǎn)為對map的操作，不再詳述。

Queue接口也繼承Collection，而且Priority跟上一篇關(guān)于簡單算法的博客中介紹的堆關(guān)系密切，所以借助分析優(yōu)先隊列復(fù)習(xí)一下堆的知識。Priority也是用動態(tài)數(shù)組存儲元素的，如下：

transient Object[] queue;
private int size = 0;
private final Comparator comparator;
//擴容函數(shù)
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

接下來是添加元素：

public boolean add(E e) {
    return offer(e);
}
public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        siftUpComparable(k, x);
}

@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
    Comparable key = (Comparable) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

add方法通過offer方法調(diào)用siftUp，siftUp根據(jù)是否有定義的comparator進行區(qū)分按不同的排序方式調(diào)整最小堆。兩種方式代碼一樣，以siftUpComparable為例，從新插入位置的父親開始比較，若父節(jié)點小于子節(jié)點退出循環(huán)，將帶插入元素放置在初始位置；否則將父節(jié)點元素移動到子節(jié)點上，再用祖父節(jié)點比較，一直找到合適位置放置新增元素為止。

再看一下與之對應(yīng)的方法SiftDownComparable：

private void siftDownComparable(int k, E x) {
    Comparable key = (Comparable)x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            ((Comparable) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}

這是從上到下的調(diào)整堆，與上面剛好相反，首先從兩個孩子中找出較小的那個，再與待插入比較，如果待插入元素小于較小子元素，那么滿足最小堆，直接退出循環(huán)并未當(dāng)前位置賦值。否則將子元素移動到父元素上，在那當(dāng)前元素與子元素的子元素比較下去一直到找到待插入元素的合適位置。

最后分析一下刪除元素的方法：

public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}
private E removeAt(int i) {
    // assert i >= 0 && i < size;
    modCount++;
    int s = --size;
    if (s == i) // removed last element
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved);
        if (queue[i] == moved) {
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}

如果刪除索引不是最后一個位置，那么獲取最后一個節(jié)點的值并刪除節(jié)點，然后用最后一個節(jié)點的值覆蓋待刪除位置節(jié)點的值并調(diào)整結(jié)構(gòu)，若調(diào)整完成之后結(jié)構(gòu)未發(fā)生改變則需要繼續(xù)向上調(diào)整，如果已經(jīng)向下調(diào)整過了（結(jié)構(gòu)發(fā)生了改變），那么無需再調(diào)整了。

還有部分容器沒有列出，關(guān)于并發(fā)部分的，例如ConcurrentHashMap會在介紹concurrent包時一并介紹。