思享工具箱

TreeMap 的排序冲突吗

摘要：
今天，我在网上看到一个问题：我如何才能完成已经构建的树集的反向排序？互联网上给出的答案是：通过TreeSet构造函数传入比较器，并指定要排序的比较器作为原始排序的闪回。TreeSet的自然排序基于集合元素的大小。TreeSet按升序对它们进行排序。如果需要实现自定义排序，则需要创建TreeSet集合对象并提供一个Comparator对象以与TreeSet集合关联。Comparator对象负责集合元素的排序逻辑。我们知道，如果要对TreeSet进行排序，必须使添加的对象可排序，否则将出现错误java.lang.ClassCastException。

今天在网上看到一个问题：一个已经构建好的 TreeSet，怎么完成倒排序？

网上给出的答案是：

通过TreeSet构造函数传入一个比较器，指定比较器进行排序为原排序的倒叙。
TreeSet的自然排序是根据集合元素的大小，TreeSet将他们以升序排列。如果需要实现定制排序，例如降序，则可以使用Comparator接口。该接口里包含一个int compare（T o1，T o2）方法，该方法用于比较o1和o2的大小。
如果需要实现定制排序，则需要在创建TreeSet集合对象时，并提供一个Comparator对象与该TreeSet集合关联，由该Comparator对象负责集合元素的排序逻辑。

我们知道，如果要实现TreeSet 的 排序（或者说让一个TreeSet可用），必须让加入的对象具有可排序性，否则就会报错 java.lang.ClassCastException。

实现思路有两个（二选一即可）：

1、加入的对象（相对于TreeMap，就是key对象，TreeSet 是通过 TreeMap 来实现的）需要实现 Comparable 接口

package com.cd.demo;

import java.util.Set;
import java.util.TreeSet;

public class TreeSetTest1 {

    public static void main(String[] args) {
        // 构造一个可用的TreeSet对象：传入对象实现 Comparable 接口 （按照年龄排序）
        Set<User> userSet = new TreeSet<>();
        userSet.add(new User(5, 32, "阿布1"));
        userSet.add(new User(12, 25, "阿布2"));
        userSet.add(new User(9, 36, "阿布3"));
        userSet.add(new User(20, 34, "阿布4"));
        userSet.add(new User(15, 48, "阿布5"));
        for (User u : userSet) {
            System.out.println(u.toString());
        }
    }

    // static 内部类，可以在main方法中 直接使用new User(...)初始化，否则就要：new TreeSetTest().new User(...) 才行
    static class User implements Comparable<User> {
        Integer id;

        Integer age;

        String name;

        public User(Integer id, int age, String name) {
            super();
            this.id = id;
            this.age = age;
            this.name = name;
        }

        public Integer getId() {
            return id;
        }

        public void setId(Integer id) {
            this.id = id;
        }

        public Integer getAge() {
            return age;
        }

