java基础

HashMap 完全指南：从源码到实践

Posted by zengchengjie on Tuesday, December 3, 2024

HashMap 完全指南：从源码到实践

引言

在 Java 面试中，HashMap 几乎是必问的知识点；在日常开发中，HashMap 更是使用频率最高的集合类之一。它就像程序员的瑞士军刀——简单、高效、无处不在。

但是，你真的了解 HashMap 吗？

  • 为什么 HashMap 的容量总是 2 的幂次方？
  • 多线程环境下使用 HashMap 会出什么问题？
  • JDK 7 和 JDK 8 的 HashMap 有什么重大区别？
  • 为什么要引入红黑树？

本文将带你从零开始，全面剖析 HashMap 的实现原理、核心源码、使用技巧和常见误区。

一、HashMap 基础概念

1.1 什么是 HashMap？

HashMap 是基于哈希表实现的 Map 接口的实现类。它存储的是 键值对（Key-Value），允许使用 null 作为 key 或 value。

┌─────────────────────────────────────────────────────────┐
│                      HashMap                              │
│  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐      │
│  │  0  │  1  │  2  │  3  │  4  │  5  │  6  │  7  │ ...  │      │
│  └──┬──┴─────┴──┬──┴─────┴──┬──┴─────┴──┬──┴─────┘      │
│     │           │           │           │                 │
│     ▼           ▼           ▼           ▼                 │
│  Node(key1)  Node(key2)  Node(key3)  Node(key4)           │
│   (链表)       (链表)       (树)        (链表)             │
└─────────────────────────────────────────────────────────┘

1.2 HashMap 的特点

特性 说明
存储结构 数组 + 链表 + 红黑树（JDK 8+）
键值对 允许 key 和 value 为 null
线程安全 非线程安全（需要同步时使用 ConcurrentHashMap）
无序性 不保证元素的顺序
扩容机制 负载因子 0.75，初始容量 16

1.3 基本操作

import java.util.HashMap;
import java.util.Map;

public class HashMapDemo {
    public static void main(String[] args) {
        // 创建 HashMap
        Map<String, Integer> map = new HashMap<>();
        
        // 添加元素
        map.put("苹果", 10);
        map.put("香蕉", 20);
        map.put("橙子", 15);
        
        // 获取元素
        Integer count = map.get("苹果");
        System.out.println("苹果数量: " + count);
        
        // 遍历方式1：keySet
        for (String key : map.keySet()) {
            System.out.println(key + " = " + map.get(key));
        }
        
        // 遍历方式2：entrySet（推荐，性能更好）
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
        
        // 遍历方式3：forEach（JDK 8+）
        map.forEach((k, v) -> System.out.println(k + " = " + v));
        
        // 检查是否包含
        System.out.println("是否包含苹果: " + map.containsKey("苹果"));
        System.out.println("是否包含数量10: " + map.containsValue(10));
        
        // 删除元素
        map.remove("苹果");
        
        // 获取大小
        System.out.println("大小: " + map.size());
    }
}

二、底层数据结构

2.1 JDK 7 及之前：数组 + 链表

┌───────────────────────────────────────────────┐
│                   Node[] table                 │
├───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┤
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │...│   │
└─┬─┴───┴─┬─┴───┴───┴─┬─┴───┴───┴─┬─┴───┴───┘
  │       │             │           │
  ▼       ▼             ▼           ▼
┌─────┐ ┌─────┐       ┌─────┐     ┌─────┐
│Node │ │Node │       │Node │     │Node │
├─────┤ ├─────┤       ├─────┤     ├─────┤
│next─┼►│null │       │next─┼►... │null │
└─────┘ └─────┘       └─────┘     └─────┘

哈希冲突：当两个不同的 key 计算出相同的数组索引时，使用链表将冲突的元素串联起来。

2.2 JDK 8 及之后：数组 + 链表 + 红黑树

