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 关键常量与变量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
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 非线程安全的特性,在并发场景下做好同步控制或使用替代方案。