← 返回首页 📚 实战课程
📑 本篇章节导航 (共4章,点击直达)
一、理论篇(30%)—— 从hash扰动到transfer的源码级拆解二、动手篇(40%)—— 源码验证与性能测试三、面试模拟篇(20%)—— 追问链式考核四、练习篇(10%)

P1-05 - HashMap与ConcurrentHashMap源码

定位:面试官问"HashMap的tableSizeFor怎么算""resize时链表为什么用头插法会死循环""ConcurrentHashMap的sizeCtl有几种状态""ForwardingNode是什么",你答不清楚。本节专治这个gap。

一、理论篇(30%)—— 从hash扰动到transfer的源码级拆解

1.1 HashMap核心参数


默认参数(面试必背):
- DEFAULT_INITIAL_CAPACITY = 16        // 初始容量
- DEFAULT_LOAD_FACTOR = 0.75f          // 负载因子
- TREEIFY_THRESHOLD = 8                // 链表转红黑树阈值
- UNTREEIFY_THRESHOLD = 6              // 红黑树退化阈值
- MIN_TREEIFY_CAPACITY = 64            // 转红黑树的最小表容量
- MAXIMUM_CAPACITY = 1 << 30           // 最大容量

为什么负载因子是0.75?
→ 泊松分布下,每个桶超过8个元素的概率仅为0.00000006
→ 太大(1.0):空间利用率高但hash冲突严重
→ 太小(0.5):hash冲突少但空间浪费
→ 0.75是时间和空间的折中

为什么链表转红黑树阈值是8?
→ 遵循泊松分布,正常情况下链表长度超过8的概率极低
→ 如果频繁超过8,应该检查hashCode()的质量

1.2 tableSizeFor —— 永远是2的幂


// HashMap 源码:保证容量永远是2的幂
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;   // 最高位1的后1位变为1     → 至少2个连续1
    n |= n >>> 2;   // 后2位变为1              → 至少4个连续1
    n |= n >>> 4;   // 后4位变为1              → 至少8个连续1
    n |= n >>> 8;   // 后8位变为1              → 至少16个连续1
    n |= n >>> 16;  // 后16位变为1             → 至少32个连续1(int共32位)
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

// 示例:tableSizeFor(13)
// cap - 1 = 12 = 0000 0000 0000 0000 0000 0000 0000 1100
// >>> 1  = 0000...0110,  |= → 0000...1110
// >>> 2  = 0000...0011,  |= → 0000...1111
// 后续 >>> 4/8/16 不变(已经全是1了)
// n + 1 = 16(2^4)

// 为什么必须是2的幂?
// 因为 hash % capacity 等价于 hash & (capacity - 1)
// 位运算比取模快得多

1.3 hash扰动函数


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

// 扰动过程:
// hashCode()    = 0xABCD1234
// >>> 16        = 0x0000ABCD
// XOR           = 0xABCD98F9  (高16位和低16位混合)
//
// 为什么要扰动?
// capacity一般较小(16、32、64...),只有低几位参与定位
// 扰动让高位也参与计算,减少碰撞概率

1.4 putVal 完整流程


putVal(key, value) 流程(Java 8):

1. 计算hash = hash(key)
2. 如果table == null || table.length == 0 → resize()
3. 定位桶:(n - 1) & hash
4. 如果桶为空 → 直接放入新Node
5. 如果桶不为空:
   5a. 如果首节点key相同(hash相等 && key相等)→ 覆盖value
   5b. 如果首节点是TreeNode → 调用红黑树插入
   5c. 否则遍历链表:
       - 尾插法追加
       - 如果链表长度 >= TREEIFY_THRESHOLD - 1 → treeifyBin()
       - 如果key已存在 → 覆盖value
6. 如果是覆盖 → 直接返回旧值
7. ++size > threshold → resize()

1.5 resize transfer(扩容迁移)


