摘要：三系列用于保存鍵值對，無論是，還是已棄用的或者線程安全的等，都是基于紅黑樹。是完全基于紅黑樹的，并在此基礎上實現了接口。可以看到，只有紅黑樹，且紅黑樹是通過內部類來實現的。

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

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

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

transient Object[] elementData;

可以通過構造函數指定數組的初始容量，也可以不指定，當首次通過add加入元素時，會通過內部擴容機制新建一個容量為10的數組（JDK1.7前在構造函數中直接新建數組）：

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

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

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

上面發現elementData數組是transient的，這表明系統默認序列化執行時跳過該數組。取而代之的是，ArrayList提供了writeObject和readObject方法來自定義寫入和讀取該數組的方式。

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

LinkedList其實與Arraylist有很多相似地方，只不過底層實現一個是通過數組，一個是通過鏈表而已。由于這兩種實現的不同，也導致的它們不同的使用場合。ArrayList是用數組實現的，那么在查的方面肯定優于基于鏈表的LinkedList，與之相對的是LinkedList在增刪改上優于ArrayList。
LinkedList的核心數據結構如下：

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節點其實就是雙向鏈表，由于是用鏈表實現，自然不用考慮擴容，只需對其修改時更新節點即可。LinkedList方法大多是跟鏈表相關，選取addFirst分析一下：

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

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

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

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

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

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

性質一：節點為紅色或者黑色；

性質二：根節點是黑色；

性質三：每個葉節點是黑色；

性質四：每個紅色節點的兩個子節點都是黑色；

性質五：從任一節點到其沒個葉節點的所有路徑都包含相同數目的黑色節點

紅黑樹是Map系列容器的底層實現細節，關于具體的對紅黑樹的操作在Map的分析中會涉及。

HashMap是很常用的Map結構，JDK1.7是由Entry數組實現，JDK1.8改為Node數組加TreeNode紅黑樹結合實現。

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數組
int threshold;//臨界值
final float loadFactor;//填充因子
transient int size;//元素個數

HashMap有四個重載的構造函數：

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

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

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

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

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

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

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

我們調用put函數往hashMap里填充元素時，會調用putVal函數，會有以下幾種情況：

數組為空則新建數組；

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

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

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

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

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

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)//數組為空新建數組
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)//table[i]為空直接插入新節點
        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))))//對應位置首個節點key相同
            e = p;
        else if (p instanceof TreeNode)//首節點為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;
}

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

final Node[] resize() {
    Node[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {//數組已存在，不為空
        if (oldCap >= MAXIMUM_CAPACITY) {//容量已經超過最大值時，不會再改動數組，只會調整臨界值
            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) //只有臨界值時，將臨界值設為數組容量
        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數組
        Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    
    //將舊數組元素填充至新數組
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)//該位置鏈表只有一個節點，計算下標并移至新數組
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)//該位置為紅黑樹，則通過樹操作分解至新數組
                    ((TreeNode)e).split(this, newTab, j, oldCap);
                else { // 將鏈表分為兩部分整體位移至新數組
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                        //新的下標值等于舊的下標值的元素
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                        //新的下標值等于舊的下標值加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;
}

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

接下來看一下hashMap中的紅黑樹操作,hashMap中的紅黑樹操作還是很多的，這里以上面插入節點后鏈表長度超過8時轉為紅黑樹調用的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) {//首節點不為空，樹化
        TreeNode hd = null, tl = null;//頭尾節點
        do {
            //用樹節點代替鏈表節點
            TreeNode p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        //頭節點不為空轉為紅黑樹
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

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

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

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

static  TreeNode balanceInsertion(TreeNode root,
                                            TreeNode x) {
    //新插入節點默認為紅節點
    x.red = true;
    for (TreeNode xp, xpp, xppl, xppr;;) {
        //x即為根節點
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
    //x為根節點的子節點或者父節點為黑節點
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
    //父節點為祖父節點的左孩子
        if (xp == (xppl = xpp.left)) {
            //叔節點為紅節點
            if ((xppr = xpp.right) != null && xppr.red) {
                //顏色轉換：祖父節點的兩個字節點由紅轉黑，祖父節點由黑轉紅
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                //繼續調整祖父節點
                x = xpp;
            }
            //叔節點為黑節點
            else {
                //x節點為父節點的右節點，左旋
                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);
                    }
                }
            }
        }
        //父節點為祖父節點的右孩子，與上面類似
        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

可以看到，當調用keySet的iterator()時，就持有了hashIterator，也就可以訪問hashMap的內部數組，獲得key的集合Set。

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

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只有紅黑樹，且紅黑樹是通過內部類Entry來實現的。接下來重點查看一下put函數：

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

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

TreeMap有一個構造函數是根據有序序列構建的：

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通過重載方法完成紅黑樹的構建：

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;

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

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，它的內部類Entry也繼承自HashMap.Node。它重寫了一些HashMap的方法，在hashMap的基礎上，將所有元素連成一個雙向鏈表。

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;//在構造函數中初始化，用來指定迭代順序，true為訪問順序，false為插入順序

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

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

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

HashSet通過內部的HashMap保存數據：

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的方法都是訪問內部的map，而鍵值對的值都是PRESENT，只有鍵是有意義的。

TreeSet內部通過NavigableMap的鍵保存數據，方法也都是轉為對map的操作，不再詳述。

Queue接口也繼承Collection，而且Priority跟上一篇關于簡單算法的博客中介紹的堆關系密切，所以借助分析優先隊列復習一下堆的知識。Priority也是用動態數組存儲元素的，如下：

transient Object[] queue;
private int size = 0;
private final Comparator comparator;
//擴容函數
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方法調用siftUp，siftUp根據是否有定義的comparator進行區分按不同的排序方式調整最小堆。兩種方式代碼一樣，以siftUpComparable為例，從新插入位置的父親開始比較，若父節點小于子節點退出循環，將帶插入元素放置在初始位置；否則將父節點元素移動到子節點上，再用祖父節點比較，一直找到合適位置放置新增元素為止。

再看一下與之對應的方法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;
}

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

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

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

如果刪除索引不是最后一個位置，那么獲取最后一個節點的值并刪除節點，然后用最后一個節點的值覆蓋待刪除位置節點的值并調整結構，若調整完成之后結構未發生改變則需要繼續向上調整，如果已經向下調整過了（結構發生了改變），那么無需再調整了。

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