一、HashMap

1. 实现原理

数据结构

• HashMap 的底层由数组 + 链表 + 红黑树组成

  • 数组（哈希桶）：初始容量为 16，存储链表头节点或红黑树根节点，每次扩容翻倍

  • 链表：解决哈希冲突，同一索引的键值对以链表形式存储

  • 红黑树（JDK 1.8+）：链表长度超过 8 且数组容量 ≥ 64 时，链表转为红黑树，查询复杂度从 O(n) 优化为 O(log n)

• 哈希函数与索引计算

  • 哈希扰动：通过 hash(key) = (h = key.hashCode()) ^ (h >>> 16) 混合高低位，降低冲突概率

  • 索引定位：index = (n - 1) & hash（n 为数组长度且保持 2 的幂次方），位运算替代取模提升效率

核心流程

• Put 操作：

  • 计算哈希值定位索引

  • 若桶为空则插入新节点，否则遍历链表/树：

    • 存在相同 key 时覆盖旧值（通过 equals 判断）

    • 不存在则插入链表末尾或红黑树

  • 触发扩容条件：元素数量 ≥ 容量 × 负载因子（默认 0.75）

• Get 操作：

  • 计算哈希值定位索引，遍历链表/树匹配 key

  • 返回 value 或 null

哈希冲突

• 解决机制

  • 链地址法：冲突键值对存入同一桶的链表或红黑树

  • 扩容：负载因子超标时数组翻倍，重新散列元素以减少冲突

线程安全

• 多线程同时修改结构（如 put/remove）可能导致数据不一致或死循环（JDK 1.7 头插法）

• 解决方案：使用 ConcurrentHashMap 或 Collections.synchronizedMap 包装

版本差异

• JDK 1.7：头插法链表，多线程扩容易引发死循环

• JDK 1.8：尾插法，引入红黑树优化，降低并发风险

自定义 Key

• 必须重写 hashCode() 和 equals()：确保相同逻辑的 key 哈希值一致且等价，否则数据可能丢失

• 示例：未重写时，内容相同的两个对象作为 key 会被视为不同，导致 get 返回 null

性能优化建议

• 初始容量：预估数据量设置（如 new HashMap<>(1000)），避免频繁扩容。

• 负载因子：内存充足时可降低负载因子以减少冲突。

• 哈希分散性：优化 hashCode() 方法，使键分布均匀。

详见 http://www.shj4u.work/itdocx/docs/java/core/collection/source-code-analysis/map/HashMap.html

2. 线程安全

结论

HashMap 不是线程安全的类，多线程环境下直接使用可能导致

• 数据丢失（多个线程 put 时覆盖写入）

• 数据不一致（读取到中间状态）

• 死循环（JDK 1.7 头插法扩容形成环形链表）

• 迭代器失效（遍历时修改结构抛出 ConcurrentModificationException）

核心原因

• 操作非原子性：put 和扩容涉及多步骤且未加锁

• 共享资源竞争：多线程同时修改同一哈希桶（链表/红黑树）

• JDK 1.7 头插法缺陷：扩容时链表顺序反转易形成环

替代方案

• ConcurrentHashMap

  • JDK 1.7 使用分段锁，JDK 1.8+ 改用 CAS + synchronized 锁桶头节点

  • 高并发场景首选，性能优异

• Collections.synchronizedMap

  • 通过 synchronized 包装 HashMap 所有方法

  • 简单但性能较差，适合低并发场景

• Hashtable（已过时）

  • 全局锁机制导致性能极低，不推荐使用

面试要点

• 明确结论：HashMap 非线程安全

• 核心问题：数据竞争导致覆盖/丢失，JDK 1.7 死循环问题

• 解决方案：优先推荐 ConcurrentHashMap，次选 SynchronizedMap

• 版本差异：JDK 1.8 尾插法解决死循环，但数据竞争仍存在

3. PUT 过程

哈希值计算

• 调用 key.hashCode() 获取原始哈希值，通过扰动函数 (h = key.hashCode()) ^ (h >>> 16) 混合高低位，降低冲突概率

• 若 key 为 null，哈希值固定为 0

定位桶索引

