小菜鸟

java菜鸟号正在起航

0%

HashMap详解

发表于 更新于 分类于 阅读次数： 66 Valine：
本文字数： 8.9k 阅读时长 ≈ 8 分钟

HashMap 深度解析（基于 JDK 8）

HashMap 是 Java 集合框架中使用最广泛的 Map 实现类，基于哈希表（数组 + 链表 + 红黑树）实现，支持高效的键值对存储与查询。其设计兼顾了时间和空间效率，是单线程环境下键值对存储的首选。本文将从底层结构、核心源码、工作机制及并发问题等方面，全面剖析 HashMap 的实现原理。

HashMap 核心特性与继承关系

核心特性

  • 键唯一性：键（key）不可重复，重复插入会覆盖原值。
  • 允许 null：键和值均可为 null（键最多 1 个 null，值可多个）。
  • 无序性：存储顺序与插入顺序无关（由键的哈希值决定）。
  • 动态扩容：容量不足时自动扩容，默认扩容为原容量的 2 倍。
  • 非线程安全：多线程并发修改可能导致数据不一致（如死循环、数据覆盖）。

继承关系

1
2
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
  • 继承 AbstractMap：复用 Map 接口的基础实现（如 entrySet、keySet 等）。
  • 实现 Map：遵循键值对集合的规范。
  • 实现 Cloneable：支持浅拷贝（仅复制结构，不复制元素对象）。
  • 实现 Serializable：支持序列化，通过 writeObject 和 readObject 自定义序列化逻辑。

底层数据结构：数组 + 链表 + 红黑树

HashMap 的底层结构是哈希表，JDK 8 中采用 “数组 + 链表 + 红黑树” 的组合结构，平衡了哈希冲突处理与查询效率：

  • 数组（Node[] table）：存储键值对的主体，每个元素是链表或红黑树的头节点。
  • 链表：解决哈希冲突（不同键哈希值相同），将冲突的键值对以链表形式存储。
  • 红黑树：当链表长度超过阈值（默认 8）且数组容量 ≥ 64 时，链表转为红黑树，将查询时间复杂度从 O(n) 优化为 O(log n)。

核心静态常量（控制结构行为）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 默认初始容量（16，必须为 2 的幂）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

// 最大容量（2^30）
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认加载因子（0.75，平衡时间与空间效率）
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转红黑树的阈值（链表长度 ≥ 8 时触发）
static final int TREEIFY_THRESHOLD = 8;

// 红黑树转链表的阈值（红黑树节点数 ≤ 6 时触发）
static final int UNTREEIFY_THRESHOLD = 6;

// 链表转红黑树的最小数组容量（数组长度 ≥ 64 时才允许转树）
static final int MIN_TREEIFY_CAPACITY = 64;

为什么容量必须是 2 的幂？
数组索引通过 (n - 1) & hash 计算（n 为数组容量）。当 n 是 2 的幂时，n - 1 的二进制为全 1（如 16-1=15 → 1111），与哈希值进行 “与运算” 可均匀分布索引，效果等同于取模（hash % n），但运算效率更高。

节点结构（Node 与 TreeNode）

（1）链表节点 Node
1
2
3
4
5
6
7
8
9
10
11
12
13
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;
    }
}

  • 存储键值对及链表后继节点，是哈希表的基本单元。
（2）红黑树节点 TreeNode
1
2
3
4
5
6
7
8
9
10
11
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;           // 节点颜色（红/黑）

    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}
  • 继承 Node，增加红黑树的父子节点引用和颜色标记，支持树结构操作（旋转、变色等）。

构造函数：初始化容量与加载因子

HashMap 提供 4 种构造函数，核心是初始化容量（数组长度）和加载因子（扩容阈值比例）。

无参构造函数

1
2
3
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // 加载因子默认 0.75，数组延迟初始化
}
  • 数组（table）在第一次 put 时初始化，初始容量为 DEFAULT_INITIAL_CAPACITY（16）。

指定初始容量

1
2
3
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
  • 初始容量会被修正为大于等于指定值的最小 2 的幂（通过 tableSizeFor 方法）。

指定初始容量和加载因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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); // 修正初始容量为 2 的幂
}

// 计算大于等于 cap 的最小 2 的幂（如 cap=10 → 返回 16）
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;  // 高位扩散，确保低位全为 1
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

基于已有 Map 初始化

1
2
3
4
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false); // 批量插入已有 Map 的键值对
}

核心方法解析：put 与 get

1. put(K key, V value)：添加键值对

put 方法是 HashMap 的核心，负责键值对的插入、哈希冲突处理、扩容及树化。

