顶尖Java工程师的红黑技能树,如何快速点亮?

在今年的杭州云栖大会上，众所期待的新书《码出高效》正式发布，并宣布将所有图书收益捐赠于公益项目。

伴随着《阿里巴巴Java开发手册》影响面越来越广，影响程度越来越深，读者也越来越好奇《码出高效》背后的故事、映射的技术问题以及深层次的技术思考。

机会来了！12月20日（本周四）晚19:30，锁定阿里技术直播，对话《码出高效》作者孤尽，共同探索代码规约之美。

直播主题：

发现代码之美——《码出高效》图书作者交流会

直播参与方式：

错过这次可能要等一年。两种直播观看的解锁方式如下↓↓，赶紧收藏起来～

• 直接观看：扫描上方图片二维码，或点击本文末尾的“阅读原文”，在浏览器中（记住！一定要用浏览器打开，手机或PC均可）打开直播链接，收藏起来，定好闹钟，12月20日准时观看。

• 钉钉群观看：使用“钉钉”搜索《码出高效》读者交流群号：23383493、21936668（择一即可，请不要重复加哦），加入永久钉钉群，既可到时观看直播，也可与作者孤尽、其他读者交流互动。

主播介绍：

孤尽，花名取意“独孤九剑，破尽天下武功之意”的意思，毕业于浙江工业大学，《阿里巴巴Java开发手册》和《码出高效》作者 。2011年校招进入阿里以来，历经淘宝聚石塔、开放平台、国际事业部，现在负责阿里巴巴代码平台建设。2016年3月，孤尽带领集团约码项目组编写《阿里巴巴Java开发手册》，码出高效，码出质量，推动阿里系与业界一起进步，让代码变得更舒服，更清澈，更好维护。

主持人：首次出镜有点忐忑求轻拍的阿里妹

直播内容：

《码出高效》源于影响了全球250万名开发工程师的《阿里巴巴Java开发手册》，涵盖计算机领域基础知识、面向对象理念、JVM核心解析、数据结构与集合、高并发多线程、异常和日志、单元测试以及如何编写可读性强、可维护性好的优雅代码等多个方面，讲解由浅入深。

本次直播，我们将重点分享此书的核心内容之一：集合与数据结构。这是走向Java高手的必经之路，但是由于数据结构相对晦涩难懂，集合类的坑比较多，有时连资深Java工程师都会失手，给工程项目带来无法预估的损失。

除了高手进阶秘籍以外，我们还将分享《码出高效》写作背后的小故事，聊聊Java学习心得。同时，阿里妹还准备了多本作者签名版的图书，送给参与直播的小伙伴们。

为什么集合与数据结构这么重要？

我们经常说，“程序=数据结构+算法”。假如程序是一道美味佳肴的话，那么数据结构就是食材，食材的选择对于菜的品质是至关重要的，烂菜叶、霉土豆是不可能做出极品菜肴的。

我们在编码时，如果数据结构存在严重的设计缺陷，在代码层面去修正，花费的代价是极大的，甚至是不可能的。底层数据结构的缺陷也是重构的第一诱因，无端地浪费宝贵的人力资源。集合作为数据结构的载体，对元素进行加工和输出，以一定的算法实现最基本的增删改查功能，它是数据结构与算法的中间纽带，因此集合是所有编程语言的基础，非常重要。在进入高并发编程时代后，由集合引发的相关故障占比越来越高。比如，多线程共享集合时出现的脏数据问题；HashMap在数据扩容时出现节点之间的死链问题；写多读少的场景误用某些集合导致性能下降问题等。

在精彩的直播开始之前，我们先来一道前菜，热热身。附上《码出高效》精彩节选：揭开红黑树的生涩面纱，期待和你在周四晚直播时一起深入探讨。

红黑树是一种熟悉而陌生的数据结构，熟悉是指“别人家的开发工程师”运用在JDK源码或各种算法中，陌生指的是理解红黑树的理论基础比较多，比较生涩而难懂。在了解红黑树之前，我们先聊聊数据结构到底是什么？

数据结构是什么？

数据结构是指逻辑意义上的数据组织方式及其相应的处理方式。