• 计算索引：index = (n - 1) & hash，其中 n 为数组长度（保持 2 的幂次方）

• 若数组未初始化（首次插入），调用 resize() 初始化容量为 16，负载因子为 0.75

哈希冲突处理

• 空桶：直接创建新节点存入数组

• 非空桶

  • 链表：遍历链表查找相同 key（equals 匹配）

    • 存在相同 key：覆盖旧 value

    • 不存在：插入链表末尾。链表长度 ≥ 8 且数组容量 ≥ 64 时转为红黑树

  • 红黑树：调用 putTreeVal() 插入或更新节点

扩容触发与迁移

• 当元素数量超过阈值（容量 × 负载因子）时触发扩容，新容量为旧容量的 2 倍

• 迁移规则：根据 (e.hash & oldCap) 判断节点分配到原索引或原索引 + 旧容量的位置

返回结果与状态更新

• key 存在时返回旧 value，否则返回 null

• 更新 modCount 计数器，用于迭代器的快速失败检测

4. GET 过程

哈希值计算与索引定位

• 计算 key 的哈希值：key.hashCode() 经扰动函数 (h = key.hashCode()) ^ (h >>> 16) 混合高低位

• 若 key 为 null，哈希值固定为 0

• 计算索引：index = (n - 1) & hash（n 为数组长度，保持 2 的幂次方）

桶位元素检查

• 根据索引定位数组中的桶，若桶为空（table[index] == null），直接返回 null

• 若桶非空，检查首节点的哈希值和 key 是否匹配（通过 == 或 equals）。若匹配则返回 value

链表或红黑树遍历

• 链表：首节点不匹配时遍历链表，通过 equals 方法逐一比对 key，找到则返回 value，否则返回 null

• 红黑树（JDK 1.8+）：调用 getTreeNode() 递归查找树节点，基于哈希值和 key 大小决定子树方向

时间复杂度与性能

• 无冲突时 O(1)，链表冲突时 O(n)，红黑树优化后 O(log n)

注意事项

• 必须正确重写 hashCode() 和 equals() 以确保 key 匹配

• JDK 1.8 红黑树优化长链表查询效率

• 迭代器依赖 modCount 检测并发修改，触发 ConcurrentModificationException

5. GET 安全性

纯读场景的理论安全性

• 若所有线程仅执行 get() 且未发生扩容，理论上是线程安全的

• 此时 get() 不修改结构，仅遍历现有节点

并发写入的潜在风险

• 死循环（JDK 1.7）：扩容时链表头插法可能形成环，get() 遍历陷入死循环

• 中间状态读取：扩容迁移过程中可能读到未完成迁移的旧数组或部分数据

• 数据不一致：并发 put() 导致覆盖写入或扩容未完成时 get() 返回 null 或旧值

JDK 版本差异影响

• JDK 1.7：头插法扩容存在成环风险，get() 高并发下可能死循环

• JDK 1.8+：尾插法避免成环，但 get() 仍可能读取到扩容中间状态

安全实践建议

• 纯读场景：初始化后不修改 HashMap 可视为安全

• 读写混合场景：使用 ConcurrentHashMap 或 Collections.synchronizedMap 包装

• 预分配容量：减少扩容触发概率

根本原因与验证

• 问题根源：HashMap 未对结构性修改（扩容）与读取操作做同步控制

• 复现方法：压力测试工具模拟并发读写，观察 CPU 占用或异常抛出

6. Key

一般用什么做 Key，为啥 String 适合做 Key 呢？

常用 Key 类型

• String：最常用，因其不可变性和哈希计算高效

• Integer/Enum：基于数值的哈希值，简单高效

• 自定义不可变类：需严格实现 hashCode() 和 equals()

• 其他包装类（如 Long）：适用于简单键值场景

String 适合作为 Key 的核心原因

• 不可变性

  • 创建后不可修改，哈希值稳定，避免数据丢失

• 哈希计算高效

  • hashCode() 使用 31 的质数乘法，分布均匀且结果缓存复用

• 字符串常量池优化

  • 相同字面量共享内存，加速比较（通过 == 判断引用相等性）

