【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

目录

TreeMap概述
红黑树回顾
TreeMap构造
put方法
get 方法
remove方法
遍历
总结

一. TreeMap概述

TreeMap存储K-V键值对,通过红黑树(R-B tree)实现;
TreeMap继承了NavigableMap接口,NavigableMap接口继承了SortedMap接口,可支持一系列的导航定位以及导航操作的方法,当然只是提供了接口,需要TreeMap自己去实现;
TreeMap实现了Cloneable接口,可被克隆,实现了Serializable接口,可序列化;
TreeMap因为是通过红黑树实现,红黑树结构天然支持排序,默认情况下通过Key值的自然顺序进行排序;
二. 红黑树回顾

因为TreeMap的存储结构是红黑树,我们回顾一下红黑树的特点以及基本操作,红黑树的原理可参考关于红黑树(R-B tree)原理:
https://www.cnblogs.com/LiaHon/p/11203229.html
下图为典型的红黑树:

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

红黑树规则特点:
节点分为红色或者黑色;
根节点必为黑色;
叶子节点都为黑色,且为null;
连接红色节点的两个子节点都为黑色(红黑树不会出现相邻的红色节点);
从任意节点出发,到其每个叶子节点的路径中包含相同数量的黑色节点;
新加入到红黑树的节点为红色节点;
红黑树自平衡基本操作:
变色:在不违反上述红黑树规则特点情况下,将红黑树某个node节点颜色由红变黑,或者由黑变红;
左旋:逆时针旋转两个节点,让一个节点被其右子节点取代,而该节点成为右子节点的左子节点
右旋:顺时针旋转两个节点,让一个节点被其左子节点取代,而该节点成为左子节点的右子节点

三. TreeMap构造

我们先看一下TreeMap中主要的成员变量

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

上面的主要成员变量根节点root是Entry类的实体,我们来看一下Entry类的源码

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

Entry静态内部类实现了Map的内部接口Entry,提供了红黑树存储结构的java实现,通过left属性可以建立左子树,通过right属性可以建立右子树,通过parent可以往上找到父节点。
大体的实现结构图如下:

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

TreeMap构造函数:

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

四. put方法

put方法为Map的核心方法,TreeMap的put方法大概流程如下:

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

我们来分析一下源码

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

put方法源码中通过fixAfterInsertion(e)方法来进行自平衡处理,我们回顾一下插入时自平衡调整的逻辑

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

源码中通过 rotateLeft 进行【左旋】,通过 rotateRight 进行【右旋】。都非常类似,我们就看一下【左旋】的代码,【左旋】规则如下:“逆时针旋转两个节点,让一个节点被其右子节点取代,而该节点成为右子节点的左子节点”。

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

就算是看了上面的注释还是并不清晰,看下图你就懂了

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

五. get 方法

get方法是通过二分查找的思想,我们看一下源码

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

六. remove方法

remove方法可以分为两个步骤,先是找到这个节点,直接调用了上面介绍的getEntry(Object key),这个步骤我们就不说了,直接说第二个步骤,找到后的删除操作。

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

通过deleteEntry(p)进行删除操作,删除操作的原理我们在前面已经讲过
删除的是根节点,则直接将根节点置为null;
待删除节点的左右子节点都为null,删除时将该节点置为null;
待删除节点的左右子节点有一个有值,则用有值的节点替换该节点即可;
待删除节点的左右子节点都不为null,则找前驱或者后继,将前驱或者后继的值复制到该节点中,然后删除前驱或者后继(前驱:左子树中值最大的节点,后继:右子树中值最小的节点);

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

操作的操作其实很简单,场景也不多,我们看一下删除后的自平衡操作方法fixAfterDeletion

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

当待操作节点为左节点时,上面描述了四种场景,而且场景之间可以相互转换,如deleteEntry后进入了场景1,经过场景1的一些列操作后,红黑树的结构并没有调整完成,而是进入了场景2,场景2执行完成后跳出循环,将待操作节点设置为黑色,完成。
我们下面用图来说明一下四种场景帮助理解,当然大家最好自己手动画一下。

【144期】考考基础部分,你能说出 TreeMap 原理实现及常用方法吗?

七. 遍历

遍历比较简单,TreeMap的遍历可以使用map.values(), map.keySet(),map.entrySet(),map.forEach(),这里不再多说。
八. 总结

本文详细介绍了TreeMap的基本特点,并对其底层数据结构红黑树进行了回顾,同时讲述了其自动排序的原理,并从源码的角度结合红黑树图形对put方法、get方法、remove方法进行了讲解,最后简单提了一下遍历操作,若有不对之处,请批评指正,望共同进步,谢谢!

上一篇:悦虎144固件,151固件,华强北二代悦虎144固件,151固件,1562M芯片144固件,151固件


下一篇:多线程问题(三)