← 返回首页 ❓ 面试题库
📑 本篇章节导航 (共11章,点击直达)
一、List体系二、Map体系 — HashMap三、Map体系 — ConcurrentHashMap四、Map体系 — 其他Map五、Set体系六、Queue与BlockingQueue七、CopyOnWrite与并发集合八、迭代器与fail-fast/fail-safe九、Collections工具类十、Stream API与集合操作十一、综合对比与源码细节

title: Java集合框架高频面试题

tags: [Java集合, HashMap, ArrayList, ConcurrentHashMap]

created: 2026-05-31


Java集合框架高频面试题

共60道题 | 难度分布:★★★☆☆~★★★★★ | 2026年20K+ Java后端面试必考:集合源码、HashMap扩容、ConcurrentHashMap分段锁演进。

一、List体系

Q1. ArrayList和LinkedList的区别?

答案:ArrayList底层基于动态数组实现,默认初始容量为10,每次扩容为原来的1.5倍(通过oldCapacity + (oldCapacity >> 1)计算),支持随机访问时间复杂度O(1),但在中间插入/删除需要移动元素,时间复杂度O(n)。LinkedList底层基于双向链表实现,每个节点保存prev和next两个指针,不支持随机访问(需从头/尾遍历,O(n)),但在已知节点位置时插入/删除只需修改指针,时间复杂度O(1)。实际开发中ArrayList在绝大多数场景下性能更优,因为CPU缓存友好(数组内存连续),而LinkedList频繁的节点创建会导致内存碎片和GC压力。

Q2. ArrayList的扩容机制是怎样的?

答案:ArrayList使用Object[] elementData数组存储元素,首次调用add()时如果使用无参构造器,会初始化为长度10的数组(JDK7是饿汉式直接创建,JDK8是懒加载在首次add时创建)。当元素个数超过当前数组长度时触发扩容,新容量 = oldCapacity + (oldCapacity >> 1),即约1.5倍。扩容过程调用Arrays.copyOf()创建新数组并拷贝元素,这是一次O(n)的操作。如果预知数据量,建议使用new ArrayList<>(initialCapacity)指定初始容量以减少扩容开销。

Q3. ArrayList的subList方法有什么坑?

答案:subList()返回的是ArrayList内部类SubList,它不是一个新的独立列表,而是原列表的一个视图(view)。对SubList的任何修改(add/remove/set)都会直接反映到原列表上,反之亦然。如果原列表在创建SubList之后被结构性修改(增删元素),再操作SubList会抛出ConcurrentModificationException。此外,SubList不支持序列化。正确用法是将subList结果用new ArrayList<>(list.subList(...))包装成独立列表。

Q4. Vector和ArrayList的区别?为什么Vector已经被淘汰?

答案:Vector的所有公开方法都使用synchronized修饰,是线程安全的,但也因此在高并发场景下性能很差(每次操作都锁整个对象)。ArrayList是非线程安全的,但性能更好。Vector每次扩容为原来的2倍(ArrayList是1.5倍),空间利用率较低。如果需要线程安全的List,推荐使用Collections.synchronizedList()或CopyOnWriteArrayList,而不是Vector。Vector被保留仅为了向后兼容。

Q5. Arrays.asList()有哪些常见陷阱?

答案:Arrays.asList()返回的是java.util.Arrays.ArrayList(Arrays的内部类),而不是java.util.ArrayList。这个内部类是原数组的视图,不支持add()和remove()操作(会抛UnsupportedOperationException),修改视图中的元素会影响原数组。此外,如果传入基本类型数组(如int[]),整个数组会被当作一个元素,长度为1而不是数组元素的个数。正确做法是使用new ArrayList<>(Arrays.asList(...))或Java 8的Stream.of().collect(Collectors.toList())。

Q6. LinkedList能否当作栈和队列使用?

答案:LinkedList同时实现了List和Deque接口,因此既可以当作双向链表使用,也可以当作栈(push()/pop())和双端队列(offerFirst()/offerLast()/pollFirst()/pollLast())使用。不过作为栈使用时,推荐使用ArrayDeque(基于数组的双端队列),因为ArrayDeque的内存局部性更好,没有链表节点的额外开销。作为队列使用时,如果需要阻塞功能则用LinkedBlockingQueue,不需要阻塞则用ArrayDeque或LinkedList。

Q7. 什么是RandomAccess接口?有什么意义?