• 完善的 equals() 实现

  • 字符逐位比对，性能高效且逻辑严谨

• 语义清晰

  • 适用于配置、URL 等场景，易读且兼容性强

使用 Key 的注意事项

• 优先选择不可变对象：可变对象可能导致哈希值变化，引发数据不一致

• 正确重写 hashCode() 和 equals()

• 确保逻辑一致，避免哈希表定位失败

• 避免复杂对象：增加冲突概率且维护成本高

HashMap key 可以为 null 吗？

允许 null 键的机制

• key 为 null 时，HashMap 通过 hash() 返回哈希值 0，避免空指针异常

• null 键存储在数组索引 0 的位置，且仅允许存在一个（键唯一性保证）

设计原因与场景

• 灵活性：支持表示“未知键”或配置中的默认值

• 单线程优化：设计未考虑多线程下 null 键的二义性（如 get(key) 返回 null 时无法区分键是否存在）

与其他容器的对比

• Hashtable：禁止 null 键/值，直接调用 key.hashCode() 会抛空指针异常

• ConcurrentHashMap：禁止 null 键/值，因多线程下无法消除二义性风险，且实用价值有限

使用注意事项

• 线程安全：多线程操作 null 键需同步控制，否则可能导致数据覆盖或逻辑错误

• 代码可读性：建议用 Optional 类或明确业务语义替代，避免过度依赖 null 键

7. 红黑树

为什么要用红黑树而不是平衡二叉树？

插入与删除性能优势

• 红黑树插入/删除最多需 2 次旋转，平衡二叉树（如 AVL 树）可能需多次旋转

• 红黑树允许局部不平衡（最长路径 ≤ 2 倍最短路径），降低调整频率，适合高频更新场景

查询效率的折中

平衡二叉树查询略优（树更平衡），但 HashMap 树规模小（阈值 8，树高 ≤ 3），红黑树 O(log n) 效率已接近理想值

计算开销与内存优化

红黑树通过颜色标记替代高度差计算，减少 CPU 开销。元素减少到 6 时转回链表，避免内存浪费

工程实现的成熟性

红黑树在 Linux 内核、Java TreeMap 等广泛应用，实现经过长期验证。平衡二叉树旋转逻辑复杂，维护成本高

综合性能平衡

红黑树在插入、删除、查询间平衡更优，适合 HashMap 动态存储需求（如扩容与数据迁移）

8. 多线程

在多线程下可能会出现的问题？

数据覆盖与丢失

多线程同时插入相同哈希桶时，可能因同时检测空桶导致数据覆盖。并发扩容时节点迁移遗漏可能造成数据丢失

死循环

• JDK 1.7 及之前：头插法扩容导致链表成环，触发 get() 或 put() 操作时陷入无限循环，CPU 占用率飙升

• JDK 1.8 之后：树化扩容时，也会出现死循环常见，不过概率很低

ConcurrentModificationException 异常

迭代器遍历期间其他线程修改结构，触发快速失败机制抛出异常

脏读与逻辑错误

读取到扩容迁移中的中间状态数据，get(key) 返回 null 时无法区分键是否存在或值为 null

扩容性能下降

多线程重复触发扩容导致哈希重计算和节点迁移，增加 CPU 负载

JDK 1.8 扩容时仍需锁定当前桶引发线程阻塞

结构破坏与内存泄漏

并发修改可能导致链表断裂或树结构失衡，节点引用错误可能引发内存无法回收

9. 扩容机制

• 扩容触发条件

  • 元素数量超过阈值（阈值 = 容量 × 负载因子，默认 0.75）

  • 链表长度 ≥8 且数组长度 <64 时优先扩容而非树化

• 扩容流程

  • 新数组创建：容量翻倍（保持 2 的幂次方）

  • 数据迁移

    • 链表拆分（JDK8+）：采用高低位分组策略，将链表拆分为低位链（原索引）和高位链（原索引 + 旧容量）

    • 红黑树处理：节点数 ≤6 时退化为链表，否则拆分迁移

    • 尾插法优化：JDK8 用尾插法替代头插法，避免多线程成环问题

