一文彻底搞懂HashMap

文章目录

1. 数据结构
2. 扩容机制
3. 常问问题
- 3.1 HashMap为什么要树化
- 3.2 链表中转红黑树的阈值为什么设为8

1. 数据结构

JDK 7 中的 HashMap 使⽤的是数组 + 链表的实现⽅式，即拉链法。当发生哈希冲突时，即多个键映射到同一个数组索引位置时，HashMap会将这些键值对存储在同一个数组位置上的链表中，并通过链表将它们串联起来。这种实现方式在处理冲突时需要顺序遍历链表，当链表长度较长时，查找效率会降低，导致性能下降。

为了解决这个问题，JDK 8引入了红黑树（Red-Black Tree）来替代链表，以提高在链表长度较长时的查找性能。具体做法是，在发生哈希冲突后，如果链表长度超过一定阈值（默认为8），HashMap会将链表转换为红黑树，这样就可以在O(log n)的时间复杂度内完成查找操作，大大提高了查找性能。这种使用红黑树替代链表的结构被称为树化桶（Tree Bins）。在红黑树的实现中，HashMap保持了与链表相同的API，并且在需要的情况下能够在链表和红黑树之间进行平稳的转换，从而在不同情况下都能够保持较好的性能表现。

JDK 8 中 HashMap 的数据结构是数组+链表+红黑树。
在这里插入图片描述

2. 扩容机制

HashMap 的初始容量是 16，随着元素的不断添加，HashMap 的容量（也就是数组大小）可能不足，于是就需要进行扩容，阈值是capacity * loadFactor，capacity 为容量，loadFactor 为负载因子，默认为 0.75。

扩容后的数组大小是原来的 2 倍，然后把原来的元素重新计算哈希值，放到新的数组中。

HashMap 的性能大大依赖于这三个重要的参数：初始容量（initial capacity）、加载因子（load factor，或者叫负载因子，默认为 0.75）、阈值（threshold）。

当HashMap中的元素数量达到了负载因子与当前容量的乘积时，就会触发扩容操作。

具体来说，HashMap在扩容时会创建一个新的容量是原容量两倍的数组，并将原来数组中的元素重新分配到新的数组中。重新分配的过程包括以下几个步骤：

创建一个新的容量是原容量两倍的数组。
遍历原数组中的每个元素，将其重新计算哈希值，然后根据新数组的长度取模得到新的索引位置。
如果新索引位置上已经有元素存在，采用链表或红黑树的方式处理冲突，将新元素插入到对应位置的链表或红黑树中。
重复以上步骤，直到原数组中的所有元素都被重新分配到新数组中。
在重新分配元素的过程中，由于元素数量增加，可能会发生哈希冲突，需要对冲突进行处理。在 JDK 8 中，如果链表长度超过一定阈值（默认为8），则会将链表转换为红黑树，以提高查找性能。

扩容操作是一个相对耗时的操作，因为它涉及到重新计算哈希值、重新分配元素等操作。为了减少扩容的频率，可以通过调整负载因子来控制HashMap的容量与元素数量的比例，以减少扩容操作的发生频率，从而提高HashMap的性能。

3. 常问问题

3.1 HashMap为什么要树化

在 JDK 8 中，HashMap 在处理哈希冲突时引入了树化机制，即将链表转换为红黑树，这是为了解决在极端情况下链表过长导致的性能问题。

当哈希表中的链表长度超过一定阈值（默认为8）时，HashMap 会将该链表转换为红黑树。这是因为在链表长度过长时，链表的查找效率会变得很低，甚至会退化为 O(n) 的线性查找时间复杂度。而红黑树的平均查找时间复杂度为 O(log n)，远远优于链表。因此，将链表转换为红黑树可以提高 HashMap 的查找性能，特别是在极端情况下，即使在大规模数据集下也能保持较稳定的性能。

树化机制的引入解决了 JDK 7 中 HashMap 的链表退化问题，提高了 HashMap 在处理大规模数据时的性能和稳定性。

3.2 链表中转红黑树的阈值为什么设为8

将链表转换为红黑树的阈值在 JDK 中是一个经过多方面考量和测试确定的参数。设定此阈值的目的是在权衡时间和空间开销的基础上，以提高在大型数据集中的 HashMap 性能。

选择阈值为8的原因主要有以下几点：

性能平衡：较小的阈值意味着更频繁地将链表转换为树，这可能会增加一些性能开销，例如树结构的维护和节点的增加。较大的阈值意味着更少的链表转换，但是当链表长度超过阈值时，链表的性能会急剧下降。因此，阈值的选择需要在时间和空间开销之间进行平衡，以达到最佳性能。
实践经验：阈值的选择可能是基于大量实际数据集的测试和分析。通过观察实际数据集中链表的长度分布，可以确定一个合适的阈值，以便在绝大多数情况下都能够有效地提高性能。
性能优化：较小的阈值可以更早地将链表转换为树，从而减少链表的长度，提高树的性能。同时，较小的树在插入、删除等操作时可能具有更高的效率，因为树的平衡性更容易维持。
内存开销：将链表转换为树会增加一些额外的内存开销，包括树节点的存储和维护。选择较小的阈值可以控制树的大小，从而限制额外的内存开销。

总的来说，将链表转换为红黑树的阈值为8是在性能、内存开销和实践经验的基础上做出的权衡选择，旨在在大多数情况下提供最佳的性能和稳定性。

标签：黑树,HashMap,阈值,性能,链表,数组,搞懂,一文
From： https://blog.csdn.net/weixin_44772566/article/details/136972092