说实话Java集合框架大概是每个Java开发者最早接触、也最常被问崩的一坨代码。日常开发里我们用得最多的就是ArrayList、HashMap这几张牌但真把这些类的源码翻一遍把接口设计者为什么要拆成List、Set、Map三套体系想明白的并不多。我自己第一次完整读集合框架源码是在准备换工作那年之前是纯粹的API调用选手遇到需要去重的列表就new一个HashSet往里塞遇到线程安全的场景就条件反射地给整个HashMap加锁能跑就行。后来发现这种用法在工作三五年之后会成为明显的瓶颈因为很多线上性能问题、偶发的不一致问题根子都出在对集合框架底层的理解不够。这篇笔记就是我把整个集合框架从头梳理一遍的总结适合正要准备求职面试的同学也适合那些想把手里的开发工作从能跑提升到心里有数的工程师。我会从接口设计、核心实现、并发场景、性能选型几个角度去拆不堆概念尽量把每个关键设计背后的为什么讲透。1. 集合框架的顶层设计为什么要拆成两棵继承树1.1 两大根接口的分工Collection与Map各管什么很多初学者第一次看Java集合框架的继承关系图会下意识认为Map也是Collection的子接口其实完全不是。在JDK里集合框架的根接口一共就两个Collection和Map它们是两条独立的继承线。Collection管理的是一组元素而Map管理的是键值对映射这是两种完全不同的抽象维度。Collection下面又拆出List、Set、Queue三个子接口这三兄弟的边界非常清晰List有序、可重复像排队打饭的队列每个人都有明确的位置你站第几个是固定的而且允许两个人拿到同样的饭。Set不可重复像门禁系统的打卡记录同一张工卡一天只能记一次重复的打卡记录会被忽略。Queue也是有序的但强调的是先进先出或者按优先级出队它更关心谁下一个被处理而不是谁在哪一个下标。Map则单独走一条线每个元素是一对键值key在Map内唯一value可以重复。如果你把key看成是索引value是数据那Map就是一个可以按名字查内容的抽屉柜而不是按顺序排好的书架。这个设计的第一个好处是面向接口编程有了落点。你写一个业务方法时参数类型声明成Collection而不是具体ArrayList那么调用方传List、Set、Queue都没问题方法内部只依赖通用的size、iterator、stream这些能力。第二个好处是算法与数据结构分离。比如排序JDK里java.util.Collections.sort是给List接口用的你自己新写一个List实现类不用额外处理排序逻辑只要实现接口约定工具类就能帮你搞定。第三个好处是泛型把类型安全带进了集合里List 在编译期就能挡住把Integer塞进字符串列表这种低级错误这是早期Java版本里最让人头疼的问题。1.2 迭代器与快速失败机制集合框架里的迭代器Iterator是一个看起来很朴素、实际上很精巧的设计。它把怎么遍历和遍历什么解耦了不管底层是数组、链表还是红黑树你都可以用统一的hasNext()和next()去消费元素。这也是为什么增强for循环能够对任何Collection生效因为编译器最终会把它改成迭代器调用。但迭代器最有趣的地方是它的快速失败fail-fast机制。你肯定见过这个异常ConcurrentModificationException。它之所以存在是因为每个集合内部都有一个modCount字段这是一个结构性修改的计数器add、remove、clear这些改变元素数量的操作都会让它加一。当你创建迭代器时迭代器会把这个值记到自己的expectedModCount里之后每次调用next()都会检查一次如果集合的modCount变了说明存在某个线程在迭代过程中修改了集合结构迭代器立即抛异常而不是继续默默遍历产生不可预测的结果。为什么要这样设计想象一下你在遍历一个ArrayList的同时另一个线程在给它删除元素。如果不做任何保护遍历可能访问到null元素或者跳过一些元素甚至数组越界这些错误比一个明确的异常更难排查。快速失败本质上是宁可错杀不可放过的思想它不能保证100%检测到所有并发修改比如修改现有元素的值不会触发modCount变化但至少能在绝大多数非法操作发生时立刻止损。这种设计哲学贯穿了整个集合框架也是后面理解并发集合时的重要参照。2. 核心实现类源码级拆解2.1 ArrayList动态数组的扩容与随机访问ArrayList应该是工作量最大的一张牌。它的底层就是一段Object数组平时声明是Object[] elementData没有元素的时候这个数组是空的第一次调用add时才真正分配默认容量10这种懒加载避免了大量空集合白白占用内存。你往里面add元素时它先检查当前容量够不够不够就扩容新容量是旧容量的1.5倍对应代码是int newCapacity oldCapacity (oldCapacity 1)。为什么是1.5倍而不是直接翻倍这是空间和时间的取舍。扩到2倍确实可以减少扩容次数但扩容意味着老数组要整体拷贝到新数组也就是System.arraycopy那行代码一次拷贝的代价是O(n)。1.5倍让扩容次数更多一些但每次浪费的空间更少在长期运行的内存敏感型服务里能明显降低内存峰值。你可以自己推算一下从一个空ArrayList连续添加100万个元素1.5倍扩容总共需要约25次拷贝2倍扩容只需要约20次只差5次但1.5倍策略在平均内存占用上要节省不少。ArrayList按下标访问get(i)是O(1)因为连续数组天然支持随机访问CPU还能利用缓存预读相邻数据。但它也有硬伤中间插入和删除是O(n)因为需要把插入点后面的所有元素往后挪一位。我见过有人在循环里对ArrayList做头插10万条数据跑了几十秒这是典型的把ArrayList用成了LinkedList的姿势。如果你确定业务里要频繁在头部操作要么用LinkedList要么用ArrayDeque要么干脆倒序填充再反转。2.2 LinkedList每个节点多两个指针的代价LinkedList底层是一个双向链表每个元素被包装成Node节点每个Node里有prev、item、next三个字段分别指向前驱、自身数据、后继。头尾插入删除都是O(1)因为它只需要改几个指针引用不需要搬移数据。这个特性让它在某些场景下非常能打比如实现一个FIFO队列或者一个撤销历史栈。但LinkedList也有两个容易被人忽略的缺点。第一是按下标访问是O(n)JDK做了一点优化get(index)时会先比较index跟size的一半如果index小于size的一半就从头部往后找否则从尾部往前找这相当于把单链表遍历优化成了双向链表上的二分查找式遍历但宏观上仍然是O(n)。第二是内存开销很大每个节点多出两个指针理论上存储同样数量的元素LinkedList占用的内存是ArrayList的好几倍而且节点在堆里是离散分布的CPU缓存命中率低在数据量上来之后实际遍历性能可能反而不如ArrayList。我实测过10万条随机访问ArrayList平均比LinkedList快两个数量级以上这个差距不是理论值是真实体感。2.3 HashMap从哈希表到红黑树HashMap在JDK 8之后是数组链表红黑树三合一的结构。核心思路是先对key做哈希算出它应该落在哪个桶里。这里有个容易被忽略的细节如果不做任何处理直接用key.hashCode()去计算桶位置那么低位的碰撞概率会很大尤其当桶数量是2的幂次时key的哈希只有低位参与了索引计算。JDK的解决方式是扰动函数把哈希值的高16位异或到低16位上也就是这段代码h ^ (h 16)。这样即使两个key的哈希值只在高16位有差异也能在索引计算时体现出来整体分布更均匀。put流程可以总结成四步。第一步如果内部table为空先触发resize初始化。第二步根据(n - 1) hash定位到桶如果桶是空的直接newNode放入。第三步如果桶不为空分三种情况处理桶头节点的key和当前key完全相等hash相同且equals成立直接覆盖value桶头节点是TreeNode走红黑树的插入逻辑否则就是普通链表遍历找key找不到就在链表尾部追加节点这里特别要注意JDK 8改成了尾插法之前JDK 7用的是头插法头插法在高并发扩容时可能形成环形链表直接导致下一次get陷入死循环这个问题当时是很多线上事故的元凶。第四步插入完成后size加一检查size是否超过threshold超过就触发扩容。另外还有一个分支链表长度超过8时会调用treeifyBin尝试把链表转成红黑树但如果此时整个Map的容量还不到64它会先扩容而不是直接树化这个设计的原因是桶少的时候扩容比树化效果更好。get流程就简单多了同样先算hash定位桶桶头节点直接命中就返回否则看是不是树节点是树就走红黑树查找不是就遍历链表。整个平均复杂度是O(1)但在哈希函数很差导致大量碰撞时最坏会退化到O(logn)树化后或者O(n)树化前。2.4 HashSet、TreeMap被低估的马甲与有序表很多人用HashSet时不知道它内部其实就是一个HashMap。你new一个HashSet的时候实际上new了一个HashMap你add进来的元素被当作key放进Map里value是一个固定的占位对象private static final Object PRESENT。这意味着HashSet的去重能力完全建立在HashMap的key唯一性上而HashMap的key唯一性又取决于hashCode和equals。所以如果你自定义对象放入HashSet却不重写这两个方法就会出现明明内容相同却被当成两个元素的情况这个坑我在第5节会细说。TreeMap则是另一种思路它不再依赖哈希而是用红黑树维护有序性。每个插入的key都会跟已有节点比较按照自然顺序或者你传入的Comparator排好位置因此整个Map始终保持有序。它支持subMap、headMap、tailMap这类范围查询也支持floorKey、ceilingKey这种找最接近的键的操作非常适合做日程安排、区间匹配这类业务。TreeSet和TreeMap的关系跟HashSet与HashMap的关系一样内部包了一层TreeMap。代价是插入和查找都是O(logn)比HashMap的O(1)慢一点但保持在可接受范围。2.5 LinkedHashMap插入序、访问序与LRULinkedHashMap平时存在感不高但它在某些场景里是神器。它是在HashMap基础上增加了一条双向链表来维护元素顺序可以按插入顺序迭代也可以按访问顺序迭代。构造函数的第三个参数accessOrder设为true时每次get一个元素都会把它移动到链表尾部这样链表头就是最久没被访问的元素——这就是LRU缓存的经典实现基础。很多本地缓存框架内部就是直接基于LinkedHashMap重写removeEldestEntry来实现容量限制的不需要额外引入任何第三方的缓存组件。不过需要注意LinkedHashMap不是线程安全的多线程环境使用时要配合外部锁。3. 并发场景下的集合正确打开方式3.1 高并发下HashMap的三宗罪我在第2节提过JDK 7的HashMap在并发扩容时会形成环形链表导致get死循环CPU直接打满。这个问题在JDK 8通过尾插法和更稳健的扩容逻辑修复了但并发问题并没有根除。就算用JDK 8并发put的时候两个线程同时命中了同一个空桶各自newNode然后塞进去就会发生数据覆盖一个key的value被另一个线程的值覆盖掉。还有一个更隐蔽的问题size字段不是原子的线程A读了size100线程B同时put了10个元素A做判断时看到的可能还是100甚至读到中间状态导致后续扩容或者条件判断出错。所以并发下用HashMap加锁这个方案其实很难用对你锁put不一定锁住get锁住get不一定锁住迭代总会漏掉某个入口。正确做法是直接用专门为并发设计的集合类而不是自己给HashMap打补丁。3.2 ConcurrentHashMap锁细化到桶JDK 8的ConcurrentHashMap放弃了JDK 7里基于Segment分段锁的设计改成CAS synchronized的组合策略。get全程无锁因为Node数组和Node的val都被声明为volatile写线程对可见性的保证足够让读线程安全拿到最新值。put时如果目标桶是空的就一次性用CAS把节点放进去失败就自旋重试如果桶已经有节点了就对桶头节点加synchronized锁再执行插入逻辑如果检测到桶头节点是ForwardingNodehash值为-1的标记节点说明此时有其他线程正在扩容当前线程会主动加入帮忙迁移数据。这个设计的精妙之处在于锁的粒度从段细化到了单个桶两个线程只要写不同的桶就完全不会互相阻塞。size()方法也不是一个简单的计数器而是通过baseCount加上CounterCell数组来统计在高并发写入时也不会因为全局竞争导致性能雪崩但代价是返回的size不一定是一个绝对一致的实时快照。迭代器的语义也变了它是弱一致性的迭代过程中别的线程修改集合不会抛出ConcurrentModificationException迭代器看到的内容可能已经不是最新状态但不会崩溃。这一点在使用时需要心里有数不要拿它跟普通HashMap的迭代语义做同样的假设。3.3 CopyOnWriteArrayList读写分离的另类实现CopyOnWriteArrayList的思路极其简单粗暴所有写操作add、remove、set先拿到一把全局锁然后把底层数组完整复制一份在副本上修改修改完再整体替换原数组引用读操作不加锁直接读原数组。因为数组引用是volatile的写线程替换引用后读线程下一次访问就能看到新数据。它最大的优点是读读、读写都不互相阻塞读操作性能极高最大的缺点是每次写都要全量复制数组写操作O(n)开销如果写频繁内存和CPU都扛不住。所以它只适合那种读极多、写极少的场景典型应用是配置白名单、敏感词过滤列表这类几乎不变的数据。我见过一个误用案例一个订单状态流转表用CopyOnWriteArrayList实现业务每秒钟要更新几十次结果GC压力暴涨后来换成ConcurrentHashMap按订单号分桶才解决。写多读少的场景用它就是灾难。线程安全的Set则有个简单技巧java.util.concurrent.ConcurrentHashMap.newKeySet()可以创建一个线程安全的Set底层就是空值版的ConcurrentHashMap去重和并发都兼顾了。4. 复杂度、内存与选型一张表看清各实现类的差别4.1 各实现类的时间复杂度全景对比聊了这么多原理最终还是要落到选型。我先整理一张我自己经常看的对比表把常用集合类的核心指标放在一起实现类查找插入/删除有序性线程安全典型内存开销ArrayList按下标O(1)按值O(n)尾部O(1)均摊中间O(n)按插入序否低连续数组LinkedListO(n)头尾O(1)中间O(n)按插入序否高节点加双指针HashSetO(1)平均O(1)平均无否中哈希桶加节点TreeSetO(logn)O(logn)按比较器排序否中高红黑树节点LinkedHashSetO(1)平均O(1)平均按插入序/访问序否中高额外链表指针HashMapO(1)平均O(1)平均无否中桶加节点TreeMapO(logn)O(logn)按key排序否中高红黑树节点LinkedHashMapO(1)平均O(1)平均按插入序/访问序否中高额外链表指针ConcurrentHashMapO(1)平均O(1)平均无是中桶加节点加CounterCellCopyOnWriteArrayList遍历O(n)写O(n)读O(1)快照按插入序是高写时全量复制注意这个表的平均两个字。哈希类集合的最坏情况是链表退化或者红黑树路径变长但正常情况下O(1)的常数开销都极低统计数据下完全够用。4.2 业务场景下的选型决策顺序我在实际项目里选集合基本按照下面这个顺序过一遍第一看并发。集合会不会被多个线程同时写只要答案是会直接进并发包选不要犹豫。读多写少用CopyOnWriteArrayList或者Collections.unmodifiableList包一层读写都频繁用ConcurrentHashMap如果只是想要一个不会抛ConcurrentModificationException的并发场景遍历可以看看ConcurrentLinkedQueue这类队列结构。第二看是否需要有序。需要按键排序就用TreeMap或TreeSet需要保持插入顺序就用LinkedHashMap或LinkedHashSet完全不需要顺序就无脑选Hash结构的哈希表的O(1)访问是性能上限。第三看数据规模。数据量在几百以内其实ArrayList和LinkedList的差距都可以忽略不计优先选代码可读性高的ArrayList数据量上了百万级就必须认真考虑底层数据结构了空间和时间的权衡都会放大。第四看操作模式。你的核心操作是按下标随机读就选ArrayList核心操作是频繁头尾增删就选ArrayDeque或LinkedList核心操作是按键查值就选HashMap核心操作是范围查询或找最邻近值就选TreeMap。4.3 被低估的工具类与不可变集合除了集合接口本身java.util.Collections这个工具类里有大量被低估的静态方法。Collections.unmodifiableList可以把一个可变集合包装成只读视图任何写操作都会抛UnsupportedOperationException这比let外部直接操作原始集合要安全得多。Collections.synchronizedList能实现线程安全但注意它是在方法级别加synchronized锁一般只适合并发冲突不激烈的场景性能远不如并发包里的专用实现。还有JDK 9之后引入的List.of、Map.of、Set.of可以直接创建不可变集合元素不允许为null也不允许修改。我建议你把把集合暴露给外部之前先想一想是否要防御性拷贝或不可变包装养成一个习惯。很多隐蔽的数据竞争和意外修改都是因为某个内部HashSet或ArrayList被直接传出去调用方顺手改了你还在用旧数据做判断最后定位问题时百思不得其解。这个坑我踩过不止一次。5. 高频面试题背后的源码细节与避坑指南5.1 为什么HashMap的容量必须是2的幂这是面试里出现率极高的一个问题。HashMap定位桶索引用的是hash (length - 1)而不是hash % length。当length是2的幂时length - 1的二进制形态是一串全1比如16对应的是二进制1111那么hash 1111就等价于hash取低4位效果跟hash % 16一样但位运算比取模快得多。更关键的是如果length不是2的幂比如length15length-11110末尾一位永远是0那么所有hash的奇数位索引二进制第一位为1的桶就永远不可能被命中空间直接浪费一半分布严重不均。JDK 8还在扩容时用上了这个性质的优化。扩容时容量变为原来的两倍老链表里的每个节点只要看一眼(e.hash oldCap)是否为0为0的节点留在原索引位置为1的节点搬到原索引oldCap的位置。这一步不需要重新计算哈希只做一次位与判断效率极高。这也是为什么即使你初始化HashMap时传了一个不是2的幂的容量比如new HashMap(17)JDK也会把它修正成最近的2的幂次实际得到32。5.2 负载因子0.75和树化阈值8/6是如何确定下来的负载因子默认0.75这是时间与空间的一个折中。太小比如0.5容量没用完就开始扩容空间浪费严重太大比如1桶填满了才扩容哈希碰撞概率上升链表变长查询变慢。0.75是官方历经大量实测后给出的黄金分割点一般不需要改。如果你明确知道Map只读不会频繁写可以适当调大一点减少扩容次数如果追求极低延迟可以调小一点降低碰撞率但要注意内存代价。树化阈值8和退树阈值6背后有一个统计学解释在负载因子0.75哈希函数分布足够均匀的前提下某个桶里的链表长度达到8的概率大约只有千万分之六这是一个非常小的事件。真出现了长度达到8的桶说明哈希函数已经严重劣化此时链表已经无法支撑高效读写需要红黑树救场。而退树阈值设置成6而不是8是为了避免在7和8之间反复横跳如果某个桶在树和链表之间频繁转换代价极其昂贵留出2个数的缓冲区间是典型的工程容错设计。5.3 equals与hashCode的约定对集合的影响这是所有Java集合面试里绕不开的经典问题也是实际开发中最容易出bug的地方。HashMap和HashSet判断两个key是不是同一个先比较hashCode结果hashCode不同直接认为是不同元素hashCode相同才继续用equals做精确比较。所以equals返回true的对象hashCode必须相同否则这个对象放进HashMap后可能永远找不回来。重写了equals却不重写hashCode是最常见的低级错误。更隐蔽的一个坑是可变键。我举个真实的例子一个Person对象有id和name两个字段你把一个id1的Person放进HashSet然后把这个对象的name改了由于hashCode是基于id和name计算的这个对象现在算出的新hash对应的桶跟它实际所在的桶已经不是同一个了。调用contains时它在新桶里找不到这个对象返回false而旧桶里那个孤零零的对象永远无人访问就变成了事实上的内存泄漏。这个问题的正确解法是放进HashMap作为key或放进HashSet的对象要么是不可变对象要么保证加入后不再修改参与hashCode计算的字段。Java 16的record类设计上就很适合当key因为它自动实现了基于所有组件的equals和hashCode而且组件全部是final的。5.4 遍历中删除元素为什么你总是看到ConcurrentModificationException这是一个我在带新人时几乎必考的问题。代码如下for (String item : list) { if (item.length() 3) { list.remove(item); } }这段代码必抛ConcurrentModificationException原因就是第1节说的modCount机制增强for循环底层是迭代器每次next都会检查expectedModCount和modCount是否一致而list.remove直接改了modCount两边的数字对不上立刻触发fail-fast。正确做法有三种。第一种用显式迭代器并在遍历时调用iterator.remove()这个方法会把修改同步到expectedModCount不会触发异常。第二种用JDK 8的removeIf一行搞定list.removeIf(item - item.length() 3)。第三种用倒序for循环从尾部往前删避免移动后续元素。我个人最推荐第二种代码最简洁而且底层已经帮你想好了遍历时的安全修改问题。5.5 认真对待不可变集合与空集合还有一个很多人没注意到的点Collections.emptyList()、emptyMap()、emptySet()返回的是共享的、不可变的空集合实例。这个方法不创建多余对象也不允许add但它在源码里有一个小坑——返回的类型是泛型的如果你把返回值赋给一个具体类型的List变量类型推断有时会出问题需要显式指定泛型。我写过List list Collections.emptyList()编译没问题但List不可变集合的核心价值不是省内存而是保证行为可预期。你return一个内部集合的不可变视图调用方再怎么折腾都影响不到你的内部状态你return一个new ArrayList复制出来的拷贝虽然数据安全但浪费空间。工程上我在定义对外API时默认返回不可变视图或者真实拷贝内部集合绝不裸奔。这个习惯可以有效减少一类只在生产环境偶现、本地永远复现不了的诡异bug。最后如果你准备系统梳理整个集合框架我个人的建议是学习顺序不要按类来按问题来先问自己那个类的接口设计解决什么问题再看源码是怎么解决这个问题的最后回到我的业务里有没有同样的问题用这个三个问题循环去逼近。最开始千万不要一头扎进每个方法的逐行源码细节先画一张总览图把Collection和Map两条线捋清楚再逐个击破核心实现。我复盘自己过去几年的项目线上真正麻烦的并发问题十有八九都跟HashMap或者HashSet在错误场景下的使用有关如果早期就能把这套框架背后的权衡思路吃透很多事故都是可以避免的。这大概就是写这篇笔记最大的意义了。
复杂度详解)
