Map集合、散列表、红黑树介绍

前言

声明,本文用得是jdk1.8

前面已经讲了Collection的总览和剖析List集合:

原本我是打算继续将Collection下的Set集合的,结果看了源码发现:Set集合实际上就是HashMap来构建的

所以,就先介绍Map集合、散列表和红黑树吧

看这篇文章之前最好是有点数据结构的基础:

当然了,如果讲得有错的地方还请大家多多包涵并不吝在评论去指正~

一、Map介绍

1.1为什么需要Map

前面我们学习的Collection叫做集合,它可以快速查找现有的元素。

而Map在《Core Java》中称之为-->映射..

映射的模型图是这样的:

那为什么我们需要这种数据存储结构呢???举个例子

  • 作为学生来说,我们是根据学号来区分不同的学生。只要我们知道学号,就可以获取对应的学生信息。这就是Map映射的作用!

生活中还有很多这样的例子:只要你掏出身份证(key),那就可以证明是你自己(value)

1.2Map与Collection的区别

1.3Map的功能

下面我们来看看Map的源码:

简单常用的Map功能有这么一些:

下面用红色框框圈住的就是Map值得关注的子类:

二、散列表介绍

无论是Set还是Map,我们会发现都会有对应的-->HashSet,HashMap

首先我们也先得回顾一下数据和链表

  • 链表和数组都可以按照人们的意愿来排列元素的次序,他们可以说是有序的(存储的顺序和取出的顺序是一致的)
  • 但同时,这会带来缺点:想要获取某个元素,就要访问所有的元素,直到找到为止。
  • 这会让我们消耗很多的时间在里边,遍历访问元素~

而还有另外的一些存储结构:不在意元素的顺序,能够快速的查找元素的数据

  • 其中就有一种非常常见的:散列表

2.1散列表工作原理

散列表为每个对象计算出一个整数,称为散列码根据这些计算出来的整数(散列码)保存在对应的位置上

在Java中,散列表用的是链表数组实现的,每个列表称之为桶。【之前也写过桶排序就这么简单,可以回顾回顾】

一个桶上可能会遇到被占用的情况(hashCode散列码相同,就存储在同一个位置上),这种情况是无法避免的,这种现象称之为:散列冲突

  • 此时需要用该对象与桶上的对象进行比较,看看该对象是否存在桶子上了~如果存在,就不添加了,如果不存在则添加到桶子上
  • 当然了,如果hashcode函数设计得足够好,桶的数目也足够,这种比较是很少的~
  • JDK1.8中,桶满时会从链表变成平衡二叉树

如果散列表太满,是需要对散列表再散列,创建一个桶数更多的散列表,并将原有的元素插入到新表中,丢弃原来的表~

  • 装填因子(load factor)决定了何时对散列表再散列~
  • 装填因子默认为0.75,如果表中超过了75%的位置已经填入了元素,那么这个表就会用双倍的桶数自动进行再散列

当然了, 在后面阅读源码的时候会继续说明的,现在简单了解一下即可~

扩展阅读:

  • https://www.cnblogs.com/s-b-b/p/6208565.html
  • https://www.cnblogs.com/chinajava/p/5808416.html

三、红黑树介绍

上面散列表中已经提过了:如果桶数满的时候,JDK8是将链表转成红黑树的~。并且,我们的TreeSet、TreeMap底层都是红黑树来实现的。

所以,在这里学习一波红黑树到底是啥玩意。

之前涉及过二叉树的文章:

在未学习之前,我们可能是听过红黑树这么一个数据结构类型的,还有其他什么B/B+树等等,反正是比较复杂的数据结构了~~~

各种常见的树的用途:

来源: https://www.zhihu.com/question/30527705/answer/52527887

3.1回顾二叉查找树

首先我们来回顾一下:利用二叉查找树的特性,我们一般来说可以很快地查找出对应的元素。

可是二叉查找树也有个例(最坏)的情况(线性):

上面符合二叉树的特性,但是它是线性的,完全没树的用处~

树是要“均衡”才能将它的优点展示出来的~,比如下面这种:

因此,就有了平衡树这么一个概念~红黑树就是一种平衡树,它可以保证二叉树基本符合矮矮胖胖(均衡)的结构

3.2知新2-3树

讲到了平衡树就不得不说最基础的2-3树,2-3树长的是这个样子:

在二叉查找树上,我们插入节点的过程是这样的:小于节点值往右继续与左子节点比,大于则继续与右子节点比,直到某节点左或右子节点为空,把值插入进去。这样无法避免偏向问题

而2-3树不一样:它插入的时候可以保持树的平衡

在2-3树插入的时可以简单总结为两个操作:

  • 合并2-节点为3-节点,扩充将3-节点扩充为一个4-节点
  • 分解4-节点为3-节点,节点3-节点为2-节点
  • ……..至使得树平衡~

合并分解的操作还是比较复杂的,要分好几种情况,代码量很大~这里我就不介绍了,因为要学起来是一大堆的,很麻烦~

3.3从2-3树到红黑树

