大家好，我是你们的朋友老赵。今天我们不聊什么高深理论，就聊一个你们迟早要面对，而且必须彻底搞懂的东西——Map。

开篇：用一个“笨办法”让你顿悟Map的价值

想象一下这个场景：你手里有一个班级花名册，是List<Student>类型，里面有10000个学生。现在校长让你立刻找到学号为20230001的“张三”同学，通知他来领奖。

你会怎么做？没错，写个循环：

List<Student> studentList = // ... 10000个学生
Student target = null;

for (Student stu : studentList) {
    if (stu.getId() == 20230001) {  // 假设id是int
        target = stu;
        break;
    }
}

if (target != null) {
    System.out.println("找到了！" + target.getName());
}

代码跑起来了，你的电脑开始疯狂比较。第1个不是，第2个不是...直到第7564个，终于找到了！

我们来小结一下：这种查找方式，最坏情况要查10000次（如果张三在最后）。专业上我们说它的时间复杂度是O(n)——数据量n越大，耗时越长。

现在我问你：现实中去图书馆找书，你会从第一本开始一本本翻吗？当然不会！你会直接走到“计算机科学”分区，然后在书架上找《Java编程思想》。

核心洞察：Map要解决的就是这个问题——如何像查字典一样，直接“翻”到目标所在的那一页？

第一部分：我们一起来设计一个简陋的“字典”（SimpleMap）

第一版：用数组直接存？

既然学号是数字，我们能不能这样：

Student[] students = new Student[100000000];  // 学号可能到99999999
students[20230001] = new Student(20230001, "张三");

需要找张三时，直接 students[20230001] 就拿到了！速度是O(1)，瞬间完成。

但是问题来了：为了存1万个学生，我们创建了1亿个位置的数组！其中9999万个位置都是空的。这就像为了放10本书，租了个能放100万本书的仓库——空间浪费太严重了。

第二版：引入“压缩器”——哈希函数

我们需要一个聪明的办法：把大的学号（比如20230001）“压缩”成一个小范围的数字（比如0-99）。

这个压缩器就叫哈希函数（Hash Function）。

比喻时刻：想象一个大型招聘会，有10000个求职者（数据）。但会场只有100个面试间（数组空间）。哈希函数就是门口的智能分流机：

• 每个求职者出示身份证（调用hashCode()）

• 分流机根据身份证号计算出一个0-99的数字（压缩）

• 求职者去对应的面试间等候

关键点：不同的身份证可能算出相同的数字！这就是哈希碰撞——两个不同的人被分到了同一个面试间。

// 看看Java自带的哈希函数
String key = "张三";
int hashCode = key.hashCode();  // 返回一个int，比如123456
int arrayLength = 100;
int index = Math.abs(hashCode) % arrayLength;  // 压缩到0-99
// index可能是 56，表示去第56号位置

第三版：解决“撞车”问题——链表来了

现在我们知道：学号20230001通过哈希函数计算后，得到了位置56。我们把张三放到array[56]。

但如果学号20230002也计算出了56，怎么办？把张三挤走吗？当然不行！

比喻升级：同一个面试间（数组位置56）里，第一个来的是张三。李四来了发现有人，他不是离开，而是拍拍张三的肩膀说“我排你后面”。这样就形成了一个队伍（链表）。

// 我们定义链表的节点
class Node {
    Object key;     // 学号
    Object value;   // 学生对象
    Node next;      // 下一个节点
}

// 数组不再直接存Student，而是存链表的头节点
Node[] array = new Node[100];

// 插入张三（假设计算出的index=56）
Node node1 = new Node(20230001, "张三", null);
array[56] = node1;

// 插入李四（也计算出index=56）
Node node2 = new Node(20230002, "李四", null);
node1.next = node2;  // 李四排在张三后面

查找时，先计算index=56，然后进入这个链表，从张三开始一个个问：“你是学号20230001吗？”直到找到为止。

我们来小结一下：你已经亲手实现了Map最核心的数组+链表结构！这个结构有个名字——拉链法。而JDK中的HashMap，核心就是这个思想。

第二部分：深入JDK的HashMap——看大师如何优化

JDK 1.7的HashMap：数组+链表（头插法）