JDK 8 引入了红黑树优化：

  • 链表：当链表长度 ≤ 8 时，使用链表存储
  • 红黑树：当链表长度 > 8 且数组长度 ≥ 64 时，链表转为红黑树
  • 退化为链表：当树节点 ≤ 6 时，红黑树退化为链表
数组槽位状态：
┌─────────────────────────────────────────────────────────┐
│ 槽位0: 单个节点    │ 槽位1: 链表（长度≤8）│ 槽位2: 红黑树（长度>8）│
│  ┌─────┐          │  ┌─────┐ ┌─────┐    │      ┌─────┐        │
│  │Node │          │  │Node │→│Node │    │      │     │        │
│  └─────┘          │  └─────┘ └─────┘    │      │ RBT │        │
│                   │                     │      │     │        │
│                   │                     │      └─────┘        │
└─────────────────────────────────────────────────────────┘

为什么要引入红黑树？

极端情况下，所有 key 的 hash 值都相同，所有元素都在同一个槽位的链表中。链表查找的时间复杂度是 O(n)，当 n 很大时性能极差。红黑树可以将查找时间优化到 O(log n)。

2.3 Node 内部类

// HashMap 的节点结构
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;      // 哈希值
    final K key;         // 键
    V value;             // 值
    Node<K,V> next;      // 下一个节点（用于链表）
    
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    // ...
}

// 树节点（红黑树）
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;   // 父节点
    TreeNode<K,V> left;     // 左子节点
    TreeNode<K,V> right;    // 右子节点
    TreeNode<K,V> prev;     // 前驱节点
    boolean red;            // 颜色（红/黑）
    // ...
}

三、核心源码解析

3.1 重要常量

// 默认初始容量（必须是2的幂次方）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

// 最大容量（2^30）
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;

3.2 核心字段

// 哈希表数组（第一次使用时初始化）
transient Node<K,V>[] table;

// 缓存 entrySet
transient Set<Map.Entry<K,V>> entrySet;

// 元素个数
transient int size;

// 修改次数（用于 fail-fast 机制）
transient int modCount;

// 扩容阈值（容量 * 负载因子）
int threshold;

// 负载因子
final float loadFactor;

3.3 put 方法源码解析

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 计算 key 的 hash 值
static final int hash(Object key) {
    int h;
    // 让高位参与低位运算，减少冲突
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

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. 如果 table 为空，进行初始化（扩容）
    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 {
        // 3. 发生哈希冲突
        Node<K,V> e; K k;
        
        // 3.1 检查第一个节点是否匹配
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 3.2 如果是树节点，进行红黑树插入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 3.3 遍历链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 到达链表尾部，插入新节点
                    p.next = newNode(hash, key, value, null);
                    // 如果链表长度达到树化阈值，转为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 找到相同 key 的节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 4. key 已经存在，覆盖旧值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    // 5. 修改计数器增加
    ++modCount;
    
    // 6. 检查是否需要扩容
    if (++size > threshold)
        resize();
    
    afterNodeInsertion(evict);
    return null;
}

3.4 为什么容量必须是 2 的幂次方？

// 计算数组索引的代码
i = (n - 1) & hash

// 当 n = 16 时，n-1 = 15（二进制 1111）
// hash 值低位直接决定索引位置，均匀分布

// 当 n = 15 时，n-1 = 14（二进制 1110）
// 最后一位永远是 0，只能放在偶数位，浪费一半空间

结论：容量为 2 的幂次方，可以使 (n-1) & hash 等同于 hash % n，但位运算效率更高，同时保证元素均匀分布。

3.5 扩容机制

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    if (oldCap > 0) {
        // 超过最大容量，不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 新容量 = 旧容量 × 2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;  // 阈值也 × 2
    }
    else if (oldThr > 0)
        newCap = oldThr;
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    // 创建新数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    // 迁移旧数据
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 单个节点，重新计算索引
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 树节点，进行树的拆分
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 链表节点，拆分成两个链表
                else {
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 判断是否在原来索引位置
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        } else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    
                    // 两个链表分别放入新数组
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

扩容优化：JDK 8 在扩容时，不需要重新计算每个元素的 hash。利用 (e.hash & oldCap) 判断：

  • 结果为 0：元素留在原索引位置
  • 结果不为 0：元素移动到 原索引 + oldCap 的位置

四、哈希冲突与解决方案

4.1 什么是哈希冲突？

当两个不同的 key 计算出相同的数组索引时，就发生了哈希冲突。

key1.hashCode() = 12345678
key2.hashCode() = 87654321

经过 hash() 和 (n-1) & hash 计算后，索引都是 5 → 冲突！

4.2 HashMap 如何解决哈希冲突？

解决方案 说明
链地址法 冲突的元素放在链表中（HashMap 使用的方式）
开放地址法 冲突后寻找下一个空槽位（ThreadLocalMap 使用）
再哈希法 使用多个不同的哈希函数
建立公共溢出区 将冲突元素放在单独的溢出区

4.3 JDK 7 的死链问题

多线程环境下，JDK 7 的 HashMap 在扩容时可能出现死循环：

// 简化的问题代码（JDK 7）
void transfer(Entry[] newTable) {
    Entry[] src = table;
    for (int j = 0; j < src.length; j++) {
        Entry e = src[j];
        while (e != null) {
            Entry next = e.next;
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];  // 头插法
            newTable[i] = e;
            e = next;
        }
    }
}