答案:RandomAccess是一个标记接口(marker interface),没有任何方法,用于标识该集合支持高效随机访问。ArrayList实现了该接口,而LinkedList没有。在工具类如Collections.binarySearch()中,会通过instanceof RandomAccess判断集合类型:如果实现了RandomAccess则使用索引二分查找(O(logn)),否则使用迭代器遍历查找。自定义工具方法中也可用此接口来选择最优的遍历策略:for循环+get(i)还是迭代器遍历。

Q8. ArrayDeque的实现原理?为什么比LinkedList更适合做栈和队列?

答案:ArrayDeque基于可扩容的Object[]数组实现,使用head和tail两个int指针标记队头和队尾位置,采用循环数组(circular buffer)的方式工作。默认初始容量为16,必须是2的幂。每次扩容为2倍。ArrayDeque不允许null元素(用null作为特殊标记判断桶位是否为空)。相比LinkedList,ArrayDeque的优势:(1) 数组内存连续,CPU缓存命中率高;(2) 没有链表节点的额外内存开销(每个LinkedList节点需要额外32字节存储prev/next/item);(3) GC压力更小(不需要为每个元素创建Node对象)。

二、Map体系 — HashMap

Q9. HashMap的底层数据结构是什么?

答案:JDK8中HashMap采用"数组+链表+红黑树"的结构。核心是一个Node<K,V>[] table数组,每个桶位(bucket)可以挂载一个链表或红黑树。当某个桶位的链表长度超过8(TREEIFY_THRESHOLD)且table数组长度达到64时,链表会转换为红黑树(TreeNode)。当红黑树的节点数减少到6以下(UNTREEIFY_THRESHOLD)时,会退化回链表。红黑树的查询时间复杂度为O(logn),远优于链表的O(n),在hash冲突严重的场景下能显著提升性能。

Q10. HashMap的默认参数有哪些?为什么负载因子是0.75?

答案:HashMap默认初始容量为16(必须是2的幂),负载因子为0.75,扩容阈值为容量×负载因子=12。负载因子选0.75是时间和空间的折中:如果太大(如1.0),虽然空间利用率高但hash冲突严重,查询效率下降;如果太小(如0.5),hash冲突少但空间浪费大,频繁扩容。0.75在统计学上使得链表长度服从泊松分布,每个桶位的链表长度超过8的概率约为千万分之一,是一个经验最优值。

Q11. HashMap为什么容量必须是2的幂?

答案:容量必须是2的幂是为了让hash % capacity等价于hash & (capacity - 1),位运算比取模运算快得多。当capacity为2的幂时,capacity - 1的二进制全是1(如15=1111),与操作能均匀地映射到所有桶位,减少hash冲突。如果容量不是2的幂,某些桶位永远不会被映射到,造成空间浪费。在构造函数中传入非2的幂的容量时,tableSizeFor()方法会将其向上调整为最接近的2的幂(如传入10会变成16)。

Q12. HashMap的put流程是怎样的?

答案:(1) 对key调用hash()方法(高16位异或低16位)计算hash值;(2) 通过(n-1) & hash确定桶位索引;(3) 如果桶为空直接放入新Node;(4) 如果桶不为空,先比较hash和key是否相等(==或equals),相等则覆盖value;(5) 如果是红黑树节点,调用putTreeVal()插入;(6) 如果是链表,遍历到尾部插入(尾插法),如果链表长度达到8则尝试树化;(7) 插入后检查++size > threshold是否需要扩容。JDK8改为尾插法是为了解决JDK7头插法在多线程扩容时链表成环导致死循环的问题。

Q13. HashMap的扩容机制是怎样的?

答案:当元素数量超过阈值(capacity × loadFactor)时触发扩容。新容量为旧容量的2倍(newCap = oldCap << 1)。扩容时需要重新计算每个元素的桶位索引:JDK8的优化是,元素在新table中的位置要么是原索引,要么是原索引 + oldCap,通过hash & oldCap是否为0来判断,避免了重新计算hash。扩容过程逐个桶位迁移,链表会被拆分成低位链和高位链两部分。这种设计使得扩容时元素分布均匀,且避免了JDK7中的链表成环问题。

Q14. HashMap中链表转红黑树的阈值为什么是8?

答案:根据泊松分布,在负载因子0.75的情况下,每个桶位链表长度达到8的概率约为0.00000006(千万分之六),正常情况下几乎不会触发树化。设为8是为了在极端hash冲突情况下提供一个兜底保障,将最坏查询复杂度从O(n)提升到O(logn)。为什么不默认就用红黑树?因为TreeNode占用的空间是普通Node的两倍(需要维护left/right/parent/prev/红黑着色),在链表较短时空间浪费不划算。阈值选8是空间和时间的最佳平衡点。