// Java 8 扩容迁移 —— 拆分 lo/hi 两条链
// 关键:新容量 = 旧容量 * 2
// 每个桶的元素只会迁移到两个位置之一:原位置 或 原位置+旧容量

// 判断方法:(e.hash & oldCap) == 0
// 如果hash在旧容量的那个bit位为0 → 位置不变(lo链)
// 如果为1 → 新位置 = 旧位置 + oldCap(hi链)

/*
 * 示例:oldCap = 16 (10000)
 *   hash1 = 0...01001  → & 10000 = 0  → 桶位置 = 1001 & 1111 = 9(不变)
 *   hash2 = 1...01001  → & 10000 ≠ 0  → 桶位置 = 1001 + 10000 = 25
 *
 * 旧表桶9:  [Node(hash1)] → [Node(hash2)]
 * 新表桶9:  [Node(hash1)]        (lo链)
 * 新表桶25: [Node(hash2)]        (hi链)
 */

Java 7 的头插法死循环问题:


Java 7 的 transfer 用头插法(多线程并发resize时):
  线程A暂停在 transfer 中间,线程B完成了 transfer
  线程A恢复后继续用旧引用做头插法,可能产生环形链表
  后续 get() 时 while(e != null) 死循环

Java 8 改为拆分lo/hi两条链 + 尾插法,解决了环形链表问题
但 HashMap 仍然不是线程安全的!并发put可能导致数据丢失

1.6 HashMap树化


树化条件(两个条件同时满足):
1. 链表长度 >= 8(TREEIFY_THRESHOLD)
2. table.length >= 64(MIN_TREEIFY_CAPACITY)
   如果表太小,优先扩容而不是树化

TreeNode vs Node 结构:
┌──────────────────────────────────────┐
│ Node                                  │
│   int hash                            │
│   K key                               │
│   V value                             │
│   Node<K,V> next                      │
└──────────────────────────────────────┘

┌──────────────────────────────────────┐
│ TreeNode extends Node                 │
│   TreeNode parent                     │
│   TreeNode left                       │
│   TreeNode right                      │
│   TreeNode prev                       │ ← 维护双向链表(用于反树化)
│   boolean red                         │ ← 红黑树节点颜色
└──────────────────────────────────────┘

退化条件:扩容后红黑树节点数 <= 6(UNTREEIFY_THRESHOLD)

1.7 ConcurrentHashMap Java 8+ 架构


CHM Java 8 核心设计:
1. 取消Segment分段锁,改用 CAS + synchronized
2. 锁粒度:每个桶的头节点(Node)
3. 读操作无锁(volatile Node.val / Node.next)
4. 写操作:桶为空用CAS,桶非空用synchronized(头节点)

sizeCtl 状态含义:
┌──────────────┬──────────────────────────────────────────┐
│ sizeCtl 值    │ 含义                                      │
├──────────────┼──────────────────────────────────────────┤
│ -1           │ 正在初始化                                 │
│ -(1+n)       │ n个线程正在扩容                             │
│ 0            │ 未初始化(默认值)                           │
│ > 0           │ 下次扩容的阈值(capacity * loadFactor)     │
└──────────────┴──────────────────────────────────────────┘

ForwardingNode(迁移标记节点):
- hash = -1(MOVED)
- 扩容时,已迁移完成的桶放ForwardingNode
- 其他线程put时遇到ForwardingNode → 帮助扩容(helpTransfer)

1.8 CHM vs synchronizedMap vs Hashtable


┌───────────────┬──────────────┬──────────────┬──────────────┐
│               │ CHM(Java 8)  │ syncMap      │ Hashtable    │
├───────────────┼──────────────┼──────────────┼──────────────┤
│ 锁粒度        │ 桶节点       │ 全表         │ 全表          │
│ 读操作        │ 无锁(volatile)│ synchronized │ synchronized │
│ 写操作        │ CAS+sync     │ synchronized │ synchronized │
│ null key/val  │ 不允许       │ 允许         │ 不允许        │
│ 迭代器        │ 弱一致       │ 快速失败     │ 枚举         │
│ 并发性能      │ 高           │ 低           │ 低           │
└───────────────┴──────────────┴──────────────┴──────────────┘

