hashMap的树化原理

哈希表的树化原理是指，当哈希表中的某个桶(bucket)中有大量的键值对时，为了减少哈希表的查找时间和空间占用，该桶中的链表将转换为树形结构。这种树结构被称为红黑树。

当一个桶中的链表长度超过了根据 JDK 的默认负载因子所计算的阈值(默认值为8)，此桶中的所有键值对将转移到一棵新的红黑树中。在这个过程中，所有的键都必须实现 Comparable 接口，因为红黑树中的节点必须是可比较的。

以树的结构代替链表可以显著地减少哈希表的查找时间，因为树的平均查找时间复杂度为 O(log n)，而链表的查找时间复杂度为 O(n)。通过使用红黑树，可以将最坏情况下的查找时间复杂度从 O(n) 降至 O(log n)。

此外，将链表转换为红黑树还有一个好处，就是可以减少哈希表空间的占用。当哈希表中的桶被树化后，可以节省大量的节点对象的内存分配，从而减少了 GC 的压力。

相关问题

hashmap红黑树树化退化

HashMap中的红黑树树化退化是指当链表中的节点数量较多时，HashMap会将链表转化为红黑树来提高查找效率。红黑树是一种自平衡的二叉查找树，可以在O(logN)的时间复杂度内进行查找、插入和删除操作。

在HashMap中，当某个哈希桶中的链表节点数量超过一个阈值（TREEIFY_THRESHOLD）时，就会触发将链表转化为红黑树的操作。这个阈值的默认值是8。具体的判断条件是binCount >= TREEIFY_THRESHOLD - 1。

转化为红黑树后，原本的链表结构就会被改变成一个更高效的树结构，这样就可以在更快的时间内执行查找、插入和删除操作。当然，如果在某些操作之后，哈希桶中的节点数量减少到一个较小的值（UNTREEIFY_THRESHOLD），则会将红黑树恢复为链表，以节省空间。

总之，在HashMap中，红黑树树化退化是为了提高链表操作的效率而引入的优化机制，它可以在特定的条件下将链表转化为红黑树，并且在节点数量变少时将红黑树恢复为链表。这样可以更好地平衡查找速度和空间的利用。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *2* *3* [HashMap红黑树原理详解及源码分析](https://blog.csdn.net/qq_43207114/article/details/128617285)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]

HashMap底层实现原理

HashMap是基于哈希表实现的，它的底层数据结构主要包括数组和链表（或红黑树）。具体实现原理如下：

1. 初始化HashMap时，会创建一个数组table用于存储数据，默认大小为16。

2. 当我们向HashMap中添加键值对时，首先会根据键的哈希值计算该键值对在数组中的位置。

3. 如果该位置上已经存在数据，那么就需要判断这个数据是否与要添加的数据的键相同。如果键相同，就直接替换掉原有的值；如果键不同，就需要采用链表（或红黑树）的方式来存储。在Java 8中，如果链表长度超过8，就会将链表转为红黑树。

4. 如果该位置上没有数据，就直接将键值对存储在该位置上。

5. 当我们通过键来获取值时，首先需要根据键的哈希值计算在数组中的位置，然后在该位置上查找对应的数据。如果该位置上没有数据，那么就返回null；如果该位置上有数据，就需要判断这个数据是否与要查找的键相同。如果相同，就返回对应的值；如果不同，就需要在链表（或红黑树）中继续查找，直到找到相同的键或者链表（或红黑树）结束。

6. 当我们从HashMap中删除键值对时，首先需要根据键的哈希值计算在数组中的位置，然后在该位置上查找对应的数据。如果该位置上没有数据，就不需要删除；如果该位置上有数据，就需要判断这个数据是否与要删除的键相同。如果相同，就直接删除；如果不同，就需要在链表（或红黑树）中继续查找，直到找到相同的键或者链表（或红黑树）结束。

总体而言，HashMap的底层实现原理主要涉及哈希函数、数组、链表（或红黑树）、键值对等概念。它的优点是可以快速地存储、查找和删除键值对，但也存在一些缺点，比如哈希冲突、扩容等问题。