所有集合基于jdk1.8，對(duì)源碼稍做調(diào)整。

HashMap

主要變量

    // 比較器
    private final Comparator<? super K> comparator;
    // 根節(jié)點(diǎn)
    private transient Entry<K, V> root;
    // TreeMap大小
    private transient int size = 0;
    // 修改量
    private transient int modCount = 0;

構(gòu)造方法

    TreeMap() {
        this.comparator = null;
    }

    TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }

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

put

    public V put(K key, V value) {
        Entry<K, V> t = root;
        //當(dāng)根節(jié)點(diǎn)為空，直接賦值給根節(jié)點(diǎn)
        if (t == null) {
            compare(key, key);

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K, V> parent;

        Comparator<? super K> cpr = comparator;
        //比較器存在時(shí)，按照比較器進(jìn)行比較
        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);
        }
        //比較器不存在，調(diào)用key的compare方法
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) 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<K, V> e = new Entry<>(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        //紅黑樹實(shí)現(xiàn)
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

    /**
     * 紅黑樹實(shí)現(xiàn)
     * @param x
     */
    private void fixAfterInsertion(Entry<K, V> x) {
        //先設(shè)為紅色節(jié)點(diǎn)
        x.color = RED;
        //父顏色P為紅時(shí)，進(jìn)行變換（紅黑樹不允許分支上連續(xù)出現(xiàn)紅色節(jié)點(diǎn)）
        while (x != null && x != root && x.parent.color == RED) {
            //當(dāng)P在其父節(jié)點(diǎn)G左邊時(shí)
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                //獲取G的右子樹Y
                Entry<K, V> y = rightOf(parentOf(parentOf(x)));
                //Y為紅,設(shè)P為紅，Y為黑，G為紅,G變換為X繼續(xù)迭代
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } 
                //Y為黑
                else {
                    //X在右邊時(shí)，X轉(zhuǎn)換為父節(jié)點(diǎn)并進(jìn)行左旋
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    //將X父節(jié)點(diǎn)設(shè)為黑色，父節(jié)點(diǎn)的父節(jié)點(diǎn)G設(shè)為紅色，并將G右旋
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                Entry<K, V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;
    }

get

    public V get(Object key) {
        Entry<K, V> p = getEntry(key);
        return (p == null ? null : p.value);
    }

    final Entry<K, V> getEntry(Object key) {
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K, V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }

TreeSet

TreeSet內(nèi)部維護(hù)了一個(gè)TreeMap，元素不重復(fù)也是依靠TreeMap的key值不重復(fù)實(shí)現(xiàn)的。

主要變量

    //實(shí)際元素
    private transient NavigableMap<E, Object> m;
    //充當(dāng)每個(gè)key的對(duì)應(yīng)value
    private static final Object PRESENT = new Object();