ArrayList的特性
实现的接口
ArrayList的类声明如下:1
2public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
轻轻一撇,我们便是可以看出,ArrayList继承自抽象泛型类AbstractList<>,它实现了List接口(Collection集合的List),也拥有RandomAccess/Cloneable/Serializable三个“标注”接口。
同步机制
与Vector相比,ArrayList放弃了同步机制。如果我想要一个支持同步的ArrayList,可以使用Collections工具类中的synchronizedList方法构建一个List:1
List list = Collections.synchronizedList(new ArrayList(...));
时间空间复杂度
ArrayList的get/size/isEmpty等方法的复杂度均为常数,add方法的复杂度为O(n),其余的都是线性复杂度。
ArrayList字段
1 | private static final long serialVersionUID = 8683452581122892189L; |
ArrayList方法分析
trimToSize(缩减容量)
1 | public void trimToSize() { |
该方法将ArrayList容量缩减为实际的容量,也就是说数组中没有多余的空位。值得注意的是,该方法里修改了抽象类AbstractList里的modCount,它的作用是监控外界对数组做出的修改,防止错误的并行发生,可以看作是一个信号量之类的东西。
ensureCapacity(扩大容量)
1 | public void ensureCapacity(int minCapacity) { |
该方法将扩张ArrayList的容量capacity。如果ArrayList仍旧为空(elementData != EMPTY_ELEMENTDATA),默认需要扩张的最少数量为10个(DEFAULT_CAPACITY),如果已经不为空则默认不需要扩张。之后再和参数相比,如果参数中的数字大,就调用ensureExplicitCapacity
扩张。
ensureExplicitCapacity
1 | private void ensureExplicitCapacity(int minCapacity) { |
该方法修改modCount来检测不合法并行,并进一步调用grow
来扩张ArrayList容量。
grow(确定新容量并扩大数组)
1 | private void grow(int minCapacity) { |
该方法中,先尝试将旧容量扩大50%(oldCapacity + (oldCapacity >> 1),如果不够再设为参数指定的大小,如果新容量超过最大值再调用hugeCapacity
来得到合适的大小;最终调用copyOf方法创建一个新容量的ArrayList。
hugeCapacity(计算合适的容量)
1 | private static int hugeCapacity(int minCapacity) { |
该方法返回一个比MAX_ARRAY_SIZE
稍微大一点的MAX_VALUE
。
contains(是否包含某对象)
1 | public boolean contains(Object o) { |
该方法调用indexOf
查找目标对象的下标,下标大于0则说明ArrayList包含该对象。
indexOf(查找下标)
1 | public int indexOf(Object o) { |
如果目标对象为null,就从头往尾去找出第一个null;否则调用对象的equals方法去判断数组中哪个对象equals目标对象。(值得注意的是这里用了equals而不是用==)
lastIndexOf(从尾往头找下标)
原理与indexOf相似,只不过方向调转。
clone(克隆出另一个ArrayList)
1 | public Object clone() { |
先克隆父类,再克隆ArrayList内部的数组,并将克隆ArrayList的modCount重置为0。
toArray(T[] a)(将ArrayList复制到目标数组T[])
1 | public <T> T[] toArray(T[] a) { |
针对目标数组的大小,分别调用Arrays.copyOf
方法或是System.arraycopy
进行复制,前者创建了一个更大的数组以便容纳ArrayList中较多的数据,后者则将ArrayList中的数据复制到目标数组中。
get(获取相应下标的对象)
1 | public E get(int index) { |
该方法先调用rangeCheck
方法检查是否越界,再调用elementData
方法去取到目标对象。
set(更新某个下标的对象并返回旧对象)
1 | public E set(int index, E element) { |
add(往数组尾部插入一个新对象)
1 | public boolean add(E e) { |
该方法先调用ensureCapacityInternal
方法来扩大ArrayList容量,保证内部数组有足够的空间,然后再插入数据。
ensureCapacityInternal(扩大ArrayList容量)
1 | private void ensureCapacityInternal(int minCapacity) { |
remove(移除某个下标对应的对象)
1 | public E remove(int index) { |
该方法在移除某个对象后,会将该对象后面的所有对象全部往前移动一个位置,复杂度稍高(难以想象移除一百亿个数据中第100个带来的后果,需要移动近一百亿个数据!)。
clear(清空ArrayList)
1 | public void clear() { |
将数组内所有变量置为null,对象失去引用,可能会被GC回收。值得注意的是,虽然清空,但是ArrayList的容量不变
,数组大小不变,数组还在,只是数组内的数据失去了意义(身体还在,但已经失去了灵魂)。
addAll(int index, Collection<? extends E> c)(将另一个集合中的数据插入到特定的位置)
1 | public boolean addAll(int index, Collection<? extends E> c) { |
在该方法中,先将原先数据往后移动,空出位置,在将新数据插入到空位之中,复杂度也是稍高。
removeRange(将范围内的数据清空)
removeAll(Collection<?> c)(将指定的数据集合从ArrayList中删除)
1 | public boolean removeAll(Collection<?> c) { |
该方法先检查参数中的数据集合是否为空,如果为空就抛出异常;而后调用batchRemove
来批量删除该数据集合。
batchRemove(保留或删除特定数据集合)
1 | private boolean batchRemove(Collection<?> c, boolean complement) { |
这个方法很巧妙,从一个大的数据集里删除小数据集,遍历大的数据集,如果某个数据符合条件就将它保存在数组前面,最后再清空无效的数据。这里我有个疑问:这个方法里的局部变量elementData就是ArrayList变量elementData么?似乎它们2个都是某个数组对象的引用,它们只是变量,这样一来倒是可以说通,那么,为什么要加关键字final呢?
writeObject(将一个ArrayList实例序列化到一个流中)
readObject(从一个流中反序列化出一个ArrayList实例)
listIterator(返回一个list的iterator)
1 | public ListIterator<E> listIterator(int index) { |
iterator(返回一个iterator)
1 | public Iterator<E> iterator() { |
有个疑问,listIterator和iterator有什么区别?
Itr内部类(类似C++中的iterator)
1 | private class Itr implements Iterator<E> { |
该类实现了Iterator泛型接口,只有5个方法。
该内部类里的hasNext
/next
/remove
方法都很好理解,但forEachRemaining
方法是干什么用的呢?里边还有个Consumer类,是消费者还是什么意思?此处需深入研究。
ListItr内部类
1 | private class ListItr extends Itr implements ListIterator<E> { |
它继承了Itr,并且实现了ListIterator接口。
由此看来,listIterator和iterator的区别是,前者是双向的,而后者只是单向的。
SubList内部类
SubList并不像SubString那样返回一段新的子串;SubList的内容依旧在操作ArrayList的内容,只不过它们的范围不同(神奇的是SubList内部实现和ArrayList差不多,也有listIterator)
forEach
1 | public void forEach(Consumer<? super E> action) { |
该方法和foreach(int a : ArrayList
该方法待深入研究。
spliterator
1 | public Spliterator<E> spliterator() { |
该方法待深入研究,Spliterator到底是什么东西?
ArrayListSpliterator静态内部类
该类待深入研究。
removeIf(Predicate<? super E> filter)
该方法待深入研究。
replaceAll(UnaryOperator operator)
该方法待深入研究。
sort(Comparator<? super E> c)(给ArrayList排序)
1 | @Override |
该方法会调用Arrays.sort
进行排序。
疑问:为什么不能根据返回类型的不同来重载?
至今理解:重载和重写不同,重载是编译时进行,重写是运行时进行。在编译时,编译器根据一种叫“方法签名”的东西来判断两个方法是否相同,而方法签名里并不包括返回类型,所以两个只有返回类型不同的方法在编译器眼里,其实是同一个方法,自然会报错方法重复,所以不能根据返回类型来重载。在运行时,JVM能够根据返回类型来判断两个方法是否相同,所以如果我们耍点小心机的话,可以让JVM正常运行两个只有返回类型不同的方法而不引起冲突。
ArrayList的全部代码
1 | /* |