?????上篇文章我們介紹了HashMap集合，這是一個(gè)鍵值對(duì)集合，可以高效的按照鍵查找數(shù)值。但是它有一個(gè)缺陷：數(shù)據(jù)如果是無序的可以是很高效的，但是如果數(shù)據(jù)需要排列有順序就不適合了。本篇將要介紹的一個(gè)集合是樹集鍵值對(duì)（TreeMap），它能夠?qū)?shù)據(jù)按照鍵值有序的存儲(chǔ)。
?????在介紹TreeMap之前，我們來了解一種數(shù)據(jù)結(jié)構(gòu)：排序二叉樹。相信學(xué)過數(shù)據(jù)結(jié)構(gòu)的同學(xué)知道，這種結(jié)構(gòu)的數(shù)據(jù)存儲(chǔ)形式在查找的時(shí)候效率非常高。

這里寫圖片描述

?????如圖所示，這種數(shù)據(jù)結(jié)構(gòu)是以二叉樹為基礎(chǔ)的，所有的左孩子的value值都是小于根結(jié)點(diǎn)的value值的，所有右孩子的value值都是大于根結(jié)點(diǎn)的。這樣做的好處在于：如果需要按照鍵值查找數(shù)據(jù)元素，只要比較當(dāng)前結(jié)點(diǎn)的value值即可（小于當(dāng)前結(jié)點(diǎn)value值的，往左走，否則往右走），這種方式，每次可以減少一半的操作，所以效率比較高。在實(shí)現(xiàn)我們的TreeMap中，使用的是紅黑樹（一種優(yōu)化了的二叉排序樹）。
一、TreeMap的超接口
?????TreeMap主要繼承了類AbstractMap（一個(gè)對(duì)Map接口的實(shí)現(xiàn)類）和 NavigableMap（主要提供了對(duì)TreeMap的一些高級(jí)操作例如：返回第一個(gè)鍵或者返回小于某個(gè)鍵的視圖等）。主要的一些操作有：put添加元素到集合中，remove根據(jù)鍵值或者value刪除指定元素，get根據(jù)指定鍵值獲取某個(gè)元素，containsValue查看是否包含某個(gè)指定的值，containsKey 查看是否包含某個(gè)指定的key數(shù)值等。
二、構(gòu)造函數(shù)
?????TreeMap 的構(gòu)造函數(shù)主要有以下幾種：

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

????? 因?yàn)樵谖覀兊膬?nèi)部存儲(chǔ)結(jié)構(gòu)中，是需要對(duì)兩個(gè)節(jié)點(diǎn)的元素的鍵值進(jìn)行比較的，所以就必須要實(shí)現(xiàn)Comparable接口來具有比較功能。第一個(gè)構(gòu)造函數(shù)默認(rèn)無參，內(nèi)部將我們的比較器賦值為null，表明：在內(nèi)部集合中不需要接受來自外部傳入的比較器，默認(rèn)使用Key的比較器（例如：Key是Integer類型就會(huì)默認(rèn)使用它的比較器）。第二種構(gòu)造函數(shù)就是從外部傳入指定的比較器，指定TreeMap內(nèi)部在對(duì)鍵進(jìn)行比較的時(shí)候使用我們從外部傳入的比較器。
三、內(nèi)部存儲(chǔ)的基本原理
?????從源碼中摘取部分代碼，能說明內(nèi)部結(jié)構(gòu)即可。

private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int modCount = 0;
//靜態(tài)成員內(nèi)部類
static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;
        .........
     }