在JDK 1.7中，HashMap的实现和我们刚才设计的SimpleMap很相似，但有一个重要区别：头插法。

什么是头插法？

• 刚才我们设计的链表是尾插法：新来的人排在队伍最后面

• JDK 1.7用的是头插法：新来的人直接插到队伍最前面

// JDK 1.7的插入逻辑（简化版）
void put(K key, V value) {
    int index = hash(key) % array.length;
    Node newNode = new Node(key, value);
    
    // 头插法：新节点的next指向原头节点
    newNode.next = array[index];
    array[index] = newNode;
}

为什么用头插法？

• 假设：新插入的数据更可能被马上访问（比如缓存）

• 优点：插入速度快，不需要遍历到链表末尾

但头插法有个致命问题：在多线程环境下扩容时可能导致死循环（后面会讲）。

JDK 1.8的HashMap：数组+链表/红黑树（尾插法）

JDK 1.8对HashMap做了重大改进，主要有三点：

1. 从头插法改为尾插法

• 为什么改？ 彻底解决多线程扩容时可能的死循环问题

• 新策略：新节点插入链表末尾

• 代码变化：

// JDK 1.8的插入逻辑（链表部分）
void put(K key, V value) {
    int index = hash(key) & (array.length - 1);  // 用位运算代替取模
    Node newNode = new Node(key, value);
    
    // 找到链表末尾
    Node current = array[index];
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;  // 尾插法
}

2. 引入红黑树（链表树化）

当链表长度≥8 且 数组总长度≥64时，链表转换为红黑树。

为什么是8？基于泊松分布统计：

• 哈希函数理想时，链表长度达到8的概率：0.00000006%

• 这是为了防御性编程：正常情况下不会发生，但能防止恶意攻击

红黑树是什么？

• 比喻：把线性排队改成"问答游戏"

  • 问："你学号大于50吗？"

  • 答"是" → 去右边

  • 答"否" → 去左边

  • 几轮问答就能定位

• 效率：链表查找是O(n)，红黑树是O(log n)

树退化回链表：当树节点数≤6时，退化回链表（维护树需要额外开销）

3. 哈希函数优化（扰动函数）

// JDK 1.8的hash()方法
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

作用：将hashCode的高16位特征"搅拌"到低16位，让分布更均匀。

4. 扩容机制的优化

JDK 1.7在扩容时需要重新计算每个元素的新位置：

// JDK 1.7的rehash
newIndex = newHash(key) % newCapacity;

JDK 1.8发现了规律：扩容后元素的新位置要么在原位置，要么在原位置+原容量：

二进制演示：

旧容量：16 = 10000b
旧容量-1：15 = 01111b
新容量：32 = 100000b  
新容量-1：31 = 011111b

元素hash值：... 1 1111  (最后5位是11111)
& 15 (01111b) = 01111  = 15（旧位置）
& 31 (11111b) = 11111  = 31（新位置 = 15 + 16）

元素hash值：... 0 1111  (最后5位是01111)
& 15 (01111b) = 01111  = 15（旧位置）
& 31 (11111b) = 01111  = 15（还在原位置）

结论：只需看hash值在扩容新增的那一位是0还是1：

• 是0：留在原位置

• 是1：新位置 = 原位置 + 原容量

优点：避免重新计算hash，提高扩容效率。

JDK 1.7 vs JDK 1.8 HashMap对比表

特性	JDK 1.7	JDK 1.8
数据结构	数组+链表	数组+链表/红黑树
插入方式	头插法	尾插法
哈希冲突解决	纯链表	链表长度≥8且数组≥64时转红黑树
扩容时rehash	重新计算所有元素hash	巧妙的位置迁移（原位置或原位置+旧容量）
多线程问题	可能死循环	不会死循环（但仍线程不安全）

第三部分：高并发下的安全地图——ConcurrentHashMap的演进

第一阶段：整个Map一把大锁（Hashtable）

// Hashtable的做法（极度简化版）
public synchronized V put(K key, V value) {
    // ... 插入逻辑
}

比喻：整个图书馆只有一把钥匙，一个人进去就锁门，其他人全在外面等。

