HashMap 源码解析（JDK 1.7）：数组 + 链表底层结构与 put/get/remove 流程

Words 1363Read Time≈ 4 min
2026-2-11
cover
type
Post
status
Published
date
Oct 15, 2020 14:44
slug
summary
深入剖析 JDK 1.7 HashMap 核心机制：Entry[] 桶数组 + 链表存储结构、hash 冲突链式解决方案、扩容阈值计算（capacity × loadFactor）及 put/get/remove 完整执行路径；对比 Hashtable 线程安全差异，解读 JDK 1.8 红黑树优化如何将最坏查找复杂度从 O(n) 降至 O(log n)。
tags
Data Structure
Java
category
CS Basic
icon
password
wordCount
1555

前言

这篇文章用 JDK 1.7 的 HashMap 作为主线来讲清楚它的核心实现。选择 1.7 的原因很简单：结构更“直给”，更容易看清数组、链表这些关键点。对于 JDK 1.8 之后的重大变化（红黑树、尾插等），文末会单独补上。
✅
读完你应该能回答三件事：
  • HashMap 的底层结构是什么？
  • put/get/remove 分别怎么走？
  • 为什么 1.8 要引入红黑树？

概述

HashMap 基于 Map 接口实现，元素以 key-value 的形式存储。
  • 允许 null key 和 null value。
  • key 不允许重复，因此最多只有一个 null key。
  • 不保证顺序。插入顺序和遍历顺序无关。
  • 线程不安全。
⚠️
HashMap 的“快”来自散列（hashing）。但当 hash 冲突变多时，性能会退化，这也是 1.8 做结构升级的核心原因。

继承关系与接口

继承关系

实现接口

基本属性（JDK 1.7）

🧠
理解 HashMap 的关键变量只有两个：
  • capacity（数组长度）
  • threshold（扩容阈值）
当 size 达到 threshold 时，HashMap 往往会触发 resize。

HashMap 的数据结构

一句话：数组 + 链表（1.7）。

为什么需要链表？

因为不同 key 的 hash 可能落到同一个桶（bucket）。当 bucket 冲突发生时，HashMap 用链表把这些 Entry 串起来。

链表类型速览

下面用最短的篇幅把“链表家族”过一遍，方便后面理解 Entry 的 next 指针。
  1. 单向链表：每个节点指向下一个，尾节点指向 null
      2. notion image
  1. 单向循环链表：尾节点指向头节点形成环
      2. notion image
  1. 双向链表：每个节点有 prev 和 next
      2. notion image
  1. 双向循环链表：首尾相接形成环（LinkedList 的设计思路常见于此）
      2. notion image

HashMap 的整体形态

HashMap 用 Entry[] table 作为“桶数组”。每个桶里挂着一个链表。
notion image
🧩
Entry（1.7）可以把它当成：链表节点 + key/value 容器。
  • 通过 key 的 hash 定位桶（数组下标）
  • 冲突时用 next 把节点串起来

源码解析（JDK 1.7）

构造方法

要点：前三个构造方法通常 不会立即分配 table，第四个会调用 inflateTable() 初始化并把 m 的元素转进来。

put：添加元素

put 过程拆解

  • 若 table 还没初始化，先 inflateTable()。
  • key == null 走 putForNullKey，固定放在 bucket 0。
  • 计算 hash，用 indexFor(hash, length) 得到桶下标。
  • 桶里已有链表就遍历。
    • 找到同 key：覆盖 value，并返回 oldValue。
    • 没找到：新增 Entry。
🧯
这里最容易忽略的点：覆盖并不会新增节点。
当 key 相同，HashMap 直接改 e.value。

addEntry：扩容与头插

  • 满足扩容条件时：resize(2 * length)。
  • 1.7 的插入策略是 头插（新节点放链表头）。

get：获取元素

get 的核心就是两步：
  1. 用 hash -> indexFor 定位桶。
  1. 在桶的链表上顺着 next 找到 key。

remove：删除元素

remove 的关键是维护链表指针：
  • 删除头节点：table[i] = next

HashMap vs Hashtable

维度
HashMap
Hashtable
是否允许 null
允许 null key 和 null value
不允许
线程安全
非线程安全
方法同步（线程安全）
接口与历史
Java 1.2 引入的 Map 体系实现
继承自 Dictionary（更早的设计）
性能倾向
更快（需要外部同步时自行处理）
同步带来额外开销
🧷
需要线程安全又不想牺牲太多性能时，更常见的选择是 ConcurrentHashMap，而不是 Hashtable。

JDK 1.8 的改变（补充）

1.8 之前：数组 + 链表。当同一个桶里节点过多时，链表查找会退化为 O(n)。
1.8 开始：数组 + 链表 + 红黑树。
  • 当链表长度超过阈值（默认 8）时，链表会树化为红黑树（TreeNode）。
  • 这样查找复杂度从 O(n) 改善到 O(log n)。

红黑树节点字段（示意）

notion image
🧊
可以把 1.8 的优化理解为：
冲突少时用链表，冲突多时上树。
HashMap 在“平均情况”和“最坏情况”之间做了更稳的折中。

总结

  • HashMap（1.7）底层是 Entry[] + 链表，用链表解决 hash 冲突。
  • put/get/remove 都遵循同一个套路：先定位桶，再在桶内结构上操作。
  • 1.8 引入红黑树，在冲突严重时把查找从 O(n) 优化到 O(log n)。
🎯
如果把 HashMap 当成一个“仓库”，hash 是导航系统：
  • 导航没撞车时，直达货架。
  • 撞车多了，货架边上开始“排队”（链表）。
  • 排队太长，就改成“按号取货”（红黑树）。

参考

  • JDK 7 HashMap 源码（java.util.HashMap）
  • JDK 8 HashMap 源码（java.util.HashMap）
Loading...