目录
5、关于ArrayList集合增/删操作慢，查询/修改操作快的分析
1、构造方法
源码分析如下：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* 对象数组
**/
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
/**
* 集合中包含的元素数量
**/
private int size;
/**
* 无参，默认空数组
**/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 传入指定容量大小
**/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 传入指定集合
**/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray(); // 注意传入的集合不能为空，否则转数组时会发生NPE
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
}
小结一下：
- 从ArrayList集合继承和实现的关系来看：ArrayList是List集合的一个实现类。它实现了RandomAccess接口（随机访问），说明ArrayList的查询速度比增删操作快。它实现了Cloneable接口、Serializable接口，说明ArrayList类的实例可克隆，可序列化。
- ArrayList集合在底层是通过维护一个对象数组Object[]来实现存储元素的，且元素是有序、可重复的存储；
- ArrayList集合的构造器有三种传参形式：无参（对象数组为空）、指定容量（指定对象数组大小）、指定集合（集合转成对象数组）。
2、扩容机制
ArrayList集合通过add()方法添加元素，会触发自动扩容操作，当集合的容量不足时会进行自动扩容，源码分析如下：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* 默认初始容量为10
**/
private static final int DEFAULT_CAPACITY = 10;
/**
* 数组最大容量
**/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 以add(E e)方法为例，扩容的关键步骤如下：
**/
public boolean add(E e) {
// 1、元素添加到数组前先进行是否扩容判断（"确保内部容量"）
ensureCapacityInternal(size + 1); // Increments modCount!!
// 7、将该元素存放在数组上，size自加1标识ArrayList集合中元素添加了1个
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 2、若对象数组为空，返回默认初始容量和minCapacity中最大的一个；
// 若不为空，返回minCapacity。而minCapacity = size+1
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //修改计数器
// 3、当minCapacity超过对象数组的大小时，需要进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// 4、扩容后的对象数组大小为原大小的1.5倍
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 5、扩容后对象数组大小出现以下两种情况，则重新赋值扩容后对象数组大小
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 6、将原对象数组按新容量大小拷贝成新的对象数组，实现扩容功能
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
* add(int index, E element)：是将元素插入到指定位置，也需要扩容判断
**/
public void add(int index, E element) {
// 检查是否数组越界
rangeCheckForAdd(index);
// 元素添加到数组前先进行是否扩容判断（"确保内部容量"）
ensureCapacityInternal(size + 1); // Increments modCount!!
// 在指定位置插入元素，要进行数组的移动
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++; //size自增1标识集合添加了一个新元素
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* addAll()：是两个集合求并集，同样需要扩容判断
**/
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
}
小结一下：
- 向ArrayList集合添加新元素之前都要进行判断是否需要扩容，保证有足够的容量存储元素。初始容量默认为10，后续的每次扩容都是按1.5倍进行的（如第2次是15，第三次是22等.....），需要注意ArrayList是不可能无限扩容，新数组容量最大不能超过Integer.MAX_VALUE；
- 若在ArrayList集合指定位置插入新元素，会发生数组的移动操作，当数组容量很大时，插入操作会是一个耗时且效率低的过程！！
3、遍历删除时的陷阱
ArrayList集合有两种删除方法：按索引位置删除的remove(int index)、按对象删除的remove(Object o)，源码分析如下：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* remove(int index)：根据索引位置删除元素，并返回删除的元素
**/
public E remove(int index) {
rangeCheck(index); //检查是否数组越界
modCount++;
E oldValue = elementData(index); //根据对象数组下标返回数组上的元素
//计算因删除导致数组需要移动的元素个数，并通过移动数组实现删除功能
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* remove(int index)：删除指定对象
**/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
// 该方法与按索引位置删除的原理一样，会发生数组移动
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
}
小结一下：
- 使用按索引位置删除元素的remove(int index)方法中，要特别注意数组越界检查，每移除一个元素时size会自减1，而index可能不会变，因此在fori遍历中要时刻保证index不能超过size；
- 使用foreach遍历删除时会使用直接删除对象的remove(Object o)方法，foreach遍历是一颗语法糖 —— 本质上是通过迭代器Iterator实现遍历的，而在Iterator源码中的next()方法中存在 checkForComodification()方法，它会检查预期修改次数expectedModCount 和实际修改次数modCount 是否一致，不一致会报并发修改异常。再反观上面的remove(Object o)方法，每执行异常modCount 会自加1，因此进行下一次遍历时，modCount 肯定不等于expectedModCount了，导致异常发生！！因此不建议使用foreach遍历的方式删除ArrayList集合元素，但可以使用迭代器Iterator及其内部的remove()方法实现遍历删除ArrayList集合元素。
4、迭代器
ArrayList集合的迭代器有Iterator和ListIterator两种，迭代器在集合遍历中至关重要，通过源码分析下Iterator和ListIterator的特点及区别。
Iterator源码分析如下：（Iterator接口方法有 —— hasNext()、next()、remove()、forEachRemaining()等）
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount; //赋值预期修改值
Itr() {}
public boolean hasNext() {return cursor != size;}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification(); //检查modCount是否符合expectedModCount
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() { // 删除方法
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification(); //检查modCount是否符合expectedModCount
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount; //重置expectedModCount
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() { // 检查并发修改异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) { // 遍历方法
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
}
ListIterator源码分析如下：（ListIterator接口方法有 —— hasPrevious()、nextIndex()、previousIndex()、previous()、set()、add()、hasNext()、next()等）
public ListIterator<E> listIterator() {
return new ListItr(0);
}
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
/** 逆向遍历 */
public boolean hasPrevious() {
return cursor != 0;
}
/** 正向遍历，下一个索引位置 */
public int nextIndex() {
return cursor;
}
/** 逆向遍历，下一个索引位置 */
public int previousIndex() {
return cursor - 1;
}
/** 逆向遍历 */
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
/** 修改方法 */
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
/** 添加方法 */
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
List集合和Set集合都有iterator()来获得其迭代器。对List集合也可以通过listIterator()获得其迭代器，两种迭代器在有些时候是不能通用的，Iterator和ListIterator主要区别在以下方面：
（1）、ListIterator有add()方法，可以向List中添加对象，而Iterator不能；
（2）、ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历，Iterator就不可以；
（3）、ListIterator可以定位当前的索引位置，nextIndex()和previousIndex()可以实现，Iterator没有此功能；
（4）、都可实现删除对象，但是ListIterator通过set()方法可以实现对象的修改，Iierator仅能遍历，不能修改。
因此，ListIterator的这些功能，可以实现对ArrayList、LinkedList、Vector等List集合的操作！！！
在ArrayList集合遍历循环时容易引发ConcurrentModificationException异常的方法有：（modCount变量存在的地方都有可能引发并发修改异常！！）
- trimToSize()、clear()、add()、addAll()、remove()等方法用在遍历时；
- Java8新增的方法：forEach()、removeIf()、sort()、replaceAll()等等。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* 修剪集合，去除预留元素的位置，当内存容量吃紧时会使用到它
**/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
/**
* 清空集合元素
**/
public void clear() {
modCount++; //注意：避免引起ConcurrentModificationException
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
* 遍历集合中的所有元素；
**/
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* 删除所有符合条件的元素
**/
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
...;
return anyToRemove;
}
/**
* 按照指定转换规则替换集合中所有的元素
**/
@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
/**
* 集合元素按Comparator比较器规则进行排序
**/
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
}
5、关于ArrayList集合增/删操作慢，查询/修改操作快的分析
元素在ArrayList集合中是按顺序进行存储的，若要在指定位置上插入元素（数组上最后一个元素除外），则会发生数组的移动操作；若删除元素（数组上最后一个元素除外）也会发生数组的移动操作，且最坏的情况是删除第一个元素导致数组所有的元素都要发生移动，因此插入和删除元素都是个耗时且效率低的过程，从上面的源码分析也可看到！！以remove()删除方法为例，用图示说明源码中的因删除导致的数组上其他的元素移动的操作：
而为什么查询和修改操作则快呢？还是看get()方法、set()方法的源码：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* 获取指定位置元素
**/
public E get(int index) {
rangeCheck(index); // 数组越界检查
return elementData(index);
}
/**
* 修改指定位置元素
**/
public E set(int index, E element) {
rangeCheck(index); // 数组越界检查
E oldValue = elementData(index);
// 指定位置更新元素
elementData[index] = element;
return oldValue;
}
E elementData(int index) {
return (E) elementData[index];
}
}
从源码中可知：get()方法、set()方法的核心都是 —— elementData[index]，也就是说基于数组下标去查询元素，加上实现RandomAccess接口，这种方式在数组上很快就能定位到元素，因此查询和修改的操作效率快于增删操作！！！！
6、并发安全问题
众所周知，ArrayList集合是一个非安全操作的集合类，但可以使用java.util下的Vector集合 或J.U.T包下的 CopyOnWriteArrayList集合来替换ArrayList集合，确保List集合在并发环境中能进行安全操作。然而，Java8开始，ArrayList类中新增了一个分割器Spliterator，它能将ArrayList集合按分割规则，分为多段，且多个线程可以并发的执行该集合。
分割器Spliterator接口的API说明：
-
boolean tryAdvance(Consumer<? super T> action);
解释：对当前分割器Spliterator的单个元素执行给定的动作，同时返回 true，否则返回 false；若分割器Spliterator 具有 ORDER特性，则动作会以指定顺序执行。
-
default void forEachRemaining(Consumer<? super T> action) {do { } while (tryAdvance(action));}
解释：线程中对当前分割器Spliterator的每个元素执行给定操作，或者动作抛出异常；若分割器Spliterator 具有 ORDER 特性，则动作会以指定顺序执行。默认的实现会重复调用 tryAdvance() ，直到返回 false。
-
Spliterator<T> trySplit();
解释：如果这个分割器Spliterator可以被分割，返回一个新的分割器Spliterator，如果不能分割，则返回null；在理想情况下（没有遍历）会将元素平均分成两半，允许平衡并行计算，被分割的迭代器只有原来的一半，新的迭代器为另一半；很多背离了此理想状态的情况仍然能够保持高效率，而平衡型较差的分割将会导致并行效率的急剧下降。
-
long estimateSize();
解释：返回会被 forEachRemaining 操作的元素数量的估算值；如果一个分割器Spliterator 具有 SIZED 特性、并且未被遍历或分割，或者此分割器Spliterator 具有 SUBSIZED 特性、并且未被分割遍历，那么返回的一定是在一次完整遍历中遇到的所有元素数量的精确的值，否则，此估算值则会是不精确的，但是一定会随着 trySplit()的调用而越来越小。
-
int characteristics();
解释：返回该分割器Spliterator及其元素的一组特征值，如ORDERED、SIZED、SUBSIZED等。
-
default Comparator<? super T> getComparator() {throw new IllegalStateException();}
解释：如果分割器Spliterator的list是通过Comparator排序的，则返回Comparator；如果是自然排序的 ，则返回null。
-
public static final int ORDERED = 0x00000010; public static final int SORTED = 0x00000004; public static final int SIZED = 0x00000040; public static final int SUBSIZED = 0x00004000;
解释：定义分割器Spliterator的一系列特征值，便于控制和优化分割器Spliterator的使用，如ORDERED表示元素是原始顺序排序的，SORTED表示元素按照某种规则排序的，SIZED表示遍历或分割之前estimesize()返回的一个有限的大小的值，SUBSIZED表示分割之后的调整的大小。
ArrayList集合的spliterator()方法的源码分析如下：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* 在ArrayList中的元素上创建一个后期绑定和fail-fast的分割器Spliterator。
**/
@Override
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
/**
* 内部类ArrayListSpliterator：基于索引的二分分割，延迟初始化Spliterator
**/
static final class ArrayListSpliterator<E> implements Spliterator<E> {
private final ArrayList<E> list;
private int index; // current index, modified on advance/split
private int fence; // -1 until used; then one past last index
private int expectedModCount; // initialized when fence set
/** Create new spliterator covering the given range */
ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
int expectedModCount) {
// 底层对ArrayList进行拷贝后，操作拷贝的ArrayList，保证并发操作安全
this.list = list; // OK if null unless traversed
this.index = origin;
this.fence = fence;
this.expectedModCount = expectedModCount;
}
/** 首次使用时初始化栅栏大小 */
private int getFence() {
int hi; // (a specialized variant appears in method forEach)
ArrayList<E> lst;
if ((hi = fence) < 0) {
if ((lst = list) == null)
hi = fence = 0;
else {
expectedModCount = lst.modCount;
hi = fence = lst.size;
}
}
return hi;
}
/** 基于index的二分分割方法 */
public ArrayListSpliterator<E> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null : // divide range in half unless too small
new ArrayListSpliterator<E>(list, lo, index = mid,
expectedModCount);
}
/** 单独循环方法：遍历当前分割器Spliterator的下一个元素 */
public boolean tryAdvance(Consumer<? super E> action) {
if (action == null)
throw new NullPointerException();
int hi = getFence(), i = index;
if (i < hi) {
index = i + 1;
@SuppressWarnings("unchecked") E e = (E)list.elementData[i];
action.accept(e);
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
}
/** 批量循环方法：遍历当前分割器Spliterator的所有元素，支持并行执行，比forEach()的性能更好 */
public void forEachRemaining(Consumer<? super E> action) {
int i, hi, mc; // hoist accesses and checks from loop
ArrayList<E> lst; Object[] a;
if (action == null)
throw new NullPointerException();
if ((lst = list) != null && (a = lst.elementData) != null) {
if ((hi = fence) < 0) {
mc = lst.modCount;
hi = lst.size;
}
else
mc = expectedModCount;
if ((i = index) >= 0 && (index = hi) <= a.length) {
//相当于重复执行 tryAdvance()
for (; i < hi; ++i) {
@SuppressWarnings("unchecked") E e = (E) a[i];
action.accept(e);
}
if (lst.modCount == mc)
return;
}
}
throw new ConcurrentModificationException();
}
/** 预估当前分割器Spliterator可使用的元素数量 */
public long estimateSize() {
return (long) (getFence() - index);
}
/** 当前分割器Spliterator的特征值 */
public int characteristics() {
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
}
小结一下：
ArrayList的spliterator()方法是支持并行和顺序处理元素的。多线程环境中，trySplit()方法能将原分割器Spliterator的元素接近半数的进行切割，即原Spliterator一半，新的Spliterator一半，以此类推还可以继续分割原Spliterator和新的Spliterator成另外新的分割器Spliterator；tryAdvance()和forEachRemaining()均能在各自的线程中遍历对应Spliterator里的元素；借助estimateSize() 和 characteristics() 可以更好的控制和优化当前Spliterator里的元素操作。
7、其他方法
ArrayList集合的其他方法：（有些方法这里不作详细分析了！）
- public int size() {return size;} // ArrayList集合大小
- public boolean isEmpty() {return size == 0;} // 集合判空
- public boolean contains(Object o) {return indexOf(o) >= 0;} // 集合中是否含有查找元素
- public int indexOf(Object o) {...; return -1} // 查找元素在集合中的位置（顺序查找）
- public int lastIndexOf(Object o) {...; return -1} // 查找元素在集合中的位置（倒序查找）
- public Object clone() {...} // 是一种浅克隆，不会将原集合的元素拷贝到新的集合
- public Object[] toArray() {return Arrays.copyOf(elementData, size);} // ArrayList集合 转 对象数组
- public T[] toArray(T[] a) { ...; System.arraycopy(elementData, 0, a, 0, size); ...; return a; } // ArrayList集合 转 泛型数组，由运行时确定数组类型
重点分析下subList(int fromIndex, int toIndex)方法，它表达的含义是：从指定范围，截取生成新的子集合，有点像String中的substring(from, to)。
源码分析如下：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* subList()：原ArrayList集合截取生成新的List集合
**/
public List<E> subList(int fromIndex, int toIndex) {
// 越界和逻辑检查
subListRangeCheck(fromIndex, toIndex, size);
// 调用内部类SubList
return new SubList(this, 0, fromIndex, toIndex);
}
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
/**
* 内部类SubList，内部实现了自己的add/remove/get/set.../listIterator/spliterator等
**/
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset; // fromIndex
private final int offset; // offset + fromIndex
int size; //截取后集合大小
/**
* SubList构造器，初始化成员属性
**/
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
......;
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
}
}
生成新的子集合subList，可以通过内部类的get/set/add/remove...等方法操作子集合，注意 —— 子集合的相关操作是非线程安全的。
小结
至此，与ArrayList集合特点相关的源码基本都涉及到了，其中最重要的是自动扩容机制，遍历的陷阱，ArrayList集合增删慢/查询快原因，Java8新增的API，ArrayList集合安全操作问题等。不积硅步无以至千里，点滴付出终将有所收获，共同进步 ~