问题：JDK 7 使用头插法，多线程并发扩容时可能形成环形链表，导致 CPU 100%。

解决方案：

  • 使用 ConcurrentHashMap（推荐）
  • 使用 Collections.synchronizedMap()
  • 升级到 JDK 8（改为尾插法）

五、遍历与迭代

5.1 三种遍历方式

Map<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

// 方式1：遍历 keySet（不推荐）
for (String key : map.keySet()) {
    System.out.println(key + " = " + map.get(key));
}
// 缺点：需要两次查找，效率低

// 方式2：遍历 entrySet（推荐）
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

// 方式3：使用迭代器（可以在遍历时删除）
Iterator<Map.Entry<String, Integer>> iter = map.entrySet().iterator();
while (iter.hasNext()) {
    Map.Entry<String, Integer> entry = iter.next();
    if (entry.getKey().equals("B")) {
        iter.remove();  // 安全删除
    }
}

5.2 遍历时删除的正确方式

// ❌ 错误：ConcurrentModificationException
for (String key : map.keySet()) {
    if (key.equals("B")) {
        map.remove(key);  // 会抛出异常
    }
}

// ✅ 正确：使用 Iterator
Iterator<String> iter = map.keySet().iterator();
while (iter.hasNext()) {
    if (iter.next().equals("B")) {
        iter.remove();
    }
}

// ✅ 正确：JDK 8+ 使用 removeIf
map.keySet().removeIf(key -> key.equals("B"));

5.3 fail-fast 机制

HashMap 是 fail-fast（快速失败）的：

  • 当检测到并发修改（modCount 变化）时，立即抛出 ConcurrentModificationException
  • 这是为了在并发问题发生时尽早暴露，而不是让程序继续错误运行

六、性能优化

6.1 初始容量设置

// 如果知道需要存储 100 个元素
// 不推荐：会触发多次扩容
Map<String, String> map1 = new HashMap<>();

// 推荐：指定初始容量
Map<String, String> map2 = new HashMap<>(100);

// 更好的：考虑负载因子（100 / 0.75 ≈ 134）
Map<String, String> map3 = new HashMap<>(134);

公式：初始容量 = (期望元素数量 / 负载因子) + 1

6.2 负载因子的权衡

负载因子 优点 缺点
较小（如 0.5） 哈希冲突少，查询快 内存浪费，扩容频繁
较大（如 0.9） 内存利用率高 哈希冲突多，查询慢
默认（0.75） 时间与空间的平衡 —

6.3 自定义对象作为 Key

// 使用自定义对象作为 key 时，必须重写 hashCode 和 equals
public class Person {
    private String name;
    private int age;
    
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

// 使用不可变对象作为 key（推荐）
// String、Integer 等都是不可变的
Map<String, String> map = new HashMap<>();

最佳实践：

