★ FEATURED ARTICLE 先说一个观点Java集合类是每一个Java开发者的“日常口粮”也是面试里出镜率最高的基础题。不管你是刚学完语法准备找工作还是已经工作两三年想跳槽集合类这一块都是绕不过去的。很多人背了一堆类名什么ArrayList、HashMap、HashSet面试时候能说出来但一追问“底层结构是什么”“为什么用红黑树”“扩容怎么扩”就卡壳了。这篇文章就把集合类整个家族捋一遍从整体框架到具体实现再到工具类、选型和面试考点尽量用大白话讲清楚让你看完不只能应付面试回到业务里也能选对容器。先明确一下适用范围你至少要知道Java基本语法、类和对象是怎么回事最好已经写过几个小项目。如果你连 ArrayList list new ArrayList() 都还没敲过建议先把环境配好跑通一个HelloWorld再回头看这篇。下面内容比较多但每节我都尽量按“是什么、为什么、怎么用、坑在哪”的顺序来写你可以跳着看面试前重点看第1、2、3和5章就够了。1. 集合框架的整体架构与核心设计思路1.1 为什么需要集合类数组先天的三宗罪很多新手一开始接触的是数组比如 int[] arr new int[10]但用久了就会发现数组在业务开发里非常难受。先说第一宗罪长度固定。你声明了10个长度存到第11个就崩要么自己写扩容逻辑要么预估一个很大的长度浪费内存。第二宗罪操作麻烦。数组只有下标访问想在中间插入一个元素需要把后面所有元素都后移一位逻辑不难但非常容易出错想删除一个元素同理。第三宗罪算法能力基本为零。数组本身没有排序、查找、去重这些方法什么都得你自己写。集合类就是为了解决这些痛点出现的。它本质上是“可以动态扩展、自带算法支持的对象容器”。你可以把它想象成一个带滑轮的整理箱东西多了会自动变大你想按颜色分类、按大小排序它都给你现成的方法。Java把这一整套容器抽象成了两个族系一个是 Collection存单个元素的一个是 Map存键值对的。这两个族系下面又衍生出List、Set、Queue、Map的各种实现类。搞懂这个框架你才算真正入门了“面向对象编程Java”里容器管理这块核心内容。1.2 两大核心接口与家族全景先看一张“家谱”式的结构描述Collection 接口是所有单列集合的根接口下面派生出 List、Set、Queue 三个子接口Map 是另一棵独立的树跟 Collection 平级。很多人刚学的时候会误以为Map属于Collection其实不是Map存的是键值对不是单元素所以它单独一棵树。这么设计有一个好处所有实现类都遵循统一的接口规范意味着你可以用同样的姿势遍历、添加、删除只是底层行为不同。我整理了一张常用实现类的速查表先混个脸熟接口实现类底层结构特点一句话ListArrayList动态数组查询快、增删慢日常最常用ListLinkedList双向链表增删快、随机访问慢也实现了DequeListVector动态数组线程安全但性能差老代码遗留SetHashSet哈希表HashMap无序、唯一、速度快SetLinkedHashSet哈希表链表有插入顺序、唯一SetTreeSet红黑树有序、唯一可自定义排序QueuePriorityQueue堆按优先级出队默认最小堆MapHashMap数组链表红黑树无序、key唯一使用率最高MapLinkedHashMap哈希表双向链表有插入顺序/访问顺序MapTreeMap红黑树key有序支持区间查询MapHashtable哈希表线程安全性能差已过时这里要补充一个很多教程不讲清楚的基础点集合里存放的是对象的引用不是对象本身。也就是说list.add(obj) 只是把对象的地址放了进去后续你修改obj的内容集合里的数据也跟着变。这点在业务代码里经常会造成诡异的bug比如你往集合里add了一个对象然后又改了对象的字段结果发现集合里的“旧数据”也变了。新手经常踩先记在心里。2. Collection家族之路List、Set、Queue逐个拆解2.1 List系列ArrayList、LinkedList、Vector怎么选List是有序、可重复的集合这个概念先记住。日常代码里出现频率最高的就是ArrayList它底层就是一个动态数组 Object[] elementData通过一个 size 字段记录实际元素个数。查询全靠下标所以时间复杂度是O(1)非常快但中间插入和删除需要移动元素最坏情况要移动n个所以是O(n)。LinkedList底层是双向链表每个节点 Node 持有prev、next、item三个引用。它的优势在增删只要修改前后节点的指针即可时间复杂度O(1)前提是你已经拿到了那个节点。但如果要在链表中间查找某个元素必须从头开始遍历时间复杂度O(n)。很多人以为“LinkedList增删一定比ArrayList快”这是个误区。如果你是在尾部追加元素ArrayList因为有自动扩容机制其实不比LinkedList慢甚至因为数组连续内存访问更友好性能反而好。真正的强项是频繁在头部或中部增删的场景。Vector是个老古董了它的方法和ArrayList几乎一样但所有方法都加了 synchronized所以线程安全。问题在于这种粗粒度加锁性能太差现在并发场景基本都用CopyOnWriteArrayList或者Collections工具类包装Vector只在面试题里还有存在感。选择建议很简单业务开发无脑ArrayList队列场景可以用LinkedList多线程读多写少的场景考虑CopyOnWriteArrayList。2.2 ArrayList扩容机制从默认容量到1.5倍ArrayList的扩容几乎是Java基础面试必考题每次面试都会被问到。它默认构造创建的是一个空数组首次调用add时才初始化容量为10。当元素个数size超过当前容量时触发扩容新容量计算公式是 int newCapacity oldCapacity (oldCapacity 1)也就是扩容为原来的1.5倍。举个例子第11个元素要加进来当前容量10不够了新容量就是 10 5 15。然后调用 Arrays.copyOf 把原数组元素复制到新数组旧数组交给垃圾回收。这里有个细节扩容是要复制所有已存元素的如果集合很大扩容一次代价很高。所以如果你知道数据量大概有1000条最好直接 new ArrayList(1000) 指定初始容量能避免多次扩容带来的性能损耗。这块也顺便解释了一个常见问题为什么ArrayList不是一开始就把容量给大因为内存是宝贵的大部分场景数据量都不大10个初始容量足够覆盖绝大多数情况扩容属于“按需分配”。还有个小点ArrayList的 ensureCapacity 方法可以主动扩容但平时很少用因为底层自动扩容已经够用了。面试官如果再追问“扩容到15之后再存多少个元素触发下一次扩容”那就数一下第16个元素超过了容量15扩容到15 151 22依此类推。这个等比增长的思路也可以用到你自己设计的缓冲结构里。2.3 Set系列HashSet、LinkedHashSet、TreeSet各自的应用Set的核心理念是“去重”但不同实现类对“顺序”的理解完全不同。最常用的HashSet底层就是HashMap元素被当成HashMap的keyvalue统一是一个固定的Object常量 PRESENT。因为HashMap的key不能重复所以HashSet天然就去重了。它的特点是无序遍历顺序不保证和插入顺序一致但查找、插入都很快平均O(1)。LinkedHashSet比HashSet多了维护一个双向链表所以遍历顺序和插入顺序一致。代价是每个元素多存了几个指针内存占用略高。如果你要做“去重但保留第一次出现的顺序”用它就对了。典型场景是处理用户提交的标签列表既要去掉重复项又不想破坏原有顺序。TreeSet底层是红黑树元素会按照自然顺序升序或者你传入的Comparator排序。注意它用的是“比较”而不是“哈希”来判断重复所以如果两个对象通过compareTo返回0即使equals为false也会被认为重复。这是TreeSet一个容易踩的坑。它的插入、删除、查找是O(log n)适合需要有序集合且数据量不大不小的场景。另外TreeSet还支持 first()、last()、subSet(a, b) 这类区间操作在做排行榜、区间筛选时很方便。关于去重的底层逻辑必须补一句HashSet去重依赖的是对象的hashCode和equals。如果往HashSet里放自定义对象一定要同时重写这两个方法否则即使两个对象业务属性完全一样hashCode不同也会被当成不同元素。重写的时候遵循规则equals相等的两个对象hashCode必须相等否则集合里会出现“看着重复但去不掉”的问题。2.4 Queue与Deque从普通队列到优先队列Queue接口代表先进先出的队列核心方法是 offer入队、poll取出并移除队头、peek只看队头不移除。注意不要用 add 和 remove因为它们在队满或队空时会抛异常而offer/poll返回特殊值更安全。实现类方面ArrayDeque底层是循环数组性能比LinkedList好做栈和队列都可以推荐使用。LinkedList也实现了Deque接口可以当作队列用但如果你只是为了当容器存数据ArrayDeque更轻量。PriorityQueue则特殊得多它的底层是一个最小堆元素出队顺序不是按照入队顺序而是按照优先级——默认是自然顺序的最小值先出队。你可以传一个Comparator改变优先级规则。PriorityQueue在算法题里出场率极高“返回TopK”其实就是一个维护大小为K的小顶堆堆顶是当前K个里最小的遇到比堆顶大的就替换。Java PriorityQueue 默认就是最小堆所以实现TopK只需要传入 (a, b) - b - a 变成最大堆即可。这个点在后面竞赛章节还会展开。3. Map家族全解析3.1 HashMap底层数组链表红黑树与树化阈值HashMap是整个集合框架里最核心的内容没有之一。它底层是一个Node数组每个Node要么是一个链表节点要么是红黑树节点。添加元素时先对key做哈希再通过 (n - 1) hash 的方式定位到数组槽位。如果槽位为空直接放入如果槽位已经有了其他元素哈希碰撞就追加到链表尾部或者树中。这里有个高频考点为什么HashMap的哈希要 h key.hashCode() ^ (h 16)因为hashCode是32位的数组长度一般没这么大计算槽位时只用了低位高位完全浪费。把高16位异或到低16位相当于把高位信息也混进低位让散列更均匀。然后 (n - 1) hash 比取模 % n 更快因为位运算直接操作二进制所以HashMap计算槽位时要求数组长度必须是2的幂。再说参数默认初始容量16加载因子0.75。加载因子的意思是当元素个数超过容量乘以0.75也就是12个时触发扩容容量变为2倍。这个0.75是空间和时间权衡的经验值太大会导致哈希碰撞变多链变长查询变慢太小会提前扩容浪费内存。至于为什么链长超过8就转红黑树官方文档给过一句话在随机哈希码下链表长度达到8的概率非常低大约是千万分之六。如果真到了8说明哈希函数有问题或者数据分布极端异常用红黑树把最差情况从O(n)降到O(log n)属于兜底方案。当树节点减少到6时再退回链表中间留了7这个缓冲防止频繁转换造成抖动。HashMap还有一个必须知道的坑线程不安全。JDK 1.7的并发扩容可能造成环形链表导致get死循环JDK 1.8改为尾插法修复了死循环但并发put仍可能覆盖数据、resize时丢失数据。所以多线程场景千万不要用HashMap。3.2 LinkedHashMap插入顺序、访问顺序与LRU缓存LinkedHashMap是HashMap的子类它在每个桶的节点之外额外维护了一条双向链表把所有键值对串起来。根据构造器参数 accessOrder 的不同这条链表有两种排列顺序默认是false按插入顺序排列设为true则按访问顺序排列每次get或put都会把对应节点移到链表尾部。基于这个特性LinkedHashMap是手写LRU缓存的利器。你只需要继承它覆写 removeEldestEntry 方法让它返回“当前大小是否超过最大容量”就可以实现一个“容量满了就把最久没访问的键值对移除”的缓存。这是什么原理accessOrdertrue时链表头就是最久未访问的数据链表尾就是最近访问的数据put新数据时如果触发移除条件移除链表的首节点即可。一行代码都不多余。面试中经常问“如何实现一个LRU缓存”标准答案就是LinkedHashMap覆写removeEldestEntry。但注意如果业务里有并发访问还要在外面加锁或者用 Collections.synchronizedMap 包裹因为LinkedHashMap本身不是线程安全的。3.3 TreeMap与Hashtable有序Map与历史遗留TreeMap底层是红黑树key按照自然顺序或者自定义Comparator排序。它不像HashMap那样通过哈希定位所有查找、插入、删除都是O(log n)。它最有价值的能力是区间查询subMap(fromKey, true, toKey, true) 可以直接切出一段排序好的键值集合在做范围统计、区间排行时非常好用。Hashtable则完全是另一个时代的产物。它是JDK 1.0就有的所有方法都加 synchronized所以是线程安全的但性能很差。它和HashMap还有两个不容忽视的差异Hashtable不允许null key和null valueHashMap允许Hashtable扩容是2倍加1而HashMap是2倍。时至今日除了面试题里问你“HashMap和Hashtable的区别”业务代码里基本见不到Hashtable了。它的位置被ConcurrentHashMap取代。3.4 ConcurrentHashMap并发场景下的正确选择如果面试官问你“并发下用哪个Map”答案必须是ConcurrentHashMap。JDK 1.7时代它用的是分段锁把数据分成一截一截的Segment每个Segment管一把锁不同线程操作不同段时可以并行锁粒度比Hashtable细得多。JDK 1.8进一步放弃了分段锁直接用Node数组加CAS加synchronized插入时如果槽位为空通过CAS放入不需要加锁如果槽位非空对头节点加synchronized锁。这样锁粒度从“段”缩小到“单个桶”并发度和性能都大幅提高。这就带来一个非常实用的结论并发读多写多的场景直接上ConcurrentHashMap不要再用Hashtable更不要自己给HashMap加全局锁。它的size方法也是基于CounterCell分段计数的在高并发下统计元素个数也不会因为锁竞争而卡死。我做了一个简单的对照表特性HashMapHashtableConcurrentHashMap线程安全否是是锁粒度无整个对象槽位/桶允许null key是否否性能最高差接近HashMap适用场景单线程内部使用几乎不用并发场景这里注意ConcurrentHashMap是不允许null key和null value的因为并发环境下无法判断value为null到底是不存在还是值为null会引发歧义。4. 工具类与常用操作4.1 Collections最常用的静态方法速查Java为集合准备了一个万能工具箱 java.util.Collections里面全是静态方法不需要new对象。日常用得最多的有sort排序、reverse反转、shuffle打乱、min/max取最值、frequency统计出现次数、copy复制、replaceAll替换。还有两个高频方法解决并发问题synchronizedList、synchronizedMap可以对现有集合加锁包装但注意包装后的集合在做迭代时仍然需要手动加锁因为迭代过程本身不是原子的。ListInteger list new ArrayList(Arrays.asList(3, 1, 4, 1, 5)); Collections.sort(list); // 升序排序 Collections.reverse(list); // 反转 Collections.shuffle(list); // 随机打乱 Collections.sort(list, Collections.reverseOrder()); // 降序排序还有一个很有用的方法 unmodifiableList返回一个只读视图任何修改操作都会抛 UnsupportedOperationException。业务中经常用它把内部集合暴露给外部调用方防止外部把数据改坏。不过要注意这个“只读”只是不能增删改元素元素本身如果是可变的仍然可以通过引用修改其字段。4.2 Arrays与集合互转一个高频坑数组和集合互转是业务里特别常见的需求坑也特别多。先说 Arrays.asList它返回的是一个内部类ArrayList虽然实现了List接口但底层仍然是原来的数组长度固定。你调用add、remove会直接抛 UnsupportedOperationException很多人第一次碰到都懵了明明返回的是List为什么不能加元素正确做法是在外面包一层真正的ArrayListString[] arr {a, b, c}; ListString list new ArrayList(Arrays.asList(arr));反过来集合转数组用 toArray。如果不传参数返回的是Object[]想得到具体类型的数组传一个空数组 list.toArray(new String[0])。JDK 8之后传入空数组比传入预先分配好大小的数组性能更好因为底层会有优化不用像传入大数组那样先判断长度再复制。这个点也可以当面试题记住。还有一个相关坑Arrays.asList 把基本类型数组转成List时如果是 int[]它会把整个数组当成一个元素而不是转成Integer列表。因为泛型不支持基本类型。解决办法是用 Arrays.stream(arr).boxed() 或者手写循环。4.3 排序与比较器Comparable与Comparator怎么选排序是集合类使用频率最高的操作之一。Java提供了两种比较方式一种是让对象自身实现 Comparable 接口重写 compareTo 方法这叫“自然排序”比如Integer、String都自带这个能力另一种是定义外部 Comparator 比较器这叫“策略排序”你可以在不同场景临时指定不同的排序规则。比较直观的选择标准如果这个类在业务全局只有一个公认的排序规则用Comparable写在类内部如果排序规则经常变或者你无法修改那个类比如第三方库的类用Comparator。现在的写法已经很简练了lambda一行搞定list.sort((a, b) - a.getAge() - b.getAge()); // 升序 list.sort(Comparator.comparing(User::getAge).reversed()); // 按年龄降序还有一个细节Collections.sort 和 List.sort 用的是稳定排序底层是归并排序和TimSort的混合。稳定意味着相等元素的相对顺序不会被颠倒这在多级排序中非常重要。比如你先按年龄排再按姓名排两轮排序不会把第一轮的结果打乱前提是每轮都用稳定排序。5. 面试、竞赛与业务选型经验5.1 面试官最爱问的5个集合类问题结合最近几年Java面试题的热门方向我把集合类的问题浓缩成5道核心题每道都给出答题主线。第一题ArrayList和LinkedList的区别。答题要有层次先说底层结构数组和双向链表再说增删查改的时间复杂度接着说扩容机制最后给一两个适用场景。如果能提到“尾部添加两者区别不大LinkedList空间开销更大”就很出彩。第二题HashMap的底层实现。主线数组加链表加红黑树哈希过程加载因子0.75扩容翻倍树化阈值8和退化阈值6。别只背公式最好能解释一下0.75是空间时间权衡、8是泊松分布小概率事件。第三题HashSet怎么做到去重的答底层是HashMap元素作为key。关键点在hashCode和equals先比较hashCode再比较equals。第四题HashMap为什么线程不安全答多线程并发写会造成数据覆盖、size不准确JDK 1.7还有循环链表风险然后给出结论——并发用ConcurrentHashMap。第五题Collection和Collections的区别。一个是接口一个是工具类这是一个基础题但常被混淆一句话讲清楚。这五题如果都能不看资料独立讲出来集合类的面试部分基本就过关了。如果你在准备“Java开发工程师面试题”和“Java八股文”把这五题当提纲去梳理就够了。5.2 不同业务场景下的集合选型回到业务开发选错集合类会带来肉眼可见的性能问题。这里总结一套我常用的选型参考业务需求推荐集合理由存一批订单按时间顺序展示频繁读下走ArrayList查询快尾部追加快需要频繁在列表顶部插入热门商品LinkedList / ArrayDeque头插成本低用户标签去重不关心顺序HashSet速度快保留第一次出现顺序的去重LinkedHashSet有序加去重排行榜按分数降序取前10名PriorityQueueTopK效率最高需要按key范围查数据如价格区间TreeMap支持区间视图需要缓存且要求淘汰最久未使用LinkedHashMap天然支持LRU并发下维护配置缓存映射ConcurrentHashMap线程安全高性能需要线程安全且读多写少的列表CopyOnWriteArrayList读不加锁另外提醒一点集合去重不是万能的。如果业务要求“根据对象的某个字段去重”你得先确认这个字段在equals里是否参与判断。很多人在数据库里看着不重复的ID放进HashSet却去不掉就是因为实体类没有重写equals和hashCode或者重写得不完整。5.3 蓝桥杯等算法竞赛中集合类的妙用再结合竞赛方向说几句。蓝桥杯这类比赛里Java组用到的核心数据结构大多就落在集合类上。比如“数字题目”经常要统计数字出现的次数用 HashMapInteger, Integer 做一个计数器一行 map.put(key, map.getOrDefault(key, 0) 1) 就能搞定比开数组灵活得多尤其是key范围很大或者很稀疏的时候。需要“去重加排序”的题用 TreeSet 一步到位它自动维护升序遍历输出就是结果。需要“每次取最大/最小”的贪心题用 PriorityQueue。这类题很典型比如合并K个有序链表、寻找第K大、任务调度。Java选手经常感叹自己写得慢其实很多时间就浪费在徒手写堆和手写快排上直接用PriorityQueue和 Arrays.sort 能节约大量时间。竞赛里还有一个更高阶的用法TreeMap 的 subMap 和 higherEntry 可以解决区间查询和最近邻问题比每次遍历整个集合快一个数量级。如果你已经能把HashMap、TreeSet、PriorityQueue烂熟于心蓝桥杯省赛的数据结构部分就问题不大了。在做算法题的时候我个人还有一个小习惯选手写代码速度很重要所以集合类的常用API一定要背到肌肉记忆比如 map.getOrDefault、set.contains、queue.offer/poll不要每次现查。真到了赛场上多一次翻阅文档就少几分钟调试。最后分享一点摸索出来的经验学集合类千万不要只靠背最好的办法是动手写一段代码把一个List反复add到十几万条观察耗时把HashMap的容量初始设定为1、2、4打印出resize前后的日志看看内部结构怎么变化。JDK里 HashMap 的源码是很值得反复读的读个两三遍很多面试题就不再需要死记硬背了因为你会从设计者角度理解为什么这个参数是0.75、为什么链表要转树。面试时候的自信感通常就来自这些底层细节。
阅读完成 · 觉得有帮助？