• 性能优化

  • 位运算 (n-1) & hash 替代取模运算，提升计算效率

  • 默认负载因子 0.75 平衡空间利用率与冲突概率

  • 初始化时建议预估容量（如 new HashMap<>(预估容量/0.75 +1)）

• 多线程风险

  • 并发插入或扩容可能导致数据覆盖、脏读

  • JDK7 头插法扩容会引发死循环，JDK8 尾插法彻底解决

  • 推荐使用 ConcurrentHashMap 保证线程安全

• 参数调优与监控

  • 强制禁用树化：通过 JVM 参数 -Djava.util.HashMap.treeifyThreshold=2147483647（牺牲查询性能）

  • 负载因子调整：内存敏感场景可调高（如 0.9），时间敏感场景调低（如 0.6）

  • 扩容性能监控：关注 GC 日志中 HashMap.resize() 耗时，优化容量规划

存 20 个元素，会扩容几次？

• 初始容量与扩容触发条件

  • 默认初始容量为 16，负载因子为 0.75，扩容阈值为 容量 × 0.75

  • 首次 put() 时初始化容量为 16（不视为扩容）

  • 当元素数量超过阈值（如 16 × 0.75 = 12）时触发扩容

• 扩容过程分析（默认参数下存入 20 个元素）

  • 第一次扩容：存入第 13 个元素时触发，容量从 16 扩容至 32，新阈值更新为 32 × 0.75 = 24

  • 后续操作：存入第 14~20 个元素时，元素数量始终 ≤24，不再触发扩容

• 特殊情况说明

  • 链表树化：若某链表长度达到 8 但数组长度 <64，会优先扩容而非树化，但仅计入一次扩容

  • 手动指定容量：例如 new HashMap<>(32) 时，阈值 = 32 × 0.75 = 24，存入 20 个元素不会触发扩容

• 总结

  • 默认场景下存入 20 个元素仅触发 1 次扩容（容量 16 → 32）

  • 扩容次数由元素数量是否超过阈值决定，与链表/树结构无关

10. 2的n次方

大小为什么是 2 的 n 次方大小呢？

• 位运算优化与计算效率

  • 容量为 2 的 n 次方时，(n-1) & hash 等价于 hash % n，但位运算性能更优（避免除法运算开销）

  • 示例：当容量为 16（二进制 10000）时，n-1 = 15（二进制 1111），位运算直接取哈希值低 4 位

• 哈希分布均匀性

  • 低位掩码（n-1 全 1）确保哈希值的所有位参与索引计算，减少哈希碰撞概率

  • 若哈希值高位不同但低位相同，仍可能分配到同一桶，但掩码机制比非 2 幂次方容量更均衡

• 扩容迁移高效性

  • 新容量为旧容量 2 倍时，迁移只需判断哈希值最高有效位

  • 最高位为 0：新索引 = 原索引

  • 最高位为 1：新索引 = 原索引 + 旧容量

  • 示例：旧容量 16，哈希值 10101 的索引从 5 变为 21（原索引 + 16）

• 容量自动对齐机制

  • 通过 tableSizeFor() 方法将用户输入容量对齐到最小 2 的幂次方。例如输入 21 时调整为 32

  • 实现方式：通过位右移和或操作填充最高位后的所有位为 1，再加 1 得到目标容量

• 数据结构兼容性

  • 链表转红黑树、拆分迁移等操作依赖容量为 2 的幂次方，例如高低位拆分逻辑与位掩码计算直接关联

  • 容量非 2 的幂次方时，扩容后无法保证高低位拆分规则的简洁性，增加迁移复杂度

11. 负载因子

• 定义与作用

  • 负载因子是 HashMap 中元素数量与容量的比率，用于控制扩容时机

  • 当元素数量超过 容量 × 负载因子 时触发扩容（容量翻倍并 rehash）

• 默认值 0.75 的权衡

  • 空间与时间平衡：

    • 过高（如 1.0）导致哈希冲突增多，查询效率降低

    • 过低（如 0.5）导致扩容频繁，空间利用率下降

  • 实践验证：0.75 是多数场景下减少冲突与避免频繁扩容的最优解