Q15. HashMap为什么用红黑树而不是AVL树?

答案:红黑树和AVL树都是自平衡二叉搜索树,但红黑树的平衡条件更宽松(最长路径不超过最短路径的2倍),而AVL树要求左右子树高度差不超过1。红黑树在插入/删除时需要的旋转操作更少,写性能更好;AVL树查询时更严格平衡,读性能略优。HashMap的场景是读写混合的,且插入/删除频繁,红黑树的综合性能更优。此外红黑树的实现更简单,TreeNode的维护成本更低。

Q16. HashMap的hash方法为什么做高16位异或低16位?

答案:hash = (h = key.hashCode()) ^ (h >>> 16)。当table长度较小时(如16),只有低4位参与索引计算((n-1) & hash),高位不参与。如果两个key的hashCode低16位相同但高位不同,不扰动就会发生冲突。高16位异或到低16位(扰动函数),让高位也参与索引计算,使得在table容量较小时也能减少hash冲突。这是对"容量小时取模冲突率高"的优化,容量越大扰动效果越弱(因为更多位直接参与与运算)。

Q17. HashMap多线程使用会有什么问题?

答案:HashMap在多线程下不安全,可能出现以下问题:(1) JDK7中多线程扩容时头插法导致链表成环,get操作死循环(CPU 100%);(2) JDK8虽然改为尾插法解决了成环问题,但put操作中如果两个线程同时判断某个桶为空并写入,后写的会覆盖先写的,导致数据丢失;(3) size计算不准确(++size不是原子操作)。如果需要线程安全的Map,应使用ConcurrentHashMap,而不是Hashtable或Collections.synchronizedMap()。

Q18. HashMap key为null时怎么处理?

答案:HashMap允许一个key为null,其hash值固定为0,所以null key的元素始终放在table[0]桶位。put时如果key为null,会单独走一个逻辑直接遍历table[0]的链表/红黑树,看是否已存在null key,存在则覆盖value,不存在则插入新Node。这与ConcurrentHashMap不同——ConcurrentHashMap不允许null key和null value,因为如果在并发场景下get返回null,无法区分是"key不存在"还是"value就是null"。

Q19. HashMap的tableSizeFor方法是怎么实现的?

答案:tableSizeFor(int cap)方法将任意正整数转换为大于等于该数的最小2的幂。实现原理:将最高位1之后的所有位都置为1,最后加1得到2的幂。例如cap=10(二进制1010),经过5次无符号右移和按位或操作后变成1111(15),加1得到10000(16)。源码核心:int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;。先减1是为了处理cap本身就是2的幂的情况。

三、Map体系 — ConcurrentHashMap

Q20. ConcurrentHashMap JDK7和JDK8的实现有什么区别?

答案:JDK7采用分段锁(Segment),整个Map被分成16个Segment,每个Segment继承ReentrantLock,各自独立加锁,默认并发度为16。每个Segment内部是一个小HashMap(HashEntry数组+链表)。JDK8取消了Segment,改为"数组+链表+红黑树"结构,锁粒度细化到每个桶位(Node),使用CAS+synchronized替代ReentrantLock。JDK8的改进:(1) 并发度不再受Segment数量限制,理论上等于table长度;(2) 查询时不需要两次hash定位(先定位Segment再定位桶位),直接一次hash定位;(3) 引入红黑树优化hash冲突时的查询性能。

Q21. ConcurrentHashMap的put方法流程(JDK8)?

答案:(1) 计算key的hash值;(2) 如果table未初始化,调用initTable()初始化(通过CAS修改sizeCtl保证只有一个线程初始化);(3) 通过(n-1) & hash定位桶位,如果桶为空则CAS写入新Node;(4) 如果桶位hash值为-1(MOVED,表示正在扩容),则帮助扩容(helpTransfer());(5) 否则对该桶位的头节点加synchronized锁,在锁内遍历链表或红黑树进行插入/更新;(6) 插入完后如果链表长度达到8尝试树化;(7) 调用addCount()更新元素计数,并检查是否需要扩容。

Q22. ConcurrentHashMap的sizeCtl变量有什么作用?

答案:sizeCtl是一个volatile int变量,在不同阶段有不同含义:(1) -1表示table正在初始化(通过CAS将sizeCtl从0改为-1来抢占初始化权限);(2) -N(负数且不是-1)表示正在扩容,其中-(1 + 参与扩容的线程数);(3) 0表示table还未初始化(使用默认初始容量);(4) 正数表示下次扩容的阈值(capacity × loadFactor)。通过sizeCtl的状态实现了无锁的初始化和扩容协调。

