hashmap的链表什么时候会变成红黑树

在Java的HashMap中，当某个桶（bucket）中存储的链表长度超过阈值（默认为8），且当前HashMap的容量大于等于64时，会将链表转换为红黑树。

这个转换操作是为了提高在长链表中进行查找、插入和删除操作的效率。红黑树是一种自平衡的二叉查找树，它的查找、插入和删除操作的时间复杂度都是O(log n)，相对于链表的O(n)具有更好的性能。

当链表转换为红黑树后，如果其中的元素数量减少到小于6，红黑树将会被重新转换回链表结构。

需要注意的是，在Java 8之前的版本中，HashMap使用的是扩展链表（linked list）而不是红黑树。而在Java 8引入了红黑树的优化机制，使得在特定条件下能够更高效地处理哈希冲突。

相关问题

hashmap链表转红黑树

哈希表（HashMap）在存储键值对时，使用链表来解决哈希冲突。当链表长度达到一定阈值时，链表会转换为红黑树，以提高查找、插入和删除操作的性能。

下面是HashMap中链表转换为红黑树的大致过程：

1. 当链表长度超过阈值（默认为8）时，HashMap会将该链表转换为红黑树。

2. 首先，HashMap会判断当前HashMap的容量是否小于64，如果小于64，则会先进行扩容，以便红黑树能够更好地发挥性能优势。

3. 创建一个新的TreeNode对象，该对象持有链表的头节点作为根节点，并将链表中的元素逐个复制到红黑树中。

4. 在进行复制操作时，HashMap会对键进行哈希计算，并根据哈希值在红黑树中找到对应的位置。

5. 如果发现在当前位置已经存在相同的键，则会进行值的替换，否则会将新的键值对添加到红黑树中。

6. 最后，将链表的头节点替换为新创建的红黑树节点，并更新相应的引用。

通过将链表转换为红黑树，HashMap可以在一定程度上减少哈希冲突带来的性能损耗，提高查找、插入和删除操作的效率。

为什么HashMap 链表长度为64后变为红黑树

当链表长度达到一定阈值（默认为8），HashMap 会将链表转化为红黑树，这是为了提高查找、插入和删除的效率。理论上，链表的时间复杂度为 O(n)，而红黑树的时间复杂度为 O(log n)，因此当链表长度过长时，红黑树的效率更高。

但是，由于红黑树的结构比链表复杂，所以在链表长度较短时，使用红黑树反而会浪费更多的空间和时间。因此，为了平衡时间和空间的利用效率，HashMap 采用了链表和红黑树相结合的方式，当链表长度达到阈值时，才将其转化为红黑树。