"/>
侧边栏壁纸
博主头像
PySuper 博主等级

千里之行,始于足下

  • 累计撰写 286 篇文章
  • 累计创建 17 个标签
  • 累计收到 2 条评论

目 录CONTENT

文章目录

Java List

PySuper
2022-10-16 / 0 评论 / 0 点赞 / 14 阅读 / 0 字
温馨提示:
所有牛逼的人都有一段苦逼的岁月。 但是你只要像SB一样去坚持,终将牛逼!!! ✊✊✊

重点

核心实现类对比

类名

底层结构

线程安全

适用场景

扩容策略

ArrayList

动态数组

高频随机访问(商品列表)

默认1.5倍扩容

LinkedList

双向链表

高频增删(消息队列)

无需扩容

Vector

动态数组(同步方法)

是(synchronized)

遗留系统

默认2倍扩容

CopyOnWriteArrayList

动态数组(写时复制)

是(ReentrantLock)

高并发读、低频写(配置中心)

写时复制新数组

关键问题

  • 线程安全改造

    • Collections.synchronizedList():包装普通List为线程安全,需手动同步复合操作

    • CopyOnWriteArrayList:写时复制新数组,读操作无锁,适合读多写少场景

  • 遍历与修改

    • 普通for循环:允许修改元素(通过索引),但需手动维护索引

    • 增强for循环:禁止结构性修改(add/remove),否则抛ConcurrentModificationException

    • 迭代器:通过iterator.remove()安全删除元素,支持双向遍历(ListIterator)

  • 删除操作性能

    • ArrayList.remove(int index):O(n)时间复杂度(需移动元素)

    • LinkedList.removeFirst():O(1)时间复杂度(头尾操作优化)

实现 & 差异

  • ArrayList:动态数组的扛把子

    • 底层结构:基于动态数组实现,初始容量 10,每次扩容 1.5 倍

    • 性能特性:

      • 随机访问快(O(1)),但中间插入/删除需要移动元素(O(n))

      • 适合读多写少场景,例如缓存、配置项存储

    • 线程安全:非线程安全,多线程环境下需手动同步

  • LinkedList:链表的灵活艺术家

    • 底层结构:基于双向链表实现,无容量限制

    • 性能特性:

      • 头尾插入/删除快(O(1)),但随机访问需遍历(O(n))

      • 额外实现 Deque 接口,可作队列/栈使用

    • 适用场景:高频增删操作(如消息队列)、实现栈/双向队列

  • Vector:过时的安全卫士

    • 底层结构:类似 ArrayList,但所有方法通过 synchronized 实现线程安全

    • 缺点:

      • 性能差(同步开销大),扩容策略更激进(默认翻倍)

      • 现代开发中已被 CopyOnWriteArrayList 或 Collections.synchronizedList() 取代

  • CopyOnWriteArrayList:并发的读多写少专家

    • 底层机制:写时复制(COW),写操作加锁复制新数组,读操作无锁。

    • 优点:读性能极高(无锁并发),适合读多写少的高并发场景(如配置中心)

    • 缺点:写操作性能差(需复制整个数组),内存占用高

  • 关键对比与选型建议

特性

ArrayList

LinkedList

Vector

CopyOnWriteArrayList

数据结构

动态数组

双向链表

动态数组

动态数组(写时复制)

线程安全

是(synchronized)

是(ReentrantLock)

适用场景

高频随机访问

高频增删

遗留系统

高并发读、低频写

扩容策略

1.5 倍

无需扩容

2 倍

写时动态复制

冷知识LinkedListget(index) 方法会触发「链表遍历杀」——越靠近中间越慢
避坑指南

  • 🚫 用 ArrayList 遍历删除元素需用迭代器,否则触发 ConcurrentModificationException

  • ✅ 超大数据量优先测试不同实现的耗时(如 LinkedList 头插快,但中间插入可能比 ArrayList 慢)

遍历修改

