HashMap 是 Java 中最常用的键值对集合。它基于哈希表实现，通过 key 快速定位 value，平均情况下 put、get、remove 的时间复杂度接近 O(1)。

HashMap 是集合章节的重点，因为它串联了哈希算法、数组寻址、链表、红黑树、扩容、equals/hashCode、线程安全和很多经典面试题。

1. 核心特点

特点	说明
key-value 结构	根据 key 查找 value
key 唯一	相同 key 会覆盖旧 value
允许 null key	只能有一个 null key
允许 null value	可以有多个 null value
不保证顺序	遍历顺序不等于插入顺序
非线程安全	并发写入应使用 ConcurrentHashMap
平均查找快	哈希分布良好时接近 O(1)

示例：

Map<Long, String> userNameMap = new HashMap<>();
userNameMap.put(1L, "Tom");
userNameMap.put(2L, "Jerry");

System.out.println(userNameMap.get(1L)); // Tom

2. 底层结构

Java 8 之后，HashMap 的桶位结构可以是链表，也可以在冲突严重时转换成红黑树。

HashMap
┌──────────────────────────────────────┐
│ table: Node<K,V>[]                   │
│ size                                 │
│ threshold                            │
│ loadFactor                           │
└──────────────────────────────────────┘

table
index 0  -> null
index 1  -> Node(k1,v1) -> Node(k2,v2)
index 2  -> null
index 3  -> TreeNode 红黑树
...

节点保存：

Node
├─ hash
├─ key
├─ value
└─ next

核心思想：

key
 │ hashCode
 ▼
hash 扰动
 │
 ▼
数组下标
 │
 ├─ 桶为空：直接放入
 └─ 桶非空：比较 key，追加链表或插入红黑树

3. put 流程

map.put(key, value);

简化流程：

计算 key 的 hash
  │
  ▼
table 是否初始化
  │
  ├─ 否：初始化数组
  └─ 是：继续
  │
  ▼
通过 (n - 1) & hash 定位桶
  │
  ├─ 桶为空：新建节点
  │
  └─ 桶非空：
       ├─ key 相等：覆盖 value
       ├─ 桶是链表：遍历链表
       └─ 桶是红黑树：树插入
  │
  ▼
size + 1
  │
  ▼
超过 threshold 则扩容

key 相等判断：

p.hash == hash && (p.key == key || key.equals(p.key))

先比较 hash，再比较引用或 equals。

4. get 流程

map.get(key);

简化流程：

计算 hash
  │
  ▼
定位桶 index
  │
  ├─ 桶为空：返回 null
  ├─ 第一个节点 key 相等：返回 value
  ├─ 红黑树：按树查找
  └─ 链表：逐个比较 key

平均 O(1) 的前提是 hash 分布良好，冲突较少。

5. 哈希扰动与下标计算

HashMap 的容量通常保持为 2 的幂，下标计算可以用位运算：

index = (capacity - 1) & hash

例如容量 16：

capacity - 1 = 15 = 0000 1111
hash         =      xxxx yyyy
index        =      0000 yyyy

如果只用低位，某些 key 的高位差异无法参与下标计算。因此实现会做 hash 扰动，让高位信息也影响低位。

原始 hashCode
   │
   ▼
高 16 位与低 16 位混合
   │
   ▼
用于桶定位的 hash

这不是为了加密，而是为了让元素分布更均匀。

6. 容量、负载因子和阈值

核心参数：

参数	含义
capacity	table 数组长度
loadFactor	负载因子，默认 0.75
threshold	扩容阈值，通常是 capacity * loadFactor
size	当前键值对数量

默认负载因子 0.75 是时间和空间的折中：

• 太小：空间浪费，扩容更频繁。
• 太大：冲突增加，查询变慢。

当：

size > threshold

触发扩容。

7. 为什么容量是 2 的幂

容量为 2 的幂时，下标计算可以用位运算替代取模：

hash % capacity

可以优化成：

hash & (capacity - 1)

同时扩容时，节点位置迁移也更高效。

扩容为两倍后，旧节点的新位置只有两种：

原位置 index
或
index + oldCapacity

判断依据是：

hash & oldCapacity

示意：

oldCap = 16
newCap = 32

旧桶 i 中节点：
  ├─ hash & 16 == 0 -> 仍在 i
  └─ hash & 16 != 0 -> 移到 i + 16

8. 扩容机制

扩容不是简单“数组变大”，而是重新分布桶位。

旧 table
index 1 -> A -> B -> C

扩容后
new index 1  -> A -> C
new index 17 -> B

扩容成本：

• 创建新数组。
• 遍历旧数组。
• 迁移链表或树节点。
• 更新阈值。

如果能预估元素数量，应指定初始容量，减少扩容：

Map<Long, User> map = new HashMap<>(expectedCapacity);

但构造参数是容量，不是元素个数。若预计放入 n 个元素，可以估算：

initialCapacity ≈ n / loadFactor + 1

例如预计 1000 个元素：

Map<Long, User> map = new HashMap<>(1340);

JDK 会把容量调整到合适的 2 的幂。

9. 哈希冲突与树化

多个 key 定位到同一个桶，就是哈希冲突。

table[5]
  │
  ▼
Node A -> Node B -> Node C -> ...

冲突过多时，链表查询会从 O(1) 退化为 O(n)。

Java 8 之后，当链表长度达到一定阈值，且数组容量足够大时，会树化为红黑树。

