HashMap 及 ConcurrentHashMap 简介

HashMap 数据结构介绍

在最新的 Java 8+ 版本中，HashMap 的物理存储结构已经非常成熟，它被形象地称为 “数组 + 链表 + 红黑树” 的混合体。我们可以用一个 “智能图书馆” 的例子来通俗地解释它的工作原理。

物理结构：三级进化。

  • 第一层：基础书架（数组 / Buckets）。HashMap 的核心是一个数组。每一个数组槽位（Slot）被称为一个桶（Bucket）。通俗理解就是图书馆里有一排编号为 0 到 15 的书架（初始容量 16）。当你存一本书（Key-Value）时，计算机会根据书名（Key）算出一个编号，直接把你带到对应的书架前。
  • 第二层：同类堆放（链表 / Chaining）。如果两本不同的书被算出了同一个编号（哈希冲突），它们会怎么放？比如如果《Java编程》和《Python入门》都要放在 5 号书架，它们会像串在一起的糖葫芦一样，挂在 5 号书架上。这就是链表。
  • 第三层：智能升级到红黑树 / Treeification。这是 Java 8 以后引入的黑科技。如果某个书架上的书太多了（默认超过 8 本），查找起来就像大海捞针。当 5 号书架挂了 9 本书时，HashMap 会自动把这一串糖葫芦拆掉，重新排列成一棵 “平衡树”。这样做的好处是在链表里找书要一本本翻（$O(n)$），在树里找书只需要“左看右看”几次就能定位（$O(\log n)$），速度极快。


为什么使用哈希函数将元素分散存储？

这是一个非常经典的问题。简单来说，HashMap 追求的是 “直达目标” 的极致速度。使用哈希函数分散存储，就是为了避免“一件件翻找”，实现 “按索引地址拿书”。

在计算机科学中，查找数据通常有两种方式：

  • 线性搜索（像排队）：如果你想找一个名字，得从第一个人开始问：“你是张三吗？”。如果有一万个人，最差要问一万次。时间复杂度是 $O(n)$。

  • 哈希定位（像查门牌号）：你把“张三”这个名字输入一个函数，它直接告诉你：“他在 502 号房”。你直接过去推门就行。时间复杂度是 $O(1)$。


哈希函数的作用，就是把任意长度的“键”（Key）转化为一个固定范围的“数字索引”（数组下标）。HashMap 的底层物理存储本质上是一个数组。如果你把元素一个挨一个地存放在数组开头，那它就变成了普通的 ArrayList。当你搜索时，依然要从下标 0 开始往后查，速度依然很慢。使用哈希分散后的物理形态是 ：

  • 计算哈希值：当你执行 map.put(“Apple”, 10) 时，HashMap 会计算 “Apple” 的 hashCode()。

  • 映射下标：通过哈希函数处理（比如取模运算），得到一个数组下标（假设是 3）。

  • 直接存放：数据被直接扔进数组下标为 3 的位置。


Hash冲突：如果两把钥匙算出的地址一样怎么办？

由于数组长度是有限的，而 Key 的可能性是无限的，必然会出现两个不同的 Key 算出了相同的下标，这叫“哈希冲突”（Hash Collision）。Java HashMap 的处理策略非常聪明：

  • 拉链法：如果两个元素都要住 3 号房，那就在 3 号房门口拉起一根绳子（链表），让后来的人挂在前面的人后面。

  • 树化：如果挂的人太多（链表长度超过 8），为了防止找起来变慢，HashMap 会把链表变成红黑树（二叉树的一种），保证即使冲突严重，查找速度依然很快。


核心的 “黑科技” 参数

为了保证图书馆不拥挤，HashMap 有两个关键的“管理员”：

参数 默认值 作用（通俗解释）
Initial Capacity 16 初始书架的数量。
Load Factor 0.75 扩容警戒线。当书架用了 75% 时，管理员会立刻扩建（容量翻倍），防止书架太满导致冲突。
TREEIFY_THRESHOLD 8 树化变身阈值。当一个书架上的书达到 8 本，链表转为红黑树。
UNTREEIFY_THRESHOLD 6 还原阈值。当书被删到只剩 6 本，红黑树退化回链表（为了省内存）。


HashMap的其他黑科技

① 瞬间定位的位运算

最新版本中，HashMap 定位书架不是用慢悠悠的除法取模，而是使用位运算：$index = (n - 1) \ \& \ hash$

这直接利用了计算机二进制底层逻辑，速度快到飞起。

② 懒加载（Lazy Initialization）

当你 new HashMap() 的时候，它其实还没真正占用内存。只有当你第一次往里面存数据（put）时，它才会真正去创建那一排书架（数组）。


HashMap典型使用提醒

线程不安全：这个图书馆没有 “管理员锁”，如果多个搬运工（线程）同时在扩建书架，可能会导致书籍丢失或图书馆（数据结构）崩溃。多线程请用 ConcurrentHashMap。

