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

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

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

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

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


先看再点赞,给自己一点思考的时间,微信搜索【沉默王二】关注这个有颜值却假装靠才华苟且的程序员。

本文 GitHub github.com/itwanger 已收录,里面还有我精心为你准备的一线大厂面试题。

吃饭间隙,迷上了《吐槽大会》,一集一集地刷啊,觉得这些嘉宾真的挺有勇气的,敢于直面自己的惨淡槽点。于是,同学们看到了,我作为一个技术博主,也受到了“传染”,不,受到了“熏陶”,本来这篇文章标题就想叫《TreeMap 指南》,是不是有点平淡无奇,没有槽点?于是我就想,不妨蹭点吐槽大会的热度吧,虽然吐槽大会现在也没什么热度了哈。


TreeMap,虽然也是个 Map,但存在感太低了。我做程序员这十多年里,HashMap 用了超过十年,TreeMap 只用了多字里那么一小会儿一小会儿,真的是,太惨了。


虽然 TreeMap 用得少,但还是有用处的。


之前 LinkedHashMap 那篇文章里提到过了,HashMap 是无序的,所有有了 LinkedHashMap,加上了双向链表后,就可以保持元素的插入顺序和访问顺序,那 TreeMap 呢?


TreeMap 由红黑树实现,可以保持元素的自然顺序,或者实现了 Comparator 接口的自定义顺序。


可能有些同学不知道红黑树,理解起来 TreeMap 就有点难度,那我先来普及一下:


红黑树(英语:Red–black tree)是一种自平衡的二叉查找树(Binary Search Tree),结构复杂,但却有着良好的性能,完成查找、插入和删除的时间复杂度均为 log(n)。

二叉查找树又是什么呢?


image.png


上图中这棵树,就是一颗典型的二叉查找树:


1)左子树上所有节点的值均小于或等于它的根结点的值。


2)右子树上所有节点的值均大于或等于它的根结点的值。


3)左、右子树也分别为二叉排序树。


理解二叉查找树了吧?不过,二叉查找树有一个不足,就是容易变成瘸子,就是一侧多,一侧少,就像下图这样:


image.png


查找的效率就要从 log(n) 变成 o(n) 了,对吧?必须要平衡一下,对吧?于是就有了平衡二叉树,左右两个子树的高度差的绝对值不超过 1,就像下图这样:


image.png


红黑树,顾名思义,就是节点是红色或者黑色的平衡二叉树,它通过颜色的约束来维持着二叉树的平衡:


1)每个节点都只能是红色或者黑色


2)根节点是黑色


3)每个叶节点(NIL 节点,空节点)是黑色的。


4)如果一个节点是红色的,则它两个子节点都是黑色的。也就是说在一条路径上不能出现相邻的两个红色节点。


5)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。


image.png


那,关于红黑树,同学们就先了解到这,脑子里有个大概的印象,知道 TreeMap 是个什么玩意。



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

相关文章
使用NAT网关轻松为单台云服务器设置多个公网IP
在应用中,有时会遇到用户询问如何使单台云服务器具备多个公网IP的问题。 具体如何操作呢,有了NAT网关这个也不是难题。
25920 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
7238 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
2503 0
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
2117 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
11017 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=.
4446 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
20957 0
+关注
沉默王二
微信搜索「沉默王二」,回复关键字「00」获取硬核计算机基础资料。
1084
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《Nacos架构&原理》
立即下载
《看见新力量:二》电子书
立即下载
云上自动化运维(CloudOps)白皮书
立即下载