声明,本文用得是jdk1.8
前面已经讲了Collection的总览和剖析List集合:
原本我是打算继续将Collection下的Set集合的,结果看了源码发现: Set集合实际上就是HashMap来构建的 !
所以,就 先介绍Map集合、散列表和红黑树吧 !
看这篇文章之前最好是有点数据结构的基础:
当然了,如果讲得有错的地方还请大家多多包涵并不吝在评论去指正~
前面我们学习的Collection叫做集合,它可以快速查找现有的元素。
而Map在《Core Java》中称之为-->映射..
映射的模型图是这样的:
那为什么我们需要这种数据存储结构呢???举个例子
生活中还有很多这样的例子: 只要你掏出身份证(key),那就可以证明是你自己(value)
下面我们来看看Map的源码:
简单常用的Map功能有这么一些:
下面用红色框框圈住的就是 Map值得关注的子类:
无论是Set还是Map,我们会发现都会有对应的--> Hash Set, Hash Map
首先我们也先得 回顾一下数据和链表 :
而还有另外的一些存储结构: 不在意元素的顺序,能够快速的查找元素的数据
散列表 为每个对象计算出一个整数,称为散列码 。 根据 这些计算出来的 整数(散列码)保存在对应的位置上 !
在Java中,散列表用的是链表数组实现的, 每个列表称之为桶。 【之前也写过 桶排序就这么简单 ,可以回顾回顾】
一个桶上可能会 遇到被占用的情况(hashCode散列码相同,就存储在同一个位置上) ,这种情况是无法避免的,这种现象称之为: 散列冲突
如果散列表太满, 是需要对散列表再散列,创建一个桶数更多的散列表,并将原有的元素插入到新表中,丢弃原来的表 ~
当然了, 在后面阅读源码的时候会继续说明的,现在简单了解一下即可~
扩展阅读:
上面散列表中已经提过了:如果桶数满的时候,JDK8是将 链表转成红黑树 的~。并且,我们的TreeSet、TreeMap底层都是红黑树来实现的。
所以,在这里学习一波红黑树到底是啥玩意。
之前涉及过二叉树的文章:
在未学习之前,我们可能是听过红黑树这么一个数据结构类型的,还有其他什么B/B+树等等,反正是 比较复杂的数据结构了 ~~~
各种常见的树的用途:
首先我们来回顾一下:利用二叉查找树的特性,我们一般来说可以很快地查找出对应的元素。
可是二叉查找树也有 个例(最坏) 的情况(线性):
上面符合二叉树的特性,但是它是线性的,完全没树的用处~
树是要 “均衡” 才能将它的优点展示出来的~,比如下面这种:
因此,就有了 平衡树 这么一个概念~红黑树就是一种平衡树,它可以 保证二叉树基本符合矮矮胖胖(均衡)的结构
讲到了平衡树就不得不说 最基础 的2-3树,2-3树 长的是这个样子:
在二叉查找树上,我们插入节点的过程是这样的:小于节点值往右继续与左子节点比,大于则继续与右子节点比,直到某节点左或右子节点为空,把值插入进去。 这样无法避免偏向问题
而2-3树不一样: 它插入的时候可以保持树的平衡 !
在2-3树插入的时可以简单总结为两个操作:
合并分解的操作还是 比较复杂的,要分好几种情况 ,代码量很大~这里我就不介绍了,因为要学起来是一大堆的,很麻烦~
由于2-3树为了保持平衡性,在维护的时候是需要大量的节点交换的!这些变换在实际代码中是很复杂的,大佬们 在2-3树的理论基础上发明了红黑树 (2-3-4树也是同样的道理,只是2-3树是最简单的一种情况,所以我就不说2-3-4树了)。
红黑树是一种 平衡二叉树 ,因此它没有3-节点。那红黑树是怎么将3-节点来改进成全都是二叉树呢?
红黑树就字面上的意思, 有红色的节点,有黑色的节点 :
我们可以将红色节点的 左链接 画平看看:
一颗典型的二叉树:
将红色节点的左链接画平之后:得到2-3平衡树:
前面已经说了,红黑树是在2-3的基础上实现的一种树,它能够用统一的方式完成所有变换。很好理解:红黑树也是平衡树的一种,在插入元素的时候它也得保持树的平衡,那红黑树是以什么的方式来保持树的平衡的呢?
红黑树用的是也是两种方式来替代2-3树不断的节点交换操作:
红黑树为了保持平衡,还有制定一些约束,遵守这些约束的才能叫做红黑树:
红黑树可以说是十分复杂的,我在学习的时候并没有去认真细看当中的处理细节,只是大概的过了一遍,知道了整体~
有了前辈很多优质的资料,相信要等到想要理解其中的细节,花点力气和时间还是可以掌握一二的。
红黑树参考资料:
这篇主要介绍了Map集合的基础知识,了解Map的常用子类~
简单介绍了散列表和红黑树,他俩作为Hashxxx和Treexxx的底层,了解其整体思想和相关基础在后续看源码也不至于那么懵~
后续会去看Map常用子类的源码,文章敬请期待
文章的目录导航 : https://zhongfucheng.bitcron.com/post/shou-ji/gong-zhong-hao-wen-zhang-zheng-li
如果文章有错的地方欢迎指正,大家互相交流。习惯在微信看技术文章,想要获取更多的Java资源的同学,可以 关注微信公众号:Java3y 。为了大家方便,刚新建了一下 qq群:742919422 ,大家也可以去交流交流。
谢谢支持了!希望能多介绍给其他有需要的朋友参考资料: