基本概念
什么是ArrayList？
该类也是实现了List的接口，实现了可变大小的数组，随机访问和遍历元素时，提供更好的性能。该类也是非同步的，在多线程的情况下不要使用。ArrayList 增长当前长度的50%，插入删除效率低，因为会引起其他元素位置改变。
ArrayList继承关系
继承关系图
ArrayList特性
- 优点
1、查找速度快，因为可以根据索引获取元素。
2、无需关心大小，动态改变大小。 - 缺点
1、插入删除效率低，因为会引起其他元素位置改变。
2、非线程安全的，在多线程的情况下不要使用。
ArrayList用法
创建一个HelloWorld程序
//初始化
ArrayList<String> list = new ArrayList<>();
//添加元素
for (int i = 0; i < 5; i++) {
list.add("test");
}
System.out.println(Arrays.toString(list.toArray(new String[0])));
//删除元素
list.remove(0);
System.out.println(Arrays.toString(list.toArray(new String[0])));
//修改元素
list.set(0, "hahah");
System.out.println(Arrays.toString(list.toArray(new String[0])));
//随机访问元素
System.out.println(list.get(2));
ArrayList源码解析
以下源码基于JDK1.8
ArrayList成员变量解析
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 默认空数组（用于构造函数初始化）
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 默认空数组（用于构造函数初始化）
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 保存ArrayList实际保存的值
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList大小
*/
private int size;
...
}
ArrayList构造函数
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
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;
}
}
构造函数只是对elementData 进行初始化。
添加元素
添加元素有4个方法，源码如下：
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
//检验是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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++;
}
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;
}
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
//索引越界校验
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
//检验是否需要扩容
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
//移位操作
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//复制元素
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
| 方法 | 索引越界检验 | 扩容检验(伴随扩容操作) | 移位操作 |
|---|---|---|---|
| add(E e) | No | Yes | No |
| add(int index, E element) | Yes | Yes | Yes |
| addAll(Collection<? extends E> c) | No | Yes | No |
| addAll(int index, Collection<? extends E> c) | Yes | Yes | Yes |
从上可知，不指定索引添加元素默认是添加在尾部，当指定索引（不是数据最后位置）添加元素存在移位操作，当元素过多的情况下性能较低，所以应尽量避免使用add(int index, E element)和addAll(int index, Collection<? extends E> c)方法。
扩容规则
//每当调用add操作时都会调用这个函数。首次调用minCapacity = 1
private void ensureCapacityInternal(int minCapacity) {
/**
*当调用默认构造函数ArrayList（）条件成立，所以初始大小为10
*/
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//当调用ArrayList(Collection<? extends E> c)和ArrayList(int initialCapacity)直接走这里
ensureExplicitCapacity(minCapacity);
}
//判断是否需要扩容：预期容量比现在的容量大就需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 预期容量比现在的容量大就需要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//实际的扩容操作
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//每次扩容大小为原有的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//当元素过多，扩容会出现堆溢出异常
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 扩容之后，需要进行复制操作
elementData = Arrays.copyOf(elementData, newCapacity);
}
由上可知：
1、当数据量少的时候尽量使用ArrayList()进行初始化；当数据量确定的时候使用ArrayList(int size)进行初始化，减少扩容次数。
2、当数据量多且不确定的时候使用ArrayList(int size)，选取适当size值，减少扩容次数。
fail-fast机制
fail-fast机制在遍历一个集合时，当集合结构被修改，会抛出Concurrent Modification Exception。
fail-fast会在以下两种情况下抛出ConcurrentModificationException
（1）单线程环境
集合被创建后，在遍历它的过程中修改了结构。
（2）多线程环境
当一个线程在遍历这个集合，而另一个线程对这个集合的结构进行了修改。
先来个HelloWorld实例
//初始化
ArrayList<Integer> list = new ArrayList<>();
//添加元素
for (int i = 0; i < 15; i++) {
list.add(i);
}
for (Integer i : list) {
if (i == 10) {
list.remove(i);
}
System.out.println(i);
}
执行结果：
0
1
2
3
4
5
6
7
8
9
10
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
at java.util.ArrayList$Itr.next(ArrayList.java:851)
at Main.main(Main.java:14)
我们继续查看ArrayList的Iterator()方法
public Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.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
//modCount是AbstractList的成员变量，默认值为0，当调用ArrayList的add、remove时修改值
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
//关键点，此处抛出ConcurrentModificationException异常
checkForComodification();
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();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
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();
}
//修改冲突检测
final void checkForComodification() {
//当在遍历的时候，存在增加、删除操作时就会导致modeCount != expectedModeCount成立
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
由此可知当发生ConcurrentModificationException异常时的解决办法：
1、单线程中在迭代器中如果要删除元素的话，需要调用Itr类的remove方法，因为Iterator的remove方法不会修改modCount值。
2、在多线程中在使用iterator迭代的时候使用synchronized或者Lock进行同步；使用并发容器CopyOnWriteArrayList代替ArrayList。
ArrayList如何优化？
1、通过上面的讲解，我们知道ArrayList性能瓶颈在于数据移位，当数据量较大时，移位操作耗时较长，所以当我们知道ArrayList需要存储大量数据时（例如：10W条），我们在初始化的时候就给定一个合理的值，减少在添加数据时的移位操作。
2、添加数据时在尾部添加，避免使用add(int index, E element)方法，减少移位操作。
