---
title: "Java `HashMap` 的结构与复杂度"
author: "Perrin Yong"
author_profile: https://www.pystone.net/profile/
published_by: "Perrin Yong"
canonical: https://www.pystone.net/notes/java-hashmap-structure-complexity/
type: note
content_role: unspecified
visibility: public
id_stability: rename-stable
source_path: "10-计算机、信息技术与工程/02-编程语言与运行时/Java HashMap的结构与复杂度.md"
content_hash: 2fc11196e0be8c2d890356f9d0207cdf6b88f2e4e9fb278e65cf65870cbf7916
knowledge_version: 224c990773de.5fa8af6e39fa
site_commit: 224c990773de166d23a886306577dd90379529ce
notes_commit: 5fa8af6e39fa3891d1b9b4832bfa6c4e0ecaaf0a
---
# Java `HashMap` 的结构与复杂度

## 基本性质

`java.util.HashMap` 基于哈希表实现 `Map` 接口。它允许一个 `null` 键和多个 `null` 值，不保证遍历顺序，也不保证顺序长期不变。若多个线程并发修改，必须在外部同步或改用合适的并发容器。

在哈希分布合理时，`get` 与 `put` 的预期成本为常数时间。最坏情况取决于碰撞、容量以及具体 JDK 实现，不能无条件写成始终 `O(1)`。

![assets/Java-HashMap-bucket-structure.png](/media/a177b2e0dd9d867986b3.png)

> **warning · 实现细节**
> Java 8 及后续 OpenJDK 实现会在满足容量和碰撞阈值等条件时，把过长桶结构树化以改善严重碰撞下的性能；阈值和节点布局属于实现细节，不是使用 `Map` 接口时应依赖的行为契约。

## 容量与负载因子

- **capacity**：桶数组容量。
- **load factor**：触发扩容的装载比例，默认值通常在时间与空间之间折中。
- **rehash/resize**：扩容会重新组织桶，成本较高。

能预估元素数量时，可设置足够的初始容量以减少扩容，但过大的容量会浪费空间，并使遍历成本增加，因为遍历与容量和元素数都有关。

## 正确使用自定义键

作为键的对象必须保持 `equals` 与 `hashCode` 契约一致：相等对象必须有相同哈希值。键参与比较的字段在放入映射后不应改变，否则对象可能仍在表中却无法按新状态查到。

## 参考资料

- [Oracle Java API：HashMap](https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/HashMap.html)