• 调整策略

  • 高并发场景：降低负载因子（0.5~0.6），减少冲突提升查询效率

  • 内存敏感场景：提高负载因子（0.8~0.9），减少扩容频率但容忍更高冲突

  • 初始化优化：通过构造函数指定（如 new HashMap<>(16, 0.6f)），或按 预估容量 / 负载因子 +1 计算初始容量

• 对性能的影响

  • 查询效率：负载因子越高，链表/红黑树遍历时间可能增加

  • 扩容成本：负载因子越低，rehash 操作越频繁，CPU 消耗增加

• 设计依据

  • 源码注释明确 0.75 是空间利用率与时间复杂度的折衷选择

  • 扩容机制（如 (n-1) & hash）需与负载因子设计兼容

二、HashTable

1. 实现原理

• 底层数据结构

  • 基于数组 + 链表实现，数组元素为 Entry 对象（包含 key、value、hash 和 next 指针）

  • 哈希函数与索引计算

  • 哈希值计算：key.hashCode()，再通过 (hash & 0x7FFFFFFF) % 数组长度 确定索引

  • 0x7FFFFFFF 确保哈希值为非负数，避免索引为负

• 线程安全实现

  • 所有公共方法（如 put、get）添加 synchronized 关键字，保证单线程操作

  • 高并发性能差，推荐改用 ConcurrentHashMap

• 扩容机制

  • 初始容量 11，负载因子 0.75，阈值 = 容量 × 负载因子

  • 触发扩容后，新容量 = 旧容量 × 2 + 1，并重新哈希所有元素

• 哈希冲突处理

  • 链地址法：冲突的 Entry 对象以链表形式存储，新元素插入链表头部（JDK 1.8 前）

  • 查找时遍历链表，时间复杂度 O(n)

• 特殊限制

  • key 和 value 均不允许为 null，否则抛出 NullPointerException

  • 继承自 Dictionary 类（已过时），与 HashMap（继承 AbstractMap）不同

2. 线程安全

• 方法级同步锁

  • 所有公共方法（如 put、get）使用 synchronized 修饰，确保同一时间仅一个线程操作 HashTable

• 内存可见性保障

  • synchronized 保证锁释放时将本地修改刷新到主内存，获取锁时读取最新值，避免数据不可见问题

• 扩容机制

  • 初始容量 11，负载因子 0.75，扩容阈值为 容量 × 负载因子。触发扩容后，新容量 = 旧容量 × 2 +1

• 与其他容器的对比

  • ConcurrentHashMap：分段锁或 CAS 机制支持并发读写，性能更高

  • synchronizedMap：对普通 HashMap 加对象级锁，性能与 HashTable 类似

• 使用限制与性能问题

  • 禁止 null 键/值，操作需显式处理空值

  • 全表锁导致读写互斥，高并发场景性能差，推荐改用 ConcurrentHashMap

三、ConcurrentHashMap

怎么实现的？

1. 实现机制

• 线程安全机制

  • JDK 1.7 分段锁：将哈希表划分为多个 Segment，每个段独立加锁，支持不同段并发操作

  • JDK 1.8 细粒度锁 + CAS：取消分段锁，对哈希桶（Node）加锁。插入时先尝试 CAS 无锁插入头节点，冲突时用 synchronized 加锁处理链表或红黑树。

• 数据结构与扩容

  • 数组 + 链表/红黑树：链表长度 ≥8 且数组容量 ≥64 时转为红黑树，查询效率提升至 O(log n)

  • 渐进式扩容：容量翻倍，多线程协作迁移数据，迁移期间读写可同时访问新旧数组。用 ForwardingNode 标记已迁移的桶

• CAS 与原子操作

  • 无锁初始化：通过 CAS 确保单线程初始化哈希表

  • 原子更新控制：插入空桶时 CAS 写入头节点，扩容时通过 sizeCtl 变量协调线程任务分配

• 内存可见性保障

  • 哈希桶数组声明为 volatile，确保读取最新状态

  • 节点 next 字段使用 volatile 修饰，防止链表遍历时数据不一致

• 性能对比

  • 相比 Hashtable：ConcurrentHashMap 支持并发读写不同桶，读操作无锁（JDK 1.8），吞吐量更高

  • 相比 synchronizedMap：细粒度锁减少竞争，支持迭代期间并发修改