Q23. ConcurrentHashMap是如何实现并发扩容的?

答案:JDK8的扩容采用多线程协同迁移的方式。扩容时创建一个容量为2倍的新table,然后从旧table的末尾开始向前分配迁移任务(每个线程领取一个步长,默认16个桶位为一个任务单位)。线程通过transferIndex变量协调迁移进度,CAS递减transferIndex来领取任务。迁移时在每个已迁移的桶位放置一个ForwardingNode(hash值为MOVED=-1),其他线程put时遇到ForwardingNode就知道该桶位正在迁移,会去新table中查找。扩容期间读操作不受影响,写操作在未迁移的桶位正常进行,在已迁移的桶位转发到新table。

Q24. ConcurrentHashMap的get方法需要加锁吗?

答案:get方法全程不加锁。它通过volatile语义保证可见性:Node数组的引用(table)和Node的val、next字段都是volatile的。get流程:(1) 计算hash定位桶位;(2) 如果桶位头节点就是要找的key直接返回;(3) 如果头节点hash < 0(可能是ForwardingNode或TreeBin),调用其find()方法在新table或红黑树中查找;(4) 否则遍历链表查找。由于val是volatile的,读线程总能看到最新的值,不需要加锁。

Q25. ConcurrentHashMap为什么不允许null key和null value?

答案:Doug Lea(ConcurrentHashMap作者)的解释是:在并发场景下如果get(key)返回null,会有歧义——无法区分是"这个key不存在"还是"这个key的value就是null"。在HashMap中可以通过containsKey()来消除歧义(HashMap是单线程的,get和containsKey之间不会有并发修改),但ConcurrentHashMap中get和containsKey是两个独立操作,中间可能有其他线程修改,因此结果不可靠。所以ConcurrentHashMap在设计层面就禁止了null key和null value,从根源上消除歧义。

Q26. ConcurrentHashMap的计数方法是怎么实现的?

答案:JDK8使用baseCount + CounterCell[]的方案,类似LongAdder的思路。addCount()时先尝试CAS更新baseCount,如果CAS失败说明有竞争,则将增量累加到CounterCell数组中的某个槽位(通过线程的探针哈希映射)。最终size()= baseCount + 所有CounterCell的值之和。CounterCell使用@sun.misc.Contended注解避免伪共享。这种分散计数的思路比JDK7的Segment内各自计数再汇总效率更高,高并发下争用更少。

Q27. ConcurrentHashMap JDK7的Segment分段锁机制?

答案:JDK7的ConcurrentHashMap由一个Segment数组和多个HashEntry组成。Segment继承ReentrantLock,默认16个Segment(可通过构造参数concurrencyLevel指定,但会被调整为2的幂)。每个Segment内部是一个小的HashMap(HashEntry数组+链表)。put操作:(1) 第一次hash定位到哪个Segment;(2) 获取该Segment的锁(tryLock或lock);(3) 第二次hash定位到Segment内的桶位;(4) 遍历链表插入或更新。get操作不需要加锁——HashEntry的val、next都是volatile的,保证可见性。缺点:Segment数量固定,并发度上限受限;两次hash定位效率低。

四、Map体系 — 其他Map

Q28. TreeMap的底层数据结构是什么?

答案:TreeMap底层基于红黑树实现,每个节点是Entry<K,V>,包含key、value、left、right、parent和color六个字段。TreeMap保证所有的key按照自然顺序(Comparable)或自定义Comparator排序,增删查操作的时间复杂度均为O(logn)。红黑树的插入和删除需要通过旋转(左旋/右旋)和变色来维持平衡。TreeMap实现了NavigableMap接口,提供了firstEntry()/lastEntry()/floorEntry()/ceilingEntry()/subMap()等丰富的导航方法。

Q29. LinkedHashMap的底层结构和特点?

答案:LinkedHashMap继承自HashMap,在HashMap的Node基础上增加了before和after两个指针,形成一个贯穿所有Entry的双向链表。这个链表维护了元素的插入顺序(默认)或访问顺序(accessOrder=true)。LinkedHashMap重写了HashMap的newNode()和afterNodeAccess()/afterNodeInsertion()等回调方法,在插入和访问时维护链表顺序。由于底层仍是HashMap,所以get/put的时间复杂度仍是O(1),只是多了链表指针的维护开销。

Q30. LinkedHashMap如何实现LRU缓存?

