TreeMap 的排序及比较器问题

本贴最后更新于 3105 天前,其中的信息可能已经事过境迁

   TreeMap 默认按键的自然顺序升序进行排序,如果有需求要按键的倒序排序,或者按值类型进行排序呢?
   在问题开始之前,让我们先回顾一下有关 Map 及其排序基本的知识点

  1. 用的最多的 HashMap,不保证映射的顺序,特别是它不保证该顺序恒久不变。
  2. LinkedHashMap,维持元素的插入顺序。
  3. TreeMap 中有一个传入比较器的构造函数, Map 中的元素可按此比较器进行排序。

   以上 3 个知识点,前 2 个作为复习,最后一个才是本次使用的重点。要想改变 TreeMap 的默认比较次序,我们可以在其构造函数中传入一个自己的比较器。TreeMap 的比较器构造函数如下:

public TreeMap(Comparator<? super K> comparator)

Comaprator 排序接口定义如下:

public interface Comparator<T> { int compare(T o1, T o2); ....... //若干方法 }

Comparator 接口必须实现 compare()方法。返回的 int 值的正负表示两值的大小。本着先易后难原则,让我们先实现 TreeMap 按键倒序排序:

package top.wthfeng.hello; import java.util.Comparator; import java.util.Map; import java.util.TreeMap; public class Map2Test{ public static void main(String[]args){ Map<String,String> map = new TreeMap<>(new Comparator<String>(){ public int compare(String o1,String o2){ return o2.compareTo(o1); //用正负表示大小值 } }); //以上4行可用下面一行lambda表达式代替 //Map<String,String> map1 = new TreeMap<>((o1,o2)->o2.compareTo(o1)); map.put("zdef","rfgh"); map.put("asrg","zfg"); map.put("rgd","dfgh"); map.put("cbf","gddf"); for(Map.Entry<String,String> entry:map.entrySet()){ System.out.println("key:"+entry.getKey()+",:value:"+entry.getValue()); } } } //输出结果(倒序): key:zdef,:value:rfgh key:rgd,:value:dfgh key:cbf,:value:gddf key:asrg,:value:zfg

   在 TreeMap 的构造函数中传入实现了 Comparator 接口的类实例(本例以内部匿名类实现,道理都一样,匿名类更简单,当然 java8 以后更推荐使用 lambda 用法),该类的唯一方法 comparaTo()实现了比较算法。这样 TreeMap 的倒序排列就解决了。下面我们来研究 TreeMap 的按值排序。
   先想想思路,map 的按值排序是没有现成方法的,这里就要变换一下想法。在集合工具类 Collections 中有对集合进行排序的方法,还可传入一个比较器按比较器进行排序。方法签名如下:

public static <T> void sort(List<T> list,Comparator<? super T> c)

   这也就是说要是一个 list 的话,就像上面一样给传一个比较器,再调用 Collections.sort()方法就能解决,可这是 map 啊,那能不能将 map 转为 list 啊?直接看下面吧:

package top.wthfeng.hello; import java.util.*; public class MapTest{ public static void main(String[]args){ Map<String,String> map = new TreeMap<>(); map.put("zdef","rfgh"); map.put("asrg","zfg"); map.put("rgd","dfgh"); map.put("cbf","gddf"); //将Map转为List List<Map.Entry<String,String>> list = new ArrayList<>(map.entrySet()); Collections.sort(list, new Comparator<Map.Entry<String, String>>() { public int compare(Map.Entry<String, String> o1, Map.Entry<String, String> o2) { return o2.getValue().compareTo(o1.getValue()); } }); //重新排序 //运用lambda表达式 //Collections.sort(list,((o1, o2) -> o2.getValue().compareTo(o1.getValue()))); for(Map.Entry<String,String> entry:list){ System.out.println("key:"+entry.getKey()+",:value:"+entry.getValue()); } } } //输出(按值倒序) key:asrg,:value:zfg key:zdef,:value:rfgh key:cbf,:value:gddf key:rgd,:value:dfgh

   OK,TreeMap 的按值排序就这样解决了。让我们总结一下,以上 2 个例子用到了 Comparator 这个接口,而这个接口到底是个怎样的存在呢?

强行对某个对象 collection 进行整体排序 的比较函数。可以使用 Comparator 来控制某些数据结构(如有序 set 或有序映射)的顺序,或者为那些没有自然顺序的对象 collection 提供排序。

   以上是 Java API6 上的说明,我又参考了其他资料,大致可以认为:是为那些没有排序方法的类自定义一个排序方法的一种手段,由于和原数据类没有耦合,又称之为外部比较器。比如说你写了一个苹果类,Apple 有 weight 属性。现要将 Apple 以 weight 升序放到 list 中,那么你就可以像上面那样,写个类实现 Comparator,在 Collections.sort()中实现排序。

package top.wthfeng.hello.test; /** * 苹果类 */ public class Apple { /** * 重量 */ private Integer weight; /** * 价格 */ private Integer price; public Integer getPrice() { return price; } public void setPrice(Integer price) { this.price = price; } public Integer getWeight() { return weight; } public void setWeight(Integer weight) { this.weight = weight; } @Override public String toString() { //重写toString()方法,方面输出 StringBuilder sb = new StringBuilder(); sb.append("["); sb.append("Apple:(weight:"); sb.append(weight); sb.append(",price:"); sb.append(price); sb.append(")]"); return sb.toString(); } } package top.wthfeng.hello; import top.wthfeng.hello.test.Apple; import java.util.*; public class Test { //测试类 public static void main(String[] args) { List<Apple> apples = new ArrayList<>(); Random random = new Random(12); for (int i = 0; i < 10; i++) { //生成10个苹果,重量随机生成 Apple apple = new Apple(); apple.setWeight(random.nextInt(1000)); apples.add(apple); } for (Apple apple : apples) { //打印10个苹果的顺序 System.out.println("apple = " + apple); } Collections.sort(apples, new Comparator<Apple>() { //排序,传入一个比较器 @Override public int compare(Apple o1, Apple o2) { return o1.getWeight().compareTo(o2.getWeight()); } }); // Collections.sort(apples,(o1,o2)->o1.getWeight().compareTo(o2.getWeight())); for (Apple apple : apples) { //排序后的顺序 System.out.println(" sort apple = " + apple); } } } //输出 apple = [Apple:(weight:866,price:12)] apple = [Apple:(weight:556,price:33)] apple = [Apple:(weight:624,price:11)] apple = [Apple:(weight:750,price:15)] apple = [Apple:(weight:596,price:21)] apple = [Apple:(weight:568,price:22)] apple = [Apple:(weight:61,price:7)] apple = [Apple:(weight:695,price:14)] apple = [Apple:(weight:536,price:31)] apple = [Apple:(weight:505,price:3)] sort apple = [Apple:(weight:61,price:7)] sort apple = [Apple:(weight:505,price:3)] sort apple = [Apple:(weight:536,price:31)] sort apple = [Apple:(weight:556,price:33)] sort apple = [Apple:(weight:568,price:22)] sort apple = [Apple:(weight:596,price:21)] sort apple = [Apple:(weight:624,price:11)] sort apple = [Apple:(weight:695,price:14)] sort apple = [Apple:(weight:750,price:15)] sort apple = [Apple:(weight:866,price:12)]

   按 weight 排序完成。总结一下:我们自定义的类想按某个字段排序,可以利用 Collections 的 sort 方法传入一个自定义的比较器,这种比较器与被比较的类不发生耦合,称为外部比较器。
   那么问题来了,如果我的 Apple 类默认排序是按价格,特殊情况才按重量。总不能每次排序时都要写遍比较器实现吧?这也太麻烦了。不知大家注意到没有,在实现 Comparator 接口中,都有类似下面的句子:

return o2.compareTo(o1);

   那 compareTo()方法从哪来的?o1,o2 是 String 类型,compareTo()正是 String 实现的 Comparable 接口的方法。那么 Comparable 又是什么鬼?

Comparable 接口对实现它的每个类的对象进行整体排序,这种排序称为类的自然排序,类的 compareTo 方法被称为类的比较方法。

   有点眉目了,再看看 Comparable 的解释,发现 java 中所有值类都实现了 Comparable 方法。像 String、Integer、Byte 等等。这些 java 内置的值类就是根据 compare 方法比较大小的,尤其重要的是,若类实现了 Comparable 接口,它就跟许多泛型算法及依赖于该接口的集合比较算法相关。这就是类的内部排序。

package top.wthfeng.hello.test; /** * 苹果类 */ public class Apple implements Comparable<Apple>{ /** * 重量 */ private Integer weight; /** * 价格 */ private Integer price; public Integer getPrice() { return price; } public void setPrice(Integer price) { this.price = price; } public Integer getWeight() { return weight; } public void setWeight(Integer weight) { this.weight = weight; } @Override public String toString() { //重写toString()方法,方面输出 StringBuilder sb = new StringBuilder(); sb.append("["); sb.append("Apple:(weight:"); sb.append(weight); sb.append(",price:"); sb.append(price); sb.append(")]"); return sb.toString(); } @Override public int compareTo(Apple o) { //实现内部排序 return this.price.compareTo(o.getPrice()); } } package top.wthfeng.hello; import top.wthfeng.hello.test.Apple; import java.util.*; public class Test { public static void main(String[] args) { List<Apple> apples = new ArrayList<>(); Random random = new Random(12); for (int i = 0; i < 10; i++) { //生成10个苹果,重量随机生成 Apple apple = new Apple(); apple.setWeight(random.nextInt(1000)); apple.setPrice(random.nextInt(50)); apples.add(apple); } for (Apple apple : apples) { //打印10个苹果的顺序 System.out.println("apple = " + apple); } Collections.sort(apples); // Collections.sort(apples,(o1,o2)->o1.getWeight().compareTo(o2.getWeight())); for (Apple apple : apples) { System.out.println(" sort apple = " + apple); } } } //输出 apple = [Apple:(weight:866,price:12)] apple = [Apple:(weight:556,price:33)] apple = [Apple:(weight:624,price:11)] apple = [Apple:(weight:750,price:15)] apple = [Apple:(weight:596,price:21)] apple = [Apple:(weight:568,price:22)] apple = [Apple:(weight:61,price:7)] apple = [Apple:(weight:695,price:14)] apple = [Apple:(weight:536,price:31)] apple = [Apple:(weight:505,price:3)] sort apple = [Apple:(weight:505,price:3)] sort apple = [Apple:(weight:61,price:7)] sort apple = [Apple:(weight:624,price:11)] sort apple = [Apple:(weight:866,price:12)] sort apple = [Apple:(weight:695,price:14)] sort apple = [Apple:(weight:750,price:15)] sort apple = [Apple:(weight:596,price:21)] sort apple = [Apple:(weight:568,price:22)] sort apple = [Apple:(weight:536,price:31)] sort apple = [Apple:(weight:556,price:33)]
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3203 引用 • 8217 回帖 • 1 关注
  • 排序
    19 引用 • 16 回帖 • 1 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • B3log

    B3log 是一个开源组织,名字来源于“Bulletin Board Blog”缩写,目标是将独立博客与论坛结合,形成一种新的网络社区体验,详细请看 B3log 构思。目前 B3log 已经开源了多款产品:SymSoloVditor思源笔记

    1062 引用 • 3455 回帖 • 147 关注
  • ZeroNet

    ZeroNet 是一个基于比特币加密技术和 BT 网络技术的去中心化的、开放开源的网络和交流系统。

    1 引用 • 21 回帖 • 651 关注
  • Vim

    Vim 是类 UNIX 系统文本编辑器 Vi 的加强版本,加入了更多特性来帮助编辑源代码。Vim 的部分增强功能包括文件比较(vimdiff)、语法高亮、全面的帮助系统、本地脚本(Vimscript)和便于选择的可视化模式。

    29 引用 • 66 回帖 • 1 关注
  • Node.js

    Node.js 是一个基于 Chrome JavaScript 运行时建立的平台, 用于方便地搭建响应速度快、易于扩展的网络应用。Node.js 使用事件驱动, 非阻塞 I/O 模型而得以轻量和高效。

    139 引用 • 269 回帖 • 1 关注
  • Spark

    Spark 是 UC Berkeley AMP lab 所开源的类 Hadoop MapReduce 的通用并行框架。Spark 拥有 Hadoop MapReduce 所具有的优点;但不同于 MapReduce 的是 Job 中间输出结果可以保存在内存中,从而不再需要读写 HDFS,因此 Spark 能更好地适用于数据挖掘与机器学习等需要迭代的 MapReduce 的算法。

    74 引用 • 46 回帖 • 566 关注
  • 快应用

    快应用 是基于手机硬件平台的新型应用形态;标准是由主流手机厂商组成的快应用联盟联合制定;快应用标准的诞生将在研发接口、能力接入、开发者服务等层面建设标准平台;以平台化的生态模式对个人开发者和企业开发者全品类开放。

    15 引用 • 127 回帖 • 1 关注
  • Word
    13 引用 • 41 回帖
  • 电影

    这是一个不能说的秘密。

    123 引用 • 608 回帖
  • Follow
    4 引用 • 12 回帖 • 10 关注
  • Latke

    Latke 是一款以 JSON 为主的 Java Web 框架。

    71 引用 • 535 回帖 • 833 关注
  • 服务

    提供一个服务绝不仅仅是简单的把硬件和软件累加在一起,它包括了服务的可靠性、服务的标准化、以及对服务的监控、维护、技术支持等。

    41 引用 • 24 回帖 • 2 关注
  • SpaceVim

    SpaceVim 是一个社区驱动的模块化 vim/neovim 配置集合,以模块的方式组织管理插件以
    及相关配置,为不同的语言开发量身定制了相关的开发模块,该模块提供代码自动补全,
    语法检查、格式化、调试、REPL 等特性。用户仅需载入相关语言的模块即可得到一个开箱
    即用的 Vim-IDE。

    3 引用 • 31 回帖 • 114 关注
  • 小说

    小说是以刻画人物形象为中心,通过完整的故事情节和环境描写来反映社会生活的文学体裁。

    32 引用 • 108 回帖
  • 七牛云

    七牛云是国内领先的企业级公有云服务商,致力于打造以数据为核心的场景化 PaaS 服务。围绕富媒体场景,七牛先后推出了对象存储,融合 CDN 加速,数据通用处理,内容反垃圾服务,以及直播云服务等。

    29 引用 • 230 回帖 • 125 关注
  • 996
    13 引用 • 200 回帖 • 2 关注
  • 国际化

    i18n(其来源是英文单词 internationalization 的首末字符 i 和 n,18 为中间的字符数)是“国际化”的简称。对程序来说,国际化是指在不修改代码的情况下,能根据不同语言及地区显示相应的界面。

    8 引用 • 26 回帖 • 1 关注
  • 房星科技

    房星网,我们不和没有钱的程序员谈理想,我们要让程序员又有理想又有钱。我们有雄厚的房地产行业线下资源,遍布昆明全城的 100 家门店、四千地产经纪人是我们坚实的后盾。

    6 引用 • 141 回帖 • 616 关注
  • 博客

    记录并分享人生的经历。

    273 引用 • 2389 回帖 • 3 关注
  • etcd

    etcd 是一个分布式、高可用的 key-value 数据存储,专门用于在分布式系统中保存关键数据。

    6 引用 • 26 回帖 • 545 关注
  • 资讯

    资讯是用户因为及时地获得它并利用它而能够在相对短的时间内给自己带来价值的信息,资讯有时效性和地域性。

    56 引用 • 85 回帖 • 4 关注
  • Thymeleaf

    Thymeleaf 是一款用于渲染 XML/XHTML/HTML5 内容的模板引擎。类似 Velocity、 FreeMarker 等,它也可以轻易的与 Spring 等 Web 框架进行集成作为 Web 应用的模板引擎。与其它模板引擎相比,Thymeleaf 最大的特点是能够直接在浏览器中打开并正确显示模板页面,而不需要启动整个 Web 应用。

    11 引用 • 19 回帖 • 398 关注
  • PHP

    PHP(Hypertext Preprocessor)是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点,主要适用于 Web 开发领域,据说是世界上最好的编程语言。

    167 引用 • 408 回帖 • 485 关注
  • 禅道

    禅道是一款国产的开源项目管理软件,她的核心管理思想基于敏捷方法 scrum,内置了产品管理和项目管理,同时又根据国内研发现状补充了测试管理、计划管理、发布管理、文档管理、事务管理等功能,在一个软件中就可以将软件研发中的需求、任务、bug、用例、计划、发布等要素有序的跟踪管理起来,完整地覆盖了项目管理的核心流程。

    10 引用 • 15 回帖 • 2 关注
  • Wide

    Wide 是一款基于 Web 的 Go 语言 IDE。通过浏览器就可以进行 Go 开发,并有代码自动完成、查看表达式、编译反馈、Lint、实时结果输出等功能。

    欢迎访问我们运维的实例: https://wide.b3log.org

    30 引用 • 218 回帖 • 643 关注
  • Office

    Office 现已更名为 Microsoft 365. Microsoft 365 将高级 Office 应用(如 Word、Excel 和 PowerPoint)与 1 TB 的 OneDrive 云存储空间、高级安全性等结合在一起,可帮助你在任何设备上完成操作。

    5 引用 • 34 回帖
  • WebSocket

    WebSocket 是 HTML5 中定义的一种新协议,它实现了浏览器与服务器之间的全双工通信(full-duplex)。

    48 引用 • 206 回帖 • 280 关注
  • webpack

    webpack 是一个用于前端开发的模块加载器和打包工具,它能把各种资源,例如 JS、CSS(less/sass)、图片等都作为模块来使用和处理。

    42 引用 • 130 回帖 • 253 关注