2. 锁

ConcurrentHashMap 用了悲观锁还是乐观锁?

• JDK 1.7 分段锁（悲观锁）

  • 基于 ReentrantLock 实现，每个 Segment 独立加锁

  • 写操作需获取分段独占锁，同一分段内线程竞争阻塞，不同分段可并行操作

• JDK 1.8 混合锁机制

  • CAS（乐观锁）

    • 初始化数组、插入空桶头节点时使用 CAS 无锁操作

    • 扩容时通过 CAS 更新 sizeCtl 协调多线程任务

  • synchronized（轻量级悲观锁）

    • 哈希冲突时（链表/红黑树操作）对当前桶加锁，锁粒度细化到单个桶

    • 读操作无锁：依赖 volatile 修饰的 Node.val 和 next 字段保证可见性

• 锁选择逻辑与优势

  • 低冲突场景（如空桶插入）优先使用 CAS，避免线程阻塞

  • 高冲突场景（如链表修改）使用 synchronized 保证数据一致性

  • 混合机制减少上下文切换和自旋开销，提升并发性能

四、分段锁

分段锁怎么加锁的？

1. 底层实现

• 定位分段与锁对象

  • 键的哈希值经过两次散列运算

    • 第一次散列定位到具体的 Segment 分段（如 hash % concurrencyLevel，默认并发级别 16）

    • 第二次散列在 Segment 内部定位到具体的 HashEntry 桶（链表头节点位置）

  • 每个 Segment 继承自 ReentrantLock，包含独立的 HashEntry 数组和锁状态

• 获取分段锁流程

  • 写操作（如 put）调用 Segment.lock() 获取该分段的可重入锁

  • 不同分段的操作并行执行（如操作 Segment[0] 和 Segment[3] 互不阻塞）

  • 若分段被占用，当前线程阻塞直到锁释放

• 操作与释放锁

  • 加锁后在 Segment 的 HashEntry 链表中执行插入/删除/更新操作

  • 操作完成后调用 Segment.unlock() 释放锁，其他线程可竞争该锁

• 并发性能优势

  • 不同分段操作完全并行，仅同一分段内触发锁竞争

  • 读操作无锁，依赖 volatile 修饰的 HashEntry 字段（如 value）保证可见性

2. 可重入性

分段锁是可重入的吗？

• 实现

  • JDK 1.7 的 Segment 锁继承自 ReentrantLock，具备可重入特性

  • 内部维护计数器（state 变量）：同一线程多次获取锁时计数器递增，释放时递减，归零后释放资源

• 原理

  • 线程持有标记：ReentrantLock 记录当前持有锁的线程，同一线程重复获取时直接累加计数器

  • 释放规则：每次 lock() 必须对应一次 unlock()，否则锁无法完全释放

• 非可重入锁

  • 非可重入锁（如简单互斥锁）无法识别持有者，同一线程重复获取会死锁

  • 分段锁的可重入性避免此问题，支持递归或嵌套调用

• 实际意义

  • 避免死锁：例如 put 操作内部调用其他需加锁的逻辑时，线程可重入同一锁

  • 简化编程：无需避免同一线程的重复加锁行为，降低代码复杂度

五、HashMap vs HashTable

HashMap 和 HashTable 有什么不一样的？HashMap 一般怎么用？

1. 核心差异

• 线程安全

  • HashTable 所有方法使用 synchronized 修饰，性能低

  • HashMap 非线程安全，高并发下推荐 ConcurrentHashMap

• null 支持

  • HashTable 禁止 null 键/值，否则抛出异常

  • HashMap 允许一个 null 键和多个 null 值

• 继承结构

  • HashTable 继承 Dictionary 类（已过时）

  • HashMap 继承 AbstractMap，实现 Map 接口

• 性能与扩容

  • HashTable 初始容量 11，扩容公式为 旧容量 × 2 +1

  • HashMap 初始容量 16，翻倍扩容，哈希桶 + 链表/红黑树结构（JDK 1.8+）

