做 Java 开发的集合框架应该算是最常用也最容易被低估的基本功。日常业务代码里天天和 HashMap、ArrayList 打交道可真要问一句“底层到底是怎么实现的为什么并发下老是出事”能讲清楚的开发者并不多。尤其一遇到多线程场景从数据丢失到 CPU 飙高踩完一个坑又踩一个坑根因往往都藏在集合的实现细节里。这篇文章围绕 HashMap、ArrayList 这两个主力容器把底层结构、扩容逻辑、线程安全方案一次讲透并附上可以直接运行的实战代码。无论你是准备面试需要把底层原理说得有底气还是写代码时被并发修改、扩容性能问题折腾过这篇内容都值得从头看到尾。1. 集合框架的全局认知与选型思路很多初学者学集合第一反应是背“List 有序可重复Set 无序不可重复Map 键值对”。这种记忆不能说错但太粗了实际选型时根本不够用。我更愿意把整个集合框架当成一张地图先搞清楚接口层的两条主线再看每个实现类的数据结构特点最后结合自己的业务场景做选择。顺序不对后面代码就容易写得别扭。1.1 两条主线Collection 与 Map集合框架最上层有两大核心接口Collection 和 Map。Collection 用于存放一组单一元素往下又分为 List、Set、Queue 三个方向Map 则用于存放键值映射一个 key 对应一个 value。接口特点常用实现类List有序、允许重复、可通过索引访问ArrayList、LinkedList、VectorSet不允许重复侧重去重HashSet、LinkedHashSet、TreeSetQueue队列结构用于排队处理ArrayDeque、LinkedList、PriorityQueueMap键值映射key 唯一HashMap、LinkedHashMap、TreeMap、ConcurrentHashMapList 底层可以基于数组也可以基于链表Set 和 Map 在很多实现里其实是“同宗同源”的HashSet 内部就是包装了一个 HashMap只是让所有 value 都指向同一个空对象。搞懂这一层你就明白了为什么 HashSet 的元素不可重复因为 HashMap 的 key 天然不可重复。接口层的价值在于面向抽象编程。写代码时尽量声明为ListString、MapString, Object这样的接口类型而不是直接写死成ArrayList或HashMap。这样一来后续如果需要从 ArrayList 换成 LinkedList或者用并发容器替换普通容器改动范围被限制住代码的弹性会好很多。1.2 不同场景下怎么选别靠感觉靠数据特征选型听起来简单实际工作中经常能看到“什么都是 ArrayList、什么都是 HashMap”的写法。选错了容器轻则性能难看重则线上事故。我有几个比较固定的判断维度读多写少且需要随机访问用 ArrayList。底层是连续数组按下标访问能做到 O(1)CPU 缓存命中率也比链表高。频繁在头部或中间插入、删除从理论上看 LinkedList 合适但现实很复杂。ArrayList 的元素移动是 System.arraycopy 这种 native 方法在小批量数据上并不慢LinkedList 每个节点还要额外维护前后指针内存占用高遍历时缓存命中率很差。所以我的习惯是除非数据量极大且插入删除确实发生在头部否则默认还是 ArrayList。需要去重用 HashSet或者需要保持插入顺序就用 LinkedHashSet。Key-Value 读写优先 HashMap。如果要求遍历时按 key 顺序则用 TreeMap如果要求按插入顺序遍历则用 LinkedHashMap。线程安全的 Map直接选 ConcurrentHashMap而不是往 HashMap 外面包一层 synchronizedMap更不应该用 Hashtable。选型不是炫技而是对数据本身特性的尊重。你在写集合代码前先问自己三个问题数据量大不大是读多还是写多要不要保证顺序答案理顺了容器基本就定下来了。2. HashMap你每天都在用的底层引擎HashMap 是面试里的“钉子户”也是线上并发事故的高发区。这一节我把它从存储结构到扩容机制拆开揉碎地讲重点放在 Java 8 之后的实现上。2.1 数组链表红黑树HashMap 的存储形态HashMap 的核心是一个NodeK,V[] table数组。每个元素要么是 null要么是一个单链表的头节点要么是一棵红黑树的根节点。put 一个键值对时流程是这样的根据 key 计算 hash 值。通过(table.length - 1) hash计算出桶下标。如果桶为空直接放入新节点。如果桶不为空遍历链表逐个比较 key 的 hashCode 和 equals。如果找到相同 key覆盖旧 value 并返回旧 value。没有找到相同 key则把新节点加入链表尾部如果链表长度达到阈值再考虑树化。插入完成后如果size threshold触发扩容。为什么要引入链表因为不同 key 完全可能算出相同的桶下标这就是 hash 冲突。在冲突不严重时链表很短增删查的代价可控但一旦某个桶挂了几百个节点查询就退化成 O(n)性能没法看。所以 Java 8 引入了红黑树当链表长度达到 8 且数组容量达到 64 时链表转成红黑树查询复杂度从 O(n) 降到 O(log n)。这里有一个很容易被忽略的细节树化不是只看链表长度还要求数组长度不小于 64。如果数组长度不到 64哪怕某个桶里已经链了 8 个节点HashMap 也不会立刻树化而是先扩容。因为扩容后 hash 分布通常会变散链表长度自然缩短。这个设计很聪明避免在小数组上过早引入更复杂的数据结构。2.2 hash 扰动与容量为什么是 2 的幂HashMap 的 hash 计算并不是直接用key.hashCode()而是先拿到 hashCode再做一次扰动static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }h 16是把高 16 位“挪”到低 16 位再和原来的低 16 位做异或。这样做的目的是让高位的差异也能参与到低位运算中从而在计算桶下标时降低冲突概率。毕竟实际参与数组下标计算的只有低位部分如果 hashCode 的低位分布不均扰动操作至少能让结果更随机一些。桶下标的计算公式是(n - 1) hash而不是hash % n。位运算比取模快得多而前提条件就是n必须是 2 的幂。你回想一下默认容量是 16扩容是翻倍到 32、64、128永远都是 2 的幂这不是偶然是为位运算铺路。当容量从 16 扩容到 32 时参与计算的掩码从15 (1111)变成31 (11111)相当于多了一位。一个旧节点在新数组中的下标就两种可能要么待在原下标index要么跑到index oldCap。这一位恰好对应旧容量最高位的那个 bithash 的第 5 位因为 16 是 2 的 4 次方。这一特性就是 Java 8 扩容时“不需要重新计算 hash”的底层依据。2.3 扩容 resize 的完整过程与源码关键逻辑默认容量 16加载因子 0.75那么 threshold扩容阈值等于 12。也就是说当元素个数超过 12 时HashMap 就把数组扩大到原来的 2 倍并重新组织所有节点。在 Java 8 中扩容迁移旧数据并不是全部重新计算 index而是通过一个非常巧妙的位运算把链表拆成两条if ((e.hash oldCap) 0) { // 节点留在低位原索引位置 } else { // 节点移动到高位原索引 oldCap }为什么e.hash oldCap能决定位置因为 oldCap 是 2 的幂二进制高位是 1其余位是 0hash 在这一位上如果是 0新数组的该位也是 0下标不变如果是 1新数组下标就多了 oldCap。这里的核心逻辑在 Java 8 源码的split方法里体现得很明显建议你亲自去读一遍比背注释有用得多。这里补充一个很多人容易忽略的点加载因子为什么是 0.75而不是 0.5 或者 1.0这是一个时间和空间的折中。加载因子太高比如 1.0意味着数组要装到很满才扩容空间利用率高但冲突概率大增链表变长查询性能下降加载因子太低比如 0.5冲突少但空间浪费严重。0.75 在多数实际场景下是经验上的平衡点这也是为什么它被大量 Java 项目沿用至今。2.4 高并发下为什么不能直接用 HashMap这个问题值得单独开一节讲因为很多人直到线上出了事故才真正理解。HashMap 本身不是线程安全的容器并发 put 时会出各种幺蛾子。Java 7 时代扩容采用头插法多个线程同时扩容时链表可能形成环。某个线程读 key 时会沿着环形链表永远转下去CPU 直接飙到 100%服务卡死。Java 8 把插入改成尾插法环形链表的场景基本消失了但并发数据丢失的问题依旧存在。举个真实场景两个线程同时判断某个桶为空然后都往这个桶写入节点。后写入的节点会直接覆盖前一个节点前一个 put 的数据就此消失而且没有任何异常提示。另外HashMap 的 size 计数在多线程下也不可靠size不是原子操作并发时统计值和实际元素个数对不上。我的建议很直接只要 Map 可能被多线程写哪怕是低概率并发也不要裸用 HashMap。换个 ConcurrentHashMap 的成本几乎为零而事故后的排查成本高得吓人。3. ArrayList 底层与扩容机制ArrayList 看起来比 HashMap 简单底层就是一个 Object[]但很多细节依然能挖出大量问题。面试官最喜欢的几个点基本都集中在扩容系数、modCount、遍历删除这几个地方。3.1 Object[] 数组与懒加载new ArrayList()创建一个空的 ArrayList内部使用的静态空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA容量为 0。第一次 add 元素时才把数组扩容到默认容量 10。这就是所谓的懒加载策略。如果你知道大概会有多少数据却直接用了无参构造前几次 add 必然触发扩容。数据量小时无所谓数据量大时扩容和数组拷贝的开销会被放大。更稳妥的写法是给一个合理的初始容量ListString list new ArrayList(2000);这个细节虽小但在高吞吐的后端服务里少一次扩容就少一次 O(n) 的数组拷贝积少成多效果很明显。3.2 扩容规则与背后的权衡ArrayList 的 add 方法会先调用ensureCapacityInternal确保内部容量够用不够就扩容。核心扩容逻辑是int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1);也就是每次扩容到原来的 1.5 倍。比如容量从 10 扩到 15再扩到 22而不是直接翻倍。为什么是 1.5 倍而不是 2 倍如果翻倍空间浪费会更明显1.5 倍在“减少扩容次数”和“避免浪费空间”之间取了中间值均摊下来单次 add 的时间复杂度依然是 O(1)。数组扩容时元素需要整体迁移这个过程依赖System.arraycopy这是一个 native 方法底层有内存拷贝优化速度很快。但千万记住它仍然是 O(n) 操作在数据量达到百万级别时每次扩容都可能带来毫秒级停顿。如果业务数据量可以预估就应该在构造时传初始容量或者调用ensureCapacity手动指定这是操作成本最低、收益最明显的优化手段。3.3 modCount 与快速失败机制ArrayList 内部维护一个modCount字段表示结构性修改次数。所谓结构性修改是指改变集合大小、添加删除元素这类操作而不是简单的替换元素。迭代器在创建时会记录modCount每次调用 next 之前都会检查当前modCount和预期值是否一致。不一致就抛出ConcurrentModificationException。这就是快速失败机制宁可尽快暴露并发问题也不让你带着隐患往下算。下面这段代码就是一个经典踩坑点ListInteger list new ArrayList(Arrays.asList(1, 2, 3)); for (Integer i : list) { if (i 2) { list.remove(i); } }运行时大概率会抛 ConcurrentModificationException因为增强 for 背后的迭代器发现modCount变了。正确的做法是使用 Iterator.remove()IteratorInteger it list.iterator(); while (it.hasNext()) { Integer i it.next(); if (i 2) { it.remove(); } }或者直接使用 Java 8 提供的removeIf简洁且安全list.removeIf(i - i 2);需要明白的是快速失败机制并不保证并发安全它只是在错误发生时尽早暴露问题。真正的并发遍历还得靠后面要讲的并发容器。3.4 ArrayList 的性能画像ArrayList 的访问是 O(1)尾部插入均摊是 O(1)头部或中间插入是 O(n)因为需要移动后续元素。从内存角度看ArrayList 是连续内存遍历时能充分利用 CPU 缓存行预读所以在绝大多数遍历场景下比 LinkedList 快。我见过不少团队在做“中间插入很多”的功能时想当然地选了 LinkedList。实际压测之后发现问题依旧甚至更慢。LinkedList 虽然理论插入复杂度是 O(1)但前提是你已经拿到了目标位置的节点而现实中你要先遍历到那个位置这个过程本身就是 O(n)再加上节点对象分散在内存各处缓存命中率低性能自然不占优。所以我的结论是80% 的列表场景ArrayList 都是更稳的选择。LinkedList 更适合的是“已知节点引用、频繁删除插入”这类特殊场景日常业务很少用得到。4. 线程安全方案从包装器到分段思想集合的线程安全是个老话题。JDK 早期提供了 Hashtable 和 Vector它们直接在方法上加 synchronized简单粗暴但全局锁竞争严重。后来出现了同步包装器、并发集合再到 ConcurrentHashMap 引入分段锁和 CAS一路演进到今天每种方案都有自己的适用边界。4.1 同步包装器Collections.synchronizedXXXCollections.synchronizedMap(map)会返回一个线程安全的 Map 包装类内部用一个互斥锁保护所有方法。它的实现思路很朴素每个方法都加 synchronized。MapString, String safeMap Collections.synchronizedMap(new HashMap());但这个方案有几个隐藏问题。第一锁的粒度是整张表所有线程操作同一个 Map 时都要竞争同一把锁并发一高就退化成串行执行。第二迭代时依然需要外部加锁否则在迭代过程中发生结构性修改还是会抛 ConcurrentModificationExceptionsynchronized (safeMap) { for (String key : safeMap.keySet()) { // 遍历逻辑 } }同步包装器更适合小型项目、并发量低、逻辑简单、迁移成本要小的场景。如果追求高并发还是建议用正统的并发容器。4.2 CopyOnWrite 系列读多写少的银弹CopyOnWriteArrayList 的设计思路非常独特每次写入都复制一份全新的底层数组写操作在副本上进行完成后用新数组替换旧数组引用。由于读操作始终面向不可变的旧数组读和读之间、读和写之间都不需要互相加锁。这带来两个明显优势读操作无锁性能极高。迭代器遍历的是“快照数组”即使其他线程正在增删元素迭代器也不会抛 ConcurrentModificationException。代价也很明显每次 add、remove 都要复制整个数组写入成本非常高。如果业务是写多读少用 CopyOnWriteArrayList 会把大量 CPU 花在数组复制上得不偿失。典型的适用场景是读远多于写比如应用启动时加载一份配置列表或白名单列表之后只偶尔更新而所有请求线程都要频繁读取遍历。我用它存过规则名单效果非常理想。CopyOnWriteArraySet 也是类似原理内部其实就是一个 CopyOnWriteArrayList专门用于“读多写少且需要去重”的场景。4.3 ConcurrentHashMap 源码级拆解ConcurrentHashMap 是并发场景下 Map 的首选也是并发容器里技术含量最高、最值得深入研究的一个。Java 8 之前的 ConcurrentHashMap 采用分段锁把数据分成一段一段的 Segment每段拥有一把锁。不同的线程如果访问不同段的数据可以并行执行锁竞争被大大分散。Java 8 之后分段锁被放弃实现改为 CAS synchronized锁粒度细到“单个桶的首节点”。put 的核心逻辑可以概括为如果 key 或 value 为 null直接抛出 NullPointerException这一点和 HashMap 不同HashMap 允许 null key。如果目标桶为空使用 CAS 原子性地把新节点放入桶中整个过程不加锁。如果目标桶非空就对桶的首节点加 synchronized 锁然后继续处理。锁的粒度从整表缩小到单个桶不同桶之间的写操作可以并行。如果当前链表过长且数组容量满足条件链表会转成红黑树。写入完成后会通过 baseCount 或 CounterCell 累加元素数量。读操作则完全无锁。关键点在内存可见性安排table 数组被 volatile 修饰Node 节点的 val 和 next 也是 volatile。通过 volatile 的写-读建立 happen-before 关系读线程无需加锁即可看到最新的安全发布内容。如果你在并发场景下需要统计每个 key 的访问次数ConcurrentHashMap 提供了非常顺手的 APIConcurrentHashMapString, LongAdder counter new ConcurrentHashMap(); counter.computeIfAbsent(login, k - new LongAdder()).increment();这里用 LongAdder 而不是 AtomicLong是因为 LongAdder 内部通过多个 Cell 分散计数高并发写同一个 key 时竞争更小吞吐更高。这些都是实战中体会得到的差距。4.4 三种方案到底怎么选很多人搞不清楚 synchronziedMap、CopyOnWrite、ConcurrentHashMap 之间的取舍我习惯用一个简单的三角判断维度Collections.synchronizedMapCopyOnWriteArrayListConcurrentHashMap锁粒度整表锁写锁加复制桶级锁 CAS读性能加锁一般无锁极高无锁高写性能一般差复制成本高好迭代行为弱一致需外部加锁快照式不抛异常弱一致基本不抛异常适用场景并发很低读多写少通用并发场景看到这里你应该能明白没有“万能线程安全集合”只有“当前场景最合适的集合”。选型之前先用数据说话。5. 实战可复现的并发丢数据实验理论讲得再多不如自己跑一段代码观察现象。这里分享两个可以直接复现的实验一个表演 HashMap 并发丢数据一个验证 ConcurrentHashMap 修复问题。5.1 用 HashMap 模拟并发丢数据写一个简单的多线程程序8 个线程同时向同一个 HashMap 写入 8 组 key 完全不同的数据每组 1000 个键值对。理论上最终 Map 大小应该是 8000因为每个线程写的是不同的 key不存在覆盖关系。public class HashMapConcurrencyDemo { public static void main(String[] args) throws InterruptedException { MapString, Integer map new HashMap(); int threads 8; ExecutorService pool Executors.newFixedThreadPool(threads); for (int t 0; t threads; t) { int threadIndex t; pool.submit(() - { for (int i 0; i 1000; i) { map.put(thread- threadIndex -key- i, i); } }); } pool.shutdown(); pool.awaitTermination(1, TimeUnit.MINUTES); System.out.println(map size map.size()); } }跑几次你会发现 map.size() 几乎不会等于 8000通常是 7000 多有时甚至更少。这些线程写的 key 明明各不相同数据却平白无故地消失了。原因就是前面讲的两个线程同时拿到同一个空桶一个 put另一个 put后者覆盖前者或者扩容时相互干扰迁移过程中旧链接新链交错数据被无意丢弃。这就是并发 HashMap 最危险的地方不报错不崩溃就是数据凭空消失排查起来非常头疼。5.2 改造为 ConcurrentHashMap 后的正确结果把上面的代码中new HashMap()换成new ConcurrentHashMap()其他代码完全不动map.size() 在多次运行后都稳定等于 8000。这就是并发容器存在的意义不靠运气靠机制保证安全。在此基础上我们还可以扩展成一个简单的访问计数器。假设需要统计不同用户的请求次数直接用一个 ConcurrentHashMap LongAdder 就能在并发环境下安全累计public class ConcurrentCounterDemo { static ConcurrentHashMapString, LongAdder counter new ConcurrentHashMap(); public static void add(String user) { counter.computeIfAbsent(user, k - new LongAdder()).increment(); } public static long get(String user) { return counter.getOrDefault(user, new LongAdder()).sum(); } public static void main(String[] args) throws InterruptedException { ExecutorService pool Executors.newFixedThreadPool(16); for (int i 0; i 10000; i) { pool.submit(() - add(user- (i % 10))); } pool.shutdown(); pool.awaitTermination(1, TimeUnit.MINUTES); for (int i 0; i 10; i) { System.out.println(user- i count get(user- i)); } } }这种写法在热点 key 并发更新时远比单纯用 synchronized 锁住整个计数逻辑吞吐要高因为 LongAdder 把同一个 key 的竞争值分散到了多个内部 Cell 上减少原子操作失败重试的概率。5.3 从实验中提炼的工程经验我做完这些实验后最大的感受是很多并发问题不是“偶发”的而是只要压力足够大就一定会发生。你测试环境跑一次没事不代表线上每秒几万请求时也没事。HashMap 在并发下的丢失率会随线程数和写频率上升而显著提高这是机制决定的不是运气决定的。所以我在实际项目中有一个默认原则凡是会被多线程访问的 Map一律上 ConcurrentHashMap凡是会被多线程修改的 List优先评估 CopyOnWriteArrayList 或加锁方案。把这个原则当成默认习惯能省掉大量返工和线上事故排查时间。习惯的养成比记住某段源码重要得多。6. 高频问题与避坑指南集合框架相关的面试题和工程坑位往往高度重合。很多面试官喜欢问那几个数字因为数字背后代表的不只是记忆更是实现者对复杂度的思考。6.1 面试里那串数字怎么答我把 HashMap 的关键参数整理成一个速查表每一行都值得展开讲讲参数默认值含义默认初始容量16必须是 2 的幂加载因子0.75容量和冲突的折中扩容阈值capacity * loadFactor超过阈值自动扩容链表转红黑树8单桶链表长度阈值红黑树转会链表6避免树链表频繁切换最小树化容量64树化前数组容量的最低要求每次扩容倍数2保证按位与运算生效解释“为什么是 0.75”时可以用泊松分布来兜底。在加载因子接近 0.75 时桶中链表长度达到 8 的概率已经降到千万分之几足以说明这个取值在时间和空间上同时具备合理性。解释“为什么树化是 8、退化是 6”时关键在于一个缓冲带避免元素在链表和红黑树之间反复切换损耗性能。至于“为什么容量必须是 2 的幂”记住两点就够了。第一(n - 1) hash可以高效取模第二扩容时节点要么留在原位要么位移 oldCap分布均匀且省去重算 hash 的步骤。6.2 一个真实线上案例ArrayList 撑爆内存的排查思路有位同行开发者在群里分享过一个案例很能说明问题。他们有个内部支持系统需要把日志文件逐行读入内存再做关键字过滤和统计。最初的实现很朴素ListString lines new ArrayList(); while ((line reader.readLine()) ! null) { lines.add(line); } // 后续过滤、统计逻辑代码看起来没什么问题但单次日志文件达到几个 GB 时JVM 直接 OOM。排查的时候先用jmap -dump:formatb,fileheap.bin pid拿到堆转储再用 MAT 分析发现 ArrayList 内部持有的 char[] 占了堆内存的 80% 以上而且因为无参构造一路扩容数组从几百万规模翻到几千万规模中间还白白复制了很多次。修复方式也不复杂。读取前先快速估算行数构造 ArrayList 时直接指定初始容量int estimatedSize 2_000_000; ListString lines new ArrayList(estimatedSize);更进一步地如果能边读边处理就上流式处理不要让几 GB 都堆在内存里。这个案例的教训很朴素集合不是用来无限装数据的仓库它只是一个存储结构装多少数据、怎么装都需要结合数据规模做设计和预估。6.3 避免踩坑的几条实操建议最后整理几条我自己踩过坑之后沉淀下来的使用习惯比较杂但每条都是实打实的经验。其一不要用可变对象作为 HashMap 的 key。比如把一个对象放进 HashMap 后又修改了它的字段导致 hashCode 变化下次 get 时很可能就找不到了。正确的做法是用不可变对象或者包装成 String、Integer 这类稳定 key。其二遍历删除元素优先使用 Iterator.remove 或 Collection.removeIf不要直接用集合自身的 remove。原因前面已经说过了modCount 会变。其三并发场景下不要对 HashMap 抱有侥幸心理。无论是缓存还是临时统计只要有多线程写入的嫌疑就老老实实用 ConcurrentHashMap。其四容量预估永远比事后优化简单。ArrayList 和 HashMap 都能指定初始容量多写一个数字不增加多少代码量却能避免若干次扩容和 rehash尤其是数据量大的场景收益非常明显。这些习惯单独拿出来都很简单难的是在写每行代码时真正记在心里。我自己也曾因为一次 HashMap 并发丢失排查整整一天最后才发现问题出在新手都会犯的错误上。从那以后我对集合的选型和细节都多了一分敬畏也希望这篇内容能让你少走一些弯路把集合真正用明白。