答案:将LinkedHashMap的accessOrder设为true,元素被访问(get/put)后会移到链表尾部,最近访问的在尾部,最久未访问的在头部。然后重写removeEldestEntry()方法返回size() > capacity,当元素数量超过容量时,LinkedHashMap会在afterNodeInsertion()中自动删除链表头部的最老元素。只需少量代码就能实现一个LRU缓存。这也是LeetCode 146题(LRU Cache)的经典Java解法。

Q31. WeakHashMap是什么?使用场景是什么?

答案:WeakHashMap的Entry继承自WeakReference,key是弱引用。当key对象除了WeakHashMap之外没有其他强引用时,GC会自动回收该key,对应的Entry会在下次操作WeakHashMap时被自动清除。典型使用场景是缓存(如Tomcat的 ConcurrentCache),以及需要将对象与元数据关联但不想阻止对象被GC回收的场景(如ThreadLocal的ThreadLocalMap就使用了类似弱引用的方案)。注意WeakHashMap的value仍然是强引用,如果value引用了key可能导致key无法回收。

Q32. IdentityHashMap和普通HashMap有什么区别?

答案:IdentityHashMap使用==(引用相等)来比较key,而HashMap使用equals()。也就是说IdentityHashMap中两个key即使equals为true,只要是不同对象就是不同的key。IdentityHashMap的桶位计算用System.identityHashCode(key)而不是key.hashCode()。典型使用场景:序列化/反序列化中需要跟踪对象引用关系、拓扑排序、实现对象图遍历时防止重复访问。它的设计目的是在需要基于对象身份(而非等价性)进行映射时使用。

Q33. EnumMap的特点和使用场景?

答案:EnumMap是专门为枚举类型key设计的Map,底层用数组实现,数组的索引就是枚举值的ordinal()。因为枚举值的数量固定且已知,所以EnumMap不需要hash计算、不需要处理冲突、不需要扩容,查询和插入都是O(1)且比HashMap更快。内存效率也更高(没有链表/树的额外开销)。使用场景:当key是枚举类型时的映射,如状态机、策略模式中枚举到处理器的映射、配置项枚举映射等。

五、Set体系

Q34. HashSet的底层实现原理?

答案:HashSet底层完全依赖HashMap实现,内部维护一个HashMap<E, Object>,所有元素作为HashMap的key存储,value统一使用一个名为PRESENT的Object常量(private static final Object PRESENT = new Object())。add操作调用map.put(e, PRESENT),如果返回null表示元素不存在则插入成功返回true;否则表示元素已存在返回false。remove操作调用map.remove(o),返回值是否为PRESENT判断是否删除成功。由于HashMap的key不允许重复,HashSet自然保证元素唯一。

Q35. HashSet如何保证元素唯一性?

答案:HashSet依赖元素的hashCode()和equals()两个方法来保证唯一性。插入元素时先计算hashCode确定桶位,然后遍历桶位的链表/红黑树,逐一调用equals比较。如果hashCode相同且equals为true,则认为元素已存在,不会重复插入(用新value覆盖旧value,但因为value都是PRESENT所以实际上没有变化)。如果hashCode不同则直接放入新桶位。因此,如果自定义对象作为HashSet元素,必须正确重写hashCode和equals方法,否则会导致"相同"对象被重复存储或找不到。

Q36. TreeSet的底层实现和排序方式?

答案:TreeSet底层基于TreeMap实现(和HashSet基于HashMap类似),元素作为TreeMap的key存储,value统一为PRESENT。TreeSet内部维护一个NavigableMap,元素按照自然顺序(Comparable)或构造时传入的Comparator排序。由于底层是红黑树,增删查操作时间复杂度均为O(logn)。TreeSet提供了first()/last()/lower()/higher()/subSet()等导航方法。注意TreeSet不允许null元素(因为需要比较),而HashSet允许一个null。

Q37. LinkedHashSet的特点是什么?

答案:LinkedHashSet继承自HashSet,底层使用LinkedHashMap实现。它在HashSet的基础上通过双向链表维护了元素的插入顺序,迭代时按照插入顺序遍历。LinkedHashMap构造时accessOrder默认为false,所以LinkedHashSet只维护插入顺序不维护访问顺序(不像LinkedHashMap可以设置为LRU模式)。LinkedHashSet的时空复杂度与HashSet相同(O(1)查询/插入),但额外消耗链表指针的内存。适合需要去重且需要保持插入顺序的场景。

六、Queue与BlockingQueue

Q38. ArrayBlockingQueue和LinkedBlockingQueue的区别?