由于2-3树为了保持平衡性,在维护的时候是需要大量的节点交换的!这些变换在实际代码中是很复杂的,大佬们在2-3树的理论基础上发明了红黑树(2-3-4树也是同样的道理,只是2-3树是最简单的一种情况,所以我就不说2-3-4树了)。

  • 红黑树是对2-3查找树的改进,它能用一种统一的方式完成所有变换

红黑树是一种平衡二叉树,因此它没有3-节点。那红黑树是怎么将3-节点来改进成全都是二叉树呢?

红黑树就字面上的意思,有红色的节点,有黑色的节点

我们可以将红色节点的左链接画平看看:

一颗典型的二叉树:

将红色节点的左链接画平之后:得到2-3平衡树:

3.4红黑树基础知识

前面已经说了,红黑树是在2-3的基础上实现的一种树,它能够用统一的方式完成所有变换。很好理解:红黑树也是平衡树的一种,在插入元素的时候它也得保持树的平衡,那红黑树是以什么的方式来保持树的平衡的呢?

红黑树用的是也是两种方式来替代2-3树不断的节点交换操作:

  • 旋转:顺时针旋转和逆时针旋转
  • 反色:交换红黑的颜色
  • 这个两个实现比2-3树交换的节点(合并,分解)要方便一些

红黑树为了保持平衡,还有制定一些约束,遵守这些约束的才能叫做红黑树:

  1. 红黑树是二叉搜索树。
  2. 根节点是黑色
  3. 每个叶子节点都是黑色的空节点(NIL节点)
  4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点(每一条树链上的黑色节点数量(称之为“黑高”)必须相等)

3.5红黑树总结

红黑树可以说是十分复杂的,我在学习的时候并没有去认真细看当中的处理细节,只是大概的过了一遍,知道了整体~

有了前辈很多优质的资料,相信要等到想要理解其中的细节,花点力气和时间还是可以掌握一二的。

红黑树参考资料:

  • https://blog.csdn.net/chen_zhang_yu/article/details/52415077
  • https://riteme.github.io/blog/2016-3-12/2-3-tree-and-red-black-tree.html#fn:red-is-left
  • http://www.sohu.com/a/201923614_466939
  • https://www.jianshu.com/p/37c845a5add6
  • https://www.cnblogs.com/nullzx/p/6111175.html
  • https://blog.csdn.net/fei33423/article/details/79132930

四、总结

这篇主要介绍了Map集合的基础知识,了解Map的常用子类~

简单介绍了散列表和红黑树,他俩作为Hashxxx和Treexxx的底层,了解其整体思想和相关基础在后续看源码也不至于那么懵~

原文发布于微信公众号 - Java3y(java3y)

原文发表时间:2018-04-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序你好

微软Build 2018:C#语言的未来

未来C#特性列表中的第一位是可空引用类型。 我们在去年首次介绍了这一点,但是要简要回顾一下:默认情况下,所有引用变量,参数和字段将不可为空。 然后,就像值类型一...

2218
来自专栏JavaQ

写这样的方法让人很反感

写作文要做到段落清晰、每段思路流畅、每段主旨明确,要有一条清晰的线穿插整篇内容,编写程序代码和写作文是一个套路。一个类就像一篇小作文,类的单一职责就是小作文要叙...

3297
来自专栏架构师之旅

JVM内存管理------GC算法精解

相信不少猿友看到标题就认为LZ是标题党了,不过既然您已经被LZ忽悠进来了,那就好好的享受一顿算法大餐吧。不过LZ丑话说前面哦,这篇文章应该能让各位彻...

1758
来自专栏梧雨北辰的开发录

Swift学习:可选型的使用

第一部分:可选型要点 可选类型顾名思义。它表示一个变量有可能有值,也可能没有值(nil)。 可选类型类似于OC指针的nil值,但是OC中的nil只对类有用,而可...

2605
来自专栏大数据架构

Java进阶(二)当我们说线程安全时,到底在说什么

这一点,跟数据库事务的原子性概念差不多,即一个操作(有可能包含有多个子操作)要么全部执行(生效),要么全部都不执行(都不生效)。

43813
来自专栏用户2442861的专栏

c++ 11 新特性

赖勇浩(http://laiyonghao.com) 声明:本文源自 Danny Kalev 在 2011 年 6 月 21 日发表的《The Bigges...

461
来自专栏web编程技术分享

JavaScript: 零基础轻松学闭包(2)

2629
来自专栏守望轩

c#的细节(一)-问号的细节

写在最前面的话: 《c#的细节》是我当初学习c#时候,做的一些学习笔记的整理,现在回头看来这些都是非常浅显的知识,是c#非常细节的地方,同时也是不能忽略的地方,...

1906
来自专栏葡萄城控件技术团队

WPF/Silverlight Layout 系统概述——Measure

前言 在WPF/Silverlight当中,如果已经存在的Element无法满足你特殊的需求,你可能想自定义Element,那么就有可能会面临重写Measure...

1688
来自专栏程序你好

微软Build 2018:C#语言的未来

651

扫码关注云+社区