第二阶段：分段锁（JDK 1.7的ConcurrentHashMap）

设计思想：分而治之

• 把整个Map分成多个小区域（Segment）

• 每个Segment有自己的锁

• 操作不同Segment时互不干扰

代码结构：

// JDK 1.7 ConcurrentHashMap结构
ConcurrentHashMap {
    Segment[] segments;  // 默认16个Segment
    
    static class Segment<K,V> extends ReentrantLock {
        HashEntry<K,V>[] table;  // 每个Segment内部是一个小HashMap
    }
}

操作流程：

1. 根据key的hash值确定属于哪个Segment

2. 获取该Segment的锁

3. 在这个Segment内部的table上操作

4. 释放锁

比喻：图书馆有16个阅览室，每个阅览室一把锁。不同阅览室的人可以同时看书。

优点：并发度由Segment数量决定（默认16，可配置）。

缺点：

1. 并发度固定，Segment数创建后不能改

2. 某些Segment可能特别繁忙，成为瓶颈

3. 查询时需要两次哈希计算

第三阶段：桶位锁+CAS（JDK 8的ConcurrentHashMap）

革命性改变：放弃分段锁

JDK 8的ConcurrentHashMap回归了与HashMap相似的数组+链表/红黑树结构，但用更细粒度的锁保证线程安全。

核心机制1：CAS（Compare-And-Swap）

比喻：超市寄存柜操作

• 你看23号柜是空的（期望值）

• 你按下存包（新值）

• 系统检查：如果23号柜确实是空的，就让你存进去；如果已经被别人用了，就操作失败

• 这个"看-比较-存"是一个原子操作，无法被打断

在代码中的应用：

// 向空位置插入节点时使用CAS
if (table[index] == null) {
    // 使用CAS尝试将新节点放入table[index]
    // 如果成功，插入完成
    // 如果失败（被其他线程抢先），重试或其他处理
}

核心机制2：synchronized锁头节点

当要操作的位置不是空（已有链表或树）时，用synchronized锁住这个链表的头节点：

synchronized (头节点) {
    // 在这个链表或树上操作
    // 其他链表不受影响
}

比喻：只锁23号书架，其他书架随便看。

JDK 1.8 ConcurrentHashMap的put流程：

1. 如果数组未初始化，先初始化（CAS）

2. 计算索引，找到桶位置

3. 如果桶为空，用CAS插入新节点

4. 如果桶不为空（已有链表/树），用synchronized锁住头节点

5. 在链表或树上插入节点

6. 如果链表长度≥8，且数组长度≥64，链表转红黑树

7. 检查是否需要扩容

扩容机制（多线程协同扩容）

这是JDK 8 ConcurrentHashMap最精妙的部分：

传统扩容问题：一个线程扩容，其他线程等待 → 性能下降

JDK 8的解决方案：多线程协同扩容

1. 当线程A发现需要扩容时，它开始迁移数据

2. 线程B来操作时，发现正在扩容，它会帮助一起迁移

3. 迁移规则：每个线程负责迁移一段连续的数据段

4. 迁移完成后，所有线程使用新数组

关键数据结构：ForwardingNode

• 当一个桶迁移完成后，会放一个ForwardingNode标记

• 其他线程看到这个标记，就知道这个桶已迁移，去新数组操作

JDK 1.7 vs JDK 1.8 ConcurrentHashMap对比表

特性	JDK 1.7	JDK 1.8
数据结构	Segment数组 + HashEntry链表	数组 + 链表/红黑树
锁粒度	Segment级别（默认16个锁）	桶级别（更细粒度）
锁类型	ReentrantLock	synchronized + CAS
并发度	固定（Segment数量）	更高（桶的数量）
查询性能	需要两次hash计算	一次hash计算
扩容机制	Segment独立扩容	多线程协同扩容
内存占用	较高（Segment对象开销）	较低

为什么JDK 8改用synchronized？

1. 性能提升：JDK 6后synchronized被大幅优化（偏向锁→轻量级锁→重量级锁）

2. 内置优化：JVM能更好地优化内置锁

3. 减少内存：相比ReentrantLock的AQS框架，synchronized更轻量

总结与行动指南

全景对比表格