Key 的稳定性：作为“书名”的 Key，最好是不可变的（比如 String 或 Integer）。如果你书存进去后，书名变了，那你这辈子都找不回这本书了（因为哈希值变了，去错了书架）。


ConcurrentHashMap简介

在 Java 8 之前，它靠的是“分段锁”；而 Java 8 之后（包括最新的 Java 21+），它进化成了更高效的“无锁 CAS + 局部锁”。

  • 曾经的王者：分段锁 (Segment) —— Java 7 时代。可以把 Segment 想象成 “一个大仓库隔成的16个小房间”。
    • 设计思路：以前的 Hashtable 是锁住整个仓库，一次只准一个搬运工（线程）进来。而 Segment 将数据分成了 16 段，每一段都有自己的一把锁。
    • 效果：如果线程 A 在 1 号房间干活，线程 B 可以同时在 2 号房间干活。
    • 缺点：如果 16 个房间都满了，想再加房间非常麻烦。而且每个 Segment 都要维护一个锁，非常重，浪费内存。
  • 现在的霸主：CAS + synchronized —— Java 8 及以后。最新的 ConcurrentHashMap 抛弃了厚重的 Segment，改用了更轻量级的 CAS (Compare And Swap)
    • 核心技术一：CAS（无锁化操作）—— “先斩后奏”：比如你要往 5 号柜子里放书，发现柜子是空的。你记住“现在是空的”，然后准备把书放进去。放的那一刻，你会再看一眼柜子。如果还是空的，说明没人动过，你直接放进去（这就是一次原子操作，不需要加锁）。如果变绿了（别人抢先了），你就失败，重新尝试。优势是在低竞争的情况下，完全没有加锁的开销，速度极快。
    • 核心技术二：synchronized（局部锁定）—— “精确打击”：如果 5 号柜子已经有书了，需要处理复杂的链表或红黑树，CAS 就不够用了。ConcurrentHashMap 会使用 synchronized 锁住这一个桶（Bucket）的头节点。它只锁住这一个柜子，不影响你操作其他编号的柜子。现在的 synchronized 经过 JVM 优化后，性能已经非常接近硬件锁了。
Map类型 类比成大型超市
HashMap 没有收银员，大家乱哄哄地往柜台挤，账目全乱。
Hashtable 整个超市只有一个收银员，所有顾客排成一队。哪怕你有 10 个收银台，也只准开一个。
ConcurrentHashMap CAS 阶段：如果收银台没人，你直接刷脸支付，一秒闪人，不用等收银员（无锁）。局部锁阶段：如果收银台有人正在结算，收银员只拉起这一个收银台的小围栏（只锁当前 Bucket），其他收银台依然正常工作。


ConcurrentHashMap 使用提示：虽然 ConcurrentHashMap 保证了每一个单独的操作（如 put、get）是原子的，但如果你要做复合操作，比如：

1
2
3
4
// 错误写法：在多线程下依然不安全
if (!map.containsKey(key)) {
    map.put(key, value);
}

替代方案：请务必使用它提供的原子复合方法，例如：

1
2
putIfAbsent(key, value)
computeIfAbsent(key, k -> new Value())


CAS 又是什么鬼？

要理解 CAS (Compare And Swap) 在 CPU 底层是如何通过一条指令（如 cmpxchg）保证绝对安全的，，我们需要从软件逻辑 一层层下钻到 CPU 硬件电路。


软件逻辑：CAS 的 “三要素”

在 Java 或 C++ 层级，CAS 操作包含三个操作数：

  • 内存地址 (V)：数据储存在哪。

  • 期望值 (A)：你认为现在数据应该是多少。

  • 新值 (B)：你想把它改成多少。

核心逻辑是： “我认为地址 V 上的值应该是 A，如果是，则将其改为 B；如果不是，说明别人动过了，我什么都不做，并告诉我自己失败了。”