        public void setAge(Integer age) {
            this.age = age;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        @Override
        public String toString() {
            return "User [id=" + id + ", age=" + age + ", name=" + name + "]";
        }

        @Override
        public int compareTo(User arg0) {
            return this.age.compareTo(arg0.getAge());
        }
    }

}
User [id=12, age=25, name=阿布2]
User [id=5, age=32, name=阿布1]
User [id=20, age=34, name=阿布4]
User [id=9, age=36, name=阿布3]
User [id=15, age=48, name=阿布5]

2、TreeSet初始化时需要一个 Comparator 接口实例 的入参

package com.cd.demo;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public class TreeSetTest2 {

    public static void main(String[] args) {
        // 构造一个可用的TreeSet对象：传入一个Comparator 接口实例作为入参 （按照id排序）
        Set<User> userSet = new TreeSet<>(new Comparator<User>() {
            @Override
            public int compare(User arg0, User arg1) {
                return arg0.getId().compareTo(arg1.getId());
            }
        });
        // 因为 userSet 已经有入参 Comparator，故不会报错
        userSet.add(new User(5, 32, "阿布1"));
        userSet.add(new User(12, 25, "阿布2"));
        userSet.add(new User(9, 36, "阿布3"));
        userSet.add(new User(20, 34, "阿布4"));
        userSet.add(new User(15, 48, "阿布5"));
        for (User u : userSet) {
            System.out.println(u.toString());
        }
    }

    static class User {
        Integer id;

        Integer age;

        String name;

        public User(Integer id, int age, String name) {
            super();
            this.id = id;
            this.age = age;
            this.name = name;
        }

        public Integer getId() {
            return id;
        }

        public void setId(Integer id) {
            this.id = id;
        }

        public Integer getAge() {
            return age;
        }

        public void setAge(Integer age) {
            this.age = age;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        @Override
        public String toString() {
            return "User [id=" + id + ", age=" + age + ", name=" + name + "]";
        }

    }

}
User [id=5, age=32, name=阿布1]
User [id=9, age=36, name=阿布3]
User [id=12, age=25, name=阿布2]
User [id=15, age=48, name=阿布5]
User [id=20, age=34, name=阿布4]

　那么，现在问题来了，如果TreeSet中 保存的对象实现了 Comparable 接口，而 TreeSet 又传入了外部的 Comparator，会怎么样呢，会出现排序冲突吗？

看代码：

package com.cd.demo;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public class TreeSetTest {

    public static void main(String[] args) {
        // 构造一个可用的TreeSet对象：要么传入一个Comparator 接口实例作为入参，要么 key 必须实现 Comparable 接口
        // 现在同时两个都满足，User内部按照 age 排序，外部 Comparator 按照id 排序，会怎么样呢
        Set<User> userSet = new TreeSet<>(new Comparator<User>() {
            @Override
            public int compare(User arg0, User arg1) {
                return arg0.getId().compareTo(arg1.getId());
            }
        });
        // 因为 userSet 已经有入参 Comparator，故不会报错
        userSet.add(new User(5, 32, "阿布1"));
        userSet.add(new User(12, 25, "阿布2"));
        userSet.add(new User(9, 36, "阿布3"));
        userSet.add(new User(20, 34, "阿布4"));
        userSet.add(new User(15, 48, "阿布5"));
        // userSet 构造测试（同时实现内外排序时，按照 Comparator 外部排序来） 
        for (User u : userSet) {
            System.out.println(u.toString());
        }
    }

    // static 内部类，可以在main方法中 直接使用new User(...)初始化，否则就要：new TreeSetTest().new User(...) 才行
    static class User implements Comparable<User> {
        Integer id;

        Integer age;

        String name;

        public User(Integer id, int age, String name) {
            super();
            this.id = id;
            this.age = age;
            this.name = name;
        }

        public Integer getId() {
            return id;
        }

        public void setId(Integer id) {
            this.id = id;
        }

        public Integer getAge() {
            return age;
        }

        public void setAge(Integer age) {
            this.age = age;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        @Override
        public String toString() {
            return "User [id=" + id + ", age=" + age + ", name=" + name + "]";
        }

        @Override
        public int compareTo(User arg0) {
            return this.age.compareTo(arg0.getAge());
        }
    }

}
User [id=5, age=32, name=阿布1]
User [id=9, age=36, name=阿布3]
User [id=12, age=25, name=阿布2]
User [id=15, age=48, name=阿布5]
User [id=20, age=34, name=阿布4]

　　可以看出，如果同时实现了内外排序（对象实现 Comparable 接口、TreeSet 初始化 传入 Comparator 接口对象），则排序 以 Comparator 的外部排序进行。

看一下TreeSet 的 add 方法源码，内部其实调用的是TreeMap 的 put：

public V put(K key, V value) {
  // 根节点
  Entry<K,V> t = root;
  // 如果根节点为空，则直接创建一个根节点，返回
  if (t == null) {
     // TBD:
     // 5045147: (coll) Adding null to an empty TreeSet should
     // throw NullPointerException
     //
     // compare(key, key); // type check
      root = new Entry<K,V>(key, value, null);
      size = 1;
      modCount++;
      return null;
  }
  // 记录比较结果
  int cmp;
  Entry<K,V> parent;
  // split comparator and comparable paths
  // 当前使用的比较器
  Comparator<? super K> cpr = comparator ;
  // 如果比较器不为空，就是用指定的比较器来维护TreeMap的元素顺序
  if (cpr != null) {
       // do while循环，查找key要插入的位置（也就是新节点的父节点是谁）
      do {
          // 记录上次循环的节点t
          parent = t;
          // 比较当前节点的key和新插入的key的大小
          cmp = cpr.compare(key, t. key);
           // 新插入的key小的话，则以当前节点的左孩子节点为新的比较节点
          if (cmp < 0)
              t = t. left;
          // 新插入的key大的话，则以当前节点的右孩子节点为新的比较节点
          else if (cmp > 0)
              t = t. right;
          else
        // 如果当前节点的key和新插入的key想的的话，则覆盖map的value，返回
              return t.setValue(value);
      // 只有当t为null，也就是没有要比较节点的时候，代表已经找到新节点要插入的位置
      } while (t != null);
  }
  else {
      // 如果比较器为空，则使用key作为比较器进行比较
      // 这里要求key不能为空，并且必须实现Comparable接口
      if (key == null)
          throw new NullPointerException();
      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<K,V>(key, value, parent);
  // 如果新节点key的值小于父节点key的值，则插在父节点的左侧
  if (cmp < 0)
      parent. left = e;
  // 如果新节点key的值大于父节点key的值，则插在父节点的右侧
  else
      parent. right = e;
  // 插入新的节点后，为了保持红黑树平衡，对红黑树进行调整
  fixAfterInsertion(e);
  // map元素个数+1
  size++;
  modCount++;
  return null;
}

注意看上面的下划线部分代码，jdk 中 默认是先使用 Comparator ，如果没有 Comparator ，才使用对象的 Comparable 接口。

那回到开篇的问题，如果需要实现倒序，就得分两种情况了：

1、只实现了 Comparable 的倒序；

2、实现了 Comparator 的倒序。

这两种情况，都可以通过 重新 建立一个 TreeSet，传入倒序的 Comparator 来实现倒序，伪代码为：

        Set<User> userSetNew = new TreeSet<>(new Comparator<User>() {
            @Override
            public int compare(User arg0, User arg1) {
                return ...; // 新的排序逻辑
            }
        });
        userSetNew.addAll(userSetOld);
        System.out.println("---------------  倒序后  ----------------");
        for (User u : userSetNew ) {
            System.out.println(u.toString());
        }

这个思路有一种投机取巧的方法，就是 compare 方法中默认返回 -1，比如上面的代码实现倒序可以为：

package com.cd.demo;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public class TreeSetTest {

    public static void main(String[] args) {
        // 构造一个可用的TreeSet对象：要么传入一个Comparator 接口实例作为入参，要么 key 必须实现 Comparable 接口
        // 现在同时两个都满足，User内部按照 age 排序，外部 Comparator 按照id 排序，会怎么样呢
        Set<User> userSet = new TreeSet<>(new Comparator<User>() {
            @Override
            public int compare(User arg0, User arg1) {
                return arg0.getId().compareTo(arg1.getId());
            }
        });
        // 因为 userSet 已经有入参 Comparator，故不会报错
        userSet.add(new User(5, 32, "阿布1"));
        userSet.add(new User(12, 25, "阿布2"));
        userSet.add(new User(9, 36, "阿布3"));
        userSet.add(new User(20, 34, "阿布4"));
        userSet.add(new User(15, 48, "阿布5"));
        // userSet 构造测试（同时实现内外排序时，按照 Comparator 外部排序来） 
        for (User u : userSet) {
            System.out.println(u.toString());
        }

        Set<User> userSet2 = new TreeSet<>(new Comparator<User>() {
            @Override
            public int compare(User arg0, User arg1) {
                return -1;
            }
        });
        userSet2.addAll(userSet);
        System.out.println("---------------  倒序后  ----------------");
        for (User u : userSet2) {
            System.out.println(u.toString());
        }
    }

    // static 内部类，可以在main方法中 直接使用new User(...)初始化，否则就要：new TreeSetTest().new User(...) 才行
    static class User implements Comparable<User> {
        Integer id;

        Integer age;

        String name;

        public User(Integer id, int age, String name) {
            super();
            this.id = id;
            this.age = age;
            this.name = name;
        }

        public Integer getId() {
            return id;
        }

        public void setId(Integer id) {
            this.id = id;
        }

        public Integer getAge() {
            return age;
        }

        public void setAge(Integer age) {
            this.age = age;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        @Override
        public String toString() {
            return "User [id=" + id + ", age=" + age + ", name=" + name + "]";
        }

        @Override
        public int compareTo(User arg0) {
            return this.age.compareTo(arg0.getAge());
        }
    }

}
User [id=5, age=32, name=阿布1]
User [id=9, age=36, name=阿布3]
User [id=12, age=25, name=阿布2]
User [id=15, age=48, name=阿布5]
User [id=20, age=34, name=阿布4]
---------------  倒序后  ----------------
User [id=20, age=34, name=阿布4]
User [id=15, age=48, name=阿布5]
User [id=12, age=25, name=阿布2]
User [id=9, age=36, name=阿布3]
User [id=5, age=32, name=阿布1]

　　

标签：#string | 浏览：101 | 发布日期：

免责声明：文章转载自《TreeMap 的排序冲突吗》仅用于学习参考。如对内容有疑问，请及时联系本站处理。

上篇visual studio code 输出乱码enum class的基于namespace的实现下篇

宿迁高防，2C2G15M，22元/月；香港BGP，2C5G5M，25元/月 雨云优惠码：MjYwNzM=

相关文章

RedisTemplate访问Redis数据结构（三）——Hash

HashOperations提供一系列方法操作hash。首先初始化spring工厂获得redisTemplate和opsForHash private RedisTemplate<String,Object> redisTemplate; private HashOperations<String,String,Objec...

Java编程：根据给定的日期，计算两个日期之间的时间差

计算两个Date之间的时间差，基本思路为把Date转换为ms（微秒），然后计算两个微秒时间差。 时间的兑换规则如下： 1s秒 = 1000ms毫秒 1min分种 = 60s秒 1hours小时 = 60min分钟 1day天 = 24hours小时   package com.qiyadeng.date; import java.text.SimpleDa...

在EggJS中使用Sequelize做联表查询

内容转自https://www.jianshu.com/p/078087c69b77，感谢 1.EggJS引用Sequelize 安装sequelize依赖和mysql驱动 cnpm i egg-sequelize mysql2 -S 启用sequelize插件 　　在config/plugin.js里面添加 sequelize: { enable...

生成唯一id写法，雪花算法

这个工具直接调用就可以了，用法和写法如下： 代码： 这个是雪花算法的写法： 1 public classSnowFlakeUtil { 2 3 /** 4 * 起始的时间戳 5 */ 6 private final static long START_STMP = 1480166465631L; 7 8 /** 9 *...

对C#委托和事件委托的理解

委托的声明 public delegate void MyDelegate(string str);注1.委托的定义和方法的定义类似，只是在前面加了一个delegate,但委托不是方法，它是一种类型。是一种特殊的类型,看成是一种新的对象类型比较好理解。用于对与该委托有相 同签名的方法调用。2.委托相当于C++中的函数指针，但它是类型安全的。3.委托是从...

mysql和Oracle在对clob和blob字段的处理

一、MySQL与Oracle数据库如何处理Clob，Blob数据类型 (1)不通数据库中对应clob,blob的类型如下： MySQL中：clob对应text，blob对应blob DB2/Oracle中：clob对应clob，blob对应blob (2)domain中对应的类型： clob对应String，blob对应byte[] clob对应ja...

最新文章

随机推荐

思享工具箱导航