摘要：并且，我们的底层都是红黑树来实现的。红黑树是一种平衡二叉树因此它没有节点。
前言
声明，本文用得是jdk1.8
前面已经讲了Collection的总览和剖析List集合：
Collection总览
List集合就这么简单【源码剖析】
原本我是打算继续将Collection下的Set集合的，结果看了源码发现：Set集合实际上就是HashMap来构建的！
所以，就先介绍Map集合、散列表和红黑树吧！
看这篇文章之前最好是有点数据结构的基础：
Java实现单向链表
栈和队列就是这么简单
二叉树就这么简单
当然了，如果讲得有错的地方还请大家多多包涵并不吝在评论去指正～
一、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.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树交换的节点(合并，分解)要方便一些
红黑树为了保持平衡，还有制定一些约束，遵守这些约束的才能叫做红黑树：
红黑树是二叉搜索树。
根节点是黑色。
每个叶子节点都是黑色的空节点（NIL节点）。
每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点(每一条树链上的黑色节点数量（称之为“黑高”）必须相等)。
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的底层，了解其整体思想和相关基础在后续看源码也不至于那么懵~
后续会去看Map常用子类的源码，文章敬请期待~~~~
文章的目录导航：https://zhongfucheng.bitcron.com/post/shou-ji/gong-zhong-hao-wen-zhang-zheng-li
如果文章有错的地方欢迎指正，大家互相交流。习惯在微信看技术文章，想要获取更多的Java资源的同学，可以关注微信公众号:Java3y。为了大家方便，刚新建了一下qq群：742919422，大家也可以去交流交流。谢谢支持了！希望能多介绍给其他有需要的朋友
参考资料：
《Core Java》
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/68995.html
前言 声明，本文用得是jdk1.8 前面已经讲了Collection的总览和剖析List集合以及散列表、Map集合、红黑树的基础了： Collection总览 List集合就这么简单【源码剖析】 Map集合、散列表、红黑树介绍 本篇主要讲解HashMap，以及涉及到一些与hashtable的比较~ 看这篇文章之前最好是有点数据结构的基础： Java实现单向链表 栈和队列就是这么简单 二叉树就...
摘要：下面总结一下集合常用的三个子类吧无序，允许为，底层是散列表红黑树，非线程同步有序，不允许为，底层是红黑树非线程同步迭代有序，允许为，底层是双向链表，非线程同步从结论而言我们就可以根据自己的实际情况来使用了。 前言 声明，本文用的是jdk1.8 前面章节回顾： Collection总览 List集合就这么简单【源码剖析】 Map集合、散列表、红黑树介绍 HashMap就是这么简单【源码...
摘要：哈希表哈希表是根据关键码值而直接进行访问的数据结构。这样做的原因是和都是的次幂，并且是的倍，表示转换为二进制的唯一一个向高位移位一次。 一、HashMap简介 HashMap是基于拉链法实现的散列表。一般用于单线程程序中，JDK 1.8对HashMap进行了比较大的优化，底层实现由之前的数组+链表改为数组+链表+红黑树。下面先介绍HashMap中一些关键的知识点。 1、哈希表 哈希表是...
摘要：下面我来简单总结一下的核心要点底层结构是散列表数组链表红黑树，这一点和是一样的。是将所有的方法进行同步，效率低下。而作为一个高并发的容器，它是通过部分锁定算法来进行实现线程安全的。 前言 声明，本文用的是jdk1.8 前面章节回顾： Collection总览 List集合就这么简单【源码剖析】 Map集合、散列表、红黑树介绍 HashMap就是这么简单【源码剖析】 LinkedHas...
摘要：判断该首节点是否与插入的键值对的和一致，若一致则替换该节点的值为，否则进入下一步判断首节点是否为树节点，若是则调用树节点的方法遍历红黑树，否则遍历链表。中的方法会在链表超过树化阈值的时候，将链表转化为红黑树。 前言 由于Java 1.7和Java 1.8的HashMap的HashMap中的put()和get()方法在实现上差异很大，所以本文将于分别分析这两个版本的put()和get()...
阅读 879·2023-04-25 19:17
阅读 2178·2021-09-10 11:26
阅读 1897·2019-08-30 15:54
阅读 3410·2019-08-30 15:53
阅读 2680·2019-08-30 11:20
阅读 3391·2019-08-29 15:12
阅读 1229·2019-08-29 13:16
阅读 2384·2019-08-26 12:19
