hashmap的底层结构，什么情况下链表转为红黑树

HashMap的底层结构是数组+链表（或者红黑树）。当发生哈希冲突时，会将元素插入到链表的末尾，如果链表长度超过8个元素，且当前HashMap的容量大于等于64，则链表会转化为红黑树，以提高查找效率。

具体而言，当链表长度超过8个元素时，HashMap会将当前链表转化为红黑树，即将链表中的元素按照哈希值的大小顺序重新排序，然后构建红黑树。这样做的目的是为了提高搜索的效率，因为红黑树的查找时间复杂度为O(log n)，比链表的O(n)更快。但是，当元素数量不足8个时，转化为红黑树反而会增加时间和空间的开销，因此只有在链表长度超过8个元素时才会进行转化。

相关问题

HashMap什么情况下会用到数组,链表,红黑树,等数据结构

HashMap中的每个元素都是一个键值对，其中键是唯一的，而值可以重复。当HashMap中的元素数量较少时，它们通常被存储在一个数组中，每个元素都是一个链表，其中包含所有具有相同哈希码的键值对。这种情况下，HashMap使用链表来解决哈希冲突。当元素数量增加时，链表可能会变得非常长，这会导致查找时间变慢。为了解决这个问题，当链表长度超过一个阈值时，HashMap会将链表转换为红黑树，以提高查找效率。因此，当HashMap中的元素数量较多时，它们通常被存储在一个数组中，每个元素都是一个红黑树，其中包含所有具有相同哈希码的键值对。

hashmap的存储结构到底是红黑树加链表还是红黑树➕数组

HashMap的存储结构是红黑树加链表（或者黑树加数组）。

在Java 8之前，HashMap使用的是数组加链表的存储结构。具体来说，HashMap内部维护了一个Entry数组，每个数组元素是一个链表的头节点，每个链表节点包含了键值对的信息。当发生哈希冲突时，即不同的键经过哈希函数计算得到相同的索引位置时，新的键值对会被插入到对应索引位置的链表中。

然而，由于链表在查找和插入操作上的效率较低，当链表长度过长时，HashMap的性能会受到影响。为了解决这个问题，Java 8引入了红黑树作为链表的替代结构。当链表长度超过一定阈值（默认为8）时，链表会被转换为红黑树，以提高查找和插入操作的效率。

而在Java 8之后，当链表长度小于等于8时，HashMap仍然使用链表存储结构；当链表长度大于8时，HashMap会将链表转换为红黑树。这样可以在保证性能的同时，减少了红黑树的创建和维护成本。

总结起来，HashMap的存储结构可以是红黑树加链表（或者红黑树加数组），具体取决于链表的长度和Java版本。