?????從代碼中，我們可以很容易的看出來，內(nèi)部包含一個(gè) comparator 比較器（或值被置為Key的比較器，或是被置為外部傳入的比較器），根結(jié)點(diǎn) root （指向紅黑樹的跟結(jié)點(diǎn)），記錄修改次數(shù) modCount （用于對(duì)集合結(jié)構(gòu)性的檢查和前面文章說的一樣），還有一個(gè)靜態(tài)內(nèi)部類（其實(shí)可以理解為一個(gè)樹結(jié)點(diǎn)），其中有存儲(chǔ)鍵和值的key和value，還有指向左孩子和右孩子的“指針”，還有指向父結(jié)點(diǎn)的“指針”，最后還包括一個(gè)標(biāo)志 color（這個(gè)暫時(shí)不用知道）。也就是說，一個(gè)root指向樹的跟結(jié)點(diǎn)，而這個(gè)跟根結(jié)點(diǎn)又鏈接為一棵樹，最后通過這個(gè)root可以遍歷整個(gè)樹。
四、put添加元素到集合中
?????在了解了TreeMap的內(nèi)部結(jié)構(gòu)之后，我們可以看看他是怎么將一個(gè)元素結(jié)點(diǎn)掛到整棵樹上的。由于put方法的源碼比較多，請(qǐng)大家慢慢看。

    public V put(K key, V value) {
        Entry<K,V> 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<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> 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<? 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;
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

?????首先判斷根結(jié)點(diǎn)是否是空的，如果是空的直接創(chuàng)建一個(gè)結(jié)點(diǎn)并將parent賦null，將其作為該樹的跟結(jié)點(diǎn)，返回null跳過余下代碼。如果跟結(jié)點(diǎn)不是空的，就去判斷 comparator 是否為null（也就是判斷comparator的值是默認(rèn)key的比較器還是外部傳入的比較器），如果comparator的值是外部傳入的，通過循環(huán)比較key的值計(jì)算將要添加的結(jié)點(diǎn)的位置（過程中如果發(fā)現(xiàn)有某個(gè)結(jié)點(diǎn)的key值和將要添加的key的值相等，說明這是修改操作，修改其value值返回舊value值）。
?????如果在創(chuàng)建對(duì)象的時(shí)候并沒有從外部傳入比較器，首先判斷key的值是否為null（如果是就拋出空指針異常），那有人說：為什么要對(duì)key是否為空做判斷呢？上面不是也沒有做判斷么？ 答案是：如果 comparator 是外部傳入的，那么沒問題，但是如果是key的默認(rèn)比較器，那如果key為null 還要調(diào)用比價(jià)器 必然拋空指針異常。接下來做的事情和上面一樣的。
?????程序執(zhí)行到最后了，我們要知道一點(diǎn)的是：parent指向的是最后一個(gè)結(jié)點(diǎn)也就是我們將要添加的結(jié)點(diǎn)的父結(jié)點(diǎn)。最后根據(jù)key和value和parent創(chuàng)建一個(gè)幾點(diǎn)（父結(jié)點(diǎn)是parent），然后根據(jù)上面的判斷確定此結(jié)點(diǎn)是parent的左孩子還是右孩子。
?????這個(gè)方法中有一個(gè) fixAfterInsertion(e); 是用于紅黑樹的構(gòu)造的，調(diào)用這個(gè)函數(shù)可以將我們剛剛創(chuàng)建完成之后的樹通過挪動(dòng)重新構(gòu)建成紅黑樹。

?????最后總結(jié)一下整個(gè)put方法的執(zhí)行過程：

• 判斷此樹是否是空的，空樹的操作就很簡(jiǎn)單了
• 判斷比較器的來源做不同的操作（比較value值確定位置）
• 構(gòu)建新結(jié)點(diǎn)掛上樹
• 調(diào)用方法重構(gòu)紅黑樹

其中，我們要區(qū)分一點(diǎn)的是，為什么有時(shí)候返回的null，有時(shí)候返回的是舊結(jié)點(diǎn)的value，主要區(qū)別還是在于，put方法作為添加元素和修改元素的兩種功能，添加元素的時(shí)候統(tǒng)一返回的是null，修改元素的時(shí)候統(tǒng)一返回的是別修改之前的元素的value。
五、根據(jù)鍵的值刪除結(jié)點(diǎn)元素
?????添加元素直到是怎么回事了之后，我們來看看刪除元素是怎么被實(shí)現(xiàn)的，首先看remove方法：

    public V remove(Object key) {
        Entry<K,V> p = getEntry(key);
        if (p == null)
            return null;

        V oldValue = p.value;
        deleteEntry(p);
        return oldValue;
    }

?????從代碼中可以看出來，刪除的操作主要還是兩個(gè)操作的結(jié)合，一個(gè)是獲取指定元素，一個(gè)是刪除指定元素。我們先看如何獲取指定元素。

    final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        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;
    }

?????這段代碼不難理解，依然是分兩種情況比較器的來源（由于兩種情況下的處理方式類似，此處指具體說其中一種），p指向根結(jié)點(diǎn)root，循環(huán)遍歷，比較key和當(dāng)前循環(huán)到的key是否相等，不相等就根據(jù)大小向左或者向右，如果相等執(zhí)行return p; 返回此結(jié)點(diǎn)。如果整棵樹遍歷完成之后，沒有找到指定鍵值的結(jié)點(diǎn)就會(huì)返回null表示未找到該結(jié)點(diǎn)。這就是查找方法，下面我們看看刪除指定結(jié)點(diǎn)的方法。
?????在看代碼之前我們先了解一下整體的思路，將要?jiǎng)h除的結(jié)點(diǎn)可能有以下三種情況：

• 該結(jié)點(diǎn)為葉子結(jié)點(diǎn)，即無左孩子和右孩子
• 該結(jié)點(diǎn)只有一個(gè)孩子結(jié)點(diǎn)