答案:ArrayBlockingQueue基于有界数组实现,在构造时必须指定容量,使用一把ReentrantLock控制读写,公平/非公平可选。因为读写共用一把锁,put和take操作互斥,高并发下吞吐量受限。LinkedBlockingQueue基于链表实现,默认容量为Integer.MAX_VALUE(可选有界),使用两把ReentrantLock(putLock和takeLock)分别控制读写,读写可以并行,吞吐量通常更高。但如果使用默认的无界容量,可能导致内存溢出。生产环境建议都显式指定容量。

Q39. PriorityBlockingQueue的特点和实现原理?

答案:PriorityBlockingQueue是一个基于二叉堆(数组实现的完全二叉树)的无界阻塞队列,元素按照自然顺序或自定义Comparator排序,队首是最小(或最大)元素。插入时offer()调用siftUp()将元素上浮到正确位置,取出时take()调用siftDown()将堆顶下沉。扩容时通过自旋CAS保证线程安全,使用一把ReentrantLock。注意PriorityBlockingQueue不保证迭代顺序(迭代是未排序的),只有出队顺序是排序的。适合实现优先级任务队列。

Q40. SynchronousQueue的特点和使用场景?

答案:SynchronousQueue是一个零容量的阻塞队列,每个put操作必须等待一个take操作配对才能完成,反之亦然。它不存储任何元素,直接在生产者和消费者之间传递。内部实现有两种模式:公平模式使用TransferQueue(FIFO链表),非公平模式使用TransferStack(LIFO栈)。Executors.newCachedThreadPool()使用SynchronousQueue作为工作队列,每个新任务都会创建新线程(因为队列无法暂存),空闲线程60秒后回收。

Q41. DelayQueue的实现原理和使用场景?

答案:DelayQueue是一个无界阻塞队列,元素必须实现Delayed接口(getDelay()返回剩余延迟时间,compareTo()定义排序)。底层使用PriorityQueue按延迟时间排序,队首是延迟到期时间最早的元素。take()时如果队首元素还没到期,线程会在available条件变量上等待。当延迟到期时leader线程会取走元素并唤醒下一个等待线程。使用场景:定时任务调度(如Redis中key过期删除)、延迟消息投递、超时订单自动取消、缓存过期清理等。

Q42. 什么是BlockingQueue的四种API形式?

答案:BlockingQueue对每种操作(插入、移除、检查)提供四种形式的API:(1) 抛异常:add()/remove()/element()——队列满/空时抛IllegalStateException/NoSuchElementException;(2) 返回boolean/null:offer()/poll()/peek()——队列满/空时返回false/null而不阻塞;(3) 阻塞等待:put()/take()——队列满/空时阻塞直到操作成功;(4) 超时等待:offer(e, timeout, unit)/poll(timeout, unit)——阻塞指定时间后放弃返回false/null。一般生产者-消费者模式使用put/take形式。

Q43. ConcurrentLinkedQueue的实现原理?

答案:ConcurrentLinkedQueue是一个基于链表的无界非阻塞并发队列,使用CAS(compareAndSwap)实现无锁操作,由head和tail两个volatile节点引用标记队头和队尾。入队offer()时通过CAS将新节点设置为尾节点的next,成功后再尝试更新tail(tail不是每次入队都更新的,存在滞后)。出队poll()时通过CAS更新head。这种"松弛"的tail/head更新策略减少了CAS操作次数,提升了高并发下的性能。适用于高并发但不需要阻塞等待的场景。

七、CopyOnWrite与并发集合

Q44. CopyOnWriteArrayList的实现原理?

答案:CopyOnWriteArrayList采用写时复制(Copy-On-Write)策略。内部使用一个volatile的Object[] array数组存储元素。读操作直接访问array,不需要加锁;写操作(add/set/remove)时先获取ReentrantLock,然后复制一份当前array(Arrays.copyOf()),在新数组上执行修改,最后将array引用指向新数组(利用volatile保证可见性)。读多写少的场景下性能极好(读完全无锁),但写操作开销大(需要复制整个数组),且迭代器使用的是快照,不会反映迭代过程中的修改。

Q45. CopyOnWriteArrayList的迭代器是weakly consistent的,什么意思?

答案:CopyOnWriteArrayList的迭代器在创建时获取当前array的引用(快照),整个迭代过程中遍历的都是这个快照,不会看到迭代创建后的修改。这称为"弱一致性"(weakly consistent)——迭代器不会抛出ConcurrentModificationException,但不保证能看到最新的数据。与之对比:HashMap等集合的迭代器是fail-fast的,如果迭代期间集合被修改会立即抛异常。弱一致性适合"最终一致性即可"的读多写少场景,如事件监听器列表、配置列表等。