方式与规则

  • 普通 for 循环

    • ✅ 允许修改:通过索引直接调用 set() 修改元素(如 list.set(i, newValue)

    • ⚠️ 注意:中间插入/删除元素需手动维护索引(可能影响性能)

  • 增强 for 循环(foreach)

    • ❌ 禁止结构性修改:直接调用 add()/remove() 会触发 ConcurrentModificationException

    • ➕ 例外:仅修改对象属性(如 obj.setName())不会触发异常

  • 迭代器(Iterator/ListIterator)

    • ✅ 安全修改:通过 iterator.remove() 删除元素,listIterator.set() 修改当前元素

    • ⚠️ 限制:只能用迭代器自身方法操作,直接调用 List 的增删方法仍会触发异常

  • 线程安全 List(如 CopyOnWriteArrayList)

    • ✅ 无锁遍历:写时复制机制允许遍历时修改(读旧数据,写新副本),无异常

核心结论

  • 单线程场景:优先用普通 for 循环或迭代器操作

  • 高并发场景:直接选 CopyOnWriteArrayList,无脑避免异常

  • 开发规范:禁止在 foreach 中增删元素,Java 8+ 用 removeIf()/replaceAll() 更简洁

底层原理

  • ConcurrentModificationException 根源:迭代器内部记录修改次数(modCount),与集合实际修改次数不一致时触发[1,2]

  • CopyOnWriteArrayList 通过复制新数组实现无锁读,但写操作性能较低(适合读多写少场景)

删除元素

快速删除指定下标元素

  • ArrayList 删除指定下标元素

    • 方法:直接调用 remove(int index)。

    • 时间复杂度:O(n)(需移动后续元素)。

    • 优化建议:高频删除中间元素可改用 LinkedList,或反向遍历避免索引错位。

  • LinkedList 删除指定下标元素

    • 方法:调用 remove(int index)。

    • 时间复杂度:O(n)(需遍历链表)。

    • 头尾优化:用 removeFirst()/removeLast() 可将时间降至 O(1)。

  • 线程安全场景

    • CopyOnWriteArrayList:调用 remove(int index) 会创建新数组,适合读多写少,但写性能差(O(n))。

  • 遍历时删除

    • 安全方法:使用迭代器的 Iterator.remove(),避免 ConcurrentModificationException。

  • 性能对比与选型

操作

ArrayList

LinkedList

CopyOnWriteArrayList

按索引删除

O(n)

O(n)

O(n)

适用场景

随机访问

头尾删除

高并发读场景

  • 面试核心点

    • ArrayList 和 LinkedList 按索引删除的时间复杂度均为 O(n),但 LinkedList 头尾删除可优化至 O(1)

    • 高频删除优先选 LinkedList 或反向遍历 ArrayList

    • 线程安全场景权衡写性能,选 CopyOnWriteArrayList 或 ConcurrentLinkedDeque

线程安全

为什么 ArrayList 不是线程安全的,具体来说是哪里不安全?

ArrayList 线程安全吗?为什么?把 ArrayList 变成线程安全有哪些方法?

非线程安全

  • 非线程安全:默认设计不支持多线程并发操作

  • 并发风险:

    • 数据不一致:多线程同时修改导致元素丢失或重复

    • 数组越界:动态扩容时并发操作可能触发非法索引访问

    • ConcurrentModificationException:迭代过程中发生结构性修改

不安全的点

  • 非原子操作引发数据竞争

    • size 递增非原子性:size++ 操作实际由读取旧值、计算新值、写入新值组成,多线程同时执行可能导致最终结果小于实际增加次数

    • 元素存储覆盖:多个线程在相同索引位置执行 elementData[i] = e,后写入的线程会覆盖前者的数据

  • 动态扩容竞态条件

    • 重复扩容数据丢失:多个线程同时检测到容量不足,各自创建更大的新数组并复制数据,最终仅保留最后一个线程的扩容结果

    • 扩容间隙越界风险:线程 A 扩容过程中,线程 B 仍使用旧容量索引插入数据,触发数组越界异常

  • 内存可见性问题

    • 脏读现象:线程修改数组元素后未及时同步到主内存,其他线程可能读取到修改前的旧数据

    • 失效状态传播延迟:扩容后的新数组引用更新未使用同步机制,导致部分线程继续访问旧数组

  • 迭代器快速失败机制缺陷

    • 并发修改检测失效:迭代器的 expectedModCount 与集合的 modCount 在多线程环境下无法保持同步

    • 结构变更暴露风险:迭代过程中其他线程删除元素,可能导致当前迭代器访问到已被移除的索引位置

  • 复合操作非原子性

    • 检查-执行间隙干扰:如 if(!contains(e)) { add(e) } 操作中,条件判断与添加动作之间可能被其他线程插入新操作

    • 中间状态不一致:扩容过程中新旧数组交替阶段,其他线程可能读取到仅部分数据迁移完成的中间数组

  • 指令重排序干扰

    • 初始化顺序错乱:对象初始化过程中,JVM 优化可能打乱 elementData 赋值与 size 初始化的顺序

    • 写操作乱序执行:元素赋值与 size 更新的顺序被重排,导致其他线程看到 size 变化但对应位置数据未更新

线程安全改造

  • Collections.synchronizedList

    • 实现方式:通过装饰器模式对所有方法添加对象级锁

    • 特点

      • 读写操作均加锁,适用于中等并发场景

      • 迭代器遍历需显式同步

      • 组合操作需外部同步控制

  • CopyOnWriteArrayList

    • 核心机制:写操作复制新数组,读操作访问旧数组

    • 优势

      • 无锁读操作,适合读多写少场景

      • 数据最终一致性保证

    • 缺陷

      • 内存占用随写操作次数线性增长

      • 不适用实时性要求高的场景

  • 手动同步锁

    • 实现要点

      • 自定义锁对象控制关键代码段

      • 缩小同步代码块范围提升性能

    • 适用场景:

      • 需要精细化控制锁粒度

      • 高并发环境下的特定操作优化

  • Vector(遗留方案)

    • 特点

      • 方法级同步锁导致性能瓶颈

      • 扩容策略与 ArrayList 不同(默认 2 倍 vs 1.5 倍)

  • 使用建议:仅用于兼容旧系统,新项目避免使用

方案对比与选型

  • 性能维度

    • 高频读:CopyOnWriteArrayList > 手动锁 > synchronizedList > Vector

    • 高频写:手动锁 > synchronizedList > Vector > CopyOnWriteArrayList

  • 内存维度:CopyOnWriteArrayList 内存消耗最大

  • 开发成本:synchronizedList 实现成本最低

底层原理

  • JVM 内存模型

    • 未同步操作可能违反 happens-before 原则

    • volatile 关键字保证可见性但无法解决原子性问题

  • 锁优化技术

    • 偏向锁 → 轻量级锁 → 重量级锁的升级过程

    • 自旋锁减少线程切换开销

  • 硬件支持

    • CAS 操作依赖 CPU 的 cmpxchg 指令

    • 内存屏障保证指令执行顺序

扩容机制

ArrayList 的扩容机制

  • 扩容机制核心流程

    • 当添加元素导致数组容量不足时触发扩容

    • 新容量计算规则:原始容量的 1.5 倍(位运算实现:oldCapacity + (oldCapacity >> 1))

    • 特殊场景处理:若计算值仍不满足需求,则直接扩容至所需的最小容量

  • 执行步骤分解

    • 创建新数组:使用 Arrays.copyOf() 生成扩容后的新数组

    • 数据迁移:将旧数组元素全量复制到新数组

    • 引用切换:将内部存储的数组引用指向新数组对象

  • 性能关键点

    • 扩容时间复杂度:O(n)(与元素数量线性相关)

    • 最佳实践:初始化时预估容量避免多次扩容

    • 内存开销:每次扩容产生旧数组的垃圾对象(可能引发 GC)

  • 容量限制机制

    • 最大数组长度限制为 Integer.MAX_VALUE - 8

    • 超过限制时可能抛出 OutOfMemoryError

    • 虚拟机的数组对象头开销导致实际最大值小于理论值

  • 特殊初始化场景

    • 默认构造器创建的空数组(DEFAULTCAPACITY_EMPTY_ELEMENTDATA)

    • 首次添加元素时直接扩容至默认容量 10

    • 显式指定初始容量为 0 时将使用特殊空数组标记

Arraylist & LinkedList

对比

  • 底层数据结构

    • ArrayList:基于动态数组(Dynamic Array)实现,内存空间连续

    • LinkedList:基于双向链表(Doubly Linked List)实现,节点包含前后指针

  • 访问性能

    • ArrayList随机访问时间复杂度O(1)

    • LinkedList随机访问时间复杂度O(n)

  • 实测对比:10万次索引访问ArrayList耗时2ms级,LinkedList耗时秒级

  • 插入/删除操作

    • LinkedList头尾操作时间复杂度O(1)

    • ArrayList尾部插入时间复杂度O(1),非尾部操作平均O(n)

    • 实测对比:头部插入1万元素LinkedList耗时毫秒级,ArrayList耗时数十毫秒

  • 内存占用

    • ArrayList仅存储实际数据

    • LinkedList每个节点额外存储两个指针引用

    • 存储整型数据时LinkedList内存消耗约为ArrayList的5-7倍

  • 扩容机制

    • ArrayList默认扩容策略为原容量的1.5倍

    • LinkedList无需预分配内存空间

  • 线程安全性

    • 两者均为非线程安全实现

    • 多线程环境下需使用同步控制

  • 应用场景

    • ArrayList适用场景:

      • 读多写少的配置类数据

      • 需要缓存友好的连续内存访问

    • LinkedList适用场景:

      • 频繁首尾操作的队列场景

      • 需要实现双向队列功能

应用场景

ArrayList

  • 高频随机访问需求

    • 基于动态数组结构,通过索引访问元素时间复杂度为 O(1)

    • 典型场景:电商商品信息存储、数据分析中的快速遍历统计

  • 尾部操作密集型任务

    • 尾部插入/删除时间复杂度为 O(1)

    • 典型场景:日志追加存储、传感器数据顺序采集

  • 内存敏感型场景

    • 连续内存空间存储,无额外指针开销

    • 典型场景:百万级配置参数存储、移动端内存限制场景

LinkedList

  • 频繁中间/头部操作

    • 插入/删除时间复杂度为 O(1)

    • 典型场景:聊天消息队列、文本编辑器撤销链

  • 特殊数据结构实现

    • 原生支持双端队列操作

    • 典型场景:任务调度插队系统、LRU 缓存算法

  • 动态伸缩需求场景

    • 无需预分配内存,按需动态增长

    • 典型场景:网络数据包接收、游戏事件处理器链

选型决策

  • 选择 ArrayList 的明确条件

    • 主要操作为索引访问或尾部增删

    • 数据规模可预估且波动范围较小

    • 需要利用 CPU 缓存空间局部性原理

  • 选择 LinkedList 的明确条件

    • 主要操作为非尾部位置增删

    • 需要实现队列/栈等数据结构

    • 内存资源充足但需规避扩容开销

性能优化

  • ArrayList 使用禁忌

    • 避免在循环中频繁执行 contains() + add() 组合操作

    • 初始化时通过 ensureCapacity() 预分配空间

  • LinkedList 使用禁忌

    • 避免通过索引遍历(时间复杂度 O(n^2))

    • 警惕超大数据量下的内存占用激增问题

组合使用

  • 冷热数据分离存储

    • 高频修改数据使用 LinkedList,只读数据使用 ArrayList

  • 分段混合存储

    • 将大数据集拆分为多个 ArrayList 子块,用链表维护块关系

  • 动态切换机制

    • 根据运行时监控数据自动切换 List 实现类型

List & CopyonWriteArraylist

线程安全的 List, CopyonWriteArraylist 是如何实现线程安全的

写时复制核心机制

  • 所有写操作前先复制当前数组生成新副本

  • 修改操作仅在新副本上执行,完成时通过原子操作替换数组引用

  • 读操作始终访问原数组,实现读写操作物理隔离

锁控制实现

  • 使用 ReentrantLock 保证写操作原子性

  • 锁粒度控制在修改操作全过程(包含复制、修改、替换引用)

  • 确保同一时刻只有一个线程执行写操作

内存可见性保障

  • 数组引用声明为 volatile

  • 新数组引用替换后对所有线程立即可见

  • 写操作完成后旧数组立即不可变

迭代器弱一致性

  • 迭代器基于创建时的数组快照工作

  • 遍历过程中不会检测并发修改

  • 可能访问到历史版本数据但保证结构完整性

性能特征

  • 读操作完全无锁,时间复杂度 O(1)

  • 写操作时间复杂度 O(n)(需完整复制数组)

  • 单次写操作内存开销与数据量成正比

适用场景边界

  • 最佳场景:读操作频率高于写操作 100 倍以上

  • 禁忌场景:高频写入大数据量集合(如实时日志记录)

  • 典型应用:白名单/黑名单配置、事件监听器列表

ArrayList & Vector

初始化

  • ArrayList 空构造函数是构造的空的集合,在添加元素时初始化默认为 10 容量的数据

  • Vector 空构造函数初始就分配了 10 个长度的空间

线程安全性

  • ArrayList 是非线程安全的

  • Vector 通过 synchronized 关键字实现了方法级别的同步

  • 在多线程场景中直接使用 Vector 更安全,但会带来额外性能开销

扩容机制

  • Vector 默认扩容为原容量的 2 倍,支持自定义扩容增量

  • ArrayList 默认扩容为原容量的 1.5 倍,且不支持自定义策略

  • 两者的动态扩容均会导致内存占用增加,但 Vector 的激进扩容可能更适合存储大量数据的场景

性能差异

  • ArrayList 无同步锁,单线程下操作效率更高

  • Vector 的同步机制会导致多线程竞争时的性能下降。若需线程安全且高效,建议使用同步包装类或并发容器

历史背景

  • Vector 是 Java 早期基于 Dictionary 类实现的遗留类

  • ArrayList 是 Java 1.2 引入的现代化集合框架组件,设计更轻量且符合接口抽象原则

适用场景

  • ArrayList:单线程环境、频繁随机访问、无需同步的高性能场景

  • Vector:需线程安全且性能要求不高的多线程场景。实际开发中更推荐通过并发包实现线程安全

0
  1. 支付宝打赏

    qrcode alipay
  2. 微信打赏

    qrcode weixin

评论区