[**14.链表是怎么转换成红黑树的？**](#14)

链表转换成红黑树的过程又称为链表升级为红黑树。Redis中的有序集合（Sorted Set）就是使用了这种数据结构。

链表转换成红黑树的具体过程如下：

1. 在链表的基础上，每隔一定的节点（默认为64个节点）选择一个节点，将这个节点作为根节点，然后将其余的节点分别作为左子树或右子树的叶子节点，构建一棵初步的红黑树。

2. 在初步构建的红黑树上进行调整，使其符合红黑树的性质。

3. 如果在插入或删除节点时，红黑树中的节点数量小于64个，可以将红黑树转换成链表。

这种数据结构的优点是在节点数量较少时使用链表进行存储，可以节省内存，而在节点数量较多时，使用红黑树进行存储，可以提高插入、删除、查找等操作的效率。而且链表升级为红黑树的过程是可逆的，可以在需要时将红黑树转换回链表。

相关问题

[**6.为什么会选择8作为链表转红黑树的阈值？**](#6)

在JDK1.8中，将链表转化为红黑树的阈值默认为8，这是一个经验值。理论上，红黑树的查找效率要高于链表，但是红黑树的插入、删除等操作也比链表要复杂和耗时，而且还需要额外的内存空间来存储树的节点。因此，为了平衡时间和空间的开销，选择合适的阈值非常重要。

8这个值是根据测试结果得出的，考虑了大量的因素，如CPU的缓存行大小等。经过测试，8被认为是一个比较合适的值，可以在大多数情况下达到比较好的性能和空间开销的平衡。但是，对于特定的应用场景，可能需要根据具体情况调整阈值，以达到更好的性能。

hashMap转红黑树的条件？

在Java 8中，HashMap的实现使用了红黑树来优化哈希冲突的性能。当一个桶中的元素个数超过了某个阈值（默认为8），并且当前HashMap的容量大于64时，会将这个桶中的链表转换为红黑树。具体的转换过程如下：

1. 遍历桶中的所有元素，统计元素个数；

2. 如果元素个数小于等于8，则不进行转换，仍然使用链表存储；

3. 如果元素个数大于8，则将链表转换为红黑树，这个过程会重新构建红黑树，需要耗费一定的时间和空间；

4. 如果转换后红黑树的元素个数小于等于6，则将红黑树重新转换为链表。

需要注意的是，转换过程是需要耗费一定时间和空间的，因此当HashMap中元素的数量较少时，使用链表进行存储更加高效。转换为红黑树可以提高元素查找的效率，但是对于插入和删除操作，红黑树的效率并不一定比链表高。因此，在实际应用中，需要根据实际情况来选择合适的数据结构。