前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >TreeMap源码解析

TreeMap源码解析

作者头像
吉林乌拉
发布2019-08-14 17:43:42
5040
发布2019-08-14 17:43:42
举报
文章被收录于专栏:吉林乌拉

在前几篇中我们主要介绍了底层是通过数组、链表、哈希表等方式实现的集合,今天我们来学习一种新的集合叫做TreeMap。TreeMap底层并不是通过哈希表的方式实现的,而是采用了一种全新的数据结构,红黑树结构存储的。下面我们简单介绍一下红黑树的相关知识。

  • 红黑树的基本概念

红黑树也叫红黑二叉树,所以它也是二叉树的一种,除了具有二叉树的基本特性外,还有自己独特的一些特性。二叉树也就是说在每个树节点最多有两个子节点的树结构。并且二叉树的子节点有左右之分,且左节点的值都要小于右节点的。所以,通过二叉树结构存储的数据在检索元素时速度会很快,因为从树根节点检索时,就会过滤掉将近一半的数据(理想情况下)。并且红黑树是一种平衡二叉树,这也是红黑树的一种特性。下面我们来看一下什么是平衡二叉树。

  • 红黑树特性

平衡二叉树主要具有以下特性:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树也都是一棵平衡二叉树。说白了红黑树就是平衡二叉树的一种实现算法,除此算法外还有AVL、Treap、伸展树、SBT等算法。(主要来源为百度百科)

下面我们继续介绍红黑树的其它特性,红黑树顾名思义就是通过设置红色或黑色等状态来保证树的平衡的。所以红黑树的主要特性如下:

  • 每个节点只能是红色,或黑色
  • 根节点必须是黑色
  • 每个叶节点(NIL或NULL)是黑色
  • 如果一个节点是红色的,则它的子节点必须是黑色(全部节点)
  • 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
  • 红黑树的旋转

上面是红黑树的相关特性,也就是说无论任何时候红黑树都必须保证具有上面的全部特性。但是在我们日常开发时,常常需要向集合中添加或者删除元素,那么在执行上述操作时,难免会破坏红黑树的相关特性,那么这时应该怎么处理呢?事实上,每当我们执行添加或者删除操作时,如果破坏了红黑树的特性,那么这时就会进行树的旋转,以保证红黑树的相关特性。红黑树的旋转主要分为左旋和右旋。下面我们分别看看具体的实现。

  • 左旋

红黑树进行左旋的逻辑是,将要左旋的节点的父节点设置为自己的左节点,然后将原左节点设置为新左节点的右节点。

  • 右旋

红黑树进行右旋的逻辑是,将要右旋的节点的父节点设置为自己的右节点,然后将原右节点设置为新右节点的左节点。

现在我们已经知道了有关红黑树的所有知识,下面我们分析一下TreeMap的底层源码,看TreeMap底层是怎么实现红黑树的逻辑的。我们还是和其它集合一样还是先看TreeMap的初始化。

上面是TreeMap的无参构造函数,我们发现当我们通过参构造函数创建TreeMap对象时,并不会执行底层树结构的初始化,而只是将comparator设置为空。那么通过我们以往分析其它集合时总结的规律,TreeMap的初始化一定是在第一次调用put方法时执行的。下面我们将重点看一下TreeMap中的put方法。

下面我们看一下上述方法中提到的fixAfterInsertion方法的具体逻辑也就是左旋和右旋的具体实现。

左旋和右旋的具体逻辑这里就不在详细分析了,主要的实现逻辑就是上面所说的,左旋就是讲要左旋的节点的父节点设置为自己的左节点,然后将原左节点设置为新左节点的右节点。右旋就是讲右旋的的父节点设置为自己的右节点,然后将原右节点设置为新右节点的左节点。

  • 总结
  • 在TreeMap中不允许用null做为key保存到TreeMap集合中
  • 我们在分析源码时并没有发现同步关键字synchronized,这就说明TreeMap也不是一个线程安全的集合类
  • 我们在分析源码时知道TreeMap每次都添加元素时都会进行key的比较,所以我们在使用TreeMap集合是必须保证存储在TreeMap中的元素是可以比较的,否则虚拟机会直接抛出一场。例如
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-07-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 吉林乌拉 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档