您当前的位置:首页 > 电脑百科 > 程序开发 > 编程百科

一起来看源代码-01TreeMap添加操作

时间:2020-08-04 14:44:22  来源:  作者:

前言

之前很多小伙伴问我怎么看源代码,还有就是越来越多的程序员都想要看源代码,搞懂底层原理,但是感觉源代码非常的晦涩难懂,不够直接和清晰,所以我希望这篇文章能够快速带同学们看懂JAVA源码,更加深入的学习java,帮助小伙伴们节约学习的时间成本.

1.树的介绍

  • 什么是树结构?其实就是一个节点下面有多个子节点,我们称之为树结构,如下图:
  • 普通节点:拥有子节点的节点。
  • 叶子节点:没有子节点的节点。
一起来看源代码-01TreeMap添加操作

 

什么是二叉树?

  • 二叉树就是一个节点最多只能有2个子节点,分为左节点和右节点,如下图:

什么是排序二叉树?

  • 若左子树不为空,则左子树所有节点的值小于根节点的值。
  • 若右子树不为空,则右子树所有节点的值大于根节点的值。
    如图:

什么是红黑树?红黑树其实是一个平衡排序二叉树,属于查询高效的树结构.请看下图:

一起来看源代码-01TreeMap添加操作

 

查询元素6普通的二叉树需要操作6次,红黑树只需要操作4次,所以红黑树查询更加高效.

##1.TreeMap的结构介绍###1.1 结构关系

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{

继承关系:

  • 父类AbstractMap,让子类拥有基本Map的方法,比如增(put)删(remove)查(get)等方法.

实现关系:

  • NavigableMap:父接口为SortedMap,所以NavigableMap为可排序接口,表示TreeMap但是一个排序的Map:
  • Cloneable:标记型的接口,内部都没有方法和属性,实现 Cloneable来表示该对象能被克隆,能使用Object.clone()方法。如果没有实现 Cloneable的类对象调用clone()就会抛出CloneNotSupportedException。
  • Serializable:标记型的接口,内部都没有方法和属性,实现Serializable表示可进行序列化和反序列化,表示能够使用在ObjectOutputStream.writeObject())和ObjectInputStream.readObject()

###1.2 基本成员组成

   /**
     * 比较器:类似于一个"裁判",用于比较插入对象和树节点的内容大小
     * 因为TreeMap是一个红黑树,红黑树是一个排序二叉树,插入元素的时候需要进行排序,排序可以使用比较器中的方式排序
     */
    private final Comparator<? super K> comparator;
    /**
     *  根节点
     */
    private transient Entry<K,V> root;
    /**
     * 树的元素个数
     */
    private transient int size = 0;
    /**
     * 操作次数:增加和删除操作数都会加1,用于控制并发修改异常
     */
    private transient int modCount = 0;

通过root根节点可以看出一个节点(元素)就是一个Entry对象,所以一个节点(元素)中包含多个数据.结构如下:

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;//键
        V value;//值
        Entry<K,V> left;//左节点
        Entry<K,V> right;//右节点
        Entry<K,V> parent;//父节点
        boolean color = BLACK;//颜色

节点表示如下:

一起来看源代码-01TreeMap添加操作

 

###1.3添加操作:

public V put(K key, V value) {
        Entry<K, V> t = root;//和插入节点进行比较的树节点
        //根节点为空
        if (t == null) {
            compare(key, key); //key比key,自己比较自己,目的是想要检查类型,确保传入了比较器或者是key实现了可比较接口
            //创建了一个没有父节点的新的节点,作为根节点
            root = new Entry<>(key, value, null);
            size = 1;//元素个数为1
            modCount++;//操作数+1
            return null;//返回空,根节点添加结束
        }
        int cmp;//表示比较结果
        Entry<K, V> parent;
        // cpr临时表示比较器
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {//比较器不为空,就使用比较器比较元素
            do {
                parent = t;//父节点为t
                cmp = cpr.compare(key, t.key);//通过比较器对key和树节点比较得到比较结果
                if (cmp < 0)//比较结果小于0,表示插入的元素比树节点小
                    t = t.left;//t往左走
                else if (cmp > 0)//比较结果大于0,表示插入的元素比树节点大
                    t = t.right;//t往右走
                else//cmp比较结果为0,覆盖节点中的value
                    return t.setValue(value);
            } while (t != null);//直到t为空停下来,保证插入的是节点
        } else {//比较器为空就使用元素中的比较方法
            if (key == null)//插入的元素key为空,没办法和树结构中的元素比较,抛出空指针异常
                throw new NullPointerException();
            /*
             *  key进行强转,看一下key是否实现了Comparable接口,是否存在compareTo方法,
             *  如果没有实现接口,也就不确定有没有compareTo方法了,没办法进行比较了
             */
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;//父节点为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);//直到没有节点可以比较
        }
        Entry<K, V> e = new Entry<>(key, value, parent);
        if (cmp < 0)//如果比较结果小于0插入左边
            parent.left = e;
        else
            parent.right = e;//否则插入右边
        fixAfterInsertion(e);//对树进行自平衡
        size++;
        modCount++;
        return null;
    }

