首先，有必要明确什么是HashMap，有图有真。 这就是HashMap
开玩笑的……o ) ……o哈哈哈~……哈希表：哈希表(hash table )又称哈希表，是非常重要的数据结构，应用场景及其丰富性，缓存很多另一方面，HashMap
在讨论哈希表之前，请大致了解一下其他数据结构的新增以及搜索等基本操作执行性能
数组:使用连续的存储单元存储数据。 对于指定下标查找，时间复杂度为o(1)； 要按指定的值进行搜索，必须遍历数组，并逐个匹配指定的关键字和数组元素。 时间的复杂性是o(n )。 当然，在规则数组的情况下，通过采用二分搜索、插值搜索、斐波那契搜索等方法，可以将搜索的复杂度提高到o ) logn )。 在一般的插入删除操作中，与数组元素的移动相关联，其平均复杂度也是o[n]
线性链表:对于添加、删除链表等操作，只要在找到指定的操作位置后处理节点间的引用即可，时间复杂度为o(1)，但检索操作遍历链表逐个进行
二叉树:对相对平衡的二叉树进行插入、检索、删除等操作，平均复杂度均为o(logn )。
哈希表:与这些数据结构相比，添加、删除、搜索哈希表等操作性能非常高，在不考虑哈希冲突的情况下只需进行一次定位。 时间的复杂性是o(1)。 接下来我们来看看哈希表是如何达到惊人的常数级o )。
据了解，数据结构的物理存储结构只有顺序存储结构和链式存储结构两种。 (堆栈、队列、树、映射等从逻辑结构中提取并映射到内存。 另外，还有这两种物理组织形式。 )如上所述，在排列中，根据下标
例如，要添加或查找某个元素，可以使用一个函数将当前元素的关键字映射到数组中的某个位置，然后使用数组下标进行单次对齐操作。
哈希表的主干就是数组
其中，该函数f一般被称为存储位置 = f(关键字)，该函数的设计好坏直接影响散列表的优劣。 例如，在哈希表中执行插入操作。
哈希函数
简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
但是，并不完美。 如果两个不同的元素从散列函数中得到的实际存储地址相同怎么办？ 也就是说，如果尝试对一个元素执行散列运算，获得存储地址，然后插入，则可以看到它已经被其他元素占用。 其实这叫哈希冲突，也叫散列冲突。 如上所述，散列函数的设计非常重要，好的散列函数尽可能保证哈希冲突和计算简单，但是数组是连续的固定长度的存储器空间，多么好散列冲突怎么解决呢？ 散列冲突的解决方法有：开放地址法(发生冲突时继续查找下一个未占用的内存地址)、重新散列函数法和链地址法，而HashMap是链地址法，即http://www
散列地址分布均匀，
3358 www.Sina.com/http://www.Sina.com/http://www.Sina.com/http://www.Sina.com /
希函数得到相应的地址，如果该地址只有一个键值对（没有链表），则直接取到，如果存在多个键值对（有链表），则使用 .equse()方法对链表上所有的键进行比较，直到找到相应的键值对。但是就算是这样，也无法避免很多键值对的键通过hash算法计算后得到的结果相同，也就是在一个链表中存在很多数据，如果这时候需要从头开始遍历链表，也不是一个好的选择，所以JDK1.8给出了一种优雅的做法——红黑树。在HashMap中Key 不允许重复出现（相信你已经明白为什么了），Value 随意，jdk 8 之前，其内部是由数组+链表来实现的，而 jdk 8 对于链表长度超过 8 的链表将转储为红黑树。
什么是红黑树？要了解红黑树，先来看看二叉树
二叉树： 左子树上所有的节点的值都小于或等于他的根节点上的值右子树上所有节点的值均大于或等于他的根节点的值左、右子树也分别为平衡二叉树例如我们查找 10
1、因为10大于9，所以从右侧开始查找，找到13；
2、 因为10 小于13 所以从13 的左侧继续找，找到11；
3、而10又小于11 所以从11 的左侧找，至此找到10；
4、Game Over ！！！
不过二叉查找树有一些问题，可能会出现不平横的情况，即如下图所示的情况
从这种情况可以看出，明显存在左子树和右子树深度相差过多，在使用平衡情况下的二叉查找树是时间复杂度为logn，而出现这种极端情况的话，想要查9的位置就需要每一次都遍历下一个右子树，很有可能时间复杂度变为n(与数组普通查询的时间复杂度相同)
基于上述情况，引入了平衡二叉树，红黑树即为平衡二叉树的一种
红黑树：
红黑树在线演示地址
节点是红色或黑色根节点一定是黑色每个叶节点都是黑色的空节点(NIL节点)每个红节点的两个子节点都是黑色的(从每个叶子到跟的所有路径上不能有两个连续的红节点)(即对于层来说除了NIL节点，红黑节点是交替的，第一层是黑节点那么其下一层肯定都是红节点，反之一样)从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点有图有真相，上图：
那么红黑树为何如此优秀呢？
假设我们向树中插入20
可以看到，插入以后树已经不是一个平衡的二叉树，而且并不满足红黑树的要求，因为20和21均为红色，这种情况下就需要对红黑树进行变色，21需要变为黑色，22就会变成红色，如果22变成红色，则需要17和25都变成黑色
而17变成黑色显然是不成立的，因为如果17变为黑色，那么13就会变为红色，不满足二叉树的规则，因此此处需要进行另一个操作---------左旋操作
左旋：下图就是一个左旋的例子，一般情况下，如果左子树深度过深，那么便需要进行左旋操作以保证左右子树深度差变小
对于上图由于右子树中17变为黑色以后需要把13变成红色，因此进行一次左旋，将17放在根节点，这样既可保证13为红色，左旋后结果
而后根据红黑树的要求进行颜色的修改
进行左旋后，发现从根节点17，到1左子树的叶子节点经过了两个黑节点，而到6的左叶子节点或者右叶子节点要经历3个黑节点，很显然也不满足红黑树，因此还需要进行下一步操作，需要进行右旋操作
右旋：与左旋正好相反
由于是从13节点出现的不平衡，因此对13节点进行右旋，得到结果
而后再对其节点进行变色，得到结果
参考链接：
https://www.cnblogs.com/chengxiao/p/6059914.html
https://blog.csdn.net/q3244676719/article/details/81540830
https://blog.csdn.net/hefenglian/article/details/79763634