您的位置 首页 java

Java集合 – TreeMap类详解

智云科技发布于 2023年1月25日评论关闭阅读(147)

前言

TreeMap的基本概念：

  • TreeMap集合是基于红黑树（Red-Black tree）的 NavigableMap实现。该集合最重要的特点就是 可排序 ，该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。这句话是什么意思呢？就是说TreeMap可以对添加进来的元素进行排序，可以按照默认的排序方式，也可以自己指定排序方式。
  • 根据上一条，我们要想使用TreeMap存储并排序我们自定义的类（如User类），那么必须自己定义比较机制：一种方式是User类去实现java.lang.Comparable接口，并实现其compareTo()方法。另一种方式是写一个类（如MyCompatator）去实现java.util.Comparator接口，并实现compare()方法，然后将MyCompatator类实例对象作为TreeMap的构造方法参数进行传参（当然也可以使用匿名内部类），这些比较方法是怎么被调用的将在源码中讲解。
  • Map集合体系类图。

  • TreeMap继承类图

  • SortedMap接口 
 public interface SortedMap<K,V> extends Map<K,V> {
      // 返回排序数据所用的Comparator
      Comparator<? super K> comparator();

      // 返回在[fromKey, toKey)之间的数据
     SortedMap<K,V> subMap(K fromKey, K toKey);

     // 返回从第一个元素到toKey之间的数据
     SortedMap<K,V> headMap(K toKey);

     // 返回从fromKey到末尾之间的数据
     SortedMap<K,V> tailMap(K fromKey);

     //返回第一个数据的key
     K firstKey();

     //返回最后一个数据的key
     K lastKey();
}
  • NavigableMap接口 
 public interface NavigableMap<K,V> extends SortedMap<K,V> {
    //返回原map中小于且最接近key的键值对（不包含等于）
    Map.Entry<K,V> lowerEntry(K key);

    //返回小于且最接近key的键（不包含等于)
    K lowerKey(K key);

    //返回小于且最接近key的键值对（包含等于）
    Map.Entry<K,V> floorEntry(K key);

    //返回最接近的大于key的键（包含等于）
    K floorKey(K key);

    //返回最接近的大于等于key的键值对
    Map.Entry<K,V> ceilingEntry(K key);

    //返回最接近的大于等于key的键
    K ceilingKey(K key);

    //返回最接近的大于key的键值对
    Map.Entry<K,V> higherEntry(K key);

    //返回最接近的大于key的键
    K higherKey(K key);

    //返回最小的Entry
    Map.Entry<K,V> firstEntry();

    //返回最大的Entry
    Map.Entry<K,V> lastEntry();

    //删除并返回最小的Entry
    Map.Entry<K,V> pollFirstEntry();

    //删除并返回最大的Entry
    Map.Entry<K,V> pollLastEntry();

    //返回一个与原map反向顺序的视图，仍然是同一个map，操作会互相影响
    NavigableMap<K,V> descendingMap();

    //返回一个所有key键的视图
    NavigableSet<K> navigableKeySet();

     //返回一个所有key键的视图，顺序是逆序
    NavigableSet<K> descendingKeySet();

    //返回fromKey到toKey的map视图，通过fromInclusive与toInclusive控制是否包含
    NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                             K toKey,   boolean toInclusive);

    //返回小于toKey的键值对的视图（inclusive为true代表包含等于）
    NavigableMap<K,V> headMap(K toKey, boolean inclusive);

    //返回大于fromKey的键值对视图（inclusive为true代表包含等于）
    NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);

    //范围 [fromKey, toKey) 的视图
    SortedMap<K,V> subMap(K fromKey, K toKey);

    //小于toKey的map视图
    SortedMap<K,V> headMap(K toKey);

    //大于等于fromKey的map视图
    SortedMap<K,V> tailMap(K fromKey);
}

正文

TreeMap源码分析

1，类名及类成员变量 

 public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    // 比较器对象
    private final Comparator<? super K> comparator;

    // 根节点
    private transient Entry<K,V> root;

    // 集合大小
    private transient int size = 0;

    // 树结构被修改的次数
    private transient int modCount = 0;

    // 静态内部类用来表示节点类型
    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; // 
    }
}