###1.4 元素插入后对树进行自平衡

红黑树的自平衡规则:(目标就是黑色节点平衡)

每个节点都只能是红色或者黑色根节点是黑色每个叶节点(空节点)是黑色的。如果一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

    private void fixAfterInsertion(Entry<K, V> x) {//x表示插入的节点,
        x.color = RED;//设置插入的节点为红色
        //当x不为空,x不为根节点,x的父节点为红色就需要进行平衡
        while (x != null && x != root && x.parent.color == RED) {
            //x的父节点等于x的爷爷节点的左边,其实就是说x的父节点是否属于左节点
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                //获取x的爷爷节点的右节点
                Entry<K, V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {//爷爷节点的右节点为红色
                    setColor(parentOf(x), BLACK);//将x的父节点设置为黑色
                    setColor(y, BLACK);//x父节点的兄弟节点设置为黑色
                    setColor(parentOf(parentOf(x)), RED);//爷爷节点设置为红色
                    x = parentOf(parentOf(x));//x指向原来的爷爷节点,目的是为了继续往上修改颜色
                } else {//不为红色,也就是子节点和父节点的颜色出现冲突
                    //如果x等于父节点的右节点
                    if (x == rightOf(parentOf(x))) {
                        //操作的x为x的父节点
                        x = parentOf(x);
                        //左自旋,旋转后x为原来x的子节点
                        rotateLeft(x);
                    }
                    //x的父节点设置为黑色
                    setColor(parentOf(x), BLACK);
                    //x的爷爷节点设置为红色
                    setColor(parentOf(parentOf(x)), RED);
                    //右自旋
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                //y为爷爷节点的左节点(父节点的兄弟节点)
                Entry<K, V> y = leftOf(parentOf(parentOf(x)));
                //如果y的颜色为红色
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);//父节点设置为黑色
                    setColor(y, BLACK);//y设置为黑色
                    setColor(parentOf(parentOf(x)), RED);//爷爷节点设置为红色
                    x = parentOf(parentOf(x));//x指向原来的爷爷节点,目的是为了继续往上修改颜色
                } else {
                    //如果父节点的左节点为x
                    if (x == leftOf(parentOf(x))) {
                        //x为父节点
                        x = parentOf(x);
                        //右自旋,旋转后x为原来x的子节点
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);//父节点设置为黑色
                    setColor(parentOf(parentOf(x)), RED);//爷爷节点设置为红色
                    rotateLeft(parentOf(parentOf(x)));//左自旋
                }
            }
        }
        root.color = BLACK;//保证根节点必须为黑色
    }

###1.5左自旋

    private void rotateLeft(Entry<K, V> p) {
        //p不为空
        if (p != null) {
            //r表示p的右节点
            Entry<K, V> r = p.right;
            //将r的左节点 赋值给 p的有右节点
            p.right = r.left;
            //如果r的左节点不为空
            if (r.left != null)
                //r的左节点的父节点为p
                r.left.parent = p;
            //r的父节点为p的父节点
            r.parent = p.parent;
            //如果p的父节点为空
            if (p.parent == null)
                //r作为根节点
                root = r;
            //如果p的父节点的左节点等于p,说明p为父节点的左节点
            else if (p.parent.left == p)
                //p的父节点的左节点为r
                p.parent.left = r;
            else
                //p的父节点的左节点为r
                p.parent.right = r;
            //r的左节点为p
            r.left = p;
            //p的父节点为r
            p.parent = r;
        }
    }

###1.6右自旋

 private void rotateRight(Entry<K, V> p) {
        //p不为空
        if (p != null) {
            //l表示p的左节点
            Entry<K, V> l = p.left;
            //p的左节点指向l的右节点
            p.left = l.right;
            //如果l的右节点不为空
            if (l.right != null)
                //l的右节点的父节点为p
                l.right.parent = p;
            //l的父节点指向p的父节点
            l.parent = p.parent;
            //如果p的父节点为空
            if (p.parent == null)
                //l为根节点
                root = l;
            //如果p的父节点的右节点为p
            else if (p.parent.right == p)
                //p的父节点的右节点为l
                p.parent.right = l;
            else
                //p的父节点的左节点为l
                p.parent.left = l;
            //l的右节点指向p
            l.right = p;
            //p的父节点指向l
            p.parent = l;
        }
    }

