Java集合中的TreeMap解讀

更新時(shí)間：2023年09月13日 09:12:34 作者：蕾峰

這篇文章主要介紹了Java集合中的TreeMap解讀,TreeMap可以傳入一個(gè)實(shí)現(xiàn)了 Comparator接口的一個(gè)匿名內(nèi)部類,匿名內(nèi)部類里面我們?nèi)匀豢梢匀ブ付ㄌ砑游覀兊逆I值對(duì)的這種排序規(guī)則,需要的朋友可以參考下

TreeMap解讀

TreeSet的底層是TreeMap。

public boolean add(E e) {
        return m.put(e, PRESENT)==null;
//其中的e為我們放進(jìn)去的元素，作為key來存放的。
//而后面的value為PRESENT為一個(gè)固定的值，
    }

而其中的PRESENT是在treeSet里面創(chuàng)建的靜態(tài)的final類型的Object.

private static final Object PRESENT = new Object();

如果我們使用TreeMap，里面放置的是（e為Key，PRESENT為對(duì)應(yīng)的那一個(gè)值）。

我們通過具體的代碼設(shè)計(jì)如下所示：

package com.rgf.map;
import java.util.TreeMap;
@SuppressWarnings({"all"})
public class TreeMap_ {
    public static void main(String[] args) {
        //使用默認(rèn)的構(gòu)造器，創(chuàng)建TreeMap,是無序的，是指輸入輸出的順序不一致
        TreeMap treeMap = new TreeMap();
        treeMap.put("jack","杰克");
        treeMap.put("tom","湯姆");
        treeMap.put("kristina","克瑞斯提諾");
        treeMap.put("smith","斯密斯");
        System.out.println("treeMap="+treeMap);
    }
}
}

運(yùn)行界面如下所示：

我們查看如下所示：

我們發(fā)現(xiàn)TreeMap類里面除了提供無參的類以外，也有TreeMap(Comparator <K>)這樣子的構(gòu)造器。TreeMap可以傳入一個(gè)實(shí)現(xiàn)了 Comparator接口的一個(gè)匿名內(nèi)部類，匿名內(nèi)部類里面我們?nèi)匀豢梢匀ブ付ㄌ砑游覀兊逆I值對(duì)的這種排序規(guī)則。

我們?cè)O(shè)計(jì)排序規(guī)則進(jìn)行如下代碼所示：

package com.rgf.map;
import java.util.Comparator;
import java.util.TreeMap;
@SuppressWarnings({"all"})
public class TreeMap_ {
    public static void main(String[] args) {
        //使用默認(rèn)的構(gòu)造器，創(chuàng)建TreeMap,是無序的，是指輸入輸出的順序不一致
        //我們按照傳入的k(String)的大小進(jìn)行排序。
        TreeMap treeMap = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                //我們按照傳入的k(String)的大小進(jìn)行排序。
                return ((String) o1).compareTo((String)o2);
            }
        });
        treeMap.put("jack","杰克");
        treeMap.put("tom","湯姆");
        treeMap.put("Kristina","克瑞斯提諾");
        treeMap.put("smith","斯密斯");
        System.out.println("treeMap="+treeMap);
    }
}

我們運(yùn)行之后如下所示：

以上排序?yàn)閺男〉酱?，我們可以將排序修改為從大到小，我們進(jìn)行修改代碼如下所示：

package com.rgf.map;
import java.util.Comparator;
import java.util.TreeMap;
@SuppressWarnings({"all"})
public class TreeMap_ {
    public static void main(String[] args) {
        //使用默認(rèn)的構(gòu)造器，創(chuàng)建TreeMap,是無序的，是指輸入輸出的順序不一致
        //我們按照傳入的k(String)的大小進(jìn)行排序。
        TreeMap treeMap = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                //我們按照傳入的k(String)的大小進(jìn)行排序。(從小到大）
                return ((String) o2).compareTo((String)o1);
            }
        }) ;
        treeMap.put("jack","杰克");
        treeMap.put("tom","湯姆");
        treeMap.put("kristina","克瑞斯提諾");
        treeMap.put("smith","斯密斯");
        System.out.println("treeMap="+treeMap);
    }
}

運(yùn)行界面如下所示：

