【后端那些事儿】Java的HashMap数据结构详解_hashmap 使用场景

目录

什么是HashMap

HashMap的应用场景

什么是红黑树

为什么选用红黑树作为底层的数据结构

HashMap一开始就是红黑树吗

---

什么是HashMap

在Java中，HashMap是一个常见的集合类，它实现了Map接口，提供了键值对存储和检索的功能。下面对Java中的HashMap进行详细解析：

1. 原理：HashMap底层采用数组和链表（或红黑树）的结合来实现。当哈希冲突发生时，采用链表或红黑树来处理冲突，以提高查找效率。

2. 特点：

   • 键的唯一性：HashMap中的键是唯一的，如果插入的键已经存在，则会进行替换。
   • 元素的无序性：HashMap中的元素存储是无序的，不是按照插入顺序来存储。
   • 允许null键和null值：HashMap允许将null作为键或值。

3. 使用方法：

   • 添加元素：使用put(key, value)方法将键值对添加到HashMap中。
   • 删除元素：使用remove(key)方法根据键删除对应的键值对。
   • 获取元素：使用get(key)方法根据键获取对应的值。
   • 判断是否包含键或值：使用containsKey(key)和containsValue(value)方法。

4. 初始容量和负载因子：HashMap在创建时，可以指定其初始容量和负载因子。初始容量是指HashMap中可以容纳的键值对的个数，默认为16；负载因子是指HashMap在扩容时，达到多少比例时进行扩容，默认为0.75。当HashMap中元素的数量达到初始容量乘以负载因子时，就会进行扩容。

5. 遍历方式：可以通过迭代器、forEach循环和keySet()、values()、entrySet()等方法来遍历HashMap中的键值对。

HashMap的应用场景

HashMap在Java中的应用场景非常广泛，常见的应用场景包括但不限于以下几种：

1. 缓存：HashMap可以作为缓存数据的容器，其中键可以是用于快速检索数据的索引，值可以是从数据库或其他耗时操作中获取的数据。通过在HashMap中保存数据，可以避免重复获取数据，提高系统性能。

2. 数据索引：HashMap可以作为索引数据的容器，其中键可以用于唯一标识数据，值可以存储数据的引用。这样可以快速根据键来获取对应的数据，而无需遍历整个数据集。

3. 缓存控制：HashMap可以用于实现缓存的过期机制。通过为每个键值对设置过期时间，在访问时判断是否过期，如果过期则移除。这样可以减少内存的占用。

4. 数据分组：HashMap可以通过键值对的方式将数据分组，键可以是用于区分不同组的标识，值可以是属于同一组的数据集合。通过HashMap的键值对结构，可以方便地按照组进行数据的存储和检索。

5. 缓存数据的排序：HashMap在Java8及以后的版本中，可以通过Stream API和Lamdba表达式对键值对进行排序。这样可以方便地对缓存数据进行排序操作，提高数据的展示效果。

需要注意的是，由于HashMap是非线程安全的，如果在多线程环境下使用，需要进行额外的同步处理，或者使用线程安全的Map实现类，如ConcurrentHashMap。

什么是红黑树

红黑树是一种自平衡的二叉搜索树数据结构。它在每个节点上增加了一个额外的"颜色"属性，可以是红色或黑色。红黑树满足以下性质：

1. 每个节点要么是红色，要么是黑色。
2. 根节点是黑色。
3. 每个叶子节点（空节点）是黑色。
4. 如果一个节点是红色，那么它的子节点必须是黑色。
5. 从任意节点到其每个叶子节点的路径上包含相同数量的黑色节点。

这些性质确保了红黑树的平衡性，使得最长路径不会超过最短路径的两倍，保证了树的查找、插入和删除的性能都能在对数时间复杂度内完成。

为什么选用红黑树作为底层的数据结构

Java中的HashMap在内部使用了一个数组来存储键值对，这个数组被称为哈希桶（hash bucket）。当键值对被放入哈希桶中时，HashMap会根据键的哈希值来计算它在数组中的索引位置，然后将键值对放入该位置。

然而，随着元素的不断插入，哈希桶可能会出现哈希冲突，即不同键计算得到的索引位置相同。为了解决哈希冲突，Java的HashMap使用了链地址法，即在同一个索引位置上，将冲突的键值对使用链表连接起来。

然而，当链表中的元素数量较多时，链表的遍历操作会变得比较耗时，因为它需要遍历整个链表才能找到目标键值对。为了提高性能，当链表的长度超过阈值（默认为8）时，Java的HashMap会将链表转换为红黑树。

红黑树是一种自平衡的二叉搜索树，它的插入、删除和查找操作的时间复杂度都是O(logN)。相比于链表，红黑树的查找速度更快，特别是当键值对较多时。

因此，Java的HashMap使用红黑树来优化具有较长链表的情况，以提高查找性能。然而，当链表中的元素数量变少，红黑树的复杂性会使得性能下降，因此在链表长度小于6时，Java的HashMap会将红黑树转换回链表。这样，HashMap能够根据元素数量的变化，灵活地选择使用链表或红黑树来存储键值对，以实现最佳的性能。

HashMap一开始就是红黑树吗

Java的HashMap最初是使用数组和链表的数据结构来实现的，在JDK 1.8版本中引入了红黑树作为HashMap的一种优化策略。

在JDK 1.8之前，当HashMap中的冲突较多时，即一个桶中的元素较多时，HashMap使用的是链表来解决冲突问题。然而，当链表的长度过长时，查找一个元素的时间复杂度将会变得很高，从而影响了HashMap的性能。

因此，可以说JDK 1.8版本之后的HashMap开始采用红黑树作为一种优化策略，而不是一开始就是红黑树。

当哈希表中某个位置的链表长度超过一定阈值时，会将该位置的链表转换为红黑树，以提高查询效率。具体来说，当链表长度超过8时，会将链表转换为红黑树。

此转换过程是为了解决哈希冲突问题，当哈希表的负载因子过大时，链表的查找效率会降低，因为链表需要遍历查找目标元素。而红黑树的平均查找时间复杂度为O(log n)，相比之下，链表的平均查找时间复杂度为O(n)。

通过将链表转换为红黑树，可以在大部分情况下将查找时间降低为O(log n)，从而提高HashMap的性能。当链表长度减少到一定程度时，会将红黑树再次转换为链表，以节省内存空间。