HashMap 深度解析

一、基本使用

1.1 初始化与添加元素

Map<String, String> map = new HashMap<>();
map.put("111", "abc");
map.put("112", "abcd");
map.put("1123", "abcde");

// HashMap 允许一个 null 键，hash 值为 0，放在数组第 0 位
map.put(null, 123);

// 默认不允许重复键，重复 put 会覆盖旧值

1.2 四种遍历方式

// 方式一：遍历 keySet()
for (String key : map.keySet()) {
    System.out.println(key + " " + map.get(key));
}

// 方式二：只遍历 value
for (String str : map.values()) {
    System.out.println(str);
}

// 方式三：遍历 Entry（键值对）
for (Map.Entry<String, String> entry : map.entrySet()) {
    String key = entry.getKey();
    String value = entry.getValue();
}

// 方式四：Stream + Lambda
map.entrySet().forEach(entry -> {
    System.out.println(entry.getKey() + " " + entry.getValue());
});

---

二、常用场景

2.1 统计字符出现次数（投票计数）

String str = "aaabbbcccdddeee";
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
    char c = str.charAt(i);
    if (map.containsKey(c)) {
        Integer value = map.get(c);
        map.put(c, value + 1);
    } else {
        map.put(c, 1);
    }
}
System.out.println(map);

2.2 Controller 层接收与返回数据

当后端返回数据不固定时，可用 Map 替代 VO 类封装数据返回前端；前端数据不固定时也可用 Map 接收。

Map<String, Object> map = new HashMap<>();
map.put("username", selectedUser.getUsername());
map.put("id", selectedUser.getId());
String token = JWTUtil.createJWT("njitzx", 1000 * 3600 * 10, map);
map.put("token", token);

@PostMapping("/login")
public Result login(@RequestBody User user) {
    Map<String, Object> map = userService.login(user);
    return Result.success(map);
}

2.3 构建 HTTP 请求参数 / 缓存静态数据

发送 HTTP 请求时，用 Map 存储请求参数；也可用于缓存键值对静态数据。

2.4 Stream 流将 List 转为 Map

List<User> users = Arrays.asList(
    new User(1, "Alice"),
    new User(2, "Bob"),
    new User(3, "Charlie")
);

// id -> User 映射
Map<Integer, User> userMap = users.stream()
    .collect(Collectors.toMap(
        User::getId,     // keyMapper
        user -> user     // valueMapper
    ));

userMap.forEach((k, v) -> System.out.println(k + " -> " + v));

---

三、数据结构

3.1 整体架构

版本	底层结构
JDK 1.7 及之前	数组 + 链表
JDK 1.8 及之后	数组 + 链表 + 红黑树

• 数据量较少：数组 + 链表
• 数据量较大（链表长度 ≥ 8 且数组长度 ≥ 64）：链表转为红黑树

3.2 核心成员变量

transient Node<K,V>[] table;                          // 哈希表数组
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   // 默认初始容量 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;       // 默认负载因子
static final int TREEIFY_THRESHOLD = 8;               // 链表转红黑树阈值
static final int MIN_TREEIFY_CAPACITY = 64;           // 最小树化容量

3.3 Node 节点结构（链表）

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;      // key 的哈希值
    final K key;         // 键
    V value;             // 值
    Node<K,V> next;      // 指向下一个节点
}

3.4 TreeNode 节点结构（红黑树）

当链表长度 ≥ 8 且数组长度 ≥ 64 时，链表转为红黑树节点 TreeNode，提升查询效率从 O(n) 到 O(log n)。

---

四、源码深度分析

4.1 构造方法 —— 懒加载

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // 仅设置负载因子 0.75，不创建数组
}

HashMap 采用懒加载机制：构造时不分配数组，第一次 put 时才通过 resize() 初始化。

4.2 hash() 哈希函数

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

设计原理：

• key 为 null → hash = 0，放在数组第 0 位
• key 不为 null → 取 hashCode()，将高 16 位与低 16 位异或混合
• 目的是让高位参与低位运算，生成更均匀的哈希分布，减少哈希碰撞

4.3 put() → putVal() 核心流程

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
    // onlyIfAbsent=false 表示重复数据会覆盖
}

putVal 方法完整流程：

1. 数组为空 → resize() 初始化数组
2. (n-1) & hash 计算下标索引
3. tab[i] == null → 直接插入新 Node
4. tab[i] != null：
   ├── 首节点 key 相同 → 覆盖
   ├── 首节点是 TreeNode → 走红黑树插入 putTreeVal()
   └── 首节点是普通 Node → 遍历链表
       ├── 找到相同 key → 覆盖
       └── 到链表末尾 → 尾插新节点
           └── 链表长度 ≥ 8 → treeifyBin() 尝试转红黑树
5. size > threshold → resize() 扩容

关键源码片段：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 步骤1：数组为空则初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤2：(n-1) & hash 计算下标，位置为空直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 步骤3：首节点 key 相同
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 步骤4：红黑树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 步骤5：链表遍历
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);  // 尾插法
                    if (binCount >= TREEIFY_THRESHOLD - 1)     // ≥8 转红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 步骤6：覆盖旧值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

4.4 定位索引：(n-1) & hash