硬件实现：

  • 单核 CPU 的 “原子性”：在单核时代，虽然有线程切换，但同一时刻只有一个指令在执行。cmpxchg 指令（Compare and Exchange）在执行时，CPU 会在一个指令周期内完成“比较+交换”。这里的关键点是 ： CPU 指令是不可分割的。就像你眨一下眼，不可能眨到一半去干别的。
  • 核心挑战：多核 CPU 下的 “抢地盘”：现在问题来了。现在的 CPU 都是多核的（比如 8 核、16 核），每个核都有自己的缓存（L1/L2 Cache）。如果核 1 和核 2 同时 执行 cmpxchg 尝试修改同一个内存地址，即便指令本身是原子的，但两个核之间可能存在“时差”，导致数据混乱。为了解决这个问题，底层硬件祭出了两个大招：
    • 大招一：LOCK 前缀（总线锁）。在早期的多核架构中，当 CPU 执行 cmpxchg 时，会在指令前加一个 LOCK 前缀。物理效果是这个 LOCK 会在电路上发送一个 LOCK# 信号，直接锁住北桥总线（Bus）。就像在村里的唯一一条路上拉了横幅，这期间只有核 1 的车能走，其他核的车都得停下等着。这太暴力了！锁住总线意味着所有核都不能访问内存，效率极低。
    • 大招二：MESI 协议（缓存锁）—— 现代主流。现在的 CPU（如 Intel Core 系列）利用缓存一致性协议 (MESI) 实现了更聪明的 “缓存锁”。当核 1 想要修改内存 0x001 时，它会先通过内部通讯告诉其他核：“我要独占这个地址的缓存行（Cache Line）”。如果核 2 也想改，它会发现该缓存行已被核 1 标记为 Modified（修改）或 Exclusive（独占）状态。核 2 必须等待核 1 处理完并把结果同步回内存（或 L3 缓存）后，才能重新读取。通俗理解就是：核 1 不再封锁整条大马路，而是只给 0x001 这个特定的抽屉挂把小锁。


绝对安全的代价：空转（Spin）

CAS 虽然在指令级别是安全的，但在业务层级会带来 “空转” 消耗。典型的示例：

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
// 这种写法通常被称为 自旋（Spinning）
// 典型的代表：AtomicInteger.getAndIncrement()
// 它的态度是：“我一定要成功，不成功我就不走了！”
// 如果竞争很小，它能很快成功，效率极高（省去了线程挂起、唤醒的开销）。
// 但在高并发下（比如 100 个线程抢一个变量）：只有一个线程能改成功，剩下 99 个线程都在疯狂跑 while 循环。
// 这时，CPU 会瞬间飙升到 100%。因为这些线程并没有“睡觉”（阻塞），而是在以极高的频率不断询问 CPU：
// “现在行了吗？现在行了吗？”这种无效的计算会白白浪费大量的电力和计算资源。
// 适用于操作非常快（比如只是给变量 +1），且并发不高的场景。
while (!cas(value, expect, update)) {
    // ...
}

// 你可能会想：既然 while 太累，那我在 while 体中 sleep 一会儿再试行不行？
while(!cas(value, expect, update)) {
    Thread.sleep(1); // 歇 1 毫秒
}
// 尴尬的是在 CPU 眼里，1毫秒是极其漫长的（足够执行几百万条指令）。
// 如果你 sleep，线程会从用户态切换到内核态，然后再切回来。
// 这种上下文切换的开销，往往比 CAS 失败几次的开销还要大。
// 所以，高性能的自旋锁通常会使用 Thread.onSpinWait()（Java 9+）
// 或者干脆自旋几次后还没成功，再升级为挂起等待。

// 真实的开发建议：
// 如果你是在写底层并发工具（比如实现一个自己的计数器），用 while，但要配合 “限次数自旋” 或 “退避策略”。
// 如果你是在写业务逻辑（比如防止重复提交、抢购名额），用 if。
// 抢不到就告诉用户“服务器繁忙”，这才是保护系统的正确做法。

风险：如果竞争非常激烈（几百个线程抢一个变量），CPU 会一直卡在 while 循环里疯狂计算，导致 CPU 占用率飙升，这种现象叫 “自旋（Spinning）”。另一种业务层面的写法是 “佛系派”：

1
2
3
4
5
6
7
8
9
10
// 随缘的“佛系派”
// 典型代表：ConcurrentHashMap 尝试插入头节点
// 它的态度是：“我就试这一次，不行就算了，回头再说。”
// 对 CPU 的影响极低。 它只执行一次 cmpxchg 指令，成功或失败都会立刻向下执行后续代码。
// 它不会让 CPU 卡在原地“空转”。
// 适用于状态更新类的业务场景。
// 比如多个线程同时尝试给一个任务加锁，谁抢到谁干活。抢不到的人（if 失败）直接走掉去干别的事，或者报错退出。
if (!cas(value, expect, update)) {
    // ...
}


CAS 的一个著名漏洞：ABA 问题

虽然 cmpxchg 保证了数值比较的正确性，但它看不出“过程”。比如：

  1. 你看到值是 A。
  2. 在你改之前，核 2 把值改成了 B，然后又迅速改回了 A。
  3. 你回来一看，哎？还是 A！于是你修改成功了。

现实后果：在某些场景（如链表栈的操作）下，这可能导致内存引用的逻辑错误。

对策：给数据加一个 版本号（Version）。比如从 1A 变成 2B 再变成 3A。Java 中对应的工具类是 AtomicStampedReference。


综上所述：CAS 的“绝对安全”源于 硬件级的指令锁定：

  • 指令层：cmpxchg 是原子指令。
  • 多核层：通过 LOCK 前缀或 MESI 协议锁住缓存行，确保同一时刻只有一个核能改成功。