###1.7案例演示:演示代码如下:

一起来看源代码-01TreeMap添加操作

 

代码执行步骤如下:

一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 


一起来看源代码-01TreeMap添加操作

 



Tags:源代码-01TreeMap   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
前言之前很多小伙伴问我怎么看源代码,还有就是越来越多的程序员都想要看源代码,搞懂底层原理,但是感觉源代码非常的晦涩难懂,不够直接和清晰,所以我希望这篇文章能够快速带...【详细内容】
2020-08-04  Tags: 源代码-01TreeMap  点击:(48)  评论:(0)  加入收藏
▌简易百科推荐
摘 要 (OF作品展示)OF之前介绍了用python实现数据可视化、数据分析及一些小项目,但基本都是后端的知识。想要做一个好看的可视化大屏,我们还要学一些前端的知识(vue),网上有很多比...【详细内容】
2021-12-27  项目与数据管理    Tags:Vue   点击:(1)  评论:(0)  加入收藏
程序是如何被执行的&emsp;&emsp;程序是如何被执行的?许多开发者可能也没法回答这个问题,大多数人更注重的是如何编写程序,却不会太注意编写好的程序是如何被运行,这并不是一个好...【详细内容】
2021-12-23  IT学习日记    Tags:程序   点击:(9)  评论:(0)  加入收藏
阅读收获✔️1. 了解单点登录实现原理✔️2. 掌握快速使用xxl-sso接入单点登录功能一、早期的多系统登录解决方案 单系统登录解决方案的核心是cookie,cookie携带会话id在浏览器...【详细内容】
2021-12-23  程序yuan    Tags:单点登录(   点击:(8)  评论:(0)  加入收藏
下载Eclipse RCP IDE如果你电脑上还没有安装Eclipse,那么请到这里下载对应版本的软件进行安装。具体的安装步骤就不在这赘述了。创建第一个标准Eclipse RCP应用(总共分为六步)1...【详细内容】
2021-12-22  阿福ChrisYuan    Tags:RCP应用   点击:(7)  评论:(0)  加入收藏
今天想简单聊一聊 Token 的 Value Capture,就是币的价值问题。首先说明啊,这个话题包含的内容非常之光,Token 的经济学设计也可以包含诸多问题,所以几乎不可能把这个问题说的清...【详细内容】
2021-12-21  唐少华TSH    Tags:Token   点击:(9)  评论:(0)  加入收藏
实现效果:假如有10条数据,分组展示,默认在当前页面展示4个,点击换一批,从第5个开始继续展示,到最后一组,再重新返回到第一组 data() { return { qList: [], //处理后...【详细内容】
2021-12-17  Mason程    Tags:VUE   点击:(14)  评论:(0)  加入收藏
什么是性能调优?(what) 为什么需要性能调优?(why) 什么时候需要性能调优?(when) 什么地方需要性能调优?(where) 什么时候来进行性能调优?(who) 怎么样进行性能调优?(How) 硬件配...【详细内容】
2021-12-16  软件测试小p    Tags:性能调优   点击:(19)  评论:(0)  加入收藏
Tasker 是一款适用于 Android 设备的高级自动化应用,它可以通过脚本让重复性的操作自动运行,提高效率。 不知道从哪里听说的抖音 app 会导致 OLED 屏幕烧屏。于是就现学现卖,自...【详细内容】
2021-12-15  ITBang    Tags:抖音防烧屏   点击:(23)  评论:(0)  加入收藏
11 月 23 日,Rust Moderation Team(审核团队)在 GitHub 上发布了辞职公告,即刻生效。根据公告,审核团队集体辞职是为了抗议 Rust 核心团队(Core team)在执行社区行为准则和标准上...【详细内容】
2021-12-15  InfoQ    Tags:Rust   点击:(24)  评论:(0)  加入收藏
一个项目的大部分API,测试用例在参数和参数值等信息会有很多相似的地方。我们可以复制API,复制用例来快速生成,然后做细微调整既可以满足我们的测试需求1.复制API:在菜单发布单...【详细内容】
2021-12-14  AutoMeter    Tags:AutoMeter   点击:(20)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条