步骤 1：计算键的哈希值（二次哈希）
1
2
3
4
5
6
7
8
9
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 二次哈希：减少哈希冲突（高位与低位异或，增强随机性）
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • 对键的原始哈希值（key.hashCode()）进行高位（16 位）与低位（16 位）异或，增强低位随机性，减少哈希冲突。
步骤 2：putVal 核心逻辑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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 { // 3. 索引位置不为空（哈希冲突）
        Node<K,V> e; K k;
        // 3.1 若头节点与当前键相同（hash 和 key 均相等），直接覆盖
        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);
        // 3.3 若为链表，遍历链表查找或插入
        else {
            for (int binCount = 0; ; ++binCount) {
                // 3.3.1 遍历到链表尾部，插入新节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 若链表长度 ≥ 8，尝试树化（需数组容量 ≥ 64）
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 3.3.2 找到相同键，跳出循环准备覆盖
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }

        // 4. 若键已存在，覆盖原值并返回旧值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); // 空实现（LinkedHashMap 重写用于维护顺序）
            return oldValue;
        }
    }

    // 5. 键不存在，更新结构修改次数和大小
    ++modCount;
    if (++size > threshold) // 若元素数超过阈值，触发扩容
        resize();
    afterNodeInsertion(evict); // 空实现（LinkedHashMap 重写用于 LRU 缓存）
    return null;
}
关键子流程：树化（treeifyBin）

当链表长度 ≥ 8 且数组容量 ≥ 64 时，链表转为红黑树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 若数组容量 < 64，不树化而是扩容（避免小容量下树化浪费空间）
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 1. 将链表转为双向链表（TreeNode 维护 prev/next）
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null) hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        // 2. 将双向链表转为红黑树
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

2. get(Object key)：查询键值对

get 方法通过键的哈希值定位索引，再遍历链表或查询红黑树获取值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 1. 数组非空且索引位置有节点
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 2. 检查头节点
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 3. 遍历后续节点
        if ((e = first.next) != null) {
            // 3.1 红黑树查询
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 3.2 链表查询
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null; // 未找到
}

扩容机制（resize）

当元素数量超过 阈值（capacity * loadFactor） 时，HashMap 会触发扩容（容量翻倍），并迁移旧数组中的键值对到新数组。

1. resize 核心逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;

    // 1. 计算新容量和新阈值
    if (oldCap > 0) {
        // 1.1 若旧容量已达最大值，阈值设为 Integer.MAX_VALUE，不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 1.2 否则容量翻倍（newCap = oldCap << 1），阈值同步翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;
    }
    // 2. 若旧容量为 0 但旧阈值 > 0（构造时指定了初始容量），新容量 = 旧阈值
    else if (oldThr > 0)
        newCap = oldThr;
    // 3. 初始化（无参构造）：新容量 = 16，新阈值 = 16 * 0.75 = 12
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 4. 修正新阈值（若未计算）
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ? (int)ft : Integer.MAX_VALUE;
    }
    threshold = newThr;

    // 5. 创建新数组并迁移旧数据
    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; // 帮助 GC
                // 5.1 单个节点（无哈希冲突）
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 5.2 红黑树节点：拆分树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 5.3 链表节点：拆分链表为两个子链表（原索引和新索引）
                else {
                    Node<K,V> loHead = null, loTail = null; // 原索引（j）
                    Node<K,V> hiHead = null, hiTail = null; // 新索引（j + oldCap）
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 通过 (e.hash & oldCap) 判断新索引：0 → 原索引；非 0 → 新索引
                        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;
}

扩容时索引计算优化：
旧容量为 oldCap（2 的幂），新容量为 2*oldCap。通过 e.hash & oldCap 可快速判断新索引：

  • 结果为 0 → 新索引 = 旧索引（j）；
  • 结果非 0 → 新索引 = 旧索引 + oldCap（j + oldCap）。
    无需重新计算哈希值，仅需一次位运算，高效迁移数据。

高并发问题

HashMap 非线程安全，多线程并发修改可能导致以下问题：

1. JDK 7 中的死循环

JDK 7 中扩容采用头插法迁移链表，多线程并发扩容可能导致链表成环。当后续查询该链表时，会陷入无限循环（next 节点永远不为空）。

2. JDK 8 中的数据覆盖

JDK 8 改用尾插法避免死循环，但仍可能出现数据覆盖：

  • 线程 A 与线程 B 同时计算出相同索引，且索引位置为空；
  • 线程 A 先插入节点，线程 B 随后插入，会覆盖线程 A 的节点。

解决方案：

  • 单线程环境：直接使用 HashMap。
  • 多线程环境：使用 ConcurrentHashMap（线程安全，高效），或通过 Collections.synchronizedMap 包装 HashMap（低效，不推荐）
相关文章

欢迎关注我的其它发布渠道

表情 | 预览
Powered By Valine
v1.3.10