预备知识和位算术知识（更多资料可私信“学习”免费获取）
位操作是处理器支持的低级操作。 底层硬件仅支持01等数字，因此位运算运行速度非常快。 尽管现代计算机处理器具有更长的指令流水线和更好的架构设计，加法和乘法运算几乎与位运算一样快，但位运算消耗的资源更少。 常用的位运算如下：
位和&
(1&1=1 1&0=0 0&0=0)
位或 |
(1|1=1 1|0=1 0|0=0)
有点不~
(~1=0~0=1)
位异或^
(1^1=0 1^0=1 0^0=0)
有符号右移 >>
进行右移操作时，若参与运算的数为正数，则高位加0； 如果是负数，则高位加1。
无符号右移>>>
无论参与运算的数是正数还是负数，运算时都会在高位加0。
左移
左移没有正数或负数之分，因为负数在CPU中以补码形式存储，正数左移相当于乘以2的N次方。
重点来了：以上都很简单，只是为了得出以下结论：
a % (Math.pow(2,n)) 等价于 a&( Math.pow(2,n)-1)
比如a的最终结果一定是0到15之间的数字，而a&1111只是让a除以16后的余数有效，因为如果是1 1111，那么第一位实际上代表的是16，也就是说，二进制从倒数第五位开始，只要出现1，就肯定代表16的倍数。 结论：位运算比除法运算效率更高。 尽量使用a&二进制数来求一个数的余数，这样可以更好地加快运算速度。
我们知道它是一个数组队列，相当于一个动态数组。 与Java中的基本数组相比，它的容量可以动态增长。 其要点有以下几点。
其实数据是通过数组来保存的。 当我们构建时； 如果我们使用默认构造函数，则默认容量大小为 10。
当容量不足以容纳所有元素时，容量将被重置：原始容量的1.5倍。
克隆函数是将所有元素克隆到一个数组中。
克隆的底层是.(0,,0,,);
java.io的实现方式。 写入输出流时，先写入“容量”，然后依次写入“每个元素”； 读取输入流时，先读取“容量”，然后依次读取“每个元素”。
优势：
基于下标遍历元素效率更高。
基于下标访问元素效率更高。
封装了对基于数组的元素进行操作的方法。
这种动态数组在本地地址上是空间连续的。
可以自动扩展。
缺点：
插入和删除效率相对较低。
根据内容查找元素效率较低。
扩容规则：每次扩容容量为现有容量的50%。
双向链表的每个节点包含三部分（data、prev、next），并且不要求空间连续。 它类似于通过前后两条线串联的节点。
和总结：
它实现了基于动态数组的数据结构，并且基于链表结构。
对于随机访问 get 和 set 方法，更好，因为需要移动指针。
对于新增和删除操作，添加和删除更有利，因为数据需要移动。
当查询较多但插入删除较少时使用。 当查询较少但插入和删除较多时使用。
首先，你需要了解二叉树以及它是一种什么样的数据组合。 那么你需要知道二叉树在搜索时的缺点，可能会出现数据倾斜。 因此，平衡二叉树被引入。 平衡二叉树左右节点的深度差不会超过1，查找起来容易，构造起来又麻烦，于是红黑树又出现了。 红黑树是一种平衡二叉搜索树。 它是计算机科学中常用的数据结构。 最典型的应用就是实现数据关联，比如map等数据结构的实现。 红黑树的重要特征是（左节点<根节点<右节点）红黑树有以下限制：
节点必须是红色或黑色
根节点是黑色的
所有叶节点都是黑色的。
每个红色节点的两个子节点都是黑色的，即不能有父子。 两个节点都是红色的。
在从任何节点到其每个叶子的所有简单路径上，黑色节点的数量都是相同的。
哈希表是一种特殊的数据结构。 它与数组、链表、二叉排序树有明显的不同。 它可以快速定位到你想要查找的记录，而不是表中存在的记录的键。 单词与搜索进行比较。 这源于哈希表设计的特殊性。 它利用==函数映射==的思想，将记录的存储位置与记录的关键字关联起来，这样就可以非常快速地查找到。评价函数性能的关键在于= =加载因子==以及如何合理解决hash冲突。 详细内容可以参见博主之前的文章 Hash
源码分析概述
通常，有了前面的一些知识点的铺垫，就可以很好地进行讲解。 既然，红黑树各有各的优缺点，能否结合百家之长，实现一个综合性的产品===>，所以本文讲解的都是基于JDK8。
组成：数组+链表+红黑树。 主干是一个节点数组。 节点是 的基本单位。 每个节点都包含一个键值对。 时间复杂度几乎可以接近O(1)（如果发生哈希冲突可能会有所波动），空间利用率一般在40%左右。 大致情况如下：
PS：几个重要节点之间的关系如下：
1.java.util.Map.Entry 这是一个接口函数，定义了一些比较。
2.java.util..Node是我们存储的基本KV。
3.java.util..Enrty Enrty类继承自.Node类。 Enrty 是一个内部类。
4、java.util..的构造函数向上追踪，继承了.Entry，而.Entry又继承了.Node。 因此，保留了Node的属性，同时增加了前驱指针prev，使得==链表==变成了==双向==。 前三个节点与第五棵红黑树有关，第四个与next和双向链表有关。
数据存储一般分为三个步骤。
5. 每个数据由映射函数决定数据在数组中的放置位置。 数组初始化时必须是2的幂，默认是16。初始化时传入的任何数字都会调整为2的幂。
6、如果同一个数组分配的数据过多，可以使用链表方法解决哈希冲突。
7、如果同一节点的链表数据节点个数>=8且数组长度>==64，则链表将演化为链表。 如果链表的节点数小于=6，就会退化为链表。
特别提醒：在阅读源码之前，需要先了解其一般特性如下：
1. 访问不是顺序的
2.KV允许为NULL
3.该类在多线程情况下是安全的，可以考虑使用。
4、JDk8底层是数组+链表+红黑树，JDK7底层是数组+链表。
5、初始容量和负载系数是决定整个班级性能的关键点，不要轻易改变。
6.它是以惰性方式创建的，只有当你放入数据时才会构建。
7、单向链表转换为红黑树时，会先转换为双向链表，最后转换为红黑树。 双向链表和红黑树是共存的，所以要记住。
8. 对于两个传入的按键，将强制确定高或低按键。 确定高低的主要目的是决定向左还是向右。
9、链表转换为红黑树后，会努力将红黑树的根节点、链表头节点和table[i]节点合并为一。
10、删除时，首先判断红黑树中删除的节点数量是否需要链表。 如果不传输链表，则与彩铃类似。 找到一个合适的节点来填充被删除的节点。
11、红黑树的根节点不一定与table[i]相同，即链表的头节点。 实现了三者的同步。 调用时 .() 将为 =false。
在此插入图片描述
重要参数：当静态参数final int CITY = 1 = 8时，可能会转换成树。 设置为8，系统根据泊松分布的数据分布图来设置。
最终整数 = 6
当哈希表展开时，如果找到链表的长度
设置实例中Entry的集合
整数大小
表中存储的实例KV数量。
整数
我们所做的所有增删改查都会引起值的变化，这与版本控制功能类似。 可以理解为需要在具体操作下进行检查，适合Fai-Fast机制。
Java的集合类中有一个Fail-Fast错误检测机制。 当多个线程操作同一个集合的内容时，可能会出现此类异常。 例如，当A正在遍历一个集合，而其他线程修改了该集合时，就会抛出异常。 这种机制是通过在迭代器初始化时赋值，并在迭代过程中判断和是否一致来实现的。
整数
扩展阈值 = *
最终浮动
负载系数可以自定义，但一般使用系统自带的0.75。
四种施工方法
1.默认构建方法
2.传入初始容量大小
3.传入初始容量和负载率
====：该功能是返回一个大于输入参数且为2的最小整数次方的数字。例如，如果使用10，则返回16。
详情如下所示：
我们先来分析一下n位运算部分：首先我们假设n的二进制数为01xxx...xxx。 然后将n右移1位：001xx...xxx，然后OR：011xx...xxx。 将 n 右移 2 位为：00011...xxx，然后或：01111...xxx。 这时，已经有四个1了，如果右移4位，可能会得到8个1。 同样的，如果有8个1，右移8位肯定会使最后8位为1。
综上所述，这个算法使得最高位1之后的所有位都变成1。最后让结果n+1，即得到2的整数次方的值。 现在回过头来看看第一条语句：
int n = 上限 - 1；
让cap-1赋值给n的目的是为了找到另一个大于等于原值的目标值。 例如，二进制的 1000 是十进制的 8。 如果直接运算，不减1，就会得到答案10000，也就是16。显然不是结果。 减1后，二进制值为111，如果再运算，则得到原来的值1000。这种二进制方法非常高效。
构造函数传入一个map并使用默认的负载因子，然后根据当前map的大小（也可能涉及到）推断出需要什么，然后放入容器中。
哈希值
无论我们放入数据还是获取数据，首先都要获取数据在这个哈希表中对应的位置。 例如，在放入数据时，其过程分为两个步骤。
1.首先获取key对应的hash值。 2. 将数据的哈希值A无符号地向右移动16位，然后得到最终值。 这种操作称为扰动。 原因是低位数字出现相同的概率太高，因此数据应尽可能均匀分布。
同时，JDK8和JDK7中扰动的目的是相同的，但复杂度不同。
1. 得到
相对来说，是非常简单的。 为了方便理解，我们先说一下代码的大致流程。
获取key的hash，然后根据插入时的思路根据hash和key查找get。
如果数组位置为NULL，则直接返回NULL。
如果数组位置不为NULL，首先直接检查数组位置是否匹配。
如果数组位置存在红黑树类型，则根据红黑树类型查找并返回。
如果数组有next，则通过遍历链表的方式查找并返回。
1.1
宏搜索功能详情：
1.3
红黑树搜索节点详细信息：
首先获取根节点、左节点、右节点。
按照左节点 < 根节点 < 右节点，逐步缩小数据范围进行搜索。
如果方法实现了，直接比较。
否则，如果根节点不匹配，则递归调用find函数。
1.4：
查询key是否实现该接口。
1.5：
既然接口已实现，请使用实现来比较并确定要做什么。
2.放置过程
按照源码来梳理一下put操作的大致流程。
插入数据时的一般流程如下：
计算数据的Hash值。 在插入数据之前，先检查当前表的状态。 如果表为空，则需要调用它进行初始化。 通过位运算获取按键的目标位置。 并确定当前位置。 如果当前位置为空，则直接放置。 如果与当前密钥一致，则会被覆盖。 如果当前有数据，则检查当前数据类型是否为红黑树。 如果是这样，则需要调用它。 否则就认为是链表，然后循环查找tail==插入==。 同时，我们还要考虑将当前链表转换为红黑树。
在JDK8中，找到要插入的点e的方式是通过==尾插入==（类似于尾部排队），而在JDK7中则是==前插入==（类似于在最前面排队，这样做的原因发明人认为后面插入的段更容易被访问），对应的代码如下。
判断找到的旧节点e
如果对应的旧值是NULL，那么是否决定替换它并不重要。 将被替换。
如果对应的旧值不为NULL，则将其替换为False。
：仅在缺席时替换，如果不缺席则不替换。 与redis Setnx功能相同。
最后添加数据后，将修改后的变量加1。 同时检查最新的总节点数是否需要扩容。 如果是这样，请将其扩展。 2放
2.1 首先找到根节点，然后判断是从左还是从右找key。 如果找到，则直接返回找到的节点。 如果没有找到，则创建一个新节点，并将新节点放置在适当的位置，同时考虑到红黑树和双向链表的节点插入情况。
2.2
主要功能是根据参数的阈值范围将链表转换为红黑树。 然后先将单链表转换为双向链表，然后调用头节点作为根节点构建红黑树。
2.3
创建双向链表和红黑树主要分为三个步骤。
从双向链表中找到第一个节点作为根节点。 每个双向链表节点以根节点为根在二叉树中找到一个位置，然后将数据插入到红黑树中。 同时要注意。 最后注意根节点与当前table[i]的匹配。
2.4
确保将根节点移动到表[first]。 如果红黑树构建成功，但本次任务没有执行成功，则[first]对应的节点将不是红黑树的根节点。 正常执行时，主要步骤分为两步。
找到跟节点，并将根节点放入跟节点中。 至此，红黑树的操作就完成了。 原来链表的头就是第一个节点。 现在将根节点（可能是中间节点）移动到第一个节点的前面。 该函数的作用是检查对象是否满足红黑树和双向链表的特性。 因为并发的情况下会出现很多异常。
3
获取旧表数据。 如果旧表足够大，则不会扩容，只调整阈值。
旧表的扩展范围也满足要求。 直接扩大容器大小和阈值。
如果是参数化构造函数，则需要将阈值复制到容器容量中。
否则，认为容器初始化时没有传递参数，需要初始化。
如果旧表有数据，新表调整大小并设置，则阈值未设置成功。 此时设置了一个新的阈值。
创建新容器。
旧表已经成功扩容为新表，这就涉及到数据传输。
如果数据不为空并且是一个单独的节点，则哈希将直接重新分配到新位置。
如果数据不为空，后面是链表，则需要区分链表数据，看看哪些分配到了旧的地方，哪些分配到了新的地方。
如果节点类型是红黑树，则调用 split。
链表形式的重新分区解释如下： 注意：不是(e.hash & (-1))，而是(e.hash & )。 后一个获取数组中元素的位置是否需要移动。 示例如下
例一：e.hash= 10 0000 1010 =16 0001 0000 & =0 0000 0000 比较高位第一位 0 结论：扩容后元素在数组中的位置没有改变例二：e.hash= 17 0001 0001 =16 0001 0000 & =1 0001 0000 第一个高位 1 结论：扩容后数组中元素位置发生了变化。 新的下标位置是原下标位置+原数组长度。
3.1 分割
扩容后原table[i]上的红黑树如何处理。 代码整体思路与处理链表类似。 只要理解了节点关系，保存了红黑树，也就保存了双向链表。
4.查找
功能是以指定节点为根节点，根据指定的key和value进行搜索。
利用哈希值来决定是向左查找还是向右查找。
如果您发现一些简单的东西，只需将其返回即可。
有可能散列值相等但键不同。 继续搜索存在三种情况。
如果左节点为空，则查找右节点
如果右节点为空，则查找左节点
左右节点不会为空。 尝试检查左侧或右侧的数据。
比较不能通过或者比较后仍然相等。
直接从右节点开始递归查找。
否则，从左侧开始搜索。
4.1
比较两个对象肯定会产生比较。
如果a和b都是字符串，则在if判断中直接完成竞争。
如果a和b都是对象，则直接查看该对象在JVM中的哈希地址，然后进行比较。
4.
只是函数入口：
4.1
无非就是检查table[i]是否存在，然后是不是在第一个节点上，是否在红黑树上，是否在链表上。 遇到这些情况，发现就直接删除，同时注意平衡。
4.2
该函数的作用是移除调用该方法的节点，也就是方法中的this节点。 去除包括链表的处理和红黑树的处理。 你可以看看我之前写的彩铃。 删除时的思路大致相同。 大致分为3步。
红黑树也是一个双向链表。 从链表的角度删除节点，然后判断是否需要退化为链表。
根据当前p节点，尝试从pr中找到最小的目标节点s或者从pl中找到最大的目标节点s，并交换两个点。
找到您想要用 p 替换的内容。
实施更换。
替换后可能需要保持红黑树特性。
4.3
红黑树退化为链表
4.4
关于这个问题，可以直接阅读博主之前红黑大叔关于添加和删除彩铃的文章。
JDK7死循环问题
JDK7将旧表数据重定位到新表的函数如下，重点部分划出。
1、头插入方法 一般情况下：
2、并发情况下，线程1只执行了Entry next = e.next，被挂起，而线程2正常完成执行。 结果如下：
然后线程1继续执行，如下： 通过一步一步的分析和绘图，我们可以知道会发生循环。
方法7v8
7 中需要 4 次才能找到哈希值，而 8 中只需要 1 次。
7=数组+链表，8=数组+链表+红黑树
7号是头部插入方式，多线程很容易造成循环，8号是尾部插入方式。
7中的扩展是重新定位所有数据，而8中最好保持位置不变+移动旧的大小。
7是先判断是否需要扩容再插入。 8、是先插入再检查是否要扩容。
不管现场78不安全，记得在多线程的情况下使用它。 下一篇文章说。
常见问题
我随机收集了一些常见问题。 如果您理解以上所有代码，您应该能够处理它们。
原理，内部数据结构。
put和get的一般过程。
哈希函数的实现。
如何扩展。
为什么几个重要的参数要这样设置呢？
为什么线程不安全以及如何替换它。
JDK7和JDK8的区别。
在链表和红黑树之间切换思想。
