引导者# HashMap底层数据结构## 简介HashMap 是 Java 集合框架中的一个重要组成部分，它基于哈希表实现，提供了键值对（key-value）的存储和快速查找功能。在实际应用中，HashMap 以其高效的性能成为开发人员处理大规模数据时的首选工具之一。本文将详细介绍 HashMap 的底层数据结构及其工作原理。---## 1. 数据结构概述HashMap 的核心在于其底层的数据结构设计。它主要由以下几个部分组成：-
数组
：用于存储数据的核心容器。 -
链表
：解决哈希冲突的主要手段。 -
红黑树
：在链表长度超过一定阈值时，转换为红黑树以优化查询效率。这些数据结构共同协作，使得 HashMap 能够在平均时间复杂度为 O(1) 的情况下完成插入、删除和查找操作。---## 2. 数组与哈希函数### 2.1 数组的作用HashMap 内部维护一个数组，称为
table
，用于存储数据。数组的每个元素被称为
桶（bucket）
，每个桶可以存放多个键值对。当需要存储一个键值对时，首先通过哈希函数计算出该键对应的哈希值，然后根据哈希值映射到数组中的某个位置。```java
// table 是 HashMap 的核心数组
transient Node
哈希冲突
。HashMap 通过链表来解决这一问题。### 3.2 链表的结构当发生哈希冲突时，新的键值对会被追加到对应桶中的链表末尾。链表的节点类型为 `Node`，包含以下字段：- `key`：键
- `value`：值
- `next`：指向下一个节点的引用```java
static class Node
rehashing
。```java
void resize() {Node
HashMap底层数据结构
简介HashMap 是 Java 集合框架中的一个重要组成部分，它基于哈希表实现，提供了键值对（key-value）的存储和快速查找功能。在实际应用中，HashMap 以其高效的性能成为开发人员处理大规模数据时的首选工具之一。本文将详细介绍 HashMap 的底层数据结构及其工作原理。---
1. 数据结构概述HashMap 的核心在于其底层的数据结构设计。它主要由以下几个部分组成：- **数组**：用于存储数据的核心容器。 - **链表**：解决哈希冲突的主要手段。 - **红黑树**：在链表长度超过一定阈值时，转换为红黑树以优化查询效率。这些数据结构共同协作，使得 HashMap 能够在平均时间复杂度为 O(1) 的情况下完成插入、删除和查找操作。---
2. 数组与哈希函数
2.1 数组的作用HashMap 内部维护一个数组，称为 **table**，用于存储数据。数组的每个元素被称为 **桶（bucket）**，每个桶可以存放多个键值对。当需要存储一个键值对时，首先通过哈希函数计算出该键对应的哈希值，然后根据哈希值映射到数组中的某个位置。```java
// table 是 HashMap 的核心数组
transient Node
2.2 哈希函数的设计为了提高数据分布的均匀性，HashMap 使用了高效的哈希函数来计算键的哈希值，并将其映射到数组的索引范围内。Java 中的 `hashCode()` 方法会返回一个整数值，而 HashMap 会对这个值进行进一步处理，以确保它落在数组的合法范围内：```java static final int hash(Object key) {int h;return (h = key.hashCode()) ^ (h >>> 16); } ```这段代码通过位运算增强了哈希值的随机性，从而减少哈希冲突的可能性。---
3. 链表与哈希冲突
3.1 哈希冲突的定义即使使用了高效的哈希函数，仍然可能因为数组大小有限而导致不同键的哈希值相同，这种情况称为 **哈希冲突**。HashMap 通过链表来解决这一问题。
3.2 链表的结构当发生哈希冲突时，新的键值对会被追加到对应桶中的链表末尾。链表的节点类型为 `Node`，包含以下字段：- `key`：键
- `value`：值
- `next`：指向下一个节点的引用```java
static class Node
4. 红黑树的引入
4.1 红黑树的优势当链表的长度超过一定阈值（默认为 8），为了提升查询效率，HashMap 会将链表转换为红黑树。红黑树是一种自平衡二叉搜索树，能够保证查询、插入和删除操作的时间复杂度为 O(log n)，显著优于链表的 O(n)。
4.2 转换逻辑当链表长度达到阈值时，HashMap 会触发链表到红黑树的转换。红黑树的节点类型为 `TreeNode`，它继承自 `Node`，并增加了额外的指针和颜色属性。```java
static final class TreeNode
5. 扩容机制
5.1 扩容的原因随着键值对的不断插入，数组可能会变得过于拥挤，导致哈希冲突增加，影响性能。因此，HashMap 提供了扩容机制，在数组利用率超过一定阈值（默认为 0.75）时，会触发扩容操作。
5.2 扩容过程扩容时，HashMap 会创建一个新的数组，其容量是原数组的两倍。然后，所有现有的键值对会被重新计算哈希值并分配到新的数组中。这一过程称为 **rehashing**。```java
void resize() {Node
6. 总结HashMap 的底层数据结构是由数组、链表和红黑树组成的复合结构。数组作为基础容器，链表用于解决哈希冲突，红黑树则在冲突严重时提供更高效的查询能力。通过哈希函数、扩容机制和动态调整策略，HashMap 实现了高效的数据存储和检索功能。理解 HashMap 的底层数据结构有助于我们更好地使用这一工具，并在实际开发中优化性能。
