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

HashMap在Java中是一种常用的散列表实现。链表是HashMap中常用的存储结构，其中链表的长度被称为链表的阈值。当链表的长度达到一定阈值时，HashMap会将链表转换为红黑树，以提高查询性能。

在Java 8中，链表转换为红黑树的阈值为64。这个值是由Java开发人员根据性能测试结果确定的，旨在在保证性能的同时尽可能减少红黑树的使用。

转换为红黑树的原因是，红黑树是一种平衡二叉树，它可以保证查询、插入和删除操作的时间复杂度都是O(log n)。而链表的时间复杂度是O(n)，在链表长度较长时查询效率就会下降。因此，为了提高查询效率，HashMap在链表长度达到一定阈值时会将链表转换为红黑树。

相关问题

hashmap链表长度为8，数组长度为什么是64才转红黑树

在Java 8中，HashMap的实现使用了"拉链法"（Chaining）来解决哈希冲突，即将哈希值相同的键值对存储在同一个链表上。默认情况下，HashMap的初始容量为16，负载因子为0.75，当HashMap中键值对的数量超过容量和负载因子的乘积时，就需要进行扩容操作。在扩容的过程中，HashMap会将数组长度扩大为原来的两倍，并将所有的键值对重新散列到新的数组中。

当链表长度超过8时，Java 8中的HashMap会将链表转换为红黑树来提高查询效率。这是因为，当链表长度过长时，查询操作的时间复杂度就会变得很高，甚至接近于O(n)，而红黑树的查询操作时间复杂度为O(log n)，所以将链表转换为红黑树可以大大提高查询效率。

因此，当HashMap中的链表长度超过8时，会考虑将链表转换为红黑树，而数组的长度在扩容的过程中会自动变成原来的两倍。所以，当数组长度为64时，每个链表的平均长度为8，正好符合转换为红黑树的条件。

hashmap链表长度为8，数组长度为什么是64才转红黑树，详细说明数组长度

### 回答1：
在Java 8中，HashMap内部使用了数组和链表来实现键值对的存储。数组用来存储桶（bucket），每个桶下面会挂一个单向链表，用来存放键值对。

当链表长度超过8时，HashMap会将链表转化为红黑树，以提高查找效率。而数组长度的选择则是为了在不同负载因子下，保证不同的性能表现。

负载因子是指HashMap中已经存储的键值对数量与数组长度之比。当负载因子大于等于0.75时，HashMap会将数组长度扩大一倍，以减少哈希冲突的概率。因为随着数组长度的增加，哈希冲突的概率会逐渐降低。

而当数组长度大于等于64时，每个桶的平均链表长度为8时，HashMap会将链表转化为红黑树。这是因为，当链表长度较短时，使用链表比较快；但当链表长度过长时，查找效率会变得很低。而使用红黑树可以将查找时间从O(n)降低到O(log n)，提高了HashMap的性能。具体的转化条件可以看下面的代码：

static final int TREEIFY_THRESHOLD = 8;

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bin. 
 */
static final int MIN_TREEIFY_CAPACITY = 64;

在Java 8中，数组长度为2的整数次幂，这样可以通过位运算来计算哈希值对数组长度取模，提高效率。因此，数组长度为64是因为它既可以容纳足够多的键值对，也可以提供足够的桶数，同时在进行哈希运算时也比较高效。

### 回答2：
在HashMap中，数组的长度涉及到HashMap的扩容机制和红黑树的转换条件。

首先，HashMap中的数组长度决定了HashMap的存储容量，当数组中的元素个数超过数组长度的0.75倍（即负载因子为0.75）时，HashMap会自动触发扩容操作。扩容操作会重新计算所有元素的哈希值，然后根据新的数组长度重新散列到新的数组中。

其次，当链表长度超过8时，HashMap会考虑将链表转换为红黑树。这是因为链表的增删操作的时间复杂度为O(n)，当链表长度过长时，查找效率会变低。而红黑树可以保证查找、插入和删除操作的时间复杂度都为O(log n)，效率更高。

为了平衡存储容量和查询效率之间的关系，HashMap设置了一个阈值，即当数组的长度大于等于64时，才会将链表转换为红黑树。这是因为当数组长度过小时，哈希冲突的概率较低，使用链表存储即可满足查询效率的要求。但当数组长度变大时，哈希冲突的概率会增加，此时将链表转换为红黑树能够更好地提高查询效率。

综上所述，HashMap中的数组长度为64才能触发链表转换为红黑树的条件，是为了在满足存储容量和查询效率的前提下，平衡哈希冲突的概率和查询操作的效率。

### 回答3：
在HashMap中，数组的长度决定了HashMap的容量。HashMap使用数组和链表的结合来实现数据存储和高效的查找。当HashMap的元素较少时，直接使用数组来存储元素是最高效的，而当元素增多时，就需要进行优化。

数组的长度为64之所以被选为转换红黑树的阈值，是因为这个值经过了大量的实验和研究得出的最优值。在这个长度的数组中，每个数组位置上的链表平均长度为8时，哈希查找和插入操作均能在O(1)的时间复杂度内完成。

当链表长度超过8时，为了维持HashMap的高效性能，就需要将链表转化为红黑树。红黑树是一种自平衡的二叉搜索树，它能够保证在最坏情况下，查找、插入和删除操作的时间复杂度为O(log n)。通过将链表转换为红黑树，可以大大提升在大容量HashMap中的操作效率。

为什么数组长度为64才转换为红黑树？这是因为在链表长度较小时，红黑树的数据结构相对于链表来说，具有更大的存储开销。只有当链表长度超过一定阈值时，将链表转换为红黑树才能带来性能上的提升。而64作为阈值的选取，可以在大多数情况下平衡存储开销和性能之间的关系。

总而言之，当HashMap中的链表长度超过8时，为了保持操作的高效性能，会选择将链表转换为红黑树。数组长度为64是经验值，在这个长度的数组中进行转换，可以在大容量HashMap中取得较好的性能表现。