吃透Java集合系列三：ArrayList
文章首发csdn博客地址：https://blog.csdn.net/u013277209?viewmode=contents
前言
本篇作为吃透Java集合系列第三篇，我们来看一下ArrayList，通过本篇我们要明白如下问题：
1、ArrayList扩容机制
2、ArrayList迭代器实现
3、fail-fast机制
4、ArrayList序列化反序列化机制
5、ArrayList clone实现
ArrayList内部是使用动态数组实现的，换句话说，ArrayList封装了对内部数组的操作，比如向数组中添加、删除、插入新的元素或者数据的扩展和重定向。
- 继承了AbstractList,此类提供 List 接口的骨干实现，以最大限度地减少实现”随机访问”数据存储（如数组）支持的该接口所需的工作.对于连续的访问数据（如链表），应优先使用 AbstractSequentialList，而不是此类。
- 实现了List接口,意味着ArrayList元素是有序的,可以重复的,可以有null元素的集合.
- 实现了RandomAccess接口标识着其支持随机快速访问,实际上,我们查看RandomAccess源码可以看到,其实里面什么都没有定义.因为ArrayList底层是数组,那么随机快速访问是理所当然的,访问速度O(1)。
- 实现了Cloneable接口,标识着可以它可以被复制.注意,ArrayList里面的clone()复制其实是浅复制。
- 实现了Serializable 标识着集合可被序列化。
一：ArrayList扩容机制
初始化：
ArrayList提供了三个构造函数来对elementData数组初始化：
无参构造函数：初始化一个空的数组，添加元素时再对数组elementData扩容。
指定容量的构造函数：直接初始化数组为指定的大小。
带有一个集合参数的构造函数：把指定集合中的数据通过Arrays.copyOf拷贝到elementData中，容量和指定集合容量相同。
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
//无参构造函数直接赋值一个空的数组
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
//指定大小的构造函数
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
//构造一个包含指定*集合的元素的列表。
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
扩容：
添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍。
扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
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;
}
二：ArrayList迭代器实现
如果对Iterable和Iterator接口不是很清楚的，请先移步到第一篇文章：
吃透Java集合系列一：Iterable和Iterator
ArrayList通过内部类实现Iterator接口来实例化迭代器类，通过Iterator我们可以实现对elementData中的元素迭代遍历。而ArrayList又实现了一种功能更为强大的ListIterator来实现迭代遍历。ListIterator继承于Iterator接口，对Iterator接口做了扩展，支持向前向后遍历、迭代过程中去修改集合等
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;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
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() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
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();
}
}
}
三： Fail-Fast机制
modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。
在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationException。如下例子
public static void main(String[] args) {
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
Iterator<Integer> iterator = list.listIterator();
while (iterator.hasNext()) {
Integer i = iterator.next();
if (i == 1) {
list.remove(i);
}
}
}
运行后会抛出异常：
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:886)
at java.util.ArrayList$Itr.next(ArrayList.java:836)
at MyTest.main(MyTest.java:12)
当我们调用list.remove的方法来删除元素后，此时modCount会+1，导致modCount和迭代器里面的expectedModCount 不相等，当遍历下一个元素调用next方法时，会先调用checkForComodification()方法，当expectedModCount！=modCount时会抛出ConcurrentModificationException，这就是Fail-Fast机制。
那我们要如何避免此问题呢？Iterator已经为我们提供了remove方法，所以我们只需要调用迭代器里面的remove方法就可以了，Iterator中的remove方法移除元素后会把modCount重写赋值给expectedModCount，下一个循环时expectedModCount与modCount相等就避免此问题。如下例子：
public static void main(String[] args) {
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
Iterator<Integer> iterator = list.listIterator();
while (iterator.hasNext()) {
Integer i = iterator.next();
if (i == 1) {
iterator.remove();
}
}
}
四： ArrayList序列化机制
我们看到ArrayList实现了Serializable接口，那么证明可以是被序列化的，但是elementData数组又被transient关键字修饰，我们知道被transient修饰的成员属性变量不被序列化，那么我们先看一个例子，ArrayList是否能被序列化成功呢？
public static void main(String[] args) throws IOException, ClassNotFoundException {
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
ObjectOutputStream objectOutputStream = new ObjectOutputStream(byteArrayOutputStream);
objectOutputStream.writeObject(list);
ByteArrayInputStream byteArrayInputStream = new ByteArrayInputStream(byteArrayOutputStream.toByteArray());
ObjectInputStream objectInputStream = new ObjectInputStream(byteArrayInputStream);
List<Integer> newList = (List<Integer>) objectInputStream.readObject();
System.out.println(Arrays.toString(newList.toArray()));
}
运行输出结果：
[1, 2, 3]
结果是序列化和反序列化成功？？这是为什么呢？
其实细心的我们在查看源码时发现，ArrayList重写了readObject和writeObject来自定义的序列化和反序列化策略。什么是自定义序列化和反序列化呢？
- 在序列化过程中，如果被序列化的类中定义了writeObject 和 readObject 方法，虚拟机会试图调用对象类里的 writeObject 和 readObject 方法，进行用户自定义的序列化和反序列化。
- 如果没有这样的方法，则默认调用是 ObjectOutputStream 的 defaultWriteObject 方法以及 ObjectInputStream 的 defaultReadObject 方法。
- 用户自定义的 writeObject 和 readObject 方法可以允许用户控制序列化的过程，比如可以在序列化的过程中动态改变序列化的数值。
那么我们来看一下ArrayList源码是怎么来自定义序列化和反序列化的：
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
可以看到通过writeObject方法和readObject方法来遍历elementData数组把数组中的元素写入ObjectOutputStream ，ObjectInputStream 中的。那么为什么ArrayList要用这种方式来实现序列化呢？
ArrayList实际上是动态数组，每次在放满以后自动增长设定的长度值，如果数组自动增长长度设为100，而实际只放了一个元素，那就会序列化99个null元素。为了保证在序列化的时候不会将这么多null同时进行序列化，ArrayList把元素数组设置为transient。
五： ArrayList clone机制
ArrayList的clone实现，其实是通过数组元素拷贝来实现的浅拷贝，很简单，我们看一下源码就行了：
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