• 該結(jié)點(diǎn)有兩個(gè)孩子結(jié)點(diǎn)
  ?????第一種情況，直接將該結(jié)點(diǎn)刪除，并將父結(jié)點(diǎn)的對(duì)應(yīng)引用賦值為null
  ?????第二種情況，跳過該結(jié)點(diǎn)將其父結(jié)點(diǎn)指向這個(gè)孩子結(jié)點(diǎn)

  
  
  這里寫圖片描述
  
  

  第三種情況，找到待刪結(jié)點(diǎn)的后繼結(jié)點(diǎn)將后繼結(jié)點(diǎn)替換到待刪結(jié)點(diǎn)并刪除后繼結(jié)點(diǎn)（將問題轉(zhuǎn)換為刪除后繼結(jié)點(diǎn)，通過前面兩種可以解決）

  
  
  

  這里寫圖片描述
  
  找到后繼結(jié)點(diǎn)
  
  

  這里寫圖片描述
  
  替換待刪結(jié)點(diǎn)
  
  這里寫圖片描述
  
  

  刪除后繼結(jié)點(diǎn)

  
  
  

  這里寫圖片描述
  
  下面我們看代碼：

/*代碼雖多，我們一點(diǎn)一點(diǎn)看*/
    private void deleteEntry(Entry<K,V> p) {
        modCount++;
        size--;

        // If strictly internal, copy successor's element to p and then make p
        // point to successor.
        if (p.left != null && p.right != null) {
            Entry<K,V> s = successor(p);
            p.key = s.key;
            p.value = s.value;
            p = s;
        } // p has 2 children

        // Start fixup at replacement node, if it exists.
        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)是否具有兩個(gè)孩子，如果有調(diào)用函數(shù) successor返回后繼結(jié)點(diǎn)，并且替換待刪結(jié)點(diǎn)。對(duì)于這條語(yǔ)句：Entry>K,V< replacement = (p.left != null ? p.left : p.right); ，我們上述的三種情況下replacement的取值值得研究，如果是第一種情況（葉子結(jié)點(diǎn)），那么replacement取值為null，進(jìn)入下面的判斷，第一個(gè)if過，第二個(gè)判斷待刪結(jié)點(diǎn)是否是根結(jié)點(diǎn)（只有根結(jié)點(diǎn)的父結(jié)點(diǎn)為null），如果是說明整個(gè)樹只有一個(gè)結(jié)點(diǎn)，那么直接刪除即可，如果不是根結(jié)點(diǎn)就說明是葉子結(jié)點(diǎn)，此時(shí)將父結(jié)點(diǎn)賦值為null然后刪除即可。
對(duì)于第二種情況下（只有一個(gè)孩子結(jié)點(diǎn)時(shí)候），最上面的if語(yǔ)句是不做的，如果那一個(gè)結(jié)點(diǎn)是左孩子 replacement為該結(jié)點(diǎn)，然后將此結(jié)點(diǎn)跳過父結(jié)點(diǎn)掛在待刪結(jié)點(diǎn)的下面，如果那一個(gè)孩子是右孩子，replacement為該結(jié)點(diǎn)，同樣操作。
第三種情況（待刪結(jié)點(diǎn)具有兩個(gè)孩子結(jié)點(diǎn)），那肯定執(zhí)行最最上面的if語(yǔ)句中代碼，找到后繼結(jié)點(diǎn)替換待刪結(jié)點(diǎn)（后繼結(jié)點(diǎn)一定沒有左孩子），成功的將問題轉(zhuǎn)換為刪除后繼結(jié)點(diǎn)，又因?yàn)楹罄^結(jié)點(diǎn)一定沒有左孩子，整個(gè)問題已經(jīng)被轉(zhuǎn)換成上述兩種情況了，（假如后繼結(jié)點(diǎn)沒有右孩子就是第一種，假如有就是第二種）所以replacement = p.right，下面分情況處理。刪除方法結(jié)束。
?????小結(jié)一下，刪除結(jié)點(diǎn)難點(diǎn)在于刪除指定鍵值的結(jié)點(diǎn)，主要分為三種情況，葉子結(jié)點(diǎn)，一個(gè)孩子結(jié)點(diǎn)，兩個(gè)孩子結(jié)點(diǎn)。而對(duì)于不同的情況，jdk編寫者將最難的兩個(gè)孩子結(jié)點(diǎn)轉(zhuǎn)換為前兩種較為簡(jiǎn)單的方式，可見大神之作。欽佩。
?????最后還是要說，本篇文章為博主反復(fù)研究jdk源碼總結(jié)而來，如果有錯(cuò)誤，望指出。