结论:CHM完胜,生产环境应始终使用CHM

二、动手篇(40%)—— 源码验证与性能测试

2.1 HashMap putVal流程跟踪


import java.lang.reflect.Field;
import java.util.HashMap;

/**
 * 实验1:验证HashMap内部结构
 * 通过反射观察table数组、链表/树结构、容量变化
 */
public class HashMapInspectDemo {

    public static void main(String[] args) throws Exception {
        HashMap<String, Integer> map = new HashMap<>(4); // 指定初始容量4

        // 反射获取table字段
        Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);

        // 插入元素观察扩容
        for (int i = 0; i < 20; i++) {
            map.put("key" + i, i);

            Object[] table = (Object[]) tableField.get(map);
            int capacity = table != null ? table.length : 0;

            // 统计每个桶的链表长度
            int maxChainLen = 0;
            if (table != null) {
                for (Object node : table) {
                    int chainLen = 0;
                    while (node != null) {
                        chainLen++;
                        Field nextField = node.getClass().getDeclaredField("next");
                        nextField.setAccessible(true);
                        node = nextField.get(node);
                    }
                    maxChainLen = Math.max(maxChainLen, chainLen);
                }
            }

            System.out.printf("size=%2d, capacity=%2d, maxChain=%d%n",
                map.size(), capacity, maxChainLen);
        }
    }
}

2.2 制造hash冲突观察链表转树


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

/**
 * 实验2:制造hash冲突,观察链表转红黑树
 * 关键:需要构造hash相同但key不同的对象
 */
public class HashMapTreeifyDemo {

    // 故意让所有对象的hashCode返回相同值
    static class BadKey {
        private final String name;

        BadKey(String name) { this.name = name; }

        @Override
        public int hashCode() { return 1; } // 所有key hash相同

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof BadKey)) return false;
            return name.equals(((BadKey) o).name);
        }

        @Override
        public String toString() { return name; }
    }

    public static void main(String[] args) throws Exception {
        Map<BadKey, String> map = new HashMap<>();

        // 先确保容量 >= 64(否则优先扩容不树化)
        // 默认容量16,负载因子0.75,阈值12
        // 需要13个元素触发第一次扩容到32
        // 需要25个元素触发第二次扩容到64
        for (int i = 0; i < 64; i++) {
            map.put(new BadKey("key" + i), "val" + i);
        }

        System.out.println("size=" + map.size());
        System.out.println("此时桶0应该已经树化(链表长度 >= 8 且 capacity >= 64)");

        // 反射检查桶0的节点类型
        Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);
        Object[] table = (Object[]) tableField.get(map);
        if (table[1] != null) {
            System.out.println("桶1节点类型: " + table[1].getClass().getName());
            // TreeNode会显示类似 java.util.HashMap$TreeNode
        }
    }
}

2.3 CHM并发安全性验证与性能对比


import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 实验3:HashMap vs CHM vs synchronizedMap 并发安全性与性能对比
 *
 * 验证点:
 * 1. HashMap并发put可能丢失数据(size不一致)
 * 2. CHM并发安全且性能最优
 * 3. synchronizedMap安全但性能差
 *
 * 典型运行结果(16线程,每线程10万次put):
 *   HashMap: size=1345210 (期望1600000) [LOST] 耗时300ms
 *   synchronizedMap: size=1600000 [OK] 耗时800ms
 *   CHM: size=1600000 [OK] 耗时400ms
 */
public class MapConcurrentTest {

    static final int THREADS = 16;
    static final int OPS_PER_THREAD = 100_000;