我們可以按照長度進(jìn)行排序（從小到大），我們將代碼修改如下所示:

package com.rgf.map;
import java.util.Comparator;
import java.util.TreeMap;
@SuppressWarnings({"all"})
public class TreeMap_ {
    public static void main(String[] args) {
        //使用默認(rèn)的構(gòu)造器，創(chuàng)建TreeMap,是無序的，是指輸入輸出的順序不一致
        //我們按照傳入的k(String)的大小進(jìn)行排序。
        TreeMap treeMap = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                //我們按照傳入的k(String)的長度大小進(jìn)行排序。(從小到大）
                return ((String) o1).length()-((String) o2).length();
            }
        }) ;
        treeMap.put("jack","杰克");
        treeMap.put("tom","湯姆");
        treeMap.put("kristina","克瑞斯提諾");
        treeMap.put("smith","斯密斯");
        System.out.println("treeMap="+treeMap);
    }
}

我們的運(yùn)行界面如下所示：

我們也可以將排序找到長度從大到小，我們將代碼修改如下所示：

package com.rgf.map;
import java.util.Comparator;
import java.util.TreeMap;
@SuppressWarnings({"all"})
public class TreeMap_ {
    public static void main(String[] args) {
        //使用默認(rèn)的構(gòu)造器，創(chuàng)建TreeMap,是無序的，是指輸入輸出的順序不一致
        //我們按照傳入的k(String)的大小進(jìn)行排序。
        TreeMap treeMap = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                //我們按照傳入的k(String)的長度大小進(jìn)行排序。(從小到大）
                return ((String) o2).length()-((String) o1).length();
            }
        }) ;
        treeMap.put("jack","杰克");
        treeMap.put("tom","湯姆");
        treeMap.put("kristina","克瑞斯提諾");
        treeMap.put("smith","斯密斯");
        System.out.println("treeMap="+treeMap);
    }
}

運(yùn)行界面如下所示:

我們來進(jìn)行Debug，我們從如下代碼開始進(jìn)行debug:

TreeMap treeMap = new TreeMap(new Comparator()

源碼

1.構(gòu)造器

把傳入的實(shí)現(xiàn)了Comparator接口的匿名內(nèi)部類（對(duì)象），傳給了TreeMap的comparator屬性。

 //他的底層仍然是TreeMap,把傳入的匿名內(nèi)部類comparator賦給TreeMap的一個(gè)屬性this.comparator.
 public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

我們退出去之后，進(jìn)去put方法：

2.調(diào)用put方法

第一次添加，把k-v封裝到Entry對(duì)象，放入root.

源碼如下所示；

public V put(K key, V value) {
        Entry<K,V> t = root;//此時(shí)root為空,將root賦值給t.
//我們第一次進(jìn)去，所以還沒有進(jìn)行初始化，第一次初始化為空。
        if (t == null) {//此時(shí)t為空，從而進(jìn)入里面代碼。
            compare(key, key); // type (and possibly null) check
//比較key值是否相同，構(gòu)造器判斷規(guī)則不同，key值不同，當(dāng)前規(guī)則為比較長度大小。則長度為key.
//TreeMap底層為Entry,Entry為TreeMap里面的一個(gè)內(nèi)部類。
            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);
        }

我們進(jìn)行第一次添加之后，我們?nèi)缦滤荆?/p>

以后添加，即要使用比較器進(jìn)行比較后添加。

此時(shí)root里面已經(jīng)有值了。此時(shí)添加第一個(gè)值得時(shí)候，沒有添加比較器。我們繼續(xù)進(jìn)行添加，查看源碼。

