hashmap底层原理在Java中，`HashMap` 一个非常常用的数据结构，用于存储键值对（Key-Value）。它的实现基于哈希表，能够快速地进行插入、删除和查找操作。领会 `HashMap` 的底层原理对于优化程序性能、避免哈希冲突以及合理使用其特性具有重要意义。
一、核心概念
| 概念 | 说明 |
| 哈希表 | 通过哈希函数将键映射到数组中的特定位置，以实现快速访问。 |
| 哈希冲突 | 不同的键经过哈希计算后得到相同的索引，需要解决这种冲突。 |
| 链表/红黑树 | 在发生哈希冲突时，采用链表或红黑树来存储多个键值对。 |
| 扩容机制 | 当元素数量超过阈值时，自动扩容并重新哈希，进步性能。 |
二、底层结构
`HashMap` 的底层主要由下面内容结构组成：
| 结构 | 影响 |
| 数组 | 存储所有键值对的“桶”（bucket），每个桶对应一个索引位置。 |
| 链表 | 当多个键哈希到同一个桶时，用链表存储多个键值对。 |
| 红黑树 | 在链表长度过长时，自动转换为红黑树，提升查询效率。 |
三、关键流程
| 步骤 | 说明 |
| 插入 | 计算键的哈希值，确定索引；若冲突，则添加到链表或红黑树中。 |
| 查询 | 根据键的哈希值找到对应的索引，遍历链表或红黑树查找键值对。 |
| 删除 | 定位索引后，遍历链表或红黑树，找到目标键值对并删除。 |
| 扩容 | 当元素数量超过阈值（容量 × 负载因子）时，重新分配更大的数组，并重新哈希。 |
四、哈希冲突处理
`HashMap` 使用 拉链法 来处理哈希冲突，即每个桶中保存一个链表或红黑树，用于存放哈希值相同的键值对。
| 处理方式 | 适用场景 | 性能表现 |
| 链表 | 冲突较少时，简单高效 | 查找时刻复杂度 O(n) |
| 红黑树 | 冲突较多时，提升查找效率 | 查找时刻复杂度 O(log n) |
五、负载因子与扩容
| 参数 | 默认值 | 影响 |
| 初始容量 | 16 | 初始数组大致 |
| 负载因子 | 0.75 | 元素数量达到容量的 75% 时触发扩容 |
| 扩容机制 | 2倍 | 扩容后容量变为原来的两倍 |
六、拓展资料
| 项目 | 说明 |
| 数据结构 | 哈希表 + 链表/红黑树 |
| 时刻复杂度 | 插入/查询/删除：平均 O(1)，最坏 O(n) |
| 冲突处理 | 拉链法，链表转红黑树 |
| 扩容策略 | 自动扩容，容量翻倍 |
| 应用场景 | 快速查找、插入、删除键值对，适合无序数据 |
通过了解 `HashMap` 的底层原理，我们可以更好地领会其性能特点，合理设置初始容量和负载因子，避免频繁扩容，提升程序运行效率。
