概述

??從API文檔上我們可以知道鞭执，TreeMap是基于紅黑樹(Red-Black tree)來實(shí)現(xiàn)的，該數(shù)據(jù)結(jié)構(gòu)最重要的特點(diǎn)就是可排序芒粹。默認(rèn)情況下根據(jù)key的自然順序進(jìn)行排序兄纺，不過我們也可以自定義排序的順序。
??至于紅黑樹的相關(guān)實(shí)現(xiàn)化漆，就先不講了估脆，由于有些復(fù)雜，并且本人對(duì)紅黑樹還沒有完成吃透座云，但紅黑樹的性質(zhì)大家起碼還是要知道的疙赠。

繼承關(guān)系

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

// NavigableMap接口繼承了SortedMap
public interface NavigableMap<K,V> extends SortedMap<K,V> {

??TreeMap實(shí)現(xiàn)了NavigableMap接口，而通過查看NavigableMap則是繼承了SortedMap接口疙教。由此我們可以知道，TreeMap排序的功能是基于NavigableMap也就是SortedMap的伞租。

NavigableMap贞谓，這個(gè)接口翻譯過來可以理解為導(dǎo)航相關(guān)，該接口提供了許多個(gè)導(dǎo)航相關(guān)的方法葵诈，比如lowerKey裸弦，ceilingKey，higherKey等作喘，同樣理疙，TreeMap實(shí)現(xiàn)該接口后，除了實(shí)現(xiàn)這些方法泞坦，也自定義類了一些導(dǎo)航相關(guān)的方法窖贤，大家可自行根據(jù)API進(jìn)行查看。

而這些排序相關(guān)的操作，基本上都離不開JDK排序相關(guān)的兩個(gè)接口：Comparator和Comparable赃梧。

屬性

/**
 * 比較器
 */
private final Comparator<? super K> comparator;

/**
 * 紅黑樹的紅黑節(jié)點(diǎn)
 */
private transient Entry<K,V> root;

/**
 * 容量大小
 */
private transient int size = 0;

/**
 * 結(jié)構(gòu)性修改
 */
private transient int modCount = 0;

/**
 * 紅黑樹節(jié)點(diǎn)類型
 */
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    // 指向左子樹
    Entry<K,V> left;
    // 指向右子樹
    Entry<K,V> right;
    // 指向父節(jié)點(diǎn)
    Entry<K,V> parent;
    boolean color = BLACK;
}

// 紅黑樹節(jié)點(diǎn)-紅顏色
private static final boolean RED   = false;
// 紅黑樹節(jié)點(diǎn)-黑顏色
private static final boolean BLACK = true;

構(gòu)造方法

/**
 * 默認(rèn)構(gòu)造器滤蝠，使用默認(rèn)排序機(jī)制
 */
public TreeMap() {
    comparator = null;
}
/**
 * 自定義比較器的構(gòu)造方法
 */
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

/**
 * 將Map構(gòu)造為TreeMap
 */
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}
/**
 * 構(gòu)造SortedMap對(duì)象為TreeMap，并使用SortedMap的比較器
 */
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方法

/**
 * 紅黑樹的put操作大體上分為兩步：構(gòu)建二叉排序樹授嘀，平衡二叉排序樹
 * 構(gòu)建的時(shí)候物咳，如果用戶自定義了比較器，則會(huì)按照用戶定義的規(guī)則來蹄皱，否則將按照默認(rèn)的比較規(guī)則來插入數(shù)據(jù)览闰；
 */