2，类构造方法 

     public TreeMap() {   // 1,无参构造方法
        comparator = null; // 默认比较机制
    }

    public TreeMap(Comparator<? super K> comparator) { // 2，自定义比较器的构造方法
        this.comparator = comparator;
    }

    public TreeMap(Map<? extends K, ? extends V> m) {  // 3，构造已知Map对象为TreeMap
        comparator = null; // 默认比较机制
        putAll(m);
    }

    public TreeMap(SortedMap<K, ? extends V> m) { // 4，构造已知的SortedMap对象为TreeMap
        comparator = m.comparator(); // 使用已知对象的构造器
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }

3，put()方法详解 

     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;    // 集合大小为1
            modCount++;  // 结构修改次数自增
            return null;
        }

        int cmp;
        Entry<K,V> parent;
        Comparator<? super K> cpr = comparator;  // 比较器对象

        // 如果比较器对象不为空，也就是自定义了比较器
        if (cpr != null) {   
            do { // 循环比较并确定元素应插入的位置(也就是找到该元素的父节点)
                parent = t;  // t就是root

                // 调用比较器对象的compare()方法，该方法返回一个整数
                cmp = cpr.compare(key, t.key); 
                if (cmp < 0)      // 待插入元素的key"小于"当前位置元素的key，则查询左子树
                    t = t.left;
                else if (cmp > 0) // 待插入元素的key"大于"当前位置元素的key，则查询右子树
                    t = t.right;
                else              // "相等"则替换其value。
                    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)       // 待插入元素的key"小于"当前位置元素的key，则查询左子树
                    t = t.left;
                else if (cmp > 0)  // 待插入元素的key"大于"当前位置元素的key，则查询右子树
                    t = t.right;
                else               // "相等"则替换其value。
                    return t.setValue(value);
            } while (t != null);
        }

        Entry<K,V> e = new Entry<>(key, value, parent);  // 根据key找到父节点后新建一个节点
        if (cmp < 0)  // 根据比较的结果来确定放在左子树还是右子树
            parent.left = e;
        else
            parent.right = e;
        fixAfterInsertion(e);
        size++;      // 集合大小+1
        modCount++;  // 集合结构被修改次数+1
        return null;
    }

3.1，自定义比较器的使用。说了这么多关于比较器的内容，不上手试试这么能行？

  • 先来看下面这段代码 
 package com.jimmy.map;

import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;

public class TreeMapDemo2 {
    public static void main(String[] args) {
        Map<String, String> map = new TreeMap<>();

        map.put("ddd", "444");
        map.put("ccc", "333");
        map.put("bbb", "222");
        map.put("aaa", "111");

        Set<Entry<String, String>> entrySet = map.entrySet();
        for (Entry<String, String> each : entrySet) {
            System.out.println(each.getKey()+"::"+each.getValue());
        }
    }
}

输出结果如下，结果是排序过的，为什么呢？那是因为String类实现了Comparable接口并实现了compareTo()方法，该方法按字典顺序比较两个字符串，请自行查看其实现。 

 aaa::111
bbb::222
ccc::333
ddd::444
  • 下面我们写个自定义User类，使用2种方式将类对象按照age字段从小到大排序。

方式1，User实现Comparable接口并实现了compareTo()方法

User类 

 package com.jimmy.domain;

public class User implements Comparable<User>{
    private String username;
    private int age;

    public User(String username, int age) {
        this.username = username;
        this.age = age;
    }

    @Override
    public String toString() {
        return "User [username=" + username + ", age=" + age + "]";
    }
    @Override
    public int compareTo(User user) {
        int temp = this.age - user.age;
        return temp == 0 ? this.username.compareTo(user.username) : temp;
    }   
}

测试代码 

 package com.jimmy.map;

import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;

import com.jimmy.domain.User;

public class TreeMapDemo1 {
    public static void main(String[] args) {
        Map<User, String> map = new TreeMap<>();

        map.put(new User("jimmy1", 30), "hello");
        map.put(new User("jimmy2", 30), "hello");
        map.put(new User("jimmy", 22), "hello");
        map.put(new User("jimmy", 20), "hello");

        Set<Entry<User, String>> entrySet = map.entrySet();
        for (Entry<User, String> each : entrySet) {
            System.out.println(each.getKey()+"::"+each.getValue());
        }
    }
}

输出结果如下，首先按age排序，若年龄相等则再按username的字母表顺序排序。 

 User [username=jimmy, age=20]::hello