• HashMap 容量 n 始终为 2 的幂（16, 32, 64...）
• (n-1) 的二进制全为 1（如 15 = 1111），与 hash 做与运算等价于 hash % n
• 位运算比取模快得多，这是容量必须为 2 的幂的根本原因

4.5 resize() 扩容机制

触发条件：size > threshold（threshold = capacity × loadFactor，默认 16 × 0.75 = 12）

扩容过程：

1. 创建两倍容量的新数组 newTab
2. 遍历旧数组每个桶，重新计算元素在新数组中的位置
3. 由于容量翻倍（2 的幂），元素只可能留在原位置或原位置 + 旧容量
4. table = newTab，更新 threshold

为什么是两倍扩容？

• 容量保持 2 的幂 → 继续用 (n-1) & hash 高效索引
• rehash 时元素分布计算简单：只需判断 hash 新增位是 0 还是 1
• 降低 rehash 计算开销

---

五、面试高频问题

Q1：介绍一下 HashMap

HashMap 是基于哈希表实现的 Map 接口，可实现 O(1) 时间复杂度的查找、插入和删除。JDK 1.7 使用数组 + 链表；JDK 1.8 改为数组 + 链表 + 红黑树，当链表长度 ≥ 8 且数组长度 ≥ 64 时转为红黑树。

Q2：HashMap 工作原理

1. 对 key 计算 hashCode()，经 hash() 扰动后得到 hash 值
2. 通过 (n-1) & hash 计算桶下标
3. 若桶为空直接插入；若有元素则通过 equals() 判断是否相同
4. 相同则覆盖，不同则追加到链表末尾或红黑树中
5. 元素数量超过 capacity × loadFactor 时触发两倍扩容

Q3：为什么容量是 2 的幂次方？

• 用 (n-1) & hash位运算替代取模hash % n，大幅提高计算速度
• 扩容时元素只需判断 hash 新增位，要么留在原位要么移动到原位置 + 旧容量，rehash 成本低

Q4：hash() 函数为什么这样设计？

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

将 hashCode 的高 16 位与低 16 位异或混合，让高位也参与索引计算。因为容量较小时（如默认 16），(n-1) & hash 只用到了低几位，高位信息被浪费，混合后分布更均匀，减少碰撞。

Q5：负载因子为什么是 0.75？

在时间与空间之间取平衡：

• 过大（如 1.0）→ 减少扩容次数节省空间，但哈希冲突加剧，查找效率下降
• 过小（如 0.5）→ 冲突少查询快，但频繁扩容浪费内存
• 0.75 是统计学上泊松分布的一个较优折中值

Q6：HashMap 扩容过程

1. 当 size > capacity × loadFactor 触发
2. 创建原容量两倍的新数组
3. 遍历旧数组，每个桶的元素重新计算下标迁移
4. JDK 1.8 优化：元素只可能去两个位置 —— 原位置 或 原位置 + 旧容量
5. table 指向新数组，更新 threshold

Q7：HashMap 是线程安全的吗？

不线程安全。多线程并发 put/get 可能出现：

• 数据丢失：两个线程同时 put 不同的 key 到同一桶位置
• get 返回 null：扩容期间一个线程迁移数据，另一个线程 get 读到中间状态（JDK 1.7 还可能形成死循环）

// 扩容时 table 引用切换非原子
// 线程1 正在迁移 → 线程2 get 可能读到未迁移完的不完整数组

替代方案：使用 ConcurrentHashMap，支持并发读写，分段锁机制保证线程安全。

Q8：HashMap 允许 null 键/值吗？

• 允许一个 null 键：hash(null) 返回 0，存在数组第 0 位；后续再 put null 键会覆盖
• 允许多个 null 值：不同键都可映射到 null 值

Q9：链表转红黑树的条件

两个条件同时满足：

1. 链表长度 ≥ TREEIFY_THRESHOLD（8）
2. 数组长度 ≥ MIN_TREEIFY_CAPACITY（64）

若数组长度不足 64，即使链表长度 ≥ 8 也只触发 resize 扩容而非树化。

Q10：为什么链表长度为 8 才转红黑树？

基于泊松分布概率计算：当负载因子为 0.75 时，桶中元素个数达到 8 的概率不到千万分之一。8 作为阈值可在极少牺牲性能的前提下避免不必要的树化开销。

Q11：HashSet 底层实现

HashSet 底层就是一个 HashMap：

public HashSet() {
    map = new HashMap<>();
}
public boolean add(E e) {
    return map.put(e, PRESENT) == null;  // PRESENT 是一个 dummy Object
}

利用 HashMap 的 key 不可重复特性实现集合去重，value 统一为一个常量占位对象。

Q12：JDK 1.7 vs JDK 1.8 主要变化

对比项	JDK 1.7	JDK 1.8
数据结构	数组 + 链表	数组 + 链表 + 红黑树
插入方式	头插法	尾插法
扩容顺序	先扩容再插入	先插入再扩容
hash 计算	4 次扰动	1 次扰动（高 16 异或低 16）
死循环风险	扩容时头插法可能形成环形链表	尾插法避免

---

参考

• HashMap 源码分析 (CSDN)