本篇文章給大家介紹基于樹實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)——TreeMap

1、TreeMap 定義

聽名字就知道，TreeMap 是由Tree 和 Map 集合有關(guān)的，沒錯(cuò)，TreeMap 是由紅黑樹實(shí)現(xiàn)的有序的 key-value 集合。

PS:想要學(xué)懂TreeMap的實(shí)現(xiàn)原理，紅黑樹的了解是必不可少的！！！

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

TreeMap 首先繼承了 AbstractMap 抽象類，表示它具有散列表的性質(zhì)，也就是由 key-value 組成。

其次 TreeMap 實(shí)現(xiàn)了 NavigableMap 接口，該接口支持一系列獲取指定集合的導(dǎo)航方法，比如獲取小于指定key的集合。

最后分別實(shí)現(xiàn) Serializable 接口以及 Cloneable 接口，分別表示支持對(duì)象序列化以及對(duì)象克隆。

2、字段定義

①、Comparator

/**
     * The comparator used to maintain order in this tree map, or
     * null if it uses the natural ordering of its keys.
     *
     * @serial
     */
    private final Comparator< ? super K > comparator;

可以看上面的英文注釋，Comparator 是用來維護(hù)treemap集合中的順序，如果為null，則按照key的自然順序。

Comparator 是一個(gè)接口，排序時(shí)需要實(shí)現(xiàn)其 compare 方法，該方法返回正數(shù)，零，負(fù)數(shù)分別代表大于，等于，小于。那么怎么使用呢？這里舉個(gè)例子：

這里有一個(gè)Person類，里面有兩個(gè)屬性pname，page，我們將該person對(duì)象放入ArrayList集合時(shí)，需要對(duì)其按照年齡進(jìn)行排序。

package com.ys.test;

/**
 * Create by YSOcean
 */
public class Person {
    private String pname;
    private Integer page;

    public Person() {
    }

    public Person(String pname, Integer page) {
        this.pname = pname;
        this.page = page;
    }

    public String getPname() {
        return pname;
    }

    public void setPname(String pname) {
        this.pname = pname;
    }

    public Integer getPage() {
        return page;
    }

    public void setPage(Integer page) {
        this.page = page;
    }