public V put(K key, V value) {
    // 二叉樹當(dāng)前節(jié)點(diǎn)
    Entry<K,V> t = root;
    // 如果二叉樹為null，直接插入
    if (t == null) {
        compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    // 使用cmp來表示排序返回的結(jié)果
    int cmp;
    // 父節(jié)點(diǎn)
    Entry<K,V> parent;
    // 比較器
    Comparator<? super K> cpr = comparator;
    // 如果比較器不為空巷折，按照用戶指定比較器進(jìn)行循環(huán)比較压鉴，確定元素插入位置
    if (cpr != null) {
        do {
            parent = t;
            // 對(duì)key進(jìn)行比較
            cmp = cpr.compare(key, t.key);
            // 比較結(jié)果小于0，表示新增節(jié)點(diǎn)的key小于當(dāng)前節(jié)點(diǎn)的key盔几，則以當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)
            if (cmp < 0)
                t = t.left;
            // 比較結(jié)果大于0晴弃，表示新增節(jié)點(diǎn)的key大于當(dāng)前節(jié)點(diǎn)的key，則以當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)
            else if (cmp > 0)
                t = t.right;
            // 比較結(jié)果等于0逊拍，說明key相等上鞠，覆蓋舊值，返回新值
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 如果比較器為null
    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);
    }
    // 新增節(jié)點(diǎn)設(shè)為parent的子節(jié)點(diǎn)
    Entry<K,V> e = new Entry<>(key, value, parent);
    // 如果新增節(jié)點(diǎn)的key小于parent的key芯丧，則當(dāng)做左子節(jié)點(diǎn)
    if (cmp < 0)
        parent.left = e;
    // 否則芍阎，右子節(jié)點(diǎn)
    else
        parent.right = e;
    // 插入完成，對(duì)二叉樹進(jìn)行平衡操作
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

get方法

/**
 * get方法相對(duì)簡單些缨恒，只是對(duì)二叉樹的比較遍歷而已
 */
final Entry<K,V> getEntry(Object key) {
    // 如果比較器不為空谴咸，則按照自定義規(guī)則遍歷二叉樹
    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;
    // 按照默認(rèn)比較規(guī)則遍歷二叉樹
    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;
}

remove方法

/**
 * 這里刪除操作其實(shí)很微妙，并不是直接刪除骗露，而是用被刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)來代替被刪掉的節(jié)點(diǎn)岭佳，然后修復(fù)被刪除節(jié)點(diǎn)的結(jié)構(gòu)來進(jìn)行操作的
 */
private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    // p節(jié)點(diǎn)為要?jiǎng)h除的節(jié)點(diǎn)，如果p節(jié)點(diǎn)的左右子節(jié)點(diǎn)都不為空
    if (p.left != null && p.right != null) {
        // 找到p節(jié)點(diǎn)的后繼節(jié)點(diǎn)萧锉，這里不是直接刪除p節(jié)點(diǎn)珊随，而是將p的后繼節(jié)點(diǎn)來代替要?jiǎng)h除的節(jié)點(diǎn)，然后再進(jìn)行修復(fù)操作
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    } // p has 2 children

    // 開始修復(fù)操作
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        // Link replacement to parent
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;

        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null;

        // Fix replacement
        if (p.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (p.parent == null) { // return if we are the only node.
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        if (p.color == BLACK)
            fixAfterDeletion(p);

        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

/**
 * 獲取后繼節(jié)點(diǎn)柿隙，其實(shí)這是一個(gè)類似中序遍歷的方式
 */
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        // 節(jié)點(diǎn)的右子樹不為空叶洞，后繼結(jié)點(diǎn)就是右子樹的最左節(jié)點(diǎn)
        // 因?yàn)樽钭笞訕涫怯易訕涞淖钚」?jié)點(diǎn)
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        // 右子樹為空，則尋找當(dāng)前節(jié)點(diǎn)左子樹的第一個(gè)父節(jié)點(diǎn)
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

獲取后繼節(jié)點(diǎn)可參考：
Java TreeMap工作原理及實(shí)現(xiàn)

??如果要深入理解TreeMap的紅黑樹實(shí)現(xiàn)禀崖，可以搜索《史上最簡單清晰的紅黑樹講解》系列博客衩辟。

文章參考自：
TreeMap源碼分析（jdk1.8）