HashMap为什么用链表加红黑树？目的是什么？原理是什么

灰太狼 2023-10-08 15:53 37阅读 0赞

关于HashMap的详解文章：

链接: [HashMap源码研究——源码一行一行的注释][HashMap]

#### 文章目录 ####

*  1为什么用链表？
 *  2为什么用红黑树？
 *   *  2.1 红黑树概述
     *  2.2 红黑树性质
     *  为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？？？？
     *  2.4 红黑树的优势
     *  2.5 HashMap使用红黑树总结
 *  3HashMap在jdk1.8之后引入了红黑树的概念，为什么采用6和8进行红黑树和链表转化

关于hashmap的其他有关问题我在源码研究专栏中都有讲解，深入到源码层次的讲解，绝对一看就懂  
链接: [深入源码，探究设计思想][Link 1]

在jdk1.8版本后，Java对HashMap做了改进，在链表长度大于8的时候，将后面的数据存在红黑树中，以加快检索速度。

## 1为什么用链表？ ##

一句话回答：  
**用链表是为了应对哈希冲突这种情况的**

我们都知道hashmap是根据算得哈希值来确定数据存放的位置，但是我们也知道哈希值会一样，也就是哈希碰撞这种情况。  
为了让哈希值一样的数据能有地方存储，于是采用了当发生哈希碰撞时，在原数据位置继续存放的方式，而链表这种数据结构就刚好满足要求

## 2为什么用红黑树？ ##

这个问题就比较大了，对于不懂红黑树的小伙伴，我先大致介绍一下红黑树，懂红黑树的小伙伴直接移步至2.5即可，跳过此节。

### 2.1 红黑树概述 ###

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

下图是一个红黑树的例子。其中26是根节点；最下面是哨兵结点；每个叶节点的空指针指向哨兵结点。

![在这里插入图片描述][f58042f952604d7d949b2e827d8c5259.png]

### 2.2 红黑树性质 ###

*  红黑树是每个节点都带有颜色属性的二叉查找树，颜色是红色或黑色（ 没有平衡二叉树（-1 +1 0）的平衡度高，左右孩子高度差可以超过1 ）。
 *  在二叉查找树强制一般要求（即中序遍历是由小到大）以外，对于任何有效的红黑树我们增加了如下的额外要求:
 *  每个节点是红色或黑色（即必须是红或黑的一种。其中新插入的结点必须着色成红色）。
 *  根节点是黑色。
 *  每个叶节点（指NIL哨兵结点）是黑色。
 *  每个红色节点的两个子节点都是黑色。(即从每个叶子到根的所有路径上不能有两个连续的红色节点；而当双亲是黑，对孩子没要求，一黑一红、两黑、两红都行（即黑色可以连续）)
 *  从任一节点到其每个叶子（算上了哨兵结点）的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

### 为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？？？？ ###

*  每个红色节点的两个子节点都是黑色。
 *  从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
 *  最短路径为全黑，最长路径就是红黑节点交替（因为红色节点不能连续），每条路径的黑色节点相同，则最长路径、刚好是最短路径的两倍。

![在这里插入图片描述][09b4d9712ffe4ab78adf165a037604a0.png]

### 2.4 红黑树的优势 ###

*  红黑树是”近似平衡“的。
 *  红黑树相比avl树，在检索的时候效率其实差不多，都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡，他允许局部很少的不完全平衡，这样对于效率影响不大，但省去了很多没有必要的调平衡操作，avl树调平衡有时候代价较大，所以效率不如红黑树，在现在很多地方都是底层都是红黑树的天下啦。
 *  红黑树的高度只比高度平衡的AVL树的高度（log2n）仅仅大了一倍，在性能上却好很多。
 *  HashMap在里面就是链表加上红黑树的一种结构，这样利用了链表对内存的使用率以及红黑树的高效检索，是一种很happy的数据结构。
 *  AVL树是一种高度平衡的二叉树，所以查找的非常高，但是，有利就有弊，AVL树为了维持这种高度的平衡，就要付出更多代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用AVL树的代价就有点高了。
 *  红黑树只是做到了近似平衡，并不严格的平衡，所以在维护的成本上，要比AVL树要低。
 *  所以，红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。

### 2.5 HashMap使用红黑树总结 ###

*  java8不是用红黑树来管理hashmap，而是在hash值相同的情况下（且重复数量大于8），用红黑树来管理数据。 红黑树相当于排序数据，可以自动的使用二分法进行定位，性能较高。一般情况下，hash值做的比较好的话基本上用不到红黑树。
 *  红黑树牺牲了一些查找性能 但其本身并不是完全平衡的二叉树。因此插入删除操作效率略高于AVL树。
 *  AVL树用于自平衡的计算牺牲了插入删除性能，但是因为最多只有一层的高度差，查询效率会高一些。

## 3HashMap在jdk1.8之后引入了红黑树的概念，为什么采用6和8进行红黑树和链表转化 ##

6和8是指：表示若桶中链表元素超过8时，会自动转化成红黑树；若桶中元素小于等于6时，树结构还原成链表形式。

1）原因：  
　　红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。

2）选择6和8的原因1：  
如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。

2）选择6和8的原因2：  
　　中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

[HashMap]: https://blog.csdn.net/weixin_44688973/article/details/119865191?spm=1001.2014.3001.5502
[Link 1]: https://blog.csdn.net/weixin_44688973/category_11281662.html
[f58042f952604d7d949b2e827d8c5259.png]: https://img-blog.csdnimg.cn/f58042f952604d7d949b2e827d8c5259.png
[09b4d9712ffe4ab78adf165a037604a0.png]: https://img-blog.csdnimg.cn/09b4d9712ffe4ab78adf165a037604a0.png