★ FEATURED ARTICLE 从入行到现在我面试过的Java候选人少说也有上百个。每次问到集合框架几乎都能听到同一套答案“ArrayList底层是数组LinkedList底层是链表数组查询快、链表增删快。”话是没错可真一写代码就露馅该用队列的时候拿LinkedList硬凑遍历集合时偷偷删元素然后被ConcurrentModificationException折磨自定义对象塞进HashMap之后改了字段就再也get不回来。集合框架从来不是用来“背”的是用来“用”的。这篇文章我就把Java集合这块从头到尾捋一遍List、Set、Map、栈和队列、迭代器、Collections工具类该看源码的地方看源码该踩的坑也都给你标出来希望对正在学集合或者项目里被集合问题卡住的同学有点实际帮助。1. 先把集合框架的地图装进脑子体系结构与选型逻辑很多新手学集合是零散地学学一个ArrayList再学一个HashMap每个类单独看都会用但遇到“这个场景该选谁”就懵了。其实Java集合框架的结构非常清晰一张族谱图就能看明白Collection接口 ├── List接口有序、可重复支持索引访问 │ ├── ArrayList │ ├── LinkedList │ └── Vector遗留类不推荐 ├── Set接口不可重复 │ ├── HashSet │ ├── LinkedHashSet │ └── TreeSet └── Queue接口队列操作 ├── LinkedList ├── PriorityQueue └── ArrayDeque实现了Deque接口 Map独立接口键值对键不可重复 ├── HashMap ├── LinkedHashMap ├── TreeMap └── Hashtable遗留类不推荐注意两个容易被忽略的点Map不继承Collection它是独立的一个接口体系只不过Map的keySet()和entrySet()能返回集合视图所以经常和Collection放在一起讲Set里面很多实现其实是“借壳”的比如HashSet底层就是一个HashMap这个后面细说。1.1 三个接口家族各自解决什么问题List解决的是“有序且可重复”的存储需求。你按顺序加了5条数据遍历的时候它们还是这个顺序而且你可以通过索引精确访问第3条。ArrayList用动态数组实现LinkedList用双向链表实现。Set解决的是“去重”问题。往HashSet里add同一个对象两次第二次会失败因为底层HashMap会认为key已经存在。它不关心顺序你插入的顺序不代表遍历顺序。如果你既想去重又想保持插入顺序用LinkedHashSet如果想去重还要按某种规则排序用TreeSet。Map解决的是“按键取值”的问题。它更像一本字典通过key找到对应value。HashMap是散列实现无序TreeMap按key排序LinkedHashMap能保持插入顺序或访问顺序后者可以做LRU缓存。1.2 选型其实就是回答三个问题遇到“该用哪个集合”的纠结我建议只问自己三个问题数据允不允许重复允许重复走List不允许走Set或Map的key。顺序重要吗要插入顺序用ArrayList/LinkedHashSet/LinkedHashMap要排序用TreeSet/TreeMap完全不在乎就用HashSet/HashMap。单线程还是多线程单线程优先考虑非同步集合性能更好多线程再考虑加锁方案或并发容器。把这三个问题想清楚90%的选型场景都能直接确定。剩下10%才是性能细节的权衡比如到底用ArrayList还是LinkedList这个我们下一节专门展开聊因为这里面的误区和套路太多了。提示不要一上来就追求“高端”集合。能用ArrayList解决的问题就不要因为“听说LinkedList增删快”而换成LinkedList。真实项目里ArrayList的出场率远高于LinkedList这不是偶然。2. ArrayList与LinkedList翻源码聊性能打破“查快增删快”的刻板印象这两兄弟是面试八股文的重灾区。网上的对比文章翻来覆去就是那几句数组查询快、增删慢链表增删快、查询慢。可你要是真按这个结论去写代码大概率会踩坑。因为这句话漏掉了最关键的前提在什么位置增删在什么位置查询。2.1 ArrayList的扩容机制与随机访问的真实代价ArrayList的底层就是Object[]数组。构造时可以指定初始容量不指定的话JDK 8之后默认是一个空数组第一次add的时候才真正分配容量10。之后每次容量不够就按oldCapacity (oldCapacity 1)扩容也就是1.5倍。比如容量10用满了下一次直接扩到15再下次是22如此类推。这个1.5倍扩容的细节为什么值得注意因为它决定了ArrayList尾部add的均摊时间复杂度是O(1)。每次扩容其实都要新建数组并System.arraycopy老数据但如果按倍增策略扩容前面这些拷贝成本会被后续很多次add分摊掉。如果你预先知道大概要存多少数据直接new ArrayList(预估容量)就能省掉扩容的拷贝开销。我见过有人往ArrayList里循环插入几十万条数据不指定容量结果扩容触发了十几次数组复制性能肉眼可见地变差。按索引插入和删除才是ArrayList真正的痛点。add(int index, E element)要先检查索引然后System.arraycopy把index位置及之后的所有元素后移一位。删除同理把后面的元素往前移。这是严格的O(n)操作而且涉及数组元素搬移。但注意这里的O(n)指的是内存拷贝速度很快实际工程里插入几万条数据的开销也没那么恐怖。至于随机访问get(int index)直接返回数组对应下标元素这是实打实的O(1)因为数组在内存里是连续的CPU缓存命中率也高。2.2 LinkedList的双向链表结构与隐蔽代价LinkedList的底层是双向链表节点大概是这样一个结构private static class NodeE { E item; NodeE next; NodeE prev; }每个元素都被包在一个Node里这个Node额外携带两个引用prev和next在64位JVM上还要考虑对象头对齐。所以LinkedList每个元素的内存占用比ArrayList大得多。我用JOL量过空Object数组和空链表差距不明显但塞一百万条Integer进去LinkedList比ArrayList多出好几十MB都是Node对象撑出来的。链表真正的O(1)优势只体现在“已知节点位置”的头尾增删上。addFirst、addLast、removeFirst、removeLast都是O(1)。但如果你用add(int index, E e)往中间插它得先从头或尾开始遍历找索引内部有个小优化判断index离头近还是离尾近从近的那边开始找。但无论如何定位节点是O(n)插入本身是O(1)总体还是O(n)。所以“LinkedList增删快”这个说法非常容易误导人。增删快的前提是你已经持有了那个节点的引用比如通过迭代器、通过node(index)拿到或者只操作链表两端。你要是每次都想按索引插入LinkedList不见得比ArrayList快甚至因为节点分散在堆上、CPU缓存不友好实际更慢。2.3 用真实场景量化对比我做过一个很简单的压测往两个列表里分别add一百万条数据。ArrayList尾部插入完胜LinkedList尾部也很快但没有ArrayList那么稳定。再测试“按索引插入到中间位置”插入一万次数据规模十万条——ArrayList和LinkedList都慢但LinkedList反而更慢因为找节点要遍历。再测试“只从头部插入一万条”LinkedList明显更快ArrayList每次头部插入都要整体后移这倒是符合直觉。结论是什么如果你要的是“两头操作、频繁头插头删”直接上ArrayDeque或者LinkedList都行如果场景是下标随机访问和尾部追加ArrayList几乎是唯一正确的选择如果场景是“已有节点的删除/插入”比如遍历过程中删除元素LinkedList配迭代器体验确实好但ArrayList用Iterator.remove()也能做到O(n)内完成删除差别没有想象中那么大。2.4 实际开发中的几个ArrayList大坑第一个是remove(Object)和remove(int)重载混淆。删除一个元素传int进去走的是按索引删而不是删这个值的元素。想按对象删就得包装成Integer否则结果永远不是你想要的。ListInteger list new ArrayList(Arrays.asList(1, 2, 3, 2)); list.remove(2); // 删的是索引2位置的元素结果是[1, 2, 2] list.remove(Integer.valueOf(2)); // 删的是值为2的元素第一个结果是[1, 3, 2]第二个是遍历中删除元素。在foreach里直接list.remove(item)必抛ConcurrentModificationException正确姿势是使用迭代器的remove或者更方便的removeIf。list.removeIf(item - item 10);第三个坑是subList返回的是原列表的视图不是快照。你拿着subList做任何结构性修改原列表的modCount就变了紧接着再操作subList会直接抛异常。很多人不知道这一点debug半天。第四个坑是toArray()转换。list.toArray()返回Object[]如果你要String[]必须用list.toArray(new String[0])。JDK 11之后官方建议传0长度的数组因为内部有优化。3. Stack、Queue与Deque从遗留类到现代队列的演进Java集合框架里有一批“出生早、设计差”的类Stack就是典型。我见过很多人还在用Stack做栈这倒不算错但真的不建议在新代码里用了。3.1 Stack为什么被打入冷宫Stack继承自VectorVector是个线程安全的类所有方法都加synchronized。单线程环境下这些锁没有意义纯属性能损耗。更糟的是由于继承的关系Stack除了push/pop外还暴露了add(int, E)、get(int)这些数组方法你可以像操作ArrayList一样操作Stack——这就破坏了栈“只能从一端进出”的抽象。栈的语义被稀释得干干净净。合理替代是ArrayDeque它实现了Deque接口提供了完整的push/pop/peek等栈操作底层是可变环形数组无锁、性能好、API语义清晰。Stack该退休了。DequeString stack new ArrayDeque(); stack.push(a); stack.push(b); String top stack.peek(); // b String popped stack.pop(); // b3.2 Queue接口的核心设计失败返回特殊值Queue接口定义了新增的语义除了Collection原有的add/remove还提供了offer/poll/peek这一组方法。前一组操作失败时抛异常后一组失败时返回null或false。用哪个取决于你的业务场景如果队列满是一种“正常情况”而不是错误就应该用offer而不是add。Java里可用的队列实现很多但日常写业务代码最常接触的应该是这几个实现类底层特点ArrayDeque循环数组双端操作O(1)不允许null性能最好LinkedList双向链表同时也是List但作为队列用不如ArrayDequePriorityQueue二叉堆按优先级出队不是FIFOArrayBlockingQueue循环数组锁有界阻塞队列适合生产者消费者很多人用LinkedList当队列使我建议改成ArrayDeque。实测下来ArrayDeque在绝大多数操作上比LinkedList快内存也更紧凑。LinkedList的最大价值反而是它同时实现了List和Deque在某些需要“既能索引访问又能双端操作”的场景下才能体现。PriorityQueue值得单独说说。它内部是堆结构构造时传Comparator决定优先级顺序默认是小顶堆。offer和poll的时间复杂度都是O(log n)peek是O(1)。注意它不保证同优先级元素的FIFO顺序因为堆调整算法本身不稳定。PriorityQueueTask queue new PriorityQueue(Comparator.comparingInt(Task::getPriority)); queue.offer(new Task(3, 低优先级任务)); queue.offer(new Task(1, 高优先级任务)); Task next queue.poll(); // 优先级为1的任务先出队3.3 Deque双端队列的实战姿势Deque既可以当栈push/pop也可以当普通队列offer/poll还可以当双端队列addFirst/addLast。我日常用得最多的场景实现操作记录undo/redo两个ArrayDeque一个存操作历史一个存撤销历史。广度优先搜索ArrayDeque当队列pollFirst往队尾放邻居特别顺手。滑动窗口题目用双端队列维护窗口内最大值的候选索引这是LeetCode经典题但真实项目里的“最近N条记录”也很实用。注意ArrayDeque不允许插入null值如果业务上有“队列里可能放null”的诉求需要换个方案或者用Object占位。标题里没提但我顺带说一句如果你需要“按固定大小自动淘汰最旧元素”的队列Java标准库其实没有现成的环形缓冲队列。可以自己用ArrayDeque加removeFirst实现或者直接上第三方缓存库别自己硬造线程安全的循环数组。4. Set与Map的哈希家族equals、hashCode、比较器与有序变体Set和Map的关系非常紧密。HashSet底层就是HashMapTreeSet底层是TreeMapLinkedHashSet底层是LinkedHashMap。搞清楚Map的机制Set基本就懂了大半。这一节我以HashMap为主线展开因为它是Java里用得最多的数据结构之一也是八股考查的重灾区。4.1 HashMap的put流程扰动函数、桶定位与树化JDK 8之后的HashMap底层结构是数组链表红黑树。默认初始容量16加载因子0.75意思是当元素数量超过16 * 0.75 12时触发扩容容量翻倍。这个0.75是空间和时间的一个折中太小浪费空间太大冲突概率上升。put一个键值对时流程是这样的先对key的hashCode做一次扰动——高16位异或低16位让散列结果更均匀然后(n - 1) hash定位到桶下标。如果该桶为空直接放。如果桶不为空遍历链表发现一样的key就覆盖value如果key不一样就尾插到链表后面。当链表长度超过8且数组长度不小于64时链表转红黑树。反过来扩容或删除后红黑树节点数降到6会退化成链表。这个过程里有几个非常容易踩坑的地方。第一个是自定义对象做key必须同时重写equals和hashCode。HashMap判断key是否相同先比hash定位桶再在桶内用equals比较。如果你只重写equals不重写hashCode两个逻辑相等的对象会散落到不同的桶HashMap自然认为它们“不相等”。类似“同一个对象存进去拿不出来”的问题十有八九是hashCode没重写。更隐蔽的问题是hashCode每次算出来还不一样比如用了一个可变字段参与hashCode计算存进去之后改了字段get的时候hash对不上就再也找不到了。所以作为key的类最好设计成不可变的。第二个是HashMap不是按插入顺序遍历的。很多人把HashMap当“有序集合”用遍历结果和插入顺序不一样又怀疑是不是自己写错了。想保持插入顺序就用LinkedHashMap它额外维护了一条双向链表串起所有entry遍历时按插入顺序输出。4.2 HashSet等于“只在乎key的HashMap”看HashSet源码会发现它内部持有一个HashMap实例private transient HashMapE,Object map; private static final Object PRESENT new Object();add操作就是map.put(e, PRESENT)put返回null说明之前没有这个key返回非null说明已经存在。所以HashSet的去重逻辑完全依赖key的equals和hashCode。HashSet遍历顺序是乱的想保持插入顺序用LinkedHashSet想按规则排序用TreeSet。如果你只需要一个布尔值表示“之前见过这个元素”那么HashSet就是最好的标记容器。比如对一批日志数据去重、对订单号去重直接用HashSet别自己写HashMap套boolean纯属多此一举。4.3 TreeSet与TreeMap红黑树与比较器陷阱TreeSet和TreeMap底层是红黑树核心是“有序”。这个有序不是插入顺序而是按比较规则排列。默认要求key实现Comparable接口或者在构造时传入Comparator。红黑树的操作复杂度是O(log n)比哈希结构的O(1)慢但它天然支持范围查询TreeMap的subMap(fromKey, toKey)、headMap(toKey)、tailMap(fromKey)TreeSet的subSet、headSet、tailSet。比较器这里有一个很隐蔽的坑TreeSet的判重逻辑不是equals而是compare或compareTo的返回值。只要返回0就认为两个元素重复。如果比较器只比较了部分字段就会出现“两个实体类对象字段不完全相同但被TreeSet当成同一个元素”的诡异结果。我建议自定义比较器时尽量做到“比较结果为0和equals结果保持一致”否则后续很多集合操作会出现反直觉的行为。4.4 LinkedHashMap实现LRU缓存LinkedHashMap还提供一个高级玩法按访问顺序排列。构造时传accessOrdertrue每次get或put一个已有key这个entry就会被移到链表末尾。更妙的它有个钩子方法removeEldestEntry默认返回false表示不淘汰你重写它就能实现“当元素超过上限时删除最老的”。class LRUCacheK, V extends LinkedHashMapK, V { private final int maxCapacity; public LRUCache(int maxCapacity) { super(maxCapacity, 0.75f, true); this.maxCapacity maxCapacity; } Override protected boolean removeEldestEntry(Map.EntryK, V eldest) { return size() maxCapacity; } }这段代码几行就实现了一个可用的LRU缓存。当然它线程不安全也没处理key为null之类的边界生产环境要加锁或用现成的缓存库。但理解这个机制能让你在答题和面试时多一份从容LinkedHashMap不仅是“有序Map”它还是LRU的基础实现。Map家族还有其他变体比如EnumMap用枚举做key、内部是数组性能极高IdentityHashMap用判断key而不是equalsWeakHashMap的key是弱引用适合做缓存场景。这些在特定场景都很有用但业务代码里出场率低就不展开讲了。5. 迭代器机制从语法糖到Fail-Fast明白遍历背后的规矩很多人写for-each循环很流畅但从来没想过它背后发生了什么。其实for-each只是一个语法糖编译之后会变成迭代器调用。数组的for-each编译成普通for加下标集合的for-each编译成iterator()拿迭代器循环调用hasNext()和next()。理解这一点很多诡异异常就都能解释了。5.1 Iterable与Iterator的分工Iterable接口只定义了一个方法iterator()它描述的是“这个对象可以被遍历”的能力。Iterator才是真正干活的游标三个核心方法public interface IteratorE { boolean hasNext(); // 还有没有下一个 E next(); // 返回下一个元素同时游标后移 default void remove() { throw new UnsupportedOperationException(); } }ListIterator是Iterator的子接口增加了previous、add、set等双向操作只有List系列才支持。这里有个常见的面试陷阱HashMap、ArrayList这些类实现的是Iterable接口而Iterable能反复调iterator()生成多个迭代器所以同一个集合可以被遍历多次。而Iterator本身是一次性的游标遍历完就到底了不能重头再来。5.2 Fail-Fast机制为什么遍历时删元素会炸java.util包下所有的非线程安全集合都有一个modCount字段记录结构性修改次数。所谓“结构性修改”就是改变集合大小或导致并发遍历出错的操作比如add、remove、clear。而set或修改已存在元素的值不算结构性修改。迭代器创建时会保存当时的expectedModCount。每次调用next或hasNext都会检查modCount和expectedModCount是否一致不一致就立刻抛ConcurrentModificationException。这就是Fail-Fast快速失败机制它不用“继续往下走到下一个异常时刻”而是在破坏现场暴露的第一时间报警。那为什么在foreach里调用list.remove会抛异常而迭代器自己的remove不抛因为集合的remove会修改modCount迭代器的expectedModCount就过期了下次next检查时发现不一致。而迭代器的remove方法在删除之后会重新同步expectedModCount保证两者一致。所以合法的遍历中删除只有两条路用迭代器的remove或者用JDK 8的removeIf。// 错误示范 for (String s : list) { if (条件) list.remove(s); // ConcurrentModificationException } // 正确示范 IteratorString it list.iterator(); while (it.hasNext()) { String s it.next(); if (条件) it.remove(); } // 更简洁的示范 list.removeIf(条件);5.3 Fail-Fast不是Fail-Safe很多资料会提到Fail-Safe安全失败说CopyOnWriteArrayList遍历时不会抛ConcurrentModificationException因此是Fail-Safe的。这个说法不太准确。CopyOnWriteArrayList的做法是每次修改都复制整个底层数组迭代器在创建时拿到的是当时数组的“快照引用”之后不管集合怎么改迭代器遍历的都是旧数组所以永远不会感知并发修改自然也不会抛异常。它不是“通过某种机制保证安全”而是“根本看不到变化”。这种快照迭代器的代价是写操作昂贵每次写都复制数组所以CopyOnWriteArrayList的应用场景非常明确读多写少。提示别指望“Fail-Fast会保护你不犯错”。它的作用只是尽早暴露错误不是保证并发安全。要并发安全请使用并发容器或加锁而不是靠不抛异常。6. Collections工具类排序、同步包装与不可变集合的实用姿势Collections是java.util下一个纯静态方法的工具类代码里几乎每天都在用。但大多数人只会用sort和shuffle其他一箩筐实用方法都闲置着。6.1 排序与查找别忽略你手写的ComparatorCollections.sort(List)在JDK 8之后内部委托给了List.sortArrayList的实现直接把底层数组拷出来排序再写回用的是TimSort——一种结合归并排序和插入排序的算法对部分有序数据特别友好。LinkedList的sort也是先转数组排好再写回链表。自定义Comparator时有一个隐藏规范比较结果要和equals保持一致。如果compare返回0而equals为false把元素放进TreeSet就会出现重复检测错乱如果反过来等于equals相等但compare非0那HashSet里能正常去重TreeSet里就出现两个你觉得“相等”的元素。这种一致性虽然不强制但在“排序去重查找”结合的复杂场景里不遵守就埋雷。Collections.binarySearch很强大但前提是列表必须按同一个比较器升序排列否则结果未定义。我见过有人对无序列表直接binarySearch结果时对时不对排查半天。6.2 同步包装用之前必须知道的全表锁代价Collections.synchronizedList(new ArrayList())能返回一个线程安全的List方法级别的synchronized保证了单个操作的原子性。但有一个大坑迭代遍历不是同步的。官方文档也建议遍历的时候必须手动锁住整个集合对象否则一边遍历一边被别的线程改照样抛CME或者拿到脏数据。ListString list Collections.synchronizedList(new ArrayList()); synchronized (list) { for (String s : list) { // 必须持有list的锁才能安全遍历 } }synchronizedMap、synchronizedSet都是同一套路全表锁。并发度低、操作简单时勉强够用一旦并发量上来所有线程争一把锁吞吐量会断崖式下跌。多线程下频繁读写的KV场景请直接用ConcurrentHashMap它用细粒度锁和无锁CAS提升并发度是每秒几十万次读写的正确姿势。6.3 不可变集合与防御性拷贝Collections.unmodifiableList(list)返回一个只读视图任何增删改都会抛UnsupportedOperationException。但注意这个“不可变”只是相对的——原始list的引用还在你手里你改了原始list视图也会跟着变。真正干净的不可变写法是ListString immutable Collections.unmodifiableList(new ArrayList(data));Java 9之后有更简洁的选择List.of(...)、Set.of(...)、Map.of(...)它们生成的是真正不可变的集合内部实现经过专门优化内存占用更小。注意它们不接受null元素Set.of还不允许重复元素。防御性拷贝的概念在传参时尤其重要。你把自己内部持有的List直接交给外部方法外部就能随意修改你的内部状态。正确的做法是返回或接收时都做一次不可变包装或拷贝。很多人被同事埋过这种雷不想重复踩就先学会这一招。还有两个Collections的方法值得提出来Collections.copy(dest, src)很多人误以为它会自动扩容目标列表其实它要求目标列表size不小于源列表size否则抛IndexOutOfBoundsException。它按索引逐个set不新增元素。Collections.frequency(list, obj)、Collections.disjoint(c1, c2)在统计元素出现次数、判断两个集合是否没有交集时非常方便比自己写循环简洁得多。另外Collections.nCopies(n, obj)可以快速生成n个相同元素的ListCollections.singletonList(obj)生成单元素不可变ListCollections.emptyList()返回空List——这三个方法在避免不必要的对象创建、快速构造入参时很实用。特别是方法返回空集合时别返回null直接返回Collections.emptyList()风格干净还能防止调用方做空指针判空时漏掉情况。写到这我顺手想到一个建议如果你们的项目还在用裸的new ArrayList()到处传建议尽早引入“可变集合只存在于方法内部跨方法传递一律用不可变视图或拷贝”的习惯。这个习惯比单纯背API有用得多我自己在代码评审里提过无数次真按这个改完线上奇怪的并发问题都少了一大半。集合框架的每一个类都有它存在的理由但把它们组合起来的正确姿势永远比单个类的特性更重要。
阅读完成 · 觉得有帮助？
