ArrayList和LinkedList到底选哪个？——Java集合框架全景

Java集合框架是面试的常规考点，但大数据面试有自己的侧重——面试官不会让你实现一个LinkedList，而是问你在Flink/Spark代码中应该选什么集合、为什么不要在热路径上用TreeMap、什么时候该用数组代替List。在某知名出海硬件品牌做Spark UDF调优时，把一个用LinkedList存储中间结果的UDF改成ArrayList后，执行时间减少了40%——因为LinkedList的随机访问是O(N)而且缓存不友好。

List家族对比

集合	底层结构	随机访问	头部插入	尾部插入	内存占用	大数据推荐度
ArrayList	动态数组	O(1)	O(N)	O(1)均摊	紧凑（连续内存）	首选
LinkedList	双向链表	O(N)	O(1)	O(1)	大（每节点额外指针）	几乎不用
int[]	原生数组	O(1)	不支持	不支持	最小	性能极致场景

为什么大数据场景几乎不用LinkedList？三个原因：① 随机访问O(N)——遍历到第i个节点要从头走；② 内存不连续——CPU缓存预取失效，每次访问节点都可能Cache Miss；③ 内存开销大——每个节点多两个指针（prev+next），存100万个Long用ArrayList需要约8MB，LinkedList需要约40MB。

Map家族对比

集合	底层结构	get/put	有序	线程安全	大数据场景
HashMap	数组+链表+红黑树	O(1)	否	否	最常用（单线程场景）
ConcurrentHashMap	分段锁+CAS	O(1)	否	是	多线程场景
TreeMap	红黑树	O(logN)	Key有序	否	需要排序时用
LinkedHashMap	HashMap+双向链表	O(1)	插入序	否	需要保持插入顺序

Set家族和特殊集合

// HashSet：底层就是HashMap（Value用一个dummy Object）
// 去重用，O(1)查找
Set<String> uniqueEvents = new HashSet<>();
uniqueEvents.add('page_view');
 
// BitSet：用位数组表示集合，极省内存
// 适合大量整数的去重/判断
BitSet bitSet = new BitSet(10_000_000);  // 10M个位 = 1.2MB
bitSet.set(userId);  // 标记userId存在
bitSet.get(userId);  // 判断userId是否存在
// 10M个用户ID去重：HashSet需要约200MB，BitSet只要1.2MB
 
// EnumSet/EnumMap：枚举类型的专用集合，极快
// 适合事件类型、状态机等枚举场景
EnumSet<EventType> types = EnumSet.of(EventType.CLICK, EventType.VIEW);
 
// 大数据框架专用集合：
// Spark: ExternalAppendOnlyMap（可溢出到磁盘的Map）
// Flink: 内部用了大量ObjectOpenHashMap（fastutil库）
// 这些比JDK集合更省内存且支持堆外溢出

CPU缓存友好性——为什么连续内存更快？

# CPU缓存层级
# L1 Cache: 64KB, 延迟 ~1ns
# L2 Cache: 256KB, 延迟 ~3ns
# L3 Cache: 8MB, 延迟 ~10ns
# 主内存: 延迟 ~100ns
 
# ArrayList（连续内存）遍历：
# CPU读取第1个元素时，L1 Cache会预取后续64字节
# 如果元素是int（4字节），一次预取就覆盖了16个元素
# 后续15次访问都是Cache Hit（1ns）
#
# LinkedList（散布内存）遍历：
# 每个节点在堆中随机分布
# CPU预取的64字节大概率不包含下一个节点
# 每次访问大概率是Cache Miss（100ns）
#
# 差距：1ns vs 100ns = 100倍！
# 大数据处理亿级数据时，这个差距累积起来非常可观

实战经验：LinkedList改ArrayList提升40%

在某知名出海硬件品牌，有一个Spark UDF接收一个用户的事件列表，按时间排序后提取最近10个事件。原来用LinkedList存储中间结果（想着方便头部插入），然后遍历取前10个。

问题：LinkedList的遍历是O(N)且缓存不友好，处理500万用户（每人平均200个事件）时非常慢。

优化：改成ArrayList存储，用Collections.sort()排序（ArrayList的排序利用了数组的连续内存，比链表排序快很多），然后subList(0, 10)取前10个。

效果：UDF执行时间从5分钟降到3分钟，减少40%。核心收益来自CPU缓存友好性——ArrayList的连续内存让遍历和排序都更快。

面试高频追问

追问一：ArrayList的扩容机制是什么？

默认初始容量10，每次扩容到原来的1.5倍（oldCapacity + oldCapacity >> 1）。扩容时创建新数组并复制所有元素（System.arraycopy），代价是O(N)。如果能预估元素数量，用new ArrayList<>(expectedSize)避免扩容。大数据场景中处理已知大小的数据集时，一定要指定初始容量。

追问二：Collections.unmodifiableList()和List.of()有什么区别？

unmodifiableList()返回的是一个视图——对原始List的修改会反映到视图中。List.of()（JDK 9+）返回的是真正不可变的List——任何修改尝试都抛UnsupportedOperationException。大数据场景中传递只读数据（比如配置列表）推荐用List.of()，更安全。

追问三：大数据处理中什么时候该用原生数组？

当你需要存储大量基本类型（int/long/double）时。Java集合只能存对象（Integer/Long/Double），有装箱开销。100万个int用ArrayList需要约16MB（对象头+包装），用int[]只需要4MB。Flink和Spark内部大量使用原生数组来存储中间数据，就是为了避免装箱开销。

总结

集合框架面试讲清楚三个维度：① 各集合的底层结构和时间复杂度（ArrayList连续数组O(1)随机访问、LinkedList链表O(N)随机访问、HashMap O(1)查找）；② CPU缓存友好性（连续内存比散布内存快100倍，ArrayList远优于LinkedList）；③ 大数据场景选型（优先ArrayList/HashMap、多线程用ConcurrentHashMap、基本类型用原生数组、大量整数去重用BitSet）。能讲出LinkedList改ArrayList提升40%的实际案例，面试官会觉得你注意过底层性能细节。

下一篇聊Java异常机制：try-catch写在循环里还是循环外？大数据作业的异常处理策略。

你们大数据代码里最常用什么集合？有没有踩过集合选型的坑？评论区聊聊～

关注「Wood聊大数据」| 9年大数据老兵，聊技术、聊职场、聊成长