面试问到List、Set、Map大概率不是要你背两个方法名而是想看你有没有在真实项目里被这些集合“折腾”过。特别是最近几年Java面试的八股越来越喜欢向源码和底层挖ArrayList扩容为什么是1.5倍而不是2倍HashMap什么时候转红黑树LinkedHashMap怎么做到有序的如果你只是背了结论一旦面试官追问“为什么”或者让你讲讲实际使用中踩过的坑很容易卡壳。这篇文章我会按自己这些年看源码、写代码、做面试官的经验把List、Set、Map这三块核心内容拆开来讲。不光是面试考点还会结合真实项目场景比如数据导入时List转Map丢数据的坑、并发环境下用错Map导致的死循环、排序时Comparator不小心写反的问题。不管是准备面试还是日常开发这篇都值得你花半小时慢慢看。1. List实现类怎么选别只盯着ArrayList1.1 ArrayList扩容细节面试官真正想听什么几乎每个人都知道“ArrayList底层是数组扩容时是1.5倍”。但当你被问到“为什么是1.5倍而不是2倍或者1.2倍”时能答清楚的人就少了。先说结论JDK里grow方法的代码是int newCapacity oldCapacity (oldCapacity 1);右移一位相当于除以2所以新容量是旧容量的1.5倍。这个设计折中了空间浪费和扩容次数。如果扩容倍数太大比如直接3倍内存浪费会很严重如果太小比如1.2倍那每次添加元素都会频繁触发数组复制性能受损。1.5倍能保证均摊时间复杂度为O(1)这是ArrayList能作为默认List实现的核心原因。再说一个细节扩容时是Arrays.copyOf底层调用System.arraycopy这是一个native方法它做的是内存块移动速度很快。但你要明白扩容发生时旧数组里的元素要一个个复制到新数组这是个O(n)的操作。所以如果预先知道数据量一定要用new ArrayList(10000)这种指定容量的构造方法能省掉很多次扩容。还有一点容易被忽略Arrays.asList生成的List不是你平时new的ArrayList它是一个Arrays内部类虽然名字也带ArrayList但底层是固定长度的数组你不能对它调用add或remove否则会抛UnsupportedOperationException。这个坑在项目里特别常见尤其是把数组转成List后习惯性去add的人。另外补充一个实际经验ArrayList和LinkedList在做“插入”时的区别要看插入位置。LinkedList的add(int index, E element)并不是O(1)它需要先遍历到指定位置最坏情况是O(n)。而ArrayList如果是往末尾插均摊O(1)往中间插则需要移动后续元素O(n)。所以面试时别直接说“ArrayList插入慢LinkedList插入快”这个话是错的要看具体场景。1.2 LinkedList你以为的“快”其实没那么简单LinkedList底层是双向链表每个节点有prev、next、item三个字段。每个节点本身是个对象还要额外保存指针所以内存占用比ArrayList大。如果你存储的是大量小对象LinkedList的额外开销可能会让你惊讶。从源码角度说LinkedList的get(int index)会先判断index是在链表前半段还是后半段然后决定从头部还是尾部开始遍历这是一个优化index (size 1)但时间复杂度依然是O(n)。所以“LinkedList查询慢”这句话在随机访问场景下是对的但如果你是用迭代器逐个访问LinkedList反而表现不错因为它是顺序访问不需要数组拷贝。LinkedList真正强的地方是作为Deque使用。ArrayDeque和LinkedList都实现了Deque接口但ArrayDeque不允许存nullLinkedList允许。日常要当队列或双端队列用我一般推荐ArrayDeque它的扩容机制和内存局部性都比LinkedList好很多。面试中如果你被问到“什么时候用LinkedList”比较安全的答法是当你需要频繁在头部或尾部插入删除且不需要随机访问时或者你需要实现一个FIFO队列且可能有大量增删时。但说实话现代Java开发里LinkedList用的地方越来越少很多高性能场景直接用ArrayDeque或者并发队列了。知道这一点面试时反而显得你有实际经验。2. HashMap核心机制hash、equals、红黑树的三角关系2.1 hashCode和equals的约定记不住就要出事HashMap的put流程是所有Java面试里绕不开的必考题。核心逻辑是先用key的hashCode经过扰动函数算出hash再用hash对数组长度取模实际是(n - 1) hash定位到桶位。如果桶位为空直接放进去如果不为空就要用equals比较key是否相等相等则替换value不相等则形成链表或树。所以hashCode和equals是有严格约定的两个对象equals相等hashCode必须相等两个对象hashCode相等equals可以不等这就是碰撞。如果你重写了equals却没重写hashCode导致两个业务上相同的对象hashCode不同HashMap就会把它们当成两个不同的key存进去。最经典的例子是new String(abc)和new String(abc)它们的hashCode一样且equals相等所以没问题但如果你自定义一个User类只重写equals不重写hashCode用同一个id的User去map.get取数据大概率取不到因为hashCode不同连桶位都定位不到。另一个常见场景是用可变对象做HashMap的key。比如把List或者一个字段可变的自定义对象当key存进map之后又修改了这个key的内容导致hashCode变了但它在map里的桶位已经固定了永远get不回来还会造成内存泄漏。这是我线上出过事故的地方后来团队就定了一条规范业务上要做key的字段强制用不可变对象或者至少保证hashCode相关字段不可变。2.2 HashMap扩容、树化阈值与退化条件JDK 8的HashMap是“数组 链表 红黑树”的结构。链表转红黑树的条件是链表长度达到8且数组长度达到64如果数组长度没到64即使链表再长也不会树化而是先扩容。为什么阈值是8官方注释里给了泊松分布的计算简单说是在负载因子0.75、随机哈希的理想情况下链表长度达到8的概率已经非常低了大约是千万分之六。所以长度达到8说明哈希分布出了问题这时候用树把查找复杂度从O(n)降到O(log n)是划算的。但注意如果数组容量不足64说明整个表都没铺开扩容是更好的策略。红黑树转回链表的条件是树中节点数小于等于6。8和6之间留了差值是为了避免在边界处频繁来回转换。如果阈值都是8那在7和8之间震荡时会反复树化、退化消耗很大。你面value试时可以提到这个设计会显得你读过源码。关于HashMap的容量还有个小知识点如果你new HashMap(7)实际数组长度是8如果你放进去7个元素到扩容阈值7 * 0.75 5.25的时候就会扩容成16。所以指定初始容量时不能直接填“预计的元素个数”要填预计元素数 / 0.75 1。比如预计100个元素初始容量应该设100 / 0.75 1 ≈ 134实际HashMap会帮你round到下一个2的幂也就是256。很多人不关心这个结果明明设了初始容量还是频繁扩容白白浪费性能。2.3 LinkedHashMap和TreeMap有顺序的Map怎么选HashMap不保证顺序遍历顺序可能跟插入顺序完全不同。如果业务上需要按插入顺序读取就得用LinkedHashMap。它内部多维护了一条双向链表指向插入顺序或访问顺序。构造方法里有个accessOrder参数如果为true就按最近访问顺序排序这正好是LRU缓存的核心机制。实现一个简单的LRU只需要继承LinkedHashMap重写removeEldestEntry方法当size超过阈值就返回true让最老的元素被移除。TreeMap则是基于红黑树实现的有序Map按key的自然顺序或自定义Comparator排序。它提供firstKey、lastKey、floorEntry、ceilingEntry这些方法在处理区间查询时非常方便。但TreeMap的put和get是O(log n)性能比HashMap差。而且TreeMap的key不能为null因为需要比较大小HashMap的key则允许一个null。实际开发中我见过不少把TreeMap当普通Map用的人明明不需要排序却付出了log n的代价。反过来需要排序时又有人自己写一堆排序代码费力不讨好。正确做法是默认用HashMap需要插入顺序用LinkedHashMap需要排序用TreeMap这个选择逻辑面试时讲出来也很有条理。3. Set的底层秘密HashMap穿了一层马甲3.1 HashSet为什么用“假value”来去重HashSet的源码极其简单里面就是持有一个HashMapadd方法是map.put(e, PRESENT)PRESENT是一个new Object()静态常量。也就是说HashSet的每个元素实际上是HashMap的key而value全部指向同一个占位对象。这就是“穿马甲”的说法。理解了这个结构你就能解释很多现象HashSet为什么不能有重复元素因为HashMap的key不能重复。元素能不能为null因为HashMap允许一个null key所以HashSet也允许一个null。遍历顺序稳定吗不稳定取决于HashMap的哈希和扩容情况。HashSet的“去重”依赖元素的hashCode和equals这个和HashMap是同一个逻辑。所以如果你往HashSet里放自定义对象却不重写equals和hashCode去重基本就是摆设。另一方面TreeSet是基于TreeMap实现的它实现去重和排序是利用元素的Comparable或者传入的Comparator它不看equals只看compareTo返回0就认为是同一个元素。所以如果compareTo和equals逻辑不一致会出现“equals为false但去重了”或者“equals为true但Set里有两个”的诡异现象。3.2 LinkedHashSet与TreeSet的实际使用场景LinkedHashSet是HashSet的子类内部通过LinkedHashMap实现保持了插入顺序。它适合需要去重且要求顺序的场景比如“按用户点击顺序去重”的埋点列表。LinkedHashSet额外维护了一个双向链表插入、删除、遍历的复杂度依然是O(1)比用ArrayList去重再排序高效得多。TreeSet适合需要有序且去重的场景比如按分数排名的玩家ID集合。你可以定义Comparator把分数高的排在前面然后迭代输出。但TreeSet的源码里大量使用了NavigableMap接口最常见的问题是如果你在Comparator里写了会被修改的字段即元素加入集合后比较字段发生变化整个结构就乱了查找时会得到错误结果而且很难排查。比如一个学生对象score字段变了但集合里的红黑树结构没有调整这个元素就可能找不到了。我在项目里一般这样用需要快速去重用HashSet去重加保序用LinkedHashSet排序加去重用TreeSet如果数据量大且需要排序优先考虑ArrayList加Collections.sort因为TreeSet的树结构在数据量大了以后内存占用和插入开销都不小。4. 集合遍历、排序与比较器实战问题集4.1 遍历时删除元素为什么ConcurrentModificationExceptionArrayList在迭代过程中删除元素很容易抛ConcurrentModificationException。原因在于ArrayList内部有一个modCount字段记录结构修改次数迭代器每次调用next时都会检查expectedModCount ! modCount不一致就抛异常。这个机制是fail-fast目的是尽早暴露并发修改问题。但很多人不知道for-each删除单个元素时并不是每次都会抛异常。因为ArrayList的remove方法会执行modCount迭代器在hasNext时只判断游标和大小不检查expectedModCount只有调用next时才检查。如果集合里没有下一个元素了hasNext返回false循环结束就没有机会触发检查所以删除最后一个元素时可能不抛异常。这个现象我刚入行时遇到过当时一度以为程序写对了后来才知道是侥幸。安全删除方式有几种用迭代器的iterator.remove()它会同步更新expectedModCount或者用JDK 8的removeIf或者先收集要删的元素循环结束后一次性removeAll。多线程环境下直接用CopyOnWriteArrayList的迭代器则完全免疫这个问题因为它的迭代器操作的是快照数组。4.2 Comparator与Comparable排序细节决定成败Comparable是“自己跟自己比”类实现compareToComparator是“第三方裁判”可以随时用Comparator.comparing链式搭规则。排序函数Collections.sort和Arrays.sort都依赖这些比较器。实际开发中最常见的坑是返回值的符号写反。compare(a, b)返回负值表示a在前正值表示b在前。很多人记忆“0是相等负数小于正数大于”但写的时候忘记是a减b还是b减a排序结果就反了。更隐蔽的是整数溢出问题如果直接用return o1.getId() - o2.getId();当两个id一个很大正数、一个很小负数时减法会溢出结果变成错误的正负号。正确写法是用Integer.compare包装或者用Comparator.comparingInt。Java 8之后Comparator.comparing、thenComparing、reversed这些方法让排序代码简洁很多但要注意链式写法中reversed()的作用域。Comparator.comparing(User::getAge).reversed()是先按age升序比较然后整个结果翻转即按age降序。而如果写成Comparator.comparing(User::getAge, Comparator.reverseOrder())效果一样。如果你还想在age相同时按name排注意reversed只作用于age后续的thenComparing是放在翻转后的比较器后面顺序可能会超出直觉。这个我建议你在本地跑一跑比光背八股强百倍。4.3 stream的toMap到底有哪些坑用Collectors.toMap把List转成Map是开发高频操作但它有三个常见坑。第一个坑是key重复。如果list里有相同key的多个元素直接toMap会抛IllegalStateException: Duplicate key。解决办法是传第三个参数mergeFunction比如(v1, v2) - v2表示后来的覆盖先来的(v1, v2) - v1表示保留第一个。也可以合并成List(v1, v2) - { List l new ArrayList(); ... }虽然这样写有点丑但确实能解决业务诉求。第二个坑是value为null。HashMap本身允许value为null但toMap的默认实现是基于Map.merge的merge在value为null时会有特殊逻辑如果key不存在就put(value)如果key存在会用remappingFunction处理。如果value是null且key不存在merge会直接put一个null进去问题不大但如果key已经存在且新value是null那么merge会把旧值删掉导致集合里根本没有这个key。在JDK 8的HashMap实现里merge处理null value时会触发resize或remove行为所以结果可能不是你想要的。稳妥起见toMap之前先过滤掉null值或者自己循环put。第三个坑是返回的Map具体类型不确定。默认toMap返回的是HashMap不保证顺序。如果你需要按插入顺序要使用LinkedHashMap::new作为第四个参数需要排序则用TreeMap。这些小问题在代码审查时经常被忽略但线上数据一变多就暴露了。5. 并发集合怎么选从Hashtable到ConcurrentHashMap的演进5.1 Vector和Hashtable为什么被淘汰早期Java集合Vector和Hashtable都是方法级别加synchronized的线程安全但性能太差。因为它们把所有方法都锁住即使读操作也要抢同一把锁并发高的时候就是串行执行。而单线程情况下还要付出加锁解锁的开销。所以现在基本不用它们了。如果你需要线程安全的List可以用Collections.synchronizedList包装它也是粗粒度锁。更好的选择是CopyOnWriteArrayList它适合读多写少的场景写的时候复制整个底层数组写完后替换引用读操作无需加锁。但写成本很高如果你频繁addCopyOnWriteArrayList性能会很差因为每次写都复制数组而且内存占用瞬间翻倍。5.2 ConcurrentHashMap的JDK 8分段锁到CAS很多面试题喜欢问ConcurrentHashMap的JDK 7和JDK 8区别。JDK 7用Segment分段锁默认16个Segment每个Segment是一把ReentrantLock最多支持16个线程并发写。JDK 8取消了Segment直接用Node数组 CAS synchronized。JDK 8的put流程是如果桶位为空用CAS直接放入不用加锁如果桶位不为空就对头节点加synchronized锁然后按链表或红黑树插入。这样并发度大大提高因为锁的粒度从Segment级别缩小到了单个桶的级别。而且JDK 8引入了Thread.yield和spinForTimeoutThreshold在写竞争激烈时会自旋等待避免频繁阻塞唤醒。如果你在面试中被问到“ConcurrentHashMap为什么读操作不需要加锁”原因在于Node的value和next字段都是用volatile修饰的读线程能看到其他线程写入的最新值。同时桶位数组本身也是volatile扩容时的节点迁移通过ForwardingNode来标记读线程遇到ForwardingNode会跳到新的数组去读保证了扩容过程中读不会丢失数据。5.3 实际并发场景缓存、计数器、去重实际项目中我用过不同并发集合来解决问题。做本地缓存且需要淘汰策略首选Caffeine或Guava Cache不自己乱写。但如果面试需要手写简化版LRULinkedHashMap的accessOrder是很好的底子。做并发计数用ConcurrentHashMap compute方法map.compute(key, (k, v) - v null ? 1 : v 1)底层对单个key是有锁的不用担心线程安全问题不要再额外套一层synchronized。做并发去重ConcurrentHashMap.newKeySet() 就可以拿到线程安全的Set比用Collections.synchronizedSet(new HashSet()) 性能更好因为它内部就是ConcurrentHashMap的keySet视图。一个特别容易踩的坑虽然ConcurrentHashMap的单个方法都是线程安全的但复合操作不是原子的。比如if (!map.containsKey(key)) { map.put(key, value); }两个线程可能同时通过containsKey检查然后都执行put造成覆盖。这时应该用putIfAbsent或者用computeIfAbsent。computeIfAbsent能保证同一个key只有一个线程执行映射函数但要注意映射函数内部不要再操作同一个map否则可能有死锁风险。这个在JDK 8里是真的能死锁的bug后来虽然在某些版本修复了一部分但厂商文档仍然建议不要在compute函数里递归操作同一个map。6. 面试连环炮与开发手记那些源码之外的经验6.1 高频面试连环炮的开场与回答路径很多面试官都会从“用过哪些集合类”开始一直深挖到“HashMap扩容死循环”。我可以给你一套比较安全的回答路径不至于被带偏。第一层介绍List、Set、Map的核心实现类及适用场景重点说ArrayList扩容机制、HashMap结构、HashSet基于HashMap。第二层谈谈源码细节比如HashMap的哈希扰动函数(h key.hashCode()) ^ (h 16)为什么异或高位因为数组长度通常比较小取模时只用了低位异或高16位可以把高位信息混入低位减少碰撞。第三层谈谈并发从HashTable到ConcurrentHashMap为什么放弃分段锁JDK 8的CAS synchronized如何提升并发度。如果能提到size()方法与mappingCount()的区别面试官会眼前一亮因为JDK 8的size可能是不精确的mappingCount返回Long用于超过int范围的情况。第四层结合实际项目说一次线上问题比如toMap重复key导致任务失败或者遍历时删除元素导致诡异数据。这一层最能加分因为它说明你不只是背八股而是真的在项目里被坑过。6.2 排查集合问题的一些小技巧排查集合相关线上问题我常用的几个方法看线程dump。如果发现很多线程阻塞在HashMap的put或get上首先怀疑是不是用了非线程安全的HashMap做共享变量或者并发扩容时出现了死循环JDK 7才有JDK 8基本没有死循环但会出现数据丢失。看GC日志。频繁FullGC可能和集合无关但如果对象全是Node或Entry那就是某个Map或Set里堆了大量对象且无法回收典型场景是缓存key没设置过期策略。看业务日志中的异常栈。ConcurrentModificationException、UnsupportedOperationException、IllegalStateException: Duplicate key这三种异常基本都能定位到集合方法用错了地方。有个小经验如果数据量很大迭代器遍历集合比用get(index)快很多。尤其是在ArrayList上for循环get每次都要做边界检查迭代器则直接游标移动。虽然现代JIT会优化但在面试里说“用迭代器避免并发修改问题”比说“迭代器更快”更稳妥。6.3 最后的小建议如果你正在准备Java面试不要死背源码行号而是要把每个集合的“数据结构形状”画出来。ArrayList就是连续数组LinkedList就是双向链表HashMap就是数组加链表加红黑树HashSet就是HashMap的key视图。把形状记住了绝大多数问题都能推出来。比如问你“HashMap允许key为null吗”你只要能想到ArrayDeque不允许null、HashMap可以就不会答错。实际开发中我这些年最大的体会是集合类的选择不要追求花哨90%的场景用ArrayList和HashMap就够了。但你要清楚它们各自的边界在哪里什么时候会让性能崩塌什么时候会抛异常什么时候会静默丢数据。理解了这些边界你和普通“会写Java”的同行差距就拉开了。