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

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

二、操作 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。核心流程如下：

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

2.3 扩容 resize() 方法

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

1. 计算新容量：通常为旧容量的 2 倍。
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 遍历方式

支持三种遍历维度：

1. keySet(): 遍历键集合。
2. values(): 遍历值集合。
3. 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 非线程安全的特性，在并发场景下做好同步控制或使用替代方案。