User [username=jimmy, age=22]::hello
User [username=jimmy1, age=30]::hello
User [username=jimmy2, age=30]::hello

方式2，写一个类实现java.util.Comparator接口，并将该类对象传递给TreeMap的构造方法。这种方式将实体类和比较机制解耦合，可以写很多个不同的比较器对象。

实体类 

 package com.jimmy.domain;

public class User3 {  // User对象不再实现任何接口
    private String username;
    private int age;

    public User3(String username, int age) {
        super();
        this.username = username;
        this.age = age;
    }
    public String getUsername() {
        return username;
    }
    public void setUsername(String username) {
        this.username = username;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public String toString() {
        return "User3 [username=" + username + ", age=" + age + "]";
    }

}

比较器类 

 package com.jimmy.map;

import java.util.Comparator;
import com.jimmy.domain.User3;

public class TreeMapComparator implements Comparator<User3>{  // 比较器类

    @Override
    public int compare(User3 o1, User3 o2) {
        int temp = o1.getAge() - o2.getAge();
        return temp == 0 ? o1.getUsername().compareTo(o2.getUsername()) : temp;
    }
}

测试代码 

 package com.jimmy.map;

import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.Map.Entry;

import com.jimmy.domain.User3;

public class TreeMapDemo3 {
    public static void main(String[] args) {
        Map<User3, String> map = new TreeMap<>(new TreeMapComparator());

        map.put(new User3("jimmy1", 30), "hello");
        map.put(new User3("jimmy2", 30), "hello");
        map.put(new User3("jimmy", 22), "hello");
        map.put(new User3("jimmy", 20), "hello");

        Set<Entry<User3, String>> entrySet = map.entrySet();
        for (Entry<User3, String> each : entrySet) {
            System.out.println(each.getKey()+"::"+each.getValue());
        }
    }
}

输出结果如下，跟上面的相同。 

 User3 [username=jimmy, age=20]::hello
User3 [username=jimmy, age=22]::hello
User3 [username=jimmy1, age=30]::hello
User3 [username=jimmy2, age=30]::hello

当然，我们还可以不写比较器类，而是使用匿名内部类的形式来写比较器。 

 package com.jimmy.map;

import java.util.Comparator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.Map.Entry;

import com.jimmy.domain.User3;

public class TreeMapDemo4 {
    public static void main(String[] args) {
        Map<User3, String> map = new TreeMap<>(new Comparator<User3>() {

            @Override
            public int compare(User3 o1, User3 o2) {
                int temp = o1.getAge() - o2.getAge();
                return temp == 0 ? o1.getUsername().compareTo(o2.getUsername()) : temp;
            }
        });

        map.put(new User3("jimmy1", 30), "hello");
        map.put(new User3("jimmy2", 30), "hello");
        map.put(new User3("jimmy", 22), "hello");
        map.put(new User3("jimmy", 20), "hello");

        Set<Entry<User3, String>> entrySet = map.entrySet();
        for (Entry<User3, String> each : entrySet) {
            System.out.println(each.getKey()+"::"+each.getValue());
        }
    }
}

4，一般以getEntry()方法为基础的 获取元素 的方法，其中包括containsKey()，get()，remove()等。 

 final Entry<K,V> getEntry(Object key) {
        // 如果有自定义比较器对象，就按照自定义规则遍历二叉树
        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;
    }

5，一般以getFirstEntry()，getLastEntry()为基础的获取头和尾元素的方法，其中包括：firstKey()，lastKey()；firstEntry()，lastEntry()；pollFirstEntry()，pollLastEntry()； 

     final Entry<K,V> getFirstEntry() { // 获取第一个元素也就是最小的元素，一直遍历左子树
        Entry<K,V> p = root;
        if (p != null)
            while (p.left != null)
                p = p.left;
        return p;
    }

    final Entry<K,V> getLastEntry() { // 获取最后个元素也就是最大的元素，一直遍历右子树
        Entry<K,V> p = root;
        if (p != null)
            while (p.right != null)
                p = p.right;
        return p;
    }

6，keySet()和entrySet()方法，在讲HashMap的时候已经讲过了，Map没有迭代器，要将Map转化为Set，用Set的迭代器才能进行元素迭代。

使用案例

1，SortedMap接口的使用 

