HashMap何时会链表转红黑树

朱雀 2024-03-24 08:39 104阅读 0赞

#### 目录 ####

*   *  什么时候才会转换为红黑树？
     *  为什么要转换为红黑树？
     *  为什么不一开始就用红黑树，反而要经历一个转换的过程呢？
     *  从链表转化为红黑树的阈值为什么是8？

### 什么时候才会转换为红黑树？ ###

当Map链表长度大于或等于阈值TREEIFY\_THRESHOLD（默认为 8）的时候，如果同时还满足容量(数组的长度)大于或等于 MIN\_TREEIFY\_CAPACITY（默认为 64）的要求，就会把链表转换为红黑树。同样，后续如果由于删除或者其他原因调整了大小，当红黑树的节点小于或等于 6 个以后，又会恢复为链表形态。

### 为什么要转换为红黑树？ ###

每次遍历一个链表，平均查找的时间复杂度是 **O(n)**，n 是链表的长度。红黑树有和链表不一样的查找性能，由于红黑树有自平衡的特点，可以防止不平衡情况的发生，所以可以始终将查找的时间复杂度控制在 **O(logn)**。最初链表还不是很长，所以可能 O(n) 和 O(log(n)) 的区别不大，但是如果链表越来越长，那么这种区别便会有所体现。所以为了提升查找性能，需要把链表转化为红黑树的形式。

### 为什么不一开始就用红黑树，反而要经历一个转换的过程呢？ ###

JDK 的源码注释中已经对这个问题作了解释：  
![在这里插入图片描述][2e9a665e5eb34b16a98ccf4d9741b161.png]  
这段话的意思是：**因为树节点(TreeNodes)所占的空间是普通节点Node的两倍**，所以我们只有在桶中包含足够的节点时才使用树节点(请参阅TREEIFY\_THRESHOLD)(只有在同一个哈希桶中的节点数量大于等于TREEIFY\_THRESHOLD时，才会将该桶中原来的链式存储的节点转化为红黑树的树节点)。并且当桶中的节点数过少时 (由于移除或调整)，树节点又会被转换回普通节点(当桶中的节点数量过少时，原来的红黑树树节点又会转化为链式存储的普通节点)，以便节省空间。

### 从链表转化为红黑树的阈值为什么是8？ ###

通过查看源码可以发现，默认是链表长度达到 8 就转成红黑树，而当长度降到 6 就转换回去，**这体现了时间和空间平衡的思想**，最开始使用链表的时候，空间占用是比较少的，而且由于链表短，所以查询时间也没有太大的问题。可是当链表越来越长，需要用红黑树的形式来保证查询的效率。对于何时应该从链表转化为红黑树，需要确定一个阈值，这个阈值默认为 8，并且在源码中也对选择 8 这个数字做了说明，原文如下：  
![在这里插入图片描述][8df701185e4444f79e07b938f156bc54.png]  
如果 hashCode 分布良好，也就是 hash 计算的结果离散好的话，那么红黑树这种形式是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。**在理想情况下，桶(bins)中的节点数概率(链表长度)符合泊松分布，当桶中节点数(链表长度)为 8 的时候，概率仅为 0.00000006。这是一个小于千万分之一的概率**，通常我们的 Map 里面是不会存储这么多的数据的，所以通常情况下，并不会发生从链表向红黑树的转换。  
但是，HashMap 决定某一个元素落到哪一个桶里，是和这个对象的 hashCode 有关的，JDK 并不能阻止我们用户实现自己的哈希算法，如果我们故意把哈希算法变得不均匀，例如：  
![在这里插入图片描述][1d0270911e7841c580b9586a1ab73042.png]  
事实上，链表长度超过 8 就转为红黑树的设计，更多的是为了防止用户自己实现了不好的哈希算法时导致链表过长，从而导致查询效率低，而此时转为红黑树更多的是一种保底策略，用来保证极端情况下查询的效率。

通常如果 hash 算法正常的话，那么链表的长度也不会很长，那么红黑树也不会带来明显的查询时间上的优势，反而会增加空间负担。所以通常情况下，并没有必要转为红黑树，所以就选择了概率非常小，小于千万分之一概率，也就是长度为 8 的概率，把长度 8 作为转化的默认阈值。

所以如果平时开发中发现 HashMap 或是 ConcurrentHashMap 内部出现了红黑树的结构，这个时候往往就说明我们的哈希算法出了问题，需要留意是不是我们实现了效果不好的 hashCode 方法，并对此进行改进，以便减少冲突。

[2e9a665e5eb34b16a98ccf4d9741b161.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/73dfc4624fe84c10a78f4acd13260def.png
[8df701185e4444f79e07b938f156bc54.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/0e7421eda26144c0b4253e4d27381008.png
[1d0270911e7841c580b9586a1ab73042.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/5a04dfa34fde49caaa8ea02cea668ba6.png