    @Override
    public String toString() {
        return "Person{" +
                "pname='" + pname + ''' +
                ", page=" + page +
                '}';
    }
}

打印結(jié)果為：

②、Entry

private transient Entry< K,V > root;

對(duì)于Entry詳細(xì)源碼這里不列舉了，主要看幾個(gè)字段：

K key;
V value;
Entry K,V > left;
Entry K,V > right;
Entry K,V > parent;
boolean color = BLACK;

相信對(duì)紅黑樹這種數(shù)據(jù)結(jié)構(gòu)了解的人，一看這幾個(gè)字段就明白了，這也印證了前面所說的TreeMap底層有紅黑樹這種數(shù)據(jù)結(jié)構(gòu)。

③、size

/**
     * The number of entries in the tree
     */
    private transient int size = 0;

用來表示entry的個(gè)數(shù)，也就是key-value的個(gè)數(shù)。

④、modCount

/**
     * The number of structural modifications to the tree.
     */
    private transient int modCount = 0;

基本上前面講的在ArrayList,LinkedList,HashMap等線程不安全的集合都有此字段，用來實(shí)現(xiàn)Fail-Fast 機(jī)制，如果在迭代這些集合的過程中，有其他線程修改了這些集合，就會(huì)拋出ConcurrentModificationException異常。

⑤、紅黑樹常量

private static final boolean RED   = false;
    private static final boolean BLACK = true;

3、構(gòu)造函數(shù)

①、無參構(gòu)造函數(shù)

1     public TreeMap() {
2         comparator = null;
3     }

將比較器 comparator 置為 null，表示按照key的自然順序進(jìn)行排序。

②、帶比較器的構(gòu)造函數(shù)

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

需要自己實(shí)現(xiàn)Comparator。

③、構(gòu)造包含指定map集合的元素

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

使用該構(gòu)造器創(chuàng)建的TreeMap,會(huì)默認(rèn)插入m表示的集合元素，并且comparator表示按照自然順序進(jìn)行插入。

④、帶 SortedMap的構(gòu)造函數(shù)

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

和上面帶Map的構(gòu)造函數(shù)不一樣，map是無序的，而SortedMap 是有序的，使用 buildFromSorted() 方法將SortedMap集合中的元素插入到TreeMap 中。

4、添加元素

//添加元素
    public V put(K key, V value) {
        TreeMap.Entry< K,V > t = root;
        //如果根節(jié)點(diǎn)為空，即TreeMap中一個(gè)元素都沒有，那么設(shè)置新添加的元素為根節(jié)點(diǎn)
        //并且設(shè)置集合大小size=1,以及modCount+1，這是用于快速失敗
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new TreeMap.Entry<  >(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        TreeMap.Entry< K,V > parent;
        // split comparator and comparable paths
        Comparator< ? super K > cpr = comparator;
        //如果比較器不為空，即初始化TreeMap構(gòu)造函數(shù)時(shí)，有傳遞comparator類
        //那么插入新的元素時(shí)，按照comparator實(shí)現(xiàn)的類進(jìn)行排序
        if (cpr != null) {
            //通過do-while循環(huán)不斷遍歷樹，調(diào)用比較器對(duì)key值進(jìn)行比較
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    //遇到key相等，直接將新值覆蓋到原值上
                    return t.setValue(value);
            } while (t != null);
        }
        //如果比較器為空，即初始化TreeMap構(gòu)造函數(shù)時(shí)，沒有傳遞comparator類
        //那么插入新的元素時(shí)，按照key的自然順序
        else {
            //如果key==null，直接拋出異常
            //注意，上面構(gòu)造TreeMap傳入了Comparator，是可以允許key==null
            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)，根據(jù)父親節(jié)點(diǎn)創(chuàng)建一個(gè)新節(jié)點(diǎn)
        TreeMap.Entry< K,V > e = new TreeMap.Entry<  >(key, value, parent);
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        //修正紅黑樹（包括節(jié)點(diǎn)的左旋和右旋，具體可以看我Java數(shù)據(jù)結(jié)構(gòu)和算法中對(duì)紅黑樹的介紹）
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }

添加元素，如果初始化TreeMap構(gòu)造函數(shù)時(shí)，沒有傳遞comparator類，是不允許插入key==null的鍵值對(duì)的，相反，如果實(shí)現(xiàn)了Comparator，則可以傳遞key=null的鍵值對(duì)。

另外，當(dāng)插入一個(gè)新的元素后（除了根節(jié)點(diǎn)），會(huì)對(duì)TreeMap數(shù)據(jù)結(jié)構(gòu)進(jìn)行修正，也就是對(duì)紅黑樹進(jìn)行修正，使其滿足紅黑樹的幾個(gè)特點(diǎn)，具體修正方法包括改變節(jié)點(diǎn)顏色，左旋，右旋等操作，這里我不做詳細(xì)介紹了.

5、刪除元素

①、根據(jù)key刪除

public V remove(Object key) {
        //根據(jù)key找到該節(jié)點(diǎn)
        TreeMap.Entry< K,V > p = getEntry(key);
        if (p == null)
            return null;
        //獲取該節(jié)點(diǎn)的value，并返回
        V oldValue = p.value;
        //調(diào)用deleteEntry()方法刪除節(jié)點(diǎn)
        deleteEntry(p);
        return oldValue;
    }

    private void deleteEntry(TreeMap.Entry< K,V > p) {
        modCount++;
        size--;

        //如果刪除節(jié)點(diǎn)的左右節(jié)點(diǎn)都不為空，即有兩個(gè)孩子
        if (p.left != null && p.right != null) {
            //得到該節(jié)點(diǎn)的中序后繼節(jié)點(diǎn)
            TreeMap.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.
        TreeMap.Entry< K,V > replacement = (p.left != null ? p.left : p.right);
        //待刪除節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)，直接刪除該節(jié)點(diǎn)，并用該節(jié)點(diǎn)的唯一子節(jié)點(diǎn)頂替該節(jié)點(diǎn)
        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);

            //TreeMap中只有待刪除節(jié)點(diǎn)P，也就是只有一個(gè)節(jié)點(diǎn)，直接返回nul即可
        } else if (p.parent == null) { // return if we are the only node.
            root = null;
        } else { //  No children. Use self as phantom replacement and unlink.
            //待刪除節(jié)點(diǎn)沒有子節(jié)點(diǎn)，即為葉子節(jié)點(diǎn)，直接刪除即可
            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)分為四種情況：

1、根據(jù)key沒有找到該節(jié)點(diǎn)：也就是集合中不存在這一個(gè)節(jié)點(diǎn)，直接返回null即可。

2、根據(jù)key找到節(jié)點(diǎn)，又分為三種情況：

①、待刪除節(jié)點(diǎn)沒有子節(jié)點(diǎn)，即為葉子節(jié)點(diǎn)：直接刪除該節(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)。

③、待刪除節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)：首先找到該節(jié)點(diǎn)的中序后繼節(jié)點(diǎn)，然后把這個(gè)后繼節(jié)點(diǎn)的內(nèi)容復(fù)制給待刪除節(jié)點(diǎn)，然后刪除該中序后繼節(jié)點(diǎn)，刪除過程又轉(zhuǎn)換成前面①、②兩種情況了，這里主要是找到中序后繼節(jié)點(diǎn)，相當(dāng)于待刪除節(jié)點(diǎn)的一個(gè)替身。

6、查找元素

①、根據(jù)key查找

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

    final TreeMap.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;
        TreeMap.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;
    }

7、遍歷元素

通常有下面兩種方法，第二種方法效率要快很多。

TreeMap< String,Integer > map = new TreeMap<  >();
map.put("A",1);
map.put("B",2);
map.put("C",3);

//第一種方法
//首先利用keySet()方法得到key的集合，然后利用map.get()方法根據(jù)key得到value
Iterator< String > iterator = map.keySet().iterator();
while(iterator.hasNext()){
    String key = iterator.next();
    System.out.println(key+":"+map.get(key));
}

//第二種方法
Iterator< Map.Entry< String,Integer >> iterator1 = map.entrySet().iterator();
while(iterator1.hasNext()){
    Map.Entry< String,Integer > entry = iterator1.next();
    System.out.println(entry.getKey()+":"+entry.getValue());
}

8、小結(jié)

好了，這就是JDK中java.util.TreeMap 類的介紹。