面试了十个应届生九个都没用过TreeMap,你确定你们是个 Java 程序员?(2)-阿里云开发者社区

开发者社区> 沉默王二> 正文

面试了十个应届生九个都没用过TreeMap,你确定你们是个 Java 程序员?(2)

简介: 面试了十个应届生九个都没用过TreeMap,你确定你们是个 Java 程序员?
+关注继续查看

01、自然顺序


默认情况下,TreeMap 是根据 key 的自然顺序排列的。比如说整数,就是升序,1、2、3、4、5。


TreeMap<Integer,String> mapInt = new TreeMap<>();
mapInt.put(3, "沉默王二");
mapInt.put(2, "沉默王二");
mapInt.put(1, "沉默王二");
mapInt.put(5, "沉默王二");
mapInt.put(4, "沉默王二");
System.out.println(mapInt);


输出结果如下所示:


{1=沉默王二, 2=沉默王二, 3=沉默王二, 4=沉默王二, 5=沉默王二}

1

TreeMap 是怎么做到的呢?想一探究竟,就得上源码了,来看 TreeMap 的 put() 方法(省去了一部分,版本为 JDK 14):


public V put(K key, V value) {
    TreeMap.Entry<K,V> t = root;
    int cmp;
    TreeMap.Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
    }
    else {
        @SuppressWarnings("unchecked")
        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);
    }
    return null;
}



注意 cmp = k.compareTo(t.key) 这行代码,就是用来进行 key 的比较的,由于此时 key 是 int,所以就会调用 Integer 类的 compareTo() 方法进行比较。


public int compareTo(Integer anotherInteger) {
    return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
    return (x < y) ? -1 : ((x == y) ? 0 : 1);
}


那相应的,如果 key 是字符串的话,也就会调用 String 类的 compareTo() 方法进行比较。


public int compareTo(String anotherString) {
    byte v1[] = value;
    byte v2[] = anotherString.value;
    byte coder = coder();
    if (coder == anotherString.coder()) {
        return coder == LATIN1 ? StringLatin1.compareTo(v1, v2)
                : StringUTF16.compareTo(v1, v2);
    }
    return coder == LATIN1 ? StringLatin1.compareToUTF16(v1, v2)
            : StringUTF16.compareToLatin1(v1, v2);
}



由于内部是由字符串的字节数组的字符进行比较的,是不是听起来很绕?对,就是很绕,所以使用中文字符串作为 key 的话,看不出来效果。


TreeMap<String,String> mapString = new TreeMap<>();
mapString.put("c", "沉默王二");
mapString.put("b", "沉默王二");
mapString.put("a", "沉默王二");
mapString.put("e", "沉默王二");
mapString.put("d", "沉默王二");
System.out.println(mapString);



输出结果如下所示:


{a=沉默王二, b=沉默王二, c=沉默王二, d=沉默王二, e=沉默王二}

1

字母的升序,对吧?


02、自定义排序


如果自然顺序不满足,那就可以在声明 TreeMap 对象的时候指定排序规则。


TreeMap<Integer,String> mapIntReverse = new TreeMap<>(Comparator.reverseOrder());

mapIntReverse.put(3, "沉默王二");

mapIntReverse.put(2, "沉默王二");

mapIntReverse.put(1, "沉默王二");

mapIntReverse.put(5, "沉默王二");

mapIntReverse.put(4, "沉默王二");


System.out.println(mapIntReverse);


TreeMap 提供了可以指定排序规则的构造方法:


public TreeMap(Comparator<? super K> comparator) {

   this.comparator = comparator;

}


Comparator.reverseOrder() 返回的是 ReverseComparator 对象,就是用来反转顺序的,非常方便。


所以,输出结果如下所示:


{5=沉默王二, 4=沉默王二, 3=沉默王二, 2=沉默王二, 1=沉默王二}

1

HashMap 是无序的,插入的顺序随着元素的增加会不停地变动。但 TreeMap 能够至始至终按照指定的顺序排列,这对于需要自定义排序的场景,实在是太有用了!


03、排序的好处


既然 TreeMap 的元素是经过排序的,那找出最大的那个,最小的那个,或者找出所有大于或者小于某个值的键来说,就方便多了。


Integer highestKey = mapInt.lastKey();
Integer lowestKey = mapInt.firstKey();
Set<Integer> keysLessThan3 = mapInt.headMap(3).keySet();
Set<Integer> keysGreaterThanEqTo3 = mapInt.tailMap(3).keySet();
System.out.println(highestKey);
System.out.println(lowestKey);
System.out.println(keysLessThan3);
System.out.println(keysGreaterThanEqTo3);



TreeMap 考虑得很周全,恰好就提供了 lastKey()、firstKey() 这样获取最后一个 key 和第一个 key 的方法。


headMap() 获取的是到指定 key 之前的 key;tailMap() 获取的是指定 key 之后的 key(包括指定 key)。


来看一下输出结果:


5

1

[1, 2]

[3, 4, 5]


04、如何选择 Map


在学习 TreeMap 之前,我们已经学习了 HashMap 和 LinkedHashMap ,那如何从它们三个中间选择呢?


HashMap、LinkedHashMap、TreeMap 都实现了 Map 接口,并提供了几乎相同的功能(增删改查)。它们之间最大的区别就在于元素的顺序:


HashMap 完全不保证元素的顺序,添加了新的元素,之前的顺序可能完全逆转。


LinkedHashMap 默认会保持元素的插入顺序。


TreeMap 默认会保持 key 的自然顺序(根据 compareTo() 方法)。


来个表格吧,一目了然。


image.png


谢谢大家,下期见,同学们。


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9698 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
9094 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13413 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
11798 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
4634 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
7094 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
4196 0
+关注
沉默王二
微信搜索「沉默王二」,回复关键字「00」获取硬核计算机基础资料。
1084
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载