• 迭代器

  • HashTable 使用 Enumerator，不支持快速失败

  • HashMap 使用 Iterator，支持快速失败机制

2. HashMap用法

• 基本操作

HashMap<String, Integer> map = new HashMap<>();
map.put("key", 100);      // 添加键值对
int value = map.get("key"); // 获取值
map.remove("key");        // 删除键值对

• 遍历方式

// entrySet() 遍历键值对
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// keySet() 或 values() 单独遍历键或值

• 嵌套结构

HashMap<String, HashMap<String, Integer>> nestedMap = new HashMap<>();
nestedMap.put("A", new HashMap<>()).put("B", 200);

• 性能优化

  • 初始化时预估容量：new HashMap<>(预期容量/0.75 +1)

  • 确保键对象正确实现 hashCode() 和 equals()

• 适用场景

  • 缓存系统（快速存取）

  • 配置管理（键值映射）

  • 数据统计（如词频统计）

3. 总结建议

• 单线程优先选择 HashMap，高并发用 ConcurrentHashMap

• 避免滥用 null 键/值，提高代码健壮性

• 合理初始化容量以减少扩容开销

六、synchronized vs CAS

已经用了 synchronized，为什么还要用 CAS 呢？

• 性能优化与场景适配

  • synchronized 的阻塞代价：线程获取不到锁时会阻塞，导致上下文切换和内核态切换，高并发下吞吐量下降

  • CAS 的无锁优势：在低冲突场景（如空桶插入）通过自旋重试避免阻塞，性能更高

• 锁粒度与并发效率

  • synchronized 的粗粒度问题：锁定整个对象或代码块，强制串行化所有操作

  • CAS 的细粒度控制：针对单个变量原子操作（如 AtomicInteger 计数更新），不影响其他变量或操作

• 功能互补性

  • CAS 的局限性：无法处理复杂逻辑（如链表遍历+修改）或多变量操作，需 synchronized 保证结构一致性

  • synchronized 的优化：Java 1.6 后引入偏向锁、轻量级锁，但 CAS 可减少锁升级概率

• 混合锁机制的实践

  • 协同使用场景：

    • 低冲突优先 CAS（如空桶插入）

    • 高冲突退化为 synchronized（如链表/红黑树修改）

    • 设计哲学：乐观并发控制（CAS）与悲观锁（synchronized）结合，平衡性能与一致性

七、HashMap & HashTable & ConcurrentHashMap

• 线程安全与锁机制

  • HashTable：使用 synchronized 锁所有方法，锁粒度粗（整表锁定），多线程性能差

  • HashMap：非线程安全，单线程性能最优，多线程操作可能导致数据不一致或死循环

  • ConcurrentHashMap：JDK 1.7 分段锁，JDK 1.8 CAS + synchronized 细粒度锁（锁定单个桶或链表节点），高并发性能优

• null 键值支持

  • HashTable：禁止 null 键/值，插入 null 抛出 NullPointerException

  • HashMap：允许一个 null 键和多个 null 值

  • ConcurrentHashMap：禁止 null 键/值，避免并发下语义歧义（如无法区分“键不存在”与“值为 null”）

• 性能对比

  • 单线程：HashMap > ConcurrentHashMap > HashTable

  • 多线程：ConcurrentHashMap 无锁读 + 细粒度写锁，性能远高于 HashTable

• 数据结构与冲突处理

  • HashTable：数组 + 链表，无红黑树优化，冲突链表可能过长

  • HashMap：JDK 1.8+ 数组 + 链表/红黑树（链表长度 ≥8 且数组容量 ≥64 时树化）

  • ConcurrentHashMap：同 HashMap，但线程安全机制保证并发操作

• 迭代器行为

  • HashTable：强一致性，迭代时修改抛 ConcurrentModificationException

  • HashMap：fail-fast 快速失败，多线程修改可能抛异常

  • ConcurrentHashMap：弱一致性，允许迭代期间修改，不保证实时数据

• 适用场景

  • HashTable：已过时，仅用于遗留系统或低并发场景

  • HashMap：单线程场景（如本地缓存、配置存储）

  • ConcurrentHashMap：高并发场景（如分布式缓存、计数器）