1、什么是逻辑意义? 数据结构的抽象表达非常丰富，而实际物理存储的方式相对单一。比如，二叉树在磁盘中的存储真的是树形排列吗？并非如此。

2、什么是数据组织方式？逻辑意义上的组织方式有很多，比如树、图、队列、哈希等。树可以是二叉树、三叉树、B+ 树等；图可以是有向图或无向图；队列是先进先出的线性结构；哈希是根据某种算法直接定位的数据组织方式。

3、什么是数据处理方式? 简单地说就是增删改查。即在既定的数据组织方式上，以某种特定的算法实现数据的增加、删除、修改、查找和遍历。不同的数据处理方式往往存在着非常大的性能差异。

数据结构的评判

那么经常有开发同学说，我的输入规模量级非常小，远没有需要考虑到数据结构时间复杂度的地步，但是，除了问题规模之外，还有一个因素需要考虑，就是调用频率，即使这个方法的算法复杂度只是快了20纳秒，在日均上亿次的调用情况下，也可能是节约了若干台服务器。

数据结构的各种类型没有好坏之分，它只有与场景、数据量结合起来综合考虑，才有实际的意义。场景包括操作类型使用频率，数据量的大小决定它选择什么样的数据结构类型。到底是写为主，还是读为主，或者说读写均衡。其中写是以插入为主，还是删除为主;读是以遍历为主，还是查询单个元素为主。数据量的不同也会决定不同数据结构的使用效率。所以单纯地说红黑树与AVL是哪个好，哪个坏，是不对的。

红黑树

AVL树与红黑树之间没有从属关系，他们都是二叉查找树。AVL 树算法是以苏联数学家Adelson-Velsky 和Landis名字命名的平衡二叉树算法。红黑树是于1972 年发明的，当时称为对称二叉B 树，1978 年得到优化，正式命名为红黑树。面对频繁的插入和删除，红黑树更为合适;面对低频修改、大量查询时，AVL 树将更为合适。

我们重点来说说红黑树，它广泛应用在JDK11的各种集合框架内，比如：HashMap，TreeMap等。它在二叉查找树的性质基础上，额外引入了5 个约束条件： 

• 节点只能是红色或黑色

• 根节点必须是黑色

• 所有NIL 节点都是黑色的

• 一条路径上不能出现相邻的两个红色节点

• 在任何递归子树内，根节点到叶子节点的所有路径上包含相同数目的黑色节点

扩展说明一下NIL释义，它可以形象理解为Nothing In Leaf，是红黑树中特殊的存在，即在叶子节点上不存在的两个虚拟节点，它是红黑树旋转的假设性理论基础，默认为黑色的。

总结一下，即“有红必有黑，红红不相连”，上述5 个约束条件保证了红黑树的新增、删除、查找的最坏时间复杂度均为O (LogN )。如果一个树的左子节点或右子节点不存在，则均认定为黑色。红黑树的任何旋转在3 次之内均可完成。我们以实际插入节点55，56，57来看看红黑树的插入，以达到抛砖引玉的效果。

当插入57 时，由于父节点56 是红色的，出现两个连续红色节点，违反红黑树特性，需要重新着色，根据算法56这个节点是变为黑色，而根节点变为红色，这个时候并不平衡并且根节点为红色，这两条违反红黑树特性。所以必须左旋操作，结果如最右端所示。如果需要重新着色或旋转，存在三种情形总结如下：

• 节点的父亲是红色，叔叔是红色的，则重新着色。

• 节点的父亲是红色，叔叔是黑色的，而新节点是父亲的左节点:进行右旋。

• 节点的父亲是红色，叔叔是黑色的，而新节点是父亲的右节点:进行左旋。

注意在第3个图的节点55的左边是一个虚拟的NIL，根据红黑树的特性，它是黑色。56这个节点需要进行旋转时，它的父亲是红色，叔叔是黑色的，进行左旋。

还想看到更多Java进阶课程？周四晚上19:30，我们在阿里技术直播间不见不散。

对于Java开发有疑惑的同学，欢迎在留言区留下你的问题，我们将在直播统一解答。

关注「阿里技术」

把握前沿技术脉搏

↓↓戳这里收藏，本周四晚畅聊Java！