Map实现类	数据结构	是否有序	线程安全	适用场景	JDK版本差异
HashMap	数组+链表/红黑树	无	否	大多数单线程场景	1.8优化：红黑树、尾插法、扩容优化
LinkedHashMap	HashMap+双向链表	插入/访问顺序	否	LRU缓存等需要顺序的场景	保持插入或访问顺序
TreeMap	红黑树	按键排序	否	需要有序遍历的场景	基于红黑树实现
Hashtable	数组+链表	无	是（全表锁）	遗留系统，不推荐	全表锁，性能差
ConcurrentHashMap (JDK 1.7)	Segment+HashEntry	无	是	高并发，已过时	分段锁，16个锁
ConcurrentHashMap (JDK 1.8)	数组+链表/红黑树	无	是	高并发，推荐	桶位锁+CAS，性能更好

“我该怎么选？”流程图

开始
  ↓
需要线程安全吗？
  ├─ 是 → 用ConcurrentHashMap (JDK 1.8+)
  ↓
 否
  ↓
需要按插入顺序或访问顺序遍历吗？
  ├─ 是 → LinkedHashMap
  ↓
 否
  ↓
需要按键排序吗？
  ├─ 是 → TreeMap
  ↓
 否
  ↓
HashMap ✓

必须动手的3个实验

实验1：体验HashMap的线程不安全

public class HashMapThreadUnsafe {
    public static void main(String[] args) throws InterruptedException {
        Map<String, Integer> map = new HashMap<>();
        
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                map.put("key" + i, i);
            }
        });
        
        Thread t2 = new Thread(() -> {
            for (int i = 1000; i < 2000; i++) {
                map.put("key" + i, i);
            }
        });
        
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        
        // 结果可能不是2000，可能更少（数据丢失）或程序异常
        System.out.println("Map大小: " + map.size());
    }
}

实验2：ConcurrentHashMap的安全使用

public class ConcurrentHashMapDemo {
    public static void main(String[] args) throws InterruptedException {
        Map<String, Integer> map = new ConcurrentHashMap<>();
        
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                map.put("key" + i, i);
            }
        });
        
        Thread t2 = new Thread(() -> {
            for (int i = 1000; i < 2000; i++) {
                map.put("key" + i, i);
            }
        });
        
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        
        // 结果稳定为2000
        System.out.println("Map大小: " + map.size());
    }
}

实验3：观察HashMap的树化过程

public class HashMapTreeify {
    public static void main(String[] args) {
        // 创建一个容量为64的HashMap（达到树化条件）
        Map<BadHashKey, Integer> map = new HashMap<>(64);
        
        // 创建一批hashCode相同的key
        for (int i = 0; i < 10; i++) {
            map.put(new BadHashKey(i), i);
        }
        
        // 通过反射查看内部结构
        try {
            Field tableField = HashMap.class.getDeclaredField("table");
            tableField.setAccessible(true);
            Object[] table = (Object[]) tableField.get(map);
            
            // 查看某个位置的节点类型
            if (table[0] != null) {
                Class<?> nodeClass = table[0].getClass();
                System.out.println("节点类型: " + nodeClass.getName());
                // 如果是TreeNode，说明已树化
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    
    static class BadHashKey {
        int id;
        BadHashKey(int id) { this.id = id; }
        
        @Override
        public int hashCode() {
            return 1;  // 所有key的hashCode都相同，强制碰撞
        }
    }
}

最后的叮嘱

今天我们完成了一次深度之旅：

1. 从零构建：我们亲手实现了SimpleMap，理解了哈希、碰撞、链表

2. HashMap进化史：从JDK 1.7的头插法到JDK 1.8的红黑树、尾插法、扩容优化

3. 高并发演进：从Hashtable的全表锁 → JDK 1.7的分段锁 → JDK 1.8的桶位锁+CAS

记住这些核心要点：

• HashMap：单线程首选，理解它的数据结构演进

• ConcurrentHashMap：高并发必备，JDK 1.8的实现是典范

• 选型原则：根据需求（线程安全、顺序、排序）选择合适实现

回去后一定要动手写代码，特别是实验部分。只有亲手实践，才能真正理解这些设计的精妙之处。