public V put(K key, V value) {
        Entry<K,V> t = root;
//由于此前已經(jīng)有一個(gè)值了，此時(shí)root不為null.t也不為空，即不再進(jìn)入下面第一個(gè)if語句。
        if (t == null) {
//第一次進(jìn)去也調(diào)用了compare方法，即動(dòng)態(tài)綁定了我們的匿名內(nèi)部類的compare方法，傳入的是兩個(gè)key,即第一次添加的key加了兩份進(jìn)去。目的是為了判定是否為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
//由于已經(jīng)有一個(gè)值了，所以我們會(huì)將比較器拿到，進(jìn)入以下代碼。
        Comparator<? super K> cpr = comparator;//比較器傳入的值賦值給cpr
        if (cpr != null) {
            do { //遍歷所有的key,給當(dāng)前key找到適當(dāng)?shù)奈恢?
                parent = t; //我們傳入的comparator賦值給parent
                cmp = cpr.compare(key, t.key); //動(dòng)態(tài)綁定到我們的匿名內(nèi)部類的compare方法。
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else  //如果遍歷過程中，發(fā)現(xiàn)準(zhǔn)備添加key和當(dāng)前已有的key相等，就不添加了，但是會(huì)進(jìn)行覆蓋原來的值。是由我們自定義的compare方法來決定的。
                    return t.setValue(value);
            } while (t != null);
        }

我們會(huì)動(dòng)態(tài)綁定到我們的匿名內(nèi)部類：

我們調(diào)用了compare方法了：

我們繼續(xù)往進(jìn)走：

  final int compare(Object k1, Object k2) {
//如果comparator不等于null的時(shí)候，我們進(jìn)行動(dòng)態(tài)綁定到我們的匿名內(nèi)部類的compare方法。
        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }

我們會(huì)動(dòng)態(tài)綁定到我們的匿名內(nèi)部類：

此時(shí)的o1和o2都是jack.但是這個(gè)結(jié)果對(duì)是否添加當(dāng)前的value值有任何影響。主要是為了檢測(cè)是否為null。如果為null，則會(huì)在comparator方法里面拋出異常。

這里的compare作用是查看key是否為空，還有就是判斷當(dāng)前key是否實(shí)現(xiàn)了compareable接口是否是可以進(jìn)行比較的。

我們進(jìn)行排序的示例如下所示：

package com.rgf.jihe;
import org.junit.Test;
import java.util.*;
/**
 * 向TreeMap中添加key-value,要求key必須是由同一個(gè)類創(chuàng)建的對(duì)象
 * 因?yàn)橐凑誯ey進(jìn)行排序：自然排序、定制排序
 *
 */
public class TreeMapTest {
    public static void main(String[] args) {
        //自然排序
        TreeMap map = new TreeMap();
        User u1 = new User("Tom",23);
        User u2 = new User("Jerry",32);
        User u3 = new User("Jack",20);
        User u4 = new User("Rose",18);
        map.put(u1,98);
        map.put(u2,89);
        map.put(u3,76);
        map.put(u4,100);
        Set set = map.entrySet();
        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            Object next = iterator.next();
            System.out.println(next);
        }
    }
    //定制排序
    @Test
    public  void test2(){
        TreeMap map = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof User && o2 instanceof User){
                    User user=(User) o1;
                    User user1=(User) o2;
                    return  Integer.compare(user.getAge(),user1.getAge());
                }
                throw new RuntimeException("輸入的類型不匹配");
            }
        });
        User user = new User("rgf",123);
        User user1 = new User("woer",456);
        User user2 = new User("fed",789);
       map.put(user1,55);
       map.put(user,66);
       map.put(user2,77);
        Set set = map.entrySet();
        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            Object next = iterator.next();
            System.out.println(next);
        }
    }
}
class User implements  Comparable{
    private String name;
    private int age;
    public User() {
    }
    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }
    //我們寫出來該方法則不會(huì)再繼續(xù)報(bào)錯(cuò)。
//按照姓名從大到小排列,年齡從小到大排列
    @Override
    public int compareTo(Object o) {
        if(o instanceof User){
            User User=(com.rgf.jihe.User)o;
            //return -this.name.compareTo(user.name);為了可以確保相同的值可以進(jìn)行排序，我們進(jìn)行二級(jí)排序
            int compare=-this.name.compareTo(User.name);
            if(compare!=0){//如果相等，則我們進(jìn)行比較年齡
                return compare;
            }else {
                return Integer.compare(this.age,User.age);
            }
        }else {
            throw  new RuntimeException("輸入的類型不匹配");
        }
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public String toString() {
        return "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User User = (com.rgf.jihe.User) o;
        if (age != User.age) return false;
        return Objects.equals(name, User.name);
    }
    @Override
    public int hashCode() {
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + age;
        return result;
    }
}

運(yùn)行之后如下所示：