Q46. CopyOnWriteArraySet的特点?

答案:CopyOnWriteArraySet底层基于CopyOnWriteArrayList实现,通过addIfAbsent()方法保证元素唯一性——每次add时遍历数组检查元素是否已存在,不存在才插入。由于每次add都需要O(n)遍历检查,写性能较差。适用于读多写少且需要保证元素唯一的场景,如注册监听器列表、白名单/黑名单集合等。注意它不保证equals和hashCode的语义一致性(因为底层是List不是Set),但API层面确实实现了Set接口的去重语义。

Q47. ConcurrentSkipListMap的实现原理?

答案:ConcurrentSkipListMap是基于跳表(Skip List)实现的并发有序Map。跳表是一种概率平衡数据结构,通过多级索引实现O(logn)的查询性能。最底层是按key排序的链表,每往上一层以一定概率(1/2)选取节点建立索引。插入时通过随机数决定节点的层数。与红黑树相比,跳表在并发场景下更友好——插入/删除只需要修改局部指针,不需要全局再平衡(旋转),容易用CAS实现无锁操作。TreeMap不是线程安全的,需要线程安全的有序Map时用ConcurrentSkipListMap。

八、迭代器与fail-fast/fail-safe

Q48. 什么是fail-fast机制?

答案:fail-fast是Java集合的一种错误检测机制,迭代器在遍历过程中如果检测到集合结构被修改(除了迭代器自身的remove/add外),会立即抛出ConcurrentModificationException。实现原理:集合内部维护一个modCount计数器,每次结构性修改(add/remove)都递增modCount;迭代器创建时记录expectedModCount = modCount,每次next()时检查modCount != expectedModCount则抛异常。注意fail-fast不是保证行为,只是一个best-effort的检测机制,不能作为并发控制手段。

Q49. 什么是fail-safe机制?

答案:fail-safe指迭代器在遍历时不受集合修改影响,不会抛ConcurrentModificationException。两种实现方式:(1) 复制集合(如CopyOnWriteArrayList的迭代器遍历的是创建时的数组快照);(2) 弱一致性(如ConcurrentHashMap的迭代器可以反映部分但不保证全部的修改)。fail-safe的代价是无法保证遍历到最新数据,但适合并发场景。注意java.util包下的集合基本都是fail-fast的,java.util.concurrent包下的集合基本都是fail-safe/weakly-consistent的。

Q50. 如何在遍历时安全地删除集合元素?

答案:(1) 使用迭代器的remove()方法——这是最推荐的方式,迭代器会同步更新expectedModCount,不会抛ConcurrentModificationException;(2) 使用Java 8的removeIf(Predicate)——底层也是迭代器remove,但语法更简洁;(3) 使用CopyOnWriteArrayList等并发集合——写时复制机制天然安全但性能有代价;(4) 使用for循环倒序遍历 + list.remove(i)——仅适用于List,且要注意index的调整。绝对不要在增强for循环(for-each)中直接调用集合的remove方法,会触发fail-fast。

九、Collections工具类

Q51. Collections.synchronizedXxx()的实现原理?

答案:Collections.synchronizedList()/synchronizedMap()等工厂方法返回一个装饰器(Decorator)模式的包装类。以SynchronizedList为例,它内部持有一个List<Object> list和一个Object mutex,所有方法(add/get/remove等)都用synchronized(mutex)包裹后委托给原始list。迭代器需要用户手动在synchronized块中创建和遍历,因为包装类的listIterator()方法返回的迭代器不是同步的。相比ConcurrentHashMap等并发集合,synchronized包装类的锁粒度粗(整个对象一把锁),并发度低。

Q52. Collections.unmodifiableXxx()的实现原理?

答案:Collections.unmodifiableList()/unmodifiableMap()返回一个不可修改的视图。以UnmodifiableList为例,它继承自包装类,但所有修改方法(add/set/remove/clear等)都直接抛出UnsupportedOperationException,只保留读取方法(get/size/contains等)。这只是浅层不可变——如果集合中存储的是可变对象,仍然可以通过引用修改对象内容。Java 9+提供了List.of()/Map.of()等工厂方法创建真正的不可变集合。

Q53. Collections.sort()和List.sort()的实现?

答案:JDK7及之前Collections.sort()使用归并排序(MergeSort),稳定排序但需要额外空间。JDK8开始改为TimSort(结合了归并排序和插入排序的混合算法,也是稳定排序)。List.sort(Comparator)是JDK8新增的默认方法,默认实现是通过Object[] a = this.toArray()转为数组排序后再用ListIterator设回。Arrays.sort()对于基本类型使用双轴快排(DualPivotQuicksort),对于对象类型使用TimSort。TimSort的时间复杂度为O(n logn),但对于部分有序数据可以接近O(n)。

