面试了十个应届生九个都没用过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 是个什么玩意。



相关文章
|
5天前
|
Java 数据库连接 数据库
spring--为web(1),富士康java面试题整理
spring--为web(1),富士康java面试题整理
|
1天前
|
数据采集 Java 数据挖掘
最新Python+OpenCV+dlib汽车驾驶员疲劳驾驶检测!,2024年最新网易云java面试
最新Python+OpenCV+dlib汽车驾驶员疲劳驾驶检测!,2024年最新网易云java面试
最新Python+OpenCV+dlib汽车驾驶员疲劳驾驶检测!,2024年最新网易云java面试
|
1天前
|
数据采集 XML 程序员
最新用Python做垃圾分类_python垃圾分类代码用key和format,5年经验Python程序员面试27天
最新用Python做垃圾分类_python垃圾分类代码用key和format,5年经验Python程序员面试27天
最新用Python做垃圾分类_python垃圾分类代码用key和format,5年经验Python程序员面试27天
|
2天前
|
算法 程序员
2024年有哪些话一听就知道一个程序员是个水货?(1),2024年最新面试真题及答案
2024年有哪些话一听就知道一个程序员是个水货?(1),2024年最新面试真题及答案
2024年有哪些话一听就知道一个程序员是个水货?(1),2024年最新面试真题及答案
|
2天前
|
前端开发 JavaScript 程序员
2024年最新65% 的程序员竟都是自学成才?_为啥学技术都自学,2024年最新42岁程序员面试
2024年最新65% 的程序员竟都是自学成才?_为啥学技术都自学,2024年最新42岁程序员面试
2024年最新65% 的程序员竟都是自学成才?_为啥学技术都自学,2024年最新42岁程序员面试
|
2天前
|
前端开发 程序员 开发工具
2024年最全0基础程序员如何快速进阶成为编程老司机?_码农速成(2),字节跳动面试攻略
2024年最全0基础程序员如何快速进阶成为编程老司机?_码农速成(2),字节跳动面试攻略
2024年最全0基础程序员如何快速进阶成为编程老司机?_码农速成(2),字节跳动面试攻略
|
2天前
|
机器学习/深度学习 数据采集 Java
2024年9(2),2024年最新大厂面试题java
2024年9(2),2024年最新大厂面试题java
2024年9(2),2024年最新大厂面试题java
|
2天前
|
数据采集 数据挖掘 程序员
2024年Python最全资深程序员:学Python我推荐你用这几款编辑器,2024年最新面试考哪些
2024年Python最全资深程序员:学Python我推荐你用这几款编辑器,2024年最新面试考哪些
2024年Python最全资深程序员:学Python我推荐你用这几款编辑器,2024年最新面试考哪些
|
2天前
|
算法 前端开发 JavaScript
2024年Python最全资深程序员对于Python各个方向的面试经验分享,非常给力!,2024年最新2024金三银四面试季
2024年Python最全资深程序员对于Python各个方向的面试经验分享,非常给力!,2024年最新2024金三银四面试季
|
4天前
|
监控 前端开发 JavaScript
1024 看到程序员的朋友圈说说,2024年最新面试阿里
1024 看到程序员的朋友圈说说,2024年最新面试阿里