"/>
侧边栏壁纸
博主头像
PySuper 博主等级

千里之行,始于足下

  • 累计撰写 286 篇文章
  • 累计创建 17 个标签
  • 累计收到 2 条评论

目 录CONTENT

文章目录

Java Map

PySuper
2022-10-17 / 0 评论 / 0 点赞 / 15 阅读 / 0 字
温馨提示:
所有牛逼的人都有一段苦逼的岁月。 但是你只要像SB一样去坚持,终将牛逼!!! ✊✊✊

一、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:高并发场景(如分布式缓存、计数器)

0
  1. 支付宝打赏

    qrcode alipay
  2. 微信打赏

    qrcode weixin

评论区