十、Stream API与集合操作

Q54. Stream API中map和flatMap的区别?

答案:map()将每个元素映射为一个新值(一对一),返回一个新Stream。flatMap()将每个元素映射为一个Stream,然后将所有Stream"拍平"合并为一个Stream(一对多)。例如:List<List<String>>用map会得到Stream<List<String>>,而用flatMap会得到Stream<String>。典型场景:提取嵌套集合中的元素、分词后合并所有单词。flatMap的函数签名是Function<T, Stream<R>>,而map是Function<T, R>。

Q55. Stream的并行流(parallel stream)原理和注意事项?

答案:并行流底层使用ForkJoinPool.commonPool()(默认线程数=CPU核心数-1),将数据源拆分为多个子任务并行处理。对于ArrayList等实现了Spliterator的集合,数据会被均匀分割。注意事项:(1) 不要在并行流中使用共享可变状态(线程安全问题);(2) 对于少量数据,并行拆分和线程调度的开销可能超过并行收益;(3) 确保操作是无状态且无副作用的;(4) ArrayList/数组等内存连续的数据源并行效果好,LinkedList/Stream.iterate等效果差;(5) 底层用的是commonPool,会影响全局其他并行流任务。

Q56. Collectors.toMap()有哪些常见坑?

答案:(1) value为null时抛NPE——Collectors.toMap()不允许null value,如果有null值会抛NullPointerException,需要改用forEach手动put到HashMap;(2) key重复时抛IllegalStateException——默认的mergeFunction在key冲突时直接抛异常,需要传入合并函数如(v1, v2) -> v1保留旧值或(v1, v2) -> v2保留新值;(3) 返回的Map不保证类型——默认返回HashMap,如果需要保持顺序应指定第四个参数Collectors.toMap(k, v, merge, LinkedHashMap::new)。

Q57. Stream的短路操作有哪些?

答案:短路操作(short-circuiting)指不需要处理所有元素就能得到结果的操作。中间短路操作:limit(n)取前n个元素、takeWhile(predicate)(JDK9)在predicate为false时停止。终端短路操作:findFirst()返回第一个元素、findAny()返回任意一个、anyMatch()有一个匹配就返回true、allMatch()遇到不匹配就返回false、noneMatch()遇到匹配就返回false。在无限流(如Stream.iterate())中必须配合短路操作使用,否则会无限执行。

Q58. Comparator常用的链式调用有哪些?

答案:JDK8为Comparator提供了丰富的链式方法:Comparator.comparing(Person::getAge)按年龄排序;.reversed()逆序;.thenComparing(Person::getName)多级排序(年龄相同时按姓名);.nullsFirst()/nullsLast()处理null值的排序位置;Comparator.comparingInt/Long/Double()避免自动装箱。示例:list.sort(Comparator.comparing(Person::getAge).reversed().thenComparing(Person::getName))表示先按年龄降序,年龄相同按姓名升序。

十一、综合对比与源码细节

Q59. 集合框架的整体继承体系是怎样的?

答案:Java集合框架的顶层接口分为两大体系:Collection(单列集合)和Map(双列键值对)。Collection下有List(有序可重复:ArrayList/LinkedList/Vector)、Set(无序不可重复:HashSet/TreeSet/LinkedHashSet)和Queue(队列:LinkedList/PriorityQueue/ArrayDeque)。Map下有HashMap/TreeMap/LinkedHashMap/Hashtable/ConcurrentHashMap等。JDK6引入了Deque(双端队列)和NavigableMap/Set(导航方法)。concurrent包下有ConcurrentHashMap/ConcurrentSkipListMap/CopyOnWriteArrayList等并发集合。

Q60. 如何选择合适的集合类型?

答案:选择流程:(1) 是否需要键值对?是→Map;否则继续;(2) 是否需要排序?是→TreeSet/TreeMap(自然排序)或优先级队列PriorityQueue;否则继续;(3) 是否需要保持插入顺序?是→LinkedHashMap/LinkedHashSet;否则继续;(4) 是否需要线程安全?是→ConcurrentHashMap/CopyOnWriteArrayList/BlockingQueue;否则继续;(5) 频繁随机访问→ArrayList;频繁头尾操作→ArrayDeque/LinkedList;去重→HashSet;缓存→WeakHashMap。90%的日常开发场景,List选ArrayList,Set选HashSet,Map选HashMap。