简介
java.util.ArrayList
List 接口的可调整大小的数组实现。
源码中对数组的操作非常精彩，值得学习
数组一旦初始化长度就不可以发生改变
数组结构特点
-
增删慢：每次删除元素，都需要更改数组长度、拷贝以及移动元素位置。
-
查询快：由于数组在内存中是一块连续空间，因此可以根据地址+索引的方式快速获取对应位置上的元素。
继承关系
-
Serializable：序列化
-
Cloneable：克隆
- 实现了 clone 方法
java.util.ArrayList#clone - 实现是 浅拷贝，如果元素是引用类型，拷贝的是引用
- 实现了 clone 方法
-
RandomAccess：随机访问，表明支持快速（通常为恒定时间）随机访问
-
AbstractList：
List接口的随机访问骨干实现 -
AbstractCollection：
Collection接口的骨架实现
RandomAccess
表明支持快速（通常为恒定时间）随机访问
Java 中的遍历会因为随机/顺序访问受到影响
// 创建List集合
List<String> list = new ArrayList<>();
// List<String> list = new LinkedList<>();
int size = 100000;
// 添加10W条数据
for (int i = 0; i < size; i++) {
list.add(i + "a");
}
System.out.println("----通过索引(随机访问:)----");
long startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
// 仅仅为了演示取出数据的时间,因此不对取出的数据进行打印
list.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("随机访问: " + (endTime - startTime));
System.out.println("----通过迭代器(顺序访问:)----");
startTime = System.currentTimeMillis();
Iterator<String> it = list.iterator();
while (it.hasNext()) {
// 仅仅为了演示取出数据的时间,因此不对取出的数据进行打印
it.next();
}
endTime = System.currentTimeMillis();
System.out.println("顺序访问: " + (endTime - startTime));
System.out.println("----通过增强for循环(顺序访问:)----");
startTime = System.currentTimeMillis();
for (String s : list) {
}
endTime = System.currentTimeMillis();
System.out.println("顺序访问: " + (endTime - startTime));
增强for循环是顺序访问，反编译后可以看到class文件中使用的是迭代器
String var9;
for(Iterator var8 = list.iterator(); var8.hasNext(); var9 = (String)var8.next()) {
}
测试结论：
-
while和for在速度上有一些差异
-
LinkedList 在随机访问时，速度下降很明显，原因是每次获取都在链表上遍历
- 参考
java.util.LinkedList#get
- 参考
-
ArrayList 在顺序访问时，速度下降不明显
大数据量时的遍历方法应该判断是否实现了 RandomAccess 方法
public void forEach(List<?> list) {
if (list instanceof RandomAccess) {
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
} else {
for (Object o : list) {
System.out.println(o);
}
}
}
方法清单
构造方法
-
ArrayList()
-
ArrayList(int initialCapacity)
- 可以指定底层数组初始大小
-
ArrayList(Collection<? extends E> c)
public 方法
-
add、addAll
-
clear
-
clone、equals、toString
-
contains、containsAll
-
ensureCapacity
- 确保最小容量，不够时会触发扩容
-
forEach
-
get
-
indexOf、lastIndexOf
-
isEmpty
-
iterator、listIterator
-
parallelStream、stream、spliterator
-
remove、removeAll、removeIf
-
removeIf 中对 BitSet 的用法非常有用
-
几种remove的方法实现都不相同，且没有共同复用的方法，源码值得一读
-
-
replaceAll
- 替换
-
retainAll
- 保留入参集合中相同的元素
-
set
-
size
-
sort
-
subList
- 子列表内数据和父列表是同一份
-
toArray
-
参数为数组的重载方法比较特别，会根据传入的数组大小有不同表现
-
如果入参是数组容量大于List，会将List内容拷贝到数组中，且数组的第size个元素被修改为null
-
如果入参是数组容量小于List，会返回一个新的数组，内容、大小和List相同
-
-
-
trimToSize
- 将底层数组的大小缩小为列表的当前大小（size）
源码分析
默认容量
-
默认10
-
构造器实现源码
-
EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATADEFAULTCAPACITY_EMPTY_ELEMENTDATA用于扩容前判断
-
频繁扩容会导致性能下降，可以通过构造器提前设定好初始容量
扩容机制
-
扩容方法
grow -
每次扩容原大小的1.5倍，需要创建新的数组
-
扩容后不会缩容
-
删除元素时可能会发生元素在数组上的拷贝，但不会创建新的数组
-
扩容时，原数组元素个数小于10时，扩大到10，否则扩大到原大小的1.5倍
- 如果从大小0开始扩容，底层数组大小应该是 0、10、15、22、33 ...
迭代器
java.util.ArrayList.Itr- 代码中的校验，如果不过会抛出并发修改异常 ConcurrentModificationException
- 如果在遍历期间需要删除元素，调用迭代器的 remove 方法（不是List的）可以避免并发修改异常
- 如果使用List.remove方法删除的是倒数第二个元素，不会抛出并发修改异常，但这只是代码实现上的巧合
ArrayList<String> list = ListUtil.toList("a", "b", "c", "d", "e");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String next = iterator.next();
// 如果删除的是倒数第二个元素，巧合地，表现正常
// 否则会抛出异常
if (next.equals("d")) {
list.remove(next); // 错误做法
// iterator.remove(); // 正确做法
}
}
System.out.println(list);
}
并发修改异常
-
iterator方法返回新建的Itr对象时，使用modCount初始化了成员变量expectedModCount -
hasNext方法判断 cursor 和 size 的大小，正常情况下，随着 cursor 的递增，最终会与 size 相等，但是中间如果调用了 ArrayList 的 add 或 remove 方法，size 会被改变，导致 hasNext 判断错误 -
next方法，刚进入方法内就会校验modCount和expectedModCount是否相等，如果不相等，会抛出异常，ArrayList 的 add 或 remove 方法会增加modCount，但是expectedModCount的值没有改变，还是创建Itr对象时的值，所以 next 校验不通过 -
使用
Itr.remove方法会设置expectedModCount和cursor，所以可以通过校验
和 LinkedList 对比
-
本质区别：ArrayList 内部使用的动态数组来存储元素，LinkedList 内部使用的双向链表来存储元素
-
通过索引随机访问元素，ArrayList 快于 LinkedList ，因为 LinkedList 需要遍历，而 ArrayList 根据下标计算无需遍历
-
顺序遍历，ArrayList 因为是数组，所以也不慢
-
add 方法，如果是在最后添加，ArrayList 可能需要扩容，而 LinkedList 因为是双向链表，所以很简单；但是如果是在指定索引添加，LinkedList 需要遍历元素，会有时间消耗
-
remove 方法，与 add 方法同理
线程安全问题
-
ArrayList 不是线程安全的
-
线程安全：
-
java.util.Vector -
Collections.synchronizedList(list) -
CopyOnWriteArrayList：读写分离
-