---
title: "01-HashMap"
created: 2025-12-02
tags:
  - Java
---
# HashMap

> [!note] 定位说明
> Map 系列第 1 篇。**核心原理速览**：put/get 存储流程 + 关键参数 + 与其他 Map 对比。想看源码细节（hash 计算、扩容、树化、线程安全）直接进 02-HashMap源码解析。

#### **核心特性**

1. **数据结构**

   - **JDK 1.8 之前**：数组 + 链表（拉链法解决哈希冲突）。
   - **JDK 1.8 及之后**：**数组 + 链表 + 红黑树**（当链表长度 ≥ 8且数组容量 ≥ 64 时，链表转为红黑树；长度 < 6 时退化为链表）。
   - **目的**：提升哈希冲突时的查询性能（链表平均查询 O (n) → 红黑树 O (log n)）。
2. **存储特点**

   - **无序性**：不保证元素插入顺序（依赖哈希值分布）。
   - **键唯一性**：键通过 `equals()` 和 `hashCode()` 保证唯一性（值可重复），**允许一个 null 键和多个 null 值**。
   - **线程不安全**：多线程下可能出现死锁、数据丢失等问题（需用 `ConcurrentHashMap` 或手动同步）。

#### **关键参数**

| **参数** | **含义** | **默认值** |
| --- | --- | --- |
| **capacity** | 哈希表初始容量（数组长度，必须为 2 的幂，如 16、32） | 16 |
| **loadFactor** | 负载因子（控制哈希表扩容时机，值越小，冲突概率越低，空间利用率越低） | 0.75 |
| **threshold** | 扩容阈值（= capacity × loadFactor，如默认 16×0.75=12） | 无默认值 |

#### **核心原理**

##### **1. 存储流程（put (key, value)）**

1. **计算哈希值**：
   - 对 key 调用 `hashCode()` 得到哈希值，再通过 **扰动函数**（`hash(key)` 方法）优化哈希分布，减少冲突：

```java
     static final int hash(Object key) {
         int h;
         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 高低位异或，降低哈希碰撞
     }
```
2. **确定数组下标**：
   - `index = hash & (capacity - 1)`（等价于取模运算 `hash % capacity`，但效率更高）。
3. **处理哈希冲突**：
   - 若该下标处无元素，直接插入。
   - 若有元素，比较 key：
     - 若 key 相等（`equals` 为 true），覆盖 value。
     - 若 key 不等，判断当前节点类型：
       - **链表节点**：遍历链表，若找到相等 key 则覆盖；否则新增节点（尾插法，JDK 1.8 后改为尾插）。
       - **红黑树节点**：按红黑树规则插入新节点，若插入后树高 < 6，退化为链表。
4. **扩容机制**：
   - 当元素数量（size）超过 `threshold` 时，触发扩容（容量翻倍，如 16 → 32）。
   - **扩容重哈希**：重新计算所有元素的哈希值和下标（性能消耗大，应避免频繁扩容）。

##### **2. 查询流程（get (key)）**

1. 计算 key 的哈希值，确定数组下标。
2. 若该下标处无元素，返回 null。
3. 若有元素，比较 key：
   - 若 key 相等，直接返回 value。
   - 若为链表，遍历链表查找；若为红黑树，按红黑树规则查找。

#### **源码分析**

[[02-HashMap源码解析|HashMap源码解析]]

#### **性能分析**

| **操作** | **平均时间复杂度** | **最坏时间复杂度** | **影响因素** |
| --- | --- | --- | --- |
| **插入** | O(1) | O (n) 或 O (log n) | 哈希冲突次数、链表 / 树长度 |
| **查询** | O(1) | O (n) 或 O (log n) | 同上 |
| **删除** | O(1) | O (n) 或 O (log n) | 同上 |

- **优势**：平均性能极高，适用于高频的插入、查询操作。
- **劣势**：扩容时性能开销大；多线程下不安全。

#### **与其他 Map 的对比**

| **实现类** | **数据结构** | **顺序性** | **线程安全** | **适用场景** |
| --- | --- | --- | --- | --- |
| **HashMap** | 数组 + 链表 + 红黑树 | 无序 | 不安全 | 单线程下的高频增删查（默认选择） |
| **LinkedHashMap** | 数组 + 链表（维护双向链表） | 插入顺序 / 访问顺序 | 不安全 | 需要保留插入顺序或实现 LRU 缓存 |
| **TreeMap** | 红黑树 | 自然顺序 / 定制顺序 | 不安全 | 需要排序或范围查询（如按 key 排序） |
| **Hashtable** | 数组 + 链表 | 无序 | 安全（synchronized） | 遗留系统的线程安全场景（性能低，不推荐） |

#### **常见问题与最佳实践**

1. **为什么容量必须是 2 的幂？**

   - 为了保证 `hash & (capacity - 1)` 等价于 `hash % capacity`，且运算更快（位运算）。
   - 若用户传入非 2 的幂，HashMap 会自动调整为大于等于该值的最小 2 的幂（如传入 10 → 16）。
2. **如何优化 HashMap 性能？**

   - **预设置合适的初始容量**：避免频繁扩容。例如，若已知存储 1000 个元素，初始容量可设为 `(1000 / 0.75) ≈ 1334`，取最近的2 的幂（16384）。
   - **选择合适的负载因子**：若内存充足且需减少冲突，可设为 0.5（空间换时间）；若内存紧张，可设为 1.0（但冲突概率增加）。
3. **多线程下如何使用 HashMap？**

   - 不推荐直接使用，可改用 `ConcurrentHashMap`（JDK 1.8 后基于 CAS + synchronized，性能更高）或手动同步（如 `Collections.synchronizedMap(new HashMap<>())`）。
4. **key 的最佳实践**

   - 自定义类作为 key 时，必须重写 `equals()` 和 `hashCode()`，且保证相同 key的 `hashCode()` 一致。
   - 推荐使用不可变类（如 String、Integer）作为 key，避免因 key 可变导致哈希值变化。

#### **总结**

- **核心优势**：高效的平均性能，适用于大多数 “键值对快速存取” 场景。
- **适用场景**：缓存、字典、统计计数等单线程场景。
- **注意事项**：多线程需同步，避免 key 可变，合理设置初始容量以减少扩容开销。
---
⬅️ [[00-Map总览|00-Map总览]] 🏠 [[00-Java|00-Java]] ➡️ [[02-HashMap源码解析|HashMap源码解析]]