- 正确答案：HashMap 是基于哈希表实现的键值对存储结构，其底层使用数组 + 链表（或红黑树）来解决哈希冲突。HashMap 不是线程安全的。在多线程环境下，推荐使用 ConcurrentHashMap，它通过分段锁（JDK 1.7）或 CAS + synchronized（JDK 1.8 及以后）实现线程安全。 - 解答思路：要回答这个问题，需要从三个层面展开：第一，HashMap 的存储结构和工作原理；第二，为什么 HashMap 不是线程安全的；第三，ConcurrentHashMap 如何在保证性能的同时实现线程安全。重点在于理解底层数据结构、哈希冲突处理、扩容机制以及并发控制策略。 - 深度知识讲解： 1. HashMap 原理： - 底层结构：HashMap 在 JDK 1.8 中采用“数组 + 链表 + 红黑树”结构。 - 数组：Node[] table，初始容量为 16，负载因子为 0.75。 - 链表：当多个键的哈希值映射到同一个数组索引时，使用链表连接这些键值对（称为“拉链法”）。 - 红黑树：当链表长度超过 8 且数组长度大于等于 64 时，链表会转换为红黑树，以提高查找效率（O(log n)）。 - 哈希函数：通过 (key == null ? 0 : hash(key)) 计算 hash 值，然后通过 (n - 1) & hash 确定数组下标（n 是数组长度，必须是 2 的幂）。 - 扩容机制：当元素数量超过 threshold（capacity * loadFactor）时，触发扩容，容量翻倍。扩容时会重新计算每个元素的位置，可能导致链表重组。 - put 操作流程： 1. 计算 key 的 hash 值； 2. 根据 hash 找到对应的桶（数组索引）； 3. 如果桶为空，直接插入； 4. 否则遍历链表或红黑树，若 key 已存在则更新 value； 5. 若不存在，则插入新节点，并判断是否需要转为红黑树； 6. 检查是否需要扩容。 - get 操作流程： 1. 计算 hash； 2. 定位到桶； 3. 遍历链表或红黑树查找对应 key。 - 代码示意（简化版 Node 结构）： ``` static class Node implements Map.Entry { final int hash; final K key; V value; Node next; // 构造函数等 } ``` 2. HashMap 是否线程安全？ - 不是线程安全的。主要原因如下： - 多线程同时 put 可能导致链表成环（JDK 1.7 头插法问题），在 get 时造成死循环； - 扩容过程中多个线程同时操作可能导致数据丢失或覆盖； - 没有同步机制保护临界资源（如 modCount、table 等）； - fail-fast 机制：迭代过程中如果其他线程修改了 map，会抛出 ConcurrentModificationException。 - 示例场景：两个线程同时执行 put，都发现需要扩容，各自执行 resize，导致引用混乱。 3. ConcurrentHashMap 原理（以 JDK 1.8 为例）： - 目标：在保证线程安全的前提下，尽量减少锁竞争，提高并发性能。 - 实现方式：采用“CAS + synchronized”机制，而不是全局锁或分段锁（JDK 1.7 使用的是 ReentrantLock 分段锁）。 - 底层结构：与 HashMap 类似，也是数组 + 链表 + 红黑树。 - 关键设计： - volatile 修饰的 table 数组，保证可见性； - 第一个节点（头节点）作为锁对象：当需要向某个桶插入数据时，对该桶的头节点使用 synchronized 加锁； - 使用 CAS 操作进行一些无锁更新（如 sizeCtl 控制初始化和扩容状态）； - 扩容是渐进式的，支持多线程协助扩容（transfer 方法中使用 advance 和 finishing 标志协调）； - put 流程（JDK 1.8）： 1. 计算 hash； 2. 如果 table 为空，先初始化（通过 CAS 设置 sizeCtl）； 3. 定位到桶，如果桶为空，使用 CAS 插入； 4. 如果桶正在扩容（f.hash == MOVED），则当前线程协助扩容； 5. 否则对头节点加 synchronized 锁，插入或更新； 6. 插入后判断是否需要转为红黑树； 7. 更新元素数量，必要时触发扩容。 - 读操作（get）完全无锁： - 因为节点的 val 和 next 都是 volatile 的，保证可见性； - get 只是遍历链表或树，不修改结构，所以不需要加锁。 - 代码示意（简化逻辑）： ``` 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(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null, new Node(hash, key, value))) 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); 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; } ``` - 扩展知识点： - sizeCtl：控制初始化和扩容的 volatile 变量。-1 表示正在初始化，-N 表示有 N-1 个线程在扩容。 - transferIndex：用于多线程分配扩容任务的索引。 - ForwardingNode：标记某个桶已迁移，在扩容期间使用，其 hash 值为 MOVED（-1）。 4. 对比总结： | 特性 | HashMap | ConcurrentHashMap | |---------------------|------------------------|----------------------------| | 线程安全 | 否 | 是 | | 实现机制 | 无同步 | CAS + synchronized | | 锁粒度 | 无 | 桶级锁（头节点锁） | | 扩容方式 | 单线程 | 支持多线程协助扩容 | | 性能 | 高（无锁） | 较高（低竞争） | | 迭代器 | fail-fast | weakly consistent（弱一致）| - weakly consistent 迭代器：允许在遍历时发生修改，不会抛异常，但不保证反映最新的修改。 - 扩展知识： - 为什么 ConcurrentHashMap 不允许 null 键或 null 值？因为 null 值无法区分是 key 不存在还是 value 为 null，在并发环境下容易产生歧义（如 get 返回 null 时无法判断是没找到还是值为 null）。而 HashMap 允许 null 键（只有一个）和 null 值。 - JDK 1.7 与 JDK 1.8 的区别： - 1.7 使用 Segment 分段锁，每个 Segment 是一个 ReentrantLock + HashEntry 数组； - 1.8 改为更细粒度的 synchronized 锁单个桶，性能更好，代码更简洁。 - 替代方案： - Collections.synchronizedMap(new HashMap<>())：全局锁，性能差； - 使用 ConcurrentSkipListMap：基于跳表，支持排序，但插入性能低于 ConcurrentHashMap。综上，HashMap 基于哈希表实现，非线程安全；ConcurrentHashMap 通过 CAS 和 synchronized 实现高效并发控制，是高并发场景下的首选。

小米面经

全站热榜

创作者周榜