Java HashMap 原理详解：哈希寻址、冲突处理与扩容机制

HashMap 是 Java 中最常用的键值对容器之一。理解它的关键，不只是记住“数组加链表”，还要弄清哈希值如何定位桶、冲突如何处理，以及扩容为什么会影响性能。本文以常见的 OpenJDK 8+ 实现为主线，梳理其核心结构与操作过程。

1. HashMap 的核心结构

HashMap 底层使用一个数组作为桶（bucket）表。每个键值对封装成节点，节点至少保存哈希值、键、值和指向下一个节点的引用：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

数组中的每个位置称为桶。理想情况下，不同键分散到不同桶中；如果多个键落到同一个桶，就发生了哈希冲突。Java 8 中，桶内节点通常先以链表组织；链表较长且满足条件时，会转为红黑树，以改善极端冲突下的查找效率。

2. 哈希值怎样映射到数组下标

调用 put(key, value) 时，HashMap 会先计算键的哈希值，再将它映射到数组下标。Java 8 的实现会把高位信息混入低位，核心形式可概括为：

h = key.hashCode();
h ^ (h >>> 16)

之后通过数组长度减一与哈希值按位与来定位桶：

index = (table.length - 1) & hash;

这也是数组长度通常保持为 2 的幂的原因：用位运算即可快速取模，并能较均匀地利用低位。若容量不是 2 的幂，简单的掩码计算就不能等价于取模。

注意：哈希值只是帮助定位桶。判断键是否相同，最终仍需要检查哈希值，并通过 equals() 判断键对象是否相等。

3. put：插入与覆盖

插入键值对时，流程可以概括为：

若表尚未初始化，先创建桶数组。
计算键的哈希值和目标桶下标。
若桶为空，直接放入新节点。
若桶中已有节点，先比较哈希值和键：相同则更新旧值；不同则继续检查链表或红黑树。
若没有找到相同键，将新节点加入桶中；必要时树化。
元素数量达到扩容阈值时，扩容并重新安排节点。

因此，put 不只是“把东西放进数组”：它还要解决覆盖语义、冲突处理和容量维护。

4. 哈希冲突：链表与红黑树

不同键可能得到相同的桶下标，这就是冲突。HashMap 用桶内结构保存这些键值对：

链表：实现简单，常见情况下开销较低；查找需要逐个比较。
红黑树：当单个桶中的链表足够长、且表容量达到树化要求时，链表可能转为红黑树，查找从线性扫描改善为对数级比较。

OpenJDK 8 中常见阈值为：链表长度达到 8 时尝试树化；如果数组容量还小于 64，通常优先扩容而不是树化。删除节点后，树结构也可能在条件满足时退化为链表。具体阈值属于实现细节，不应当作所有 Map 实现的通用契约。

5. 扩容：为什么容量翻倍

HashMap 使用负载因子控制空间利用率与冲突概率的平衡。默认负载因子是 0.75；当元素数量超过 capacity × loadFactor，就会触发扩容。默认初始容量通常为 16，因此阈值通常是 12。

扩容时，数组容量一般翻倍。新容量是旧容量的两倍，节点在新表中的位置具有一个便于判断的规律：它要么留在原下标，要么移动到“原下标 + 旧容量”。实现通过检查哈希值中对应的位来完成拆分，而不是对每个键重新做昂贵的完整哈希运算。

扩容需要遍历节点并调整位置，因此不是常数时间操作；但扩容间隔逐渐拉大，put 在长期平均意义上仍具有较好的性能。若大致知道元素数量，可以合理设置初始容量，减少构建过程中的多次扩容。

6. get：查找键值对

调用 get(key) 时，HashMap 先计算哈希并定位桶，再在桶内查找：

检查桶首节点是否匹配。
若不匹配，在链表中逐个查找，或在红黑树中按树结构查找。
找到相等的键则返回对应值；否则返回 null。

在哈希分布良好时，查找平均表现接近 O(1)。但这不是无条件保证：严重冲突、低质量的 hashCode() 或高成本的 equals() 都可能拖慢操作。

7. hashCode 与 equals 的约定

自定义对象作为 HashMap 的键时，必须遵守 Java 的对象契约：

如果两个对象通过 equals() 判断相等，它们必须返回相同的 hashCode()。
equals() 和 hashCode() 涉及的字段，在对象作为键期间应保持稳定。

如果键插入后修改了参与哈希计算的字段，之后再用该对象查找，可能会定位到另一个桶，导致看起来“键丢了”。因此，不建议使用可变对象作为 HashMap 键；需要使用时，应确保键在存放期间不改变相关状态。

8. 线程安全与遍历顺序

普通 HashMap 不是线程安全容器。多个线程并发修改时，应用应采用合适的并发方案，例如 ConcurrentHashMap，或在明确的同步策略下访问。不要把旧版本实现中的并发扩容细节直接套用到现代 JDK；实际行为应以目标 JDK 文档和实现为准。

此外，HashMap 不保证迭代顺序。若业务依赖插入顺序，可考虑 LinkedHashMap；若需要按键排序，可考虑 TreeMap。

9. 常见误区

误区	更准确的理解
HashMap 就是数组	桶数组是主体，桶内还可能有链表或红黑树
哈希值相同就代表键相同	仍需通过键相等性判断，哈希冲突是允许的
查询永远是 O(1)	平均表现良好，但依赖哈希分布、桶结构和比较成本
扩容会给每个节点重新计算完整哈希	Java 8 的扩容利用容量翻倍的位规律拆分节点
HashMap 可以安全并发写入	普通 HashMap 不提供线程安全保证
HashMap 有固定遍历顺序	它不承诺迭代顺序

10. 小结

理解 HashMap，可以抓住四个关键词：桶数组负责定位、哈希扰动帮助分布、链表/红黑树处理冲突、负载因子触发扩容。在业务代码中，还要特别关注键对象的 equals()/hashCode() 契约、键的不可变性、容量预估以及并发访问方式。掌握这些机制，既能读懂常见源码，也能避免许多隐蔽的集合使用问题。