  • 使用不可变对象作为 key
  • 如果使用可变对象，不要修改 key 的属性（否则无法再找到）

七、常见问题

7.1 HashMap 与 Hashtable 的区别

特性 HashMap Hashtable
线程安全 非线程安全 线程安全（synchronized）
null 支持 key 和 value 都可以为 null 不允许 null
性能 高 低（同步开销）
初始容量 16 11
迭代器 fail-fast fail-safe
继承 AbstractMap Dictionary

7.2 HashMap 与 ConcurrentHashMap

特性 HashMap ConcurrentHashMap
线程安全 ❌ ✅
性能（单线程） 高 略低
性能（多线程） 不安全 高
null 支持 允许 不允许

7.3 为什么字符串常用作 key？

// String 是不可变的
// 1. 不可变性保证了 hashCode 可以被缓存，计算一次后重复使用
// 2. 不可变性保证了 equals 的稳定性
// 3. String 的 hashCode 实现经过优化，分布均匀

// String 的 hashCode 实现
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        for (char c : value) {
            h = 31 * h + c;  // 31 是质数，减少冲突
        }
        hash = h;
    }
    return h;
}

八、性能对比测试

public class HashMapPerformanceTest {
    public static void main(String[] args) {
        int size = 100_000;
        
        // 测试1：不同初始容量
        testCapacity(size);
        
        // 测试2：不同负载因子
        testLoadFactor(size);
    }
    
    static void testCapacity(int size) {
        // 不指定容量（会多次扩容）
        Map<Integer, Integer> map1 = new HashMap<>();
        long start = System.nanoTime();
        for (int i = 0; i < size; i++) map1.put(i, i);
        long time1 = System.nanoTime() - start;
        
        // 指定合适容量
        Map<Integer, Integer> map2 = new HashMap<>((int)(size / 0.75f) + 1);
        start = System.nanoTime();
        for (int i = 0; i < size; i++) map2.put(i, i);
        long time2 = System.nanoTime() - start;
        
        System.out.printf("默认容量: %.2f ms\n", time1 / 1_000_000.0);
        System.out.printf("指定容量: %.2f ms\n", time2 / 1_000_000.0);
        // 结果：指定容量快 30%~50%
    }
}

九、总结

9.1 核心要点

知识点 要点
数据结构 数组 + 链表 + 红黑树
初始容量 16，必须是 2 的幂次方
负载因子 0.75
扩容 容量翻倍，元素迁移优化
线程安全 非安全，多线程用 ConcurrentHashMap
null 支持 key 和 value 都可以为 null

9.2 最佳实践清单

  • ✅ 预估元素数量，设置合理的初始容量
  • ✅ 使用 entrySet() 遍历，而不是 keySet()
  • ✅ 使用不可变对象作为 key
  • ✅ 重写 equals 时一定要重写 hashCode
  • ✅ 多线程环境使用 ConcurrentHashMap
  • ✅ 遍历时删除使用 Iterator.remove() 或 removeIf()
  • ❌ 不要把 HashMap 用于多线程场景
  • ❌ 不要使用可变对象作为 key
  • ❌ 不要在遍历时直接调用 map.remove()

9.3 JDK 7 vs JDK 8 对比

特性 JDK 7 JDK 8
数据结构 数组 + 链表 数组 + 链表 + 红黑树
插入方式 头插法 尾插法
扩容优化 重新计算 hash 利用原容量判断
并发问题 死循环风险 不会死循环（但仍不安全）

一句话总结：HashMap 是 Java 中最常用的集合之一，它通过哈希表实现 O(1) 的平均查询时间复杂度。理解它的底层原理，不仅能帮助你写出更高效的代码，也是应对技术面试的必备知识。

CATALOG
    FEATURED TAGS
    docker flink golang java基础 jumpserver linux maven mongodb mybatis mycat mysql redis socket springboot springcloud sqlite 并发 微服务 服务编排 消息队列 监控 系统设计 虚拟机