 static void testSortedMap(){
        SortedMap<String,String> map = new TreeMap<String,String>() ;// 通过子类实例化接口对象
        map.put("D、baidu","#34;) ;
        map.put("A、alibaba","www.alibaba.com") ;
        map.put("C、tencent","www.tencent.cn") ;
        map.put("B、csdn","www.csdn.cn") ;
        System.out.println("第一个元素的内容的key：" + map.firstKey() + " 对应的值：" + map.get(map.firstKey()));
        System.out.println("最后一个元素的内容的key：" + map.lastKey() + " 对应的值：" + map.get(map.lastKey())) ;
        System.out.println("返回小于指定范围的集合：") ;
        for(Map.Entry<String,String> me:map.headMap("B、csdn").entrySet()){
            System.out.println("\t|- " + me.getKey() + " --> " + me.getValue()) ;
        }
        System.out.println("返回大于指定范围的集合：") ;
        for(Map.Entry<String,String> me:map.tailMap("B、csdn").entrySet()){
            System.out.println("\t|- " + me.getKey() + " --> " + me.getValue()) ;
        }
        System.out.println("部分集合：") ;
        for(Map.Entry<String,String> me:map.subMap("A、alibaba","C、tencent").entrySet()){
            System.out.println("\t|- " + me.getKey() + " --> " + me.getValue()) ;
        }
    }

输出结果： 

 第一个元素的内容的key：A、alibaba 对应的值：www.alibaba.com
最后一个元素的内容的key：D、baidu 对应的值：
返回小于指定范围的集合：
|- A、alibaba --> www.alibaba.com
返回大于指定范围的集合：
|- B、csdn ---> www.csdn.cn
|- C、tencent ---> www.tencent.cn
|- D、baidu ---> 
部分集合：
|- A、alibaba ---> www.alibaba.com
|- B、csdn ---> www.csdn.cn

2，自然排序和自定义比较器 

 static void testTreeMap(){
        //使用自然排序
        TreeMap<String, String> map = new TreeMap<>();
        map.put("ddd", "444");
        map.put("ccc", "333");
        map.put("bbb", "222");
        map.put("aaa", "111");
        System.out.println("自然顺序-----------------------------------------");
        Set<Map.Entry<String, String>> entrySet = map.entrySet();
        for (Map.Entry<String, String> each : entrySet) {
            System.out.println(each.getKey()+"::"+each.getValue());
        }

        //自定义比较器
        TreeMap<String, String> map1 = new TreeMap<>((t1,t2)->t2.compareTo(t1));
        map1.put("ddd", "444");
        map1.put("ccc", "333");
        map1.put("bbb", "222");
        map1.put("aaa", "111");
        System.out.println("倒序-----------------------------------------");
        Set<Map.Entry<String, String>> entrySet1 = map1.entrySet();
        for (Map.Entry<String, String> each : entrySet1) {
            System.out.println(each.getKey()+"::"+each.getValue());
        }
    }

输出结果： 

 自然顺序-----------------------------------------
aaa::111
bbb::222
ccc::333
ddd::444
倒序-----------------------------------------
ddd::444
ccc::333
bbb::222
aaa::111

3，NavigableMap接口的使用 

 static void testNavigableMap(){
        // SortedMap接收TreeMap的实例
        NavigableMap<String, Integer> navigatorTreeMap = new TreeMap<>();
        // 增加元素
        navigatorTreeMap.put("aa", 11);
        navigatorTreeMap.put("bb", 22);
        navigatorTreeMap.put("cc", 33);
        navigatorTreeMap.put("dd", 44);
        navigatorTreeMap.put("ee", 55);
        navigatorTreeMap.put("ff", 55);
        navigatorTreeMap.put("gg", 55);

        // 7个元素：7
        System.out.println(navigatorTreeMap.size());
        // 返回大于等于cc的最小键：cc
        System.out.println(navigatorTreeMap.ceilingKey("cc"));
        // 返回一个键-值映射关系，它与大于等于cc的最小键关联：cc=33
        System.out.println(navigatorTreeMap.ceilingEntry("c"));
        // 返回逆序视图:{gg=55, ff=55, ee=55, dd=44, cc=33, bb=22, aa=11}
        System.out.println(navigatorTreeMap.descendingMap());
        // 最小键:aa
        System.out.println(navigatorTreeMap.firstKey());
        // 最小键对应的k-v键值对：aa=11
        System.out.println(navigatorTreeMap.firstEntry());
        // 返回一个键-值映射关系，它与小于等于给定键的最大键关联:bb=22
        System.out.println(navigatorTreeMap.floorEntry("c"));
        // 返回小于等于cc的最大键:cc
        System.out.println(navigatorTreeMap.floorKey("cc"));
        // 返回此映射的部分视图，其键值严格小于bb:{aa=11}
        System.out.println(navigatorTreeMap.headMap("bb"));
        // 同上小于等于（true）:{aa=11, bb=22}
        System.out.println(navigatorTreeMap.headMap("bb", true));
        // 返回一个键-值映射关系，它与小于等于给定键的最大键关联:cc=33
        System.out.println(navigatorTreeMap.higherEntry("c"));
        // 返回小于等于cc的最大键:dd
        System.out.println(navigatorTreeMap.higherKey("cc"));
        // 返回一个键-值映射关系，它与小于等于给定键的最大键关联:gg=55
        System.out.println(navigatorTreeMap.lastEntry());
        // 返回小于等于cc的最大键:gg
        System.out.println(navigatorTreeMap.lastKey());
        // 返回一个键-值映射关系，它与小于等于给定键的最大键关联:bb=22
        System.out.println(navigatorTreeMap.lowerEntry("c"));
        // 返回严格小于cc的最大键:bb
        System.out.println(navigatorTreeMap.lowerKey("cc"));
        // 移除并返回与此映射中的最小键关联的键-值映射关系:aa=11
        System.out.println(navigatorTreeMap.pollFirstEntry());
        // 移除并返回与此映射中的最大键关联的键-值映射关系:gg=55
        System.out.println(navigatorTreeMap.pollLastEntry());
        // 返回此映射中所包含键的,NavigableSet 视图。:[bb, cc, dd, ee, ff]
        System.out.println(navigatorTreeMap.navigableKeySet());
        // 返回部分视图，true表示包括当前元素键值对:{bb=22, cc=33, dd=44}
        System.out.println(navigatorTreeMap.subMap("aa", true, "dd", true));
        // 返回部分视图包括前面的元素，不包括后面的：{bb=22, cc=33}
        System.out.println(navigatorTreeMap.subMap("bb", "dd"));
        // 返回元素大于cc的元素映射视图,包括cc：//{cc=33, dd=44, ee=55, ff=55}
        System.out.println(navigatorTreeMap.tailMap("cc"));
        // 返回元素大于等于cc的元素映射视图:{dd=44, ee=55, ff=55}
        System.out.println(navigatorTreeMap.tailMap("cc", false));
        // 返回此映射中所包含映射关系的逆序：{ff=55, ee=55, dd=44, cc=33, bb=22}视图
        System.out.println(navigatorTreeMap.descendingMap());
        // 返回此映射中所包含键的逆序,NavigableSet视图:[ff, ee, dd, cc, bb]
        System.out.println(navigatorTreeMap.descendingKeySet());
    }

输出结果： 

 7
cc
cc=33
{gg=55, ff=55, ee=55, dd=44, cc=33, bb=22, aa=11}
aa
aa=11
bb=22
cc
{aa=11}
{aa=11, bb=22}
cc=33
dd
gg=55
gg
bb=22
bb
aa=11
gg=55
[bb, cc, dd, ee, ff]
{bb=22, cc=33, dd=44}
{bb=22, cc=33}
{cc=33, dd=44, ee=55, ff=55}
{dd=44, ee=55, ff=55}
{ff=55, ee=55, dd=44, cc=33, bb=22}
[ff, ee, dd, cc, bb]

总结

TreeMap继承了Map的性质，同时其树结构又可以进行元素排序，用处很大。

———————————————-

转载自：

标签:
打赏 点赞(1)

文章来源：智云一二三科技

文章标题：Java集合 – TreeMap类详解

文章地址：https://www.zhihuclub.com/197814.shtml

关于作者: 智云科技

相关文章

热门文章

1分享新浪图床上传接口源码

点赞(908)阅读(60,225)

2PHP简单实现路由Route功能

点赞(1.12K)阅读(35,951)

3Tideways、xhprof 和 xhgui 打造 PHP 非侵入式监控平台

点赞(334)阅读(4,280)

4centos系统如何查看是否安装了mysql

点赞(509)阅读(3,769)

5curl 工具简述

点赞(478)阅读(2,964)
网站地图