链表
A -> B -> C -> D -> E -> F -> G -> H

树化后
       D
     /   \
    B     F
   / \   / \
  A  C  E  H
          /
         G

常见阈值：

参数	常见值	含义
TREEIFY_THRESHOLD	8	链表达到该长度可能树化
UNTREEIFY_THRESHOLD	6	树节点减少到该长度可能退化
MIN_TREEIFY_CAPACITY	64	table 至少达到该容量才树化

如果 table 太小，优先扩容而不是树化，因为扩容可能直接减少冲突。

10. equals 与 hashCode

HashMap 的 key 必须满足 equals/hashCode 契约。

equals 相等 -> hashCode 必须相等
hashCode 相等 -> equals 不一定相等

错误示例：

public class UserKey {
    private Long id;

    @Override
    public boolean equals(Object obj) {
        return obj instanceof UserKey other && Objects.equals(id, other.id);
    }

    // 忘记重写 hashCode
}

后果：

Map<UserKey, String> map = new HashMap<>();
map.put(new UserKey(1L), "Tom");

System.out.println(map.get(new UserKey(1L))); // 可能是 null

因为两个逻辑相等的 key 可能定位到不同桶。

正确写法：

@Override
public int hashCode() {
    return Objects.hash(id);
}

11. 可变对象作为 key 的风险

不要使用会变化的字段参与 key 的 hashCode 和 equals。

UserKey key = new UserKey(1L);
map.put(key, "Tom");

key.setId(2L);
System.out.println(map.get(key)); // 可能取不到

过程：

put 时：id=1 -> 桶 A
修改后：id=2 -> 查找桶 B
原节点还在桶 A，get 失败

适合作为 key 的对象应尽量不可变，例如 String、Long、枚举、自定义不可变值对象。

12. null key 与 null value

HashMap 允许一个 null key：

map.put(null, "default");

也允许多个 null value：

map.put("A", null);
map.put("B", null);

因此：

map.get("A") == null

可能表示：

• key 不存在。
• key 存在，但 value 就是 null。

需要区分时：

if (map.containsKey("A")) {
    // key 存在
}

13. 常用增强方法

13.1 putIfAbsent

map.putIfAbsent(key, value);

key 不存在或当前 value 为 null 时放入。

13.2 computeIfAbsent

List<Order> orders = orderMap.computeIfAbsent(userId, k -> new ArrayList<>());
orders.add(order);

常用于分组收集。

注意：不要在计算函数里对同一个 Map 做复杂结构修改，容易引入可读性和递归问题。

13.3 merge

统计次数：

Map<String, Integer> countMap = new HashMap<>();
countMap.merge("Java", 1, Integer::sum);

等价于：

如果 key 不存在 -> 放入 1
如果 key 存在   -> oldValue + 1

14. 遍历方式

推荐遍历 entry：

for (Map.Entry<Long, User> entry : userMap.entrySet()) {
    Long id = entry.getKey();
    User user = entry.getValue();
}

如果只需要 key：

for (Long id : userMap.keySet()) {
}

如果只需要 value：

for (User user : userMap.values()) {
}

不推荐：

for (Long id : userMap.keySet()) {
    User user = userMap.get(id);
}

这会二次查找。

15. 线程安全

HashMap 非线程安全，多线程并发写入会出现数据竞争。

错误用法：

Map<String, String> map = new HashMap<>();
// 多个线程同时 put

并发场景选择：

场景	推荐
并发读写 Map	ConcurrentHashMap
初始化后只读	构建完成后安全发布，或使用不可变 Map
简单同步	Collections.synchronizedMap
顺序 + 并发	通常需要额外设计，不要直接套普通 Map

HashMap 在并发下的问题不是“偶尔慢”，而是语义不安全。

16. LinkedHashMap 与 TreeMap 对比

实现	顺序	查找复杂度	适合场景
HashMap	不保证	平均 O(1)	普通映射
LinkedHashMap	插入或访问顺序	平均 O(1)	有序遍历、LRU
TreeMap	key 排序	O(log n)	排序、范围查询

如果只是希望遍历顺序稳定，优先 LinkedHashMap；如果需要按 key 比较大小、查区间，选择 TreeMap。

Tips 快问快答

Q：HashMap 为什么快？ A：通过 key 的 hash 快速定位数组桶，冲突少时无需遍历太多元素。

Q：HashMap 一定是 O(1) 吗？ A：不是。平均接近 O(1)，冲突严重时会退化，树化后相关桶操作约 O(log n)。

Q：为什么容量要是 2 的幂？ A：可以用 (n - 1) & hash 快速定位桶，并简化扩容迁移。

Q：负载因子为什么默认 0.75？ A：这是空间利用和冲突概率之间的折中。

Q：链表长度到 8 一定树化吗？ A：不一定，还要看 table 容量是否至少达到树化最小容量，容量太小时优先扩容。

Q：HashMap 允许 null key 吗？ A：允许一个 null key，也允许多个 null value。

Q：get(key) == null 能说明 key 不存在吗？ A：不能，value 可能就是 null。需要用 containsKey 区分。

Q：自定义对象做 key 要注意什么？ A：正确重写 equals 和 hashCode，并避免参与计算的字段变化。

Q：HashMap 线程安全吗？ A：不安全，并发读写应使用 ConcurrentHashMap 或外部同步。

Q：为什么遍历 Map 推荐 entrySet？ A：可以一次拿到 key 和 value，避免先遍历 key 再二次查找 value。