    public static void main(String[] args) throws Exception {
        System.out.println("===== 并发安全性与性能测试 =====\n");

        // 测试1:HashMap(不安全,数据可能丢失)
        System.out.println("--- HashMap(不安全)---");
        testMap(new HashMap<>(), "HashMap");

        // 测试2:Collections.synchronizedMap
        System.out.println("--- synchronizedMap ---");
        testMap(Collections.synchronizedMap(new HashMap<>()), "synchronizedMap");

        // 测试3:ConcurrentHashMap
        System.out.println("--- ConcurrentHashMap ---");
        testMap(new ConcurrentHashMap<>(), "CHM");

        // 测试4:CHM 读写并发
        System.out.println("--- CHM 高并发写入+读取 ---");
        testConcurrentReadWrite();
    }

    static void testMap(Map<Integer, Integer> map, String name) throws Exception {
        CountDownLatch latch = new CountDownLatch(THREADS);

        long start = System.currentTimeMillis();
        for (int i = 0; i < THREADS; i++) {
            final int threadId = i;
            new Thread(() -> {
                for (int j = 0; j < OPS_PER_THREAD; j++) {
                    int key = threadId * OPS_PER_THREAD + j;
                    map.put(key, key);
                }
                latch.countDown();
            }).start();
        }
        latch.await();
        long cost = System.currentTimeMillis() - start;

        int expected = THREADS * OPS_PER_THREAD;
        int actual = map.size();
        String status = (actual == expected) ? "OK" : "LOST " + (expected - actual);
        System.out.printf("  %s: size=%d (期望%d) [%s] 耗时%dms%n",
            name, actual, expected, status, cost);
    }

    static void testConcurrentReadWrite() throws Exception {
        ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<>();
        AtomicInteger readCount = new AtomicInteger(0);
        CountDownLatch latch = new CountDownLatch(THREADS * 2);

        // 写线程
        for (int i = 0; i < THREADS; i++) {
            final int id = i;
            new Thread(() -> {
                for (int j = 0; j < 10_000; j++) {
                    map.put(id * 10_000 + j, "val");
                }
                latch.countDown();
            }).start();
        }

        // 读线程(CHM读无锁)
        for (int i = 0; i < THREADS; i++) {
            new Thread(() -> {
                for (int j = 0; j < 100_000; j++) {
                    map.get(j % 1000);
                    readCount.incrementAndGet();
                }
                latch.countDown();
            }).start();
        }

        long start = System.currentTimeMillis();
        latch.await();
        long cost = System.currentTimeMillis() - start;
        System.out.printf("  CHM 读写并发: 写入%d 读取%d 耗时%dms%n",
            map.size(), readCount.get(), cost);
    }
}

2.4 CHM sizeCtl状态观察


import java.util.concurrent.ConcurrentHashMap;
import java.lang.reflect.Field;

/**
 * 实验4:观察CHM的sizeCtl状态变化
 *
 * 预期观察:
 *   初始 sizeCtl = 0(未初始化)
 *   首次put后 sizeCtl = 12(16 * 0.75,下次扩容阈值)
 *   size超过12后扩容,sizeCtl = 24(32 * 0.75)
 */
public class CHMSizeCtlDemo {

    public static void main(String[] args) throws Exception {
        ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();

        Field sizeCtlField = ConcurrentHashMap.class.getDeclaredField("sizeCtl");
        sizeCtlField.setAccessible(true);

        System.out.println("初始 sizeCtl = " + sizeCtlField.get(map));

        for (int i = 0; i < 30; i++) {
            map.put("key" + i, "val" + i);
            System.out.printf("size=%2d, sizeCtl=%d%n",
                map.size(), sizeCtlField.get(map));
        }
    }
}

三、面试模拟篇(20%)—— 追问链式考核

Q1: HashMap的底层数据结构是什么?


Q1.1: Java 7和Java 8有什么区别?
→ Java 7: 数组 + 链表(头插法)
→ Java 8: 数组 + 链表 + 红黑树(尾插法)
→ 树化条件: 链表长度>=8 且 数组长度>=64

