目錄

1、認識 TreeMap 和 TreeSet

2、TreeMap 的主要成員變量

3、TreeMap 的主要構造方法

4、TreeMap 和 TreeSet 的元素必須可比較

5、TreeMap 和 TreeSet 關于 key 有序?

6、TreeMap 和 TreeSet 的關系?

7、總結

1、認識 TreeMap 和 TreeSet

TreeMap 和 TreeSet 是Java中利用搜索樹實現的 Map 和 Set，它們的底層是紅黑樹，而紅黑樹是一棵近似平衡的二叉搜索樹，關于紅黑樹相關知識后續(xù)講解。本期主要是學會 TreeMap 和 TreeSet 的使用，以及知道他們的特點即可。

2、TreeMap 的主要成員變量

// 存儲傳入比較器的引用
private final Comparator<? super K> comparator;

// 搜索樹的根節(jié)點
private transient Entry<K,V> root;

// 節(jié)點個數
private transient int size = 0;

// 統(tǒng)計搜索樹結構修改的次數
private transient int modCount = 0;

這里我們需要注意的是 comparator 這個引用，它是用來接收一個比較器的，主要功能后續(xù)會講解，這里注意一下即可。

3、TreeMap 的主要構造方法

public TreeMap() {
    comparator = null;
}

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

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

• 第一個構造方法，沒什么意外的，你沒傳比較器嘛，自然就是 null。
• 第二個是傳了比較器的構造方法， 指定了比較器也很簡單。
• 第三個構造方法， 則是把你傳遞的 Map?構造一個新的樹映射，包含與給定映射相同的映射，并根據其 key 的自然順序進行排序，這些 key，必須可相互比較！

4、TreeMap 和 TreeSet 的元素必須可比較

因為 TreeMap 和 TreeSet 實現了 SortedSet 接口，表示是一個需要實現排序功能的 Map 或 Set，那實現排序的前提，你放入的元素必須是可比較的，那么也就是說，當你往 TreeMap 里面放 key 的時候，這個 key 必須可比較，也就是重寫了 compaerTo?方法，你也可也直接傳一個比較器也是可以的。

public class Test {
    public static void main(String[] args) {
        Map<Person, Integer> map = new TreeMap<>();
        System.out.println(map);
    }
}

這個報錯就是在說，?Person 無法被轉換成 Comparable，也就是在 TreeMap 底層實現中無法將 key 對象中的 compareTo 方法。

具體我們還是要去看 TreeMap 的無參構造方法以及 put 的源碼：

public TreeMap() {
    comparator = null;
}

對于 TreeMap 的無參構造方法，其實很簡單，如果你沒有傳比較器進去，默認就是 null 的，接下來就得看一下 put 方法了。

源碼中比較多，我們這里只截取一小部分，能明白為啥重寫 compareTo 方法即可。

很明顯，我們是第一次 put 元素，所以搜索樹的根節(jié)點也就是 root 節(jié)點為 null，接著將我們 put 進去的 key 作為 compare 兩個參數傳遞進去，接著去看 compare 的實現：

這里我們沒有傳比較器，所以剛開始的無參構造方法已經將 comparator 置 null了，很明顯這里可以發(fā)現，如果我們傳了比較器，就按照比較器的方式來比較，如果沒有比較器，則會將 key 轉換成 Comparable<Person>，這個尖括號中的類型，?此時我們這里是轉換成 Person，這也是泛型上界的相關知識，所以即最終調用了我們 key 對象中的 compareTo 方法，那如果我們沒有實現 Comparable 這個接口，也沒有重寫 compareTo 方法自然會拋異常。

當然后續(xù) put 元素也是按照上面的方法來比較的，有比較器，使用比較器來比較，無比較器，調用對象中的 compareTo 進行比較。

5、TreeMap 和 TreeSet 關于 key 有序?

我們前面講到過， TreeMap 和 TreeSet 的底層其實是搜索樹，而且是紅黑樹，那么中序遍歷搜索樹是有序的，也即按照 key 提供的比較方式，或者你自己提供的比較器，關于 key 是有序的。

class Person implements Comparable<Person> {
    private String name;
    private int age;
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public int compareTo(Person o) {
        return this.age - o.age;
    }
}

public class Test {
    public static void main(String[] args) {
        TreeMap<Person, Integer> map = new TreeMap<>();
        map.put(new Person("張三", 12), 1);
        map.put(new Person("李四", 21), 2);
        map.put(new Person("王五", 16), 3);
        Set<Map.Entry<Person, Integer>> entrySet = map.entrySet();
        for (Map.Entry<Person, Integer> personIntegerEntry : entrySet) {
            System.out.println(personIntegerEntry);
        }
    }
}

由于 Map 沒有繼承于Iterable 接口，所以不能采用 for-each 遍歷，只能返回 Key-value 的映射關系放入 Set 中進行遍歷。

上述代碼是按照 Person 中的年齡進行比較的，所以如果最終打印出來的結果是 12 21 16 這樣的年齡排序的順序話，也足以說明，在 TreeMap 和 TreeSet 中是關于 key 有序的，打印結果：

看到這，可能有的小伙伴說，確實是關于 key 有序，但是怎么保證底層是一棵搜索樹呢？其實也很簡單驗證，搜索樹前幾期也講過，如果是按照我們 Person 類比較的方式的話，那么根節(jié)點的左邊都小于它，根節(jié)點的右邊都大于它，這里我們通過調試看看 map 中存儲的結構就ok了：

這里我們通過調試的方式進入到源碼中，輸入我們想觀察的變量，于是可以看到，確實是一棵搜索樹，而且不是簡單的二叉搜索樹，是一棵紅黑樹。

為什么是這里就能看出來是紅黑樹呢，因為如果是按照我們前面講二叉搜索樹的邏輯，?根節(jié)點一定是第一次插入的 “張三，12”，而這里跟節(jié)點為什么是 “王五，16”，因為當插入 “王五” 的時候，搜索樹的左右子樹高度不平衡了，紅黑樹進行了旋轉調整，至于更多底層實現細節(jié)，目前我們可以不用關心，由此也可能看出來并不是一棵簡單的二叉搜索樹。

6、TreeMap 和 TreeSet 的關系?

上期其實也提到過，Set 的底層其實就是 Map，而 TreeSet 也是一樣，底層仍然是 TreeMap，拿什么證明呢？其實我們來看 Set 的構造方法就可以了：

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

public TreeSet() {
    this(new TreeMap<E,Object>());
}

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}

這里的 NavigableMap 也是一個繼承 SortedMap 的接口，因此具有SortedMap，Map接口的屬性方法，通過上述的構造方法也能看出，當你實例化一個 TreeSet 對象的時候，本質上還是 new 了一個 TreeMap 對象。而能明顯看到，value 為一個 Object 默認對象。

7、總結

TreeMap 和 TreeSet 底層都是紅黑樹，插入刪除查找的時間復雜度為 O(logN)，數據關于 key 是有序的，key 必須要能夠比較，不然會拋出 ClassCastException 異常，主要運用于需要 key 有序的場景下，TreeMap 和 TreeSet 是線程不安全的。?

下期預告：【Java 數據結構】HashMap和HashSet文章來源地址http://www.zghlxwxcb.cn/news/detail-808213.html

到了這里，關于【Java 數據結構】TreeMap和TreeSet的介紹的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！