Java ArrayList

Java ArrayList 详细学习笔记目录概述与核心特性底层数据结构核心源码深度解析构造方法add 方法 (扩容机制)get/set 方法remove 方法迭代器与 Fail-Fast扩容机制详解性能分析与复杂度ArrayList vs LinkedList常见面试题与陷阱最佳实践1. 概述与核心特性1.1 什么是 ArrayListArrayList是 Java 集合框架中List接口的最主要实现类。它是一个动态数组底层使用数组存储元素支持自动扩容。1.2 核心特性有序性: 元素按照插入顺序存储可以通过索引下标访问。可重复: 允许存储重复元素。允许 null: 可以存储null值。非线程安全: 多线程环境下需手动同步或使用CopyOnWriteArrayList。随机访问: 支持O ( 1 ) O(1)O(1)时间复杂度的随机访问。1.3 继承体系Serializable (可序列化) Cloneable (可克隆) RandomAccess (标记接口支持快速随机访问) ↓ AbstractList ↓ ArrayList2. 底层数据结构2.1 核心字段// 底层存储数组 (JDK 1.8)transientObject[]elementData;// 实际存储的元素个数privateintsize;// 默认初始容量privatestaticfinalintDEFAULT_CAPACITY10;// 空数组常量 (用于无参构造实现懒加载)privatestaticfinalObject[]EMPTY_ELEMENTDATA{};2.2 为什么是transient?elementData被标记为transient意味着它不会被序列化。原因: 数组的实际容量 (elementData.length) 可能大于实际元素个数 (size)。序列化时只序列化size个有效元素可以节省空间并提高序列化/反序列化效率。实现:ArrayList自定义了writeObject和readObject方法只序列化有效数据。3. 核心源码深度解析3.1 构造方法无参构造publicArrayList(){this.elementDataDEFAULTCAPACITY_EMPTY_ELEMENTDATA;// 指向空数组常量}特点:懒加载。此时elementData为空直到第一次add元素时才初始化数组。指定初始容量publicArrayList(intinitialCapacity){if(initialCapacity0){this.elementDatanewObject[initialCapacity];}elseif(initialCapacity0){this.elementDataEMPTY_ELEMENTDATA;}else{thrownewIllegalArgumentException(Illegal Capacity: initialCapacity);}}特点: 立即分配内存。如果预估数据量较大推荐使用此构造方法避免频繁扩容。集合构造publicArrayList(Collection?extendsEc){elementDatac.toArray();if((sizeelementData.length)!0){// 防御性编程如果 c.toArray 返回空数组但 c 不为空极少见重置if(c.getClass()ArrayList.class){elementData(Object[])elementData;}else{elementDataArrays.copyOf(elementData,size,Object[].class);}}else{this.elementDataEMPTY_ELEMENTDATA;}}3.2 add 方法 (扩容机制)添加元素到末尾publicbooleanadd(Ee){ensureCapacityInternal(size1);// 检查容量elementData[size]e;// 赋值并增加 sizereturntrue;}容量检查逻辑privatevoidensureCapacityInternal(intminCapacity){// 如果是默认空数组初始容量至少为 DEFAULT_CAPACITY (10)if(elementDataDEFAULTCAPACITY_EMPTY_ELEMENTDATA){minCapacityMath.max(DEFAULT_CAPACITY,minCapacity);}ensureExplicitCapacity(minCapacity);}privatevoidensureExplicitCapacity(intminCapacity){modCount;// 修改次数计数用于 fail-fast// 如果最小需求容量 当前数组长度触发扩容if(minCapacity-elementData.length0)grow(minCapacity);}扩容核心逻辑growprivatevoidgrow(intminCapacity){intoldCapacityelementData.length;// 新容量 旧容量 (旧容量 1) 1.5 倍intnewCapacityoldCapacity(oldCapacity1);// 如果 1.5 倍还不够直接使用 minCapacityif(newCapacity-minCapacity0)newCapacityminCapacity;// 防止溢出 (Integer.MAX_VALUE)if(newCapacity-MAX_ARRAY_SIZE0)newCapacityhugeCapacity(minCapacity);// 复制数组elementDataArrays.copyOf(elementData,newCapacity);}3.3 get/set 方法// 随机访问 O(1)publicEget(intindex){rangeCheck(index);// 边界检查returnelementData(index);}publicEset(intindex,Eelement){rangeCheck(index);EoldValueelementData(index);elementData[index]element;returnoldValue;}特点: 直接通过下标访问数组速度极快。3.4 remove 方法publicEremove(intindex){rangeCheck(index);modCount;EoldValueelementData(index);// 计算需要移动的元素个数intnumMovedsize-index-1;if(numMoved0){// 核心System.arraycopy 移动后续元素// 源数组源位置目标数组目标位置移动长度System.arraycopy(elementData,index1,elementData,index,numMoved);}elementData[--size]null;// 帮助 GC清除尾部的引用returnoldValue;}特点: 删除中间元素需要移动后续所有元素时间复杂度O ( n ) O(n)O(n)。3.5 迭代器与 Fail-FastArrayList的迭代器是Fail-Fast(快速失败) 的。原理:ArrayList内部有一个modCount变量每次结构修改增删都会 1。迭代器创建时记录expectedModCount modCount。每次next()或remove()时检查modCount expectedModCount。如果不等抛出ConcurrentModificationException。陷阱:ListStringlistnewArrayList(Arrays.asList(A,B,C));IteratorStringitlist.iterator();while(it.hasNext()){Stringsit.next();if(B.equals(s)){list.remove(s);// 错误直接调用 list.remove 会修改 modCount导致迭代器下次检查失败}}正确做法: 使用迭代器的remove()方法或使用 Java 8 的removeIf。list.removeIf(s-B.equals(s));4. 扩容机制详解4.1 触发条件当size 1 elementData.length时触发。4.2 扩容倍数公式:newCapacity oldCapacity (oldCapacity 1)结果: 约为1.5 倍。原因: 平衡空间利用率与扩容频率。1.5 倍是一个经验值既能减少扩容次数又不会造成过多的内存浪费。4.3 扩容成本时间:O ( n ) O(n)O(n)需要创建新数组并复制旧数据 (System.arraycopy)。空间: 旧数组暂时无法回收直到新数组创建完成。4.4 优化建议如果知道大概的数据量务必在构造时指定容量// 避免扩容 3-4 次ListStringlistnewArrayList(1000);5. 性能分析与复杂度操作时间复杂度说明get / setO ( 1 ) O(1)O(1)数组随机访问add (尾部)O ( 1 ) O(1)O(1)均摊复杂度 (偶尔触发扩容O ( n ) O(n)O(n))add (指定位置)O ( n ) O(n)O(n)需移动后续元素remove (指定位置)O ( n ) O(n)O(n)需移动后续元素remove (尾部)O ( 1 ) O(1)O(1)无需移动contains / indexOfO ( n ) O(n)O(n)线性遍历扩容O ( n ) O(n)O(n)数组复制空间复杂度:O ( n ) O(n)O(n)但实际占用空间可能大于n nn(因为预留了扩容空间)。6. ArrayList vs LinkedList特性ArrayListLinkedList底层动态数组双向链表随机访问快(O ( 1 ) O(1)O(1))慢 (O ( n ) O(n)O(n))头部插入/删除慢 (O ( n ) O(n)O(n))快(O ( 1 ) O(1)O(1))尾部插入/删除快(O ( 1 ) O(1)O(1))快(O ( 1 ) O(1)O(1))中间插入/删除慢 (O ( n ) O(n)O(n))慢 (O ( n ) O(n)O(n)) (需先遍历)内存占用低 (仅存储数据)高 (每个节点需存 prev, next)缓存友好性高(连续内存)低 (内存分散)线程安全否否结论:90% 的场景首选ArrayList(读多写少缓存友好)。仅在频繁在头部或中间进行插入删除且数据量极大时考虑LinkedList。7. 常见面试题与陷阱Q1: ArrayList 的扩容机制是怎样的答:初始容量为 0 (懒加载)。第一次 add 时扩容为 10。后续扩容为原容量的 1.5 倍 (old old 1)。如果 1.5 倍仍不足则直接使用所需容量。扩容涉及Arrays.copyOf成本较高。Q2: 为什么 ArrayList 的elementData是transient答:为了优化序列化。数组长度可能大于实际元素个数transient阻止默认序列化转而使用自定义的writeObject只序列化有效元素 (size个)节省空间。Q3: 如何在遍历 ArrayList 时安全地删除元素答:使用迭代器的remove()方法。使用 Java 8 的removeIf()方法。不要在foreach循环中直接调用list.remove()会抛出ConcurrentModificationException。Q4: ArrayList 是线程安全的吗如何解决答:不安全。多线程下可能导致数据覆盖或ArrayIndexOutOfBoundsException。解决方案:Collections.synchronizedList(new ArrayList())(性能一般全表锁)。CopyOnWriteArrayList(写时复制适合读多写少)。手动加锁 (synchronized或ReentrantLock)。Q5:new ArrayList(Arrays.asList(A, B))能 add 元素吗答:不能。Arrays.asList返回的是Arrays.ArrayList(内部类)它是固定长度的不支持add/remove。解决:new ArrayList(Arrays.asList(A, B))创建一个新的可变 ArrayList。8. 最佳实践预估容量: 如果知道数据量构造函数指定容量避免扩容。ListUserusersnewArrayList(1000);避免在循环中扩容: 尽量一次性添加数据或使用ensureCapacity预分配。遍历删除: 使用removeIf或迭代器。list.removeIf(item-item.isExpired());转数组: 使用list.toArray(new String[0])(JDK 6)让 JVM 优化数组分配。String[]arrlist.toArray(newString[0]);空列表返回: 返回空列表时优先返回Collections.emptyList()而不是new ArrayList()节省内存。if(list.isEmpty())returnCollections.emptyList();附录源码关键类图ArrayList ├── elementData: Object[] (底层数组) ├── size: int (元素个数) ├── modCount: int (修改计数) ├── add(E e) ├── get(int index) ├── remove(int index) ├── ensureCapacityInternal(int) └── grow(int)