Java HashMap 源码深度解析：原理、API 与扩容机制

Java HashMap 源码深度解析：原理、API 与扩容机制 | 极客日志

Java HashMap 源码深度解析

一、基本原理

HashMap 继承自 AbstractMap 类，实现了 Map 接口。它基于哈希表（Hash Table）实现，允许 null 键和 null 值。在 JDK 1.8 中，HashMap 采用'数组 + 链表 + 红黑树'的结构，旨在平衡查询效率与空间占用。

1.1 存储节点结构

HashMap 的存储节点主要涉及以下四类：

Entry: JDK 1.7 中的节点结构。
Node: JDK 1.8 中主要的节点结构，包含 key、value、hash、next。
TreeNode: 当链表长度超过阈值时转换成的红黑树节点。
LinkedHashMapEntry: LinkedHashMap 特有的节点。

当哈希冲突较少时，表现为数组；当冲突较多形成链表时，若链表长度大于 8 且数组长度大于等于 64，则转换为红黑树以提升查询效率至 O(logN)。

1.2 关键常量与变量

// 默认初始容量：16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
// 最大容量：2^30
static final int MAXIMUM_CAPACITY = 1 << 30; 
// 默认加载因子：0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树退化为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 最小树化容量阈值
static final int MIN_TREEIFY_CAPACITY = 64;

// 成员变量
transient int size; // 元素个数
int threshold;      // 扩容阈值
final float loadFactor; // 加载因子

了解这些常量的含义对于理解扩容和树化逻辑至关重要。

二、操作 API 源码解析

2.1 构造方法

2.1.1 空参构造

仅初始化加载因子为 0.75，其他字段延迟初始化，直到第一次 put 时才创建数组。

2.1.2 有参构造

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0) throw new IllegalArgumentException(...);
    if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException(...);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

tableSizeFor 方法确保容量始终为 2 的幂次方，例如输入 3 返回 4，输入 5 返回 8。这是为了利用位运算优化取余操作。

2.2 插入元素 put() 方法

put 方法调用 putVal。核心流程如下：

初始化：如果数组为空，先进行扩容初始化。
定位：计算 key 的 hash 值，通过 (n - 1) & hash 获取数组下标。这里利用了 n-1 是 2 的幂减 1 的特性，用位与代替取模。
插入：
- 若该位置为空，直接插入新节点。
- 若该位置已有节点，比较 hash 和 key。
- 若 key 相同，更新 value。
- 若不同，判断是否为红黑树节点。若是，插入红黑树；若不是，遍历链表。
- 若链表尾部插入后长度超过 8，触发树化检查。
扩容检查：插入成功后，若 size > threshold，触发扩容。

2.3 扩容 resize() 方法

扩容是 HashMap 性能的关键。JDK 1.8 优化了数据迁移过程，避免了重新计算 hash 取余的开销。

计算新容量：通常为旧容量的 2 倍。
数据迁移：
- 单节点：直接重新计算下标存入新数组。
- 链表：利用 e.hash & oldCap 将链表分为两组。低位组保留在原下标，高位组移动到下标 + 旧容量处。这是因为新容量是旧容量的 2 倍，只有 hash 值的第 N 位发生变化才会改变索引位置。
- 红黑树：调用 split 方法进行切割重组。若树节点数小于 6，会退化为链表以节省内存。

2.4 树化 treeifyBin() 方法

当链表长度达到 8 时，首先检查数组长度是否小于 64。如果是，优先扩容而不是树化，因为扩容可能解决哈希冲突问题。只有数组足够大时才进行树化。树化过程是将单向链表转换为双向链表，并构建红黑树结构，填充 left、right、parent 指针。

2.5 获取与删除

get(): 计算 hash，定位数组下标，依次检查头节点、红黑树或链表，找到即返回。
remove(): 类似 get 找到节点，根据节点类型（树或链表）执行移除逻辑，并更新 size。

2.6 遍历方式

支持三种遍历维度：

keySet(): 遍历键集合。
values(): 遍历值集合。
entrySet(): 遍历键值对集合。底层均使用 HashIterator 迭代器，支持快速失败（fail-fast）机制，即在遍历过程中若检测到 modCount 变化，抛出 ConcurrentModificationException。

三、与其他 Hash 表的对比

为了更全面地理解 HashMap，需要将其与其他常用 Map 实现进行对比。

3.1 HashMap vs ConcurrentHashMap

线程安全: HashMap 是非线程安全的，多线程环境下并发修改可能导致死循环（JDK 1.7）或数据覆盖（JDK 1.8）。ConcurrentHashMap 是线程安全的。
实现机制: JDK 1.7 使用分段锁（Segment），JDK 1.8 使用 CAS + synchronized 锁住链表头节点或红黑树根节点，粒度更细，并发性能更高。
适用场景: 单线程环境首选 HashMap；多线程高并发环境必须使用 ConcurrentHashMap。

3.2 HashMap vs TreeMap

排序: HashMap 是无序的（不保证顺序）。TreeMap 基于红黑树实现，按键的自然顺序或自定义 Comparator 排序。
性能: HashMap 平均 O(1)，最坏 O(n)。TreeMap 所有操作均为 O(logN)。
适用场景: 不需要排序用 HashMap；需要有序遍历或范围查询用 TreeMap。

3.3 HashMap vs LinkedHashMap

顺序: HashMap 不保证插入顺序。LinkedHashMap 维护了一个双向链表，记录元素的插入顺序或访问顺序。
性能: LinkedHashMap 略低于 HashMap，因为多了链表维护开销。
适用场景: 需要按插入顺序或最近最少使用（LRU）缓存场景使用 LinkedHashMap。

四、总结

HashMap 是 Java 集合框架的核心组件。理解其底层数组、链表、红黑树的转换机制，以及扩容策略和哈希碰撞处理，对于编写高性能代码至关重要。在实际开发中，应关注负载因子的设置，避免频繁的扩容操作，并根据业务需求选择合适的 Map 实现。同时，需注意 HashMap 非线程安全的特性，在并发场景下做好同步控制或使用替代方案。

Java HashMap 源码深度解析：原理、API 与扩容机制