- 正确答案：HashMap 是基于哈希表实现的键值对存储结构，采用数组+链表/红黑树的方式组织数据。它不是线程安全的，在多线程环境下可能引发数据不一致、死循环等问题。ConcurrentHashMap 是线程安全的哈希表实现，JDK 1.8 中使用 CAS + synchronized 实现并发控制，锁的粒度是桶（即数组中的单个节点），而不是整个表，从而提高了并发性能。 - 解答思路： 1. 首先说明 HashMap 的基本结构和工作原理。 2. 指出 HashMap 不是线程安全的原因及其在并发环境下的典型问题。 3. 转向 ConcurrentHashMap，解释其如何通过 CAS 和 synchronized 实现线程安全。 4. 明确锁的粒度从 JDK 1.7 的分段锁（Segment）演进到 JDK 1.8 的基于节点的细粒度锁。 5. 结合底层数据结构与并发机制，深入分析其实现细节。 - 深度知识讲解：一、HashMap 实现原理（JDK 1.8） HashMap 内部由一个 Node[] 数组构成，每个元素是一个链表头节点或红黑树根节点。当发生哈希冲突时，使用拉链法解决。核心字段： transient Node[] table; transient int size; int threshold; // 扩容阈值 final float loadFactor; // 负载因子，默认0.75 put 流程简述： 1. 计算 key 的 hash 值（高位参与运算，减少碰撞） 2. 根据 hash 找到数组下标 index = (n - 1) & hash 3. 若该位置为空，则直接插入 4. 否则遍历链表或红黑树插入新节点 5. 当链表长度 >= 8 且数组长度 >= 64 时，链表转为红黑树 6. 插入后判断是否需要扩容（size > threshold）代码示意（简化版）： ``` static class Node implements Map.Entry { final int hash; final K key; V value; Node next; } public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; return oldValue; } } ++modCount; if (++size > threshold) resize(); return null; } ``` 二、HashMap 是否线程安全？存在什么问题？答案：不是线程安全的。主要问题包括： 1. 并发 put 导致数据覆盖：多个线程同时执行 put，都检测到某个桶为空，各自创建节点写入，但只有一个会生效，造成数据丢失。 2. 扩容期间的死循环（JDK 1.7 特有）：在 JDK 1.7 中，扩容采用头插法迁移链表，多线程下可能导致链表成环，后续 get 操作陷入无限循环。示例场景（JDK 1.7）：线程 A 和 B 同时触发 resize() 原链表：A -> B -> C A 先暂停在 transfer 过程中 B 完整执行头插法，得到 C -> B -> A A 继续执行，将 B.next 指向自己……最终形成环注：JDK 1.8 改为尾插法，避免了此问题，但仍不保证线程安全。 3. 可见性问题：由于没有 volatile 或同步机制，一个线程修改的内容其他线程可能看不到。三、ConcurrentHashMap 实现原理（JDK 1.8）目标：在保证线程安全的同时尽可能提高并发性能。核心思想：降低锁粒度，只在必要时加锁。关键改进（相比 JDK 1.7 的 Segment 分段锁）： - 使用 CAS + synchronized 控制并发 - 锁的粒度细化到每一个桶（table[i]） - 利用 volatile 保证内存可见性重要字段： transient volatile Node[] table; private transient volatile int sizeCtl; // sizeCtl: // <0: 表示有线程正在进行初始化或扩容 // =0: 初始化时默认容量 // >0: 下一次扩容阈值 Node 节点定义增强： ``` static class Node implements Map.Entry { final int hash; final K key; volatile V val; // 值是 volatile，保证可见性 volatile Node next; // next 指针也是 volatile } ``` 特殊节点类型用于标识状态： - ForwardingNode：表示当前桶正在迁移中 - TreeBin：代理红黑树操作，内部加锁 - ReservationNode：占位符 put 操作流程（putVal 方法）： 1. 如果 table 为空，先初始化（通过 CAS 设置 sizeCtl） 2. 定位桶位置 i = (n - 1) & hash 3. 如果 table[i] == null，尝试用 CAS 插入新节点（无锁） 4. 如果 table[i] 不为空： a. 检查是否是 ForwardingNode（说明正在扩容），帮助迁移 b. 否则对该桶头节点加 synchronized 锁（锁的是第一个节点对象） c. 在同步块内插入链表或树节点代码逻辑伪代码表示： ``` final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node[] tab = table;;) { Node f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable(); // CAS 初始化 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 尝试无锁插入 if (casTabAt(tab, i, null, new Node(hash, key, value, null))) break; } else if ((fh = f.hash) == MOVED) // 正在迁移 tab = helpTransfer(tab, f); // 协助扩容 else { V oldVal = null; synchronized (f) { // 对该桶头节点加锁 if (tabAt(tab, i) == f) { if (fh >= 0) { // 普通链表 binCount = 1; for (Node e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node pred = e; if ((e = e.next) == null) { pred.next = new Node(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { // 红黑树 // ... } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); // 链表转树 if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; } ``` 四、CAS 和 synchronized 的作用 1. CAS（Compare-And-Swap）： - 用于无竞争场景下的原子操作 - 如初始化 table、插入空桶、修改 sizeCtl - 底层依赖 Unsafe 类的 compareAndSwapObject 等方法 - 乐观锁思想，失败则重试 2. synchronized： - 仅在桶非空且未迁移时才对头节点加锁 - 锁的是具体的 Node 对象，不是整个 table - 因为每次只锁一个桶，多个线程可以同时操作不同桶，极大提升并发度五、锁的粒度是什么？在 JDK 1.8 的 ConcurrentHashMap 中，**锁的粒度是桶级别（即数组中的每一个槽位）**。具体来说： - 每个 table[i] 的头节点作为 monitor 对象 - 多个线程访问不同的 bucket 可以并行执行 - 最大并发度理论上等于数组长度（实际受负载影响）例如： thread1 修改 table[0] thread2 修改 table[1] 两者互不影响，无需等待这比早期的 Hashtable（全表锁）和 JDK 1.7 的 ConcurrentHashMap（Segment 分段锁，默认16段）更加精细。六、扩展知识点 1. 扩容并发机制（transfer）： - 多个线程可协助扩容 - 使用步长控制迁移进度（stride） - 设置 ForwardingNode 标记已迁移的桶 2. size 控制： - 使用 CounterCell 类似 LongAdder 思想统计元素个数 - 避免多线程更新 baseCount 的竞争 - 最终 sum 所有 cell 值 + base 得到总大小 3. volatile 的作用： - 保证 table、node.next、node.val 的可见性 - 配合 CAS 实现无锁读操作（get 方法完全无锁） 4. get 方法为什么不需要加锁？ - 因为所有关键字段都是 volatile - 链表遍历过程中即使被修改也能正确读取最新值 - 读操作天然线程安全（前提是不能破坏结构一致性）总结对比： | 特性 | HashMap | ConcurrentHashMap | |--------------------|----------------------|----------------------------| | 线程安全 | 否 | 是 | | 实现方式 | 数组+链表/红黑树 | 数组+链表/红黑树 | | 并发控制 | 无 | CAS + synchronized | | 锁粒度 | 无锁 | 桶级锁（单个 node） | | 扩容方式 | 单线程扩容 | 多线程协助扩容 | | 读操作是否加锁 | 否 | 否（get 无锁） | | 是否允许 null 键值 | 是 | 否（防止歧义和 NPE） | 因此，ConcurrentHashMap 在保持高并发性能的同时提供了线程安全性，是多线程环境中推荐使用的 Map 实现。

字节后端一面凉经

全站热榜

创作者周榜