Q1.2: 为什么Java 8改为尾插法?
→ Java 7头插法在多线程并发resize时可能产生环形链表(死循环)
→ 尾插法保持了链表的相对顺序,避免了环形链表
→ 但HashMap仍然不是线程安全的(并发put会丢数据)

Q1.3: 红黑树和链表什么时候互相转换?
→ 链表→红黑树: 链表长度>=8 且 数组长度>=64(否则优先扩容)
→ 红黑树→链表: 扩容后树节点数<=6
→ 为什么阈值不同(8和6)?避免频繁转换(中间态7)

Q2: HashMap的扩容机制?


Q2.1: 扩容时元素怎么重新分布?
→ 不需要重新计算hash
→ 每个元素只有两种去向:原位置 或 原位置+旧容量
→ 判断条件:(e.hash & oldCap) == 0
→ Java 8拆分为lo/hi两条链,一次性迁移

Q2.2: 为什么容量必须是2的幂?
→ (n-1) & hash 等价于 hash % n,但位运算快
→ 扩容时只需要看新增的那一位bit是0还是1
→ 保证元素均匀分布

Q2.3: HashMap默认容量是多少?指定11会怎样?
→ 默认16
→ 指定11会被tableSizeFor调整为16(大于等于11的最小2的幂)

Q3: ConcurrentHashMap怎么保证线程安全?


Q3.1: Java 7和Java 8的CHM有什么区别?
→ Java 7: Segment分段锁(ReentrantLock),默认16段
→ Java 8: CAS + synchronized,锁粒度细化到每个桶的头节点
→ Java 8并发度从固定16变为等于桶数量

Q3.2: CHM的读操作需要加锁吗?
→ 不需要。Node的val和next是volatile的
→ 读操作直接读取,保证可见性
→ 如果遇到ForwardingNode(hash=-1),会转到新表读取

Q3.3: CHM的size()方法怎么实现的?
→ baseCount + CounterCell[](类似LongAdder的思路)
→ sum = baseCount + 所有CounterCell的value
→ 精确度:非精确(类似LongAdder的sum())

Q4: HashMap为什么不是线程安全的?


Q4.1: 多线程并发put会发生什么?
→ 数据丢失:两个线程同时判断桶为空,一个覆盖另一个
→ size不准:++size不是原子操作
→ Java 7还可能死循环(头插法环形链表)

Q4.2: 怎么选择线程安全的Map?
→ 高并发读写:ConcurrentHashMap
→ 低并发:Collections.synchronizedMap
→ 只读为主:CopyOnWriteArraySet(数据量小时)
→ 绝对不要用Hashtable

常见踩坑

1. HashMap并发死循环 —— Java 7头插法导致环形链表,Java 8改为尾插法但仍不安全

2. CHM不允许null key/value —— HashMap允许,但CHM在并发环境下null有歧义

3. HashMap容量不是传入值 —— tableSizeFor会向上取到最近的2的幂

4. 红黑树不一定在链表长度8时触发 —— 还需要表容量>=64,否则优先扩容

5. 以为指定初始容量就能避免扩容 —— 如果负载因子0.75,容量16最多存12个元素


四、练习篇(10%)

练习1:验证tableSizeFor

手写tableSizeFor方法,用二进制打印每一步的结果,验证cap=13->16、cap=17->32、cap=100->128。

练习2:HashMap vs CHM并发丢失数据

写一个程序,16个线程各往HashMap中put 10000个不同的key,最后检查map.size()是否等于160000。换成CHM再试一次,对比结果。

练习3:阅读CHM putVal源码

打开JDK源码,阅读ConcurrentHashMap.putVal()方法,标注以下关键步骤:

1. 桶为空时的CAS操作

2. 桶非空时的synchronized锁

3. ForwardingNode的处理

4. treeifyBin的触发条件

练习4:设计一个线程安全的LRU缓存

基于HashMap + 双向链表实现,要求: