java源码学习，四ArrayList
ArrayList是基于数组实现的，是一个动态数组，其容量能自动增长，类似于C语言中的动态申请内存，动态增长内存。
ArrayList不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类。
以下分析的是JDK1.8的ArrayList源码，跟JDK1.7的区别还是蛮大的。
一、定义
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
- 从ArrayList<E>可以看出它是支持泛型的，它继承自AbstractList，实现了List、RandomAccess、Cloneable、Java.io.Serializable接口
- AbstractList提供了List接口的默认实现（个别方法为抽象方法）
- List接口定义了列表必须实现的方法
- RandomAccess是一个标记接口，接口内没有定义任何内容,支持快速随机访问，实际上就是通过下标序号进行快速访问
- 实现了Cloneable接口的类，可以调用Object.clone方法返回该对象的浅拷贝
- 通过实现 java.io.Serializable 接口以启用其序列化功能。未实现此接口的类将无法使其任何状态序列化或反序列化。序列化接口没有方法或字段，仅用于标识可序列化的语义
二、属性
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
- ArrayList提供了2个私有属性，elementData和size；很容易理解，elementData存储ArrayList内的元素，size表示它包含的元素的数量（实际数量而非容量）
- transient关键字的作用：在采用Java默认的序列化机制的时候，被该关键字修饰的属性不会被序列化。
三、构造方法
ArrayList提供了三个构造方法：
// 带容量参数的构造方法
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 创建一个空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 参数小于0，抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// 默认无参构造方法，创建一个容量为10的数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 集合作为参数的构造方法，集合转化为Object[]
// c为null throws NullPointerException
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray 不一定返回的是Object[]
if (elementData.getClass() != Object[].class)
// 数组复制到 elementData
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// c的长度为0，创建容量为0的数组
this.elementData = EMPTY_ELEMENTDATA;
}
}
第一个构造方法使用initialCapacity来初始化elementData数组的大小；
第二个构造方法创建一个空的容量为10的elementData数组；
第三个构造方法将提供的集合转成数组并给elementData（返回若不是Object[]，则转换为Object[]）；
四、方法详细介绍
1. 元素存储
关于ArrayList元素的存储，提供了5个方法：
public E set(int index, E element)
public boolean add(E e)
public void add(int index, E element)
public boolean addAll(Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c)
set方法，替换元素
// 用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
// 检验index是否在范围内，不校验index为负数的情况，index为负数由数组校验
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 返回指定位置上的元素
E elementData(int index) {
return (E) elementData[index];
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
add(E e)方法，尾部添加元素
// 添加元素到列表的尾部，并返回true
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!（这注释还两感叹号）
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 若是默认容量为10，则minCapacity取minCapacity和DEFAULT_CAPACITY最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
// 记录容量扩容次数（Fast Fail机制，多线程）
protected transient int modCount = 0;
private void ensureExplicitCapacity(int minCapacity) {
// 扩容次数+1
modCount++;
// 若需要的容量大于目前elementData的容量，则进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// ArrayList容量的最大值（为啥是这个值设定？）
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 扩容到指定容量（有溢出处理）
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// oldCapacity >> 1相当于 oldCapacity / 2，则下面的就是扩容50%
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 若扩容50%还没到minCapacity，则扩容minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 扩容容量 大于最大容量（溢出处理）
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 扩容容量elementData
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // 溢出处理
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!!
// index后面的元素往后下标+1并复制到elementData
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 参数element赋值给指定位置的elementData
elementData[index] = element;
// 数组实际长度+1
size++;
}
// 校验索引下标范围（不能大于数组实际大小以及小于0，是就抛出异常）
// 方法用于 add 和 addAll
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
此方法是System类提供的native方法，用于copy数组所用
src:源数组； srcPos:源数组要复制的起始位置； dest:目的数组； destPos:目的数组放置的起始位置； length:复制的长度
此方法的功能就是把dest从destPos到destPos+length的元素用src数组的srcPos位置开始替换
arraycopy调用了系统的C/C++代码，在JDK中是看不到的，但在openJDK中可以看到其源码。该函数实际上最终调用了C语言的memmove()函数，因此它可以保证同一个数组内元素的正确复制和移动，比一般的复制方法的实现效率要高很多，很适合用来批量处理数组。Java强烈推荐在复制大量数组元素时用该方法，以取得更高的效率。
public class ArrayCopyTest { public static void main(String[] args) { char[] c1 = new String("123456").toCharArray(); char[] c2 = new String("abcdef").toCharArray(); System.arraycopy(c1,2 , c2, 1, 2); for(char c : c1){ System.out.print(c); } System.out.println(); for(char c : c2){ System.out.print(c); } } }结果为：
123456
a34def
addAll(Collection<? extends E> c)方法，尾部按顺序添加所有集合元素
// c为null 会抛出NullPointerException
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);// 数组copy
size += numNew;// elementData实际大小size增加
return numNew != 0;// 返回是否有新元素添加
}
addAll(int index, Collection<? extends E> c)方法，指定位置按顺序添加所有集合元素
// c为null 会抛出NullPointerException
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;
// elementData数组index后面的元素移动到elementData的末端
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 添加的集合c中的所有元素index到index+numNewcopy进来
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;// elementData实际大小size增加
return numNew != 0;// 返回是否有新元素添加
}
2. 元素读取
// 返回数组index所在的元素
public E get(int index) {
rangeCheck(index);// 校验index是否越界
return elementData(index);
}
// 检验index是否在范围内，不校验index为负数的情况，index为负数由数组校验
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 返回指定位置上的元素
E elementData(int index) {
return (E) elementData[index];
}
3. 元素删除
关于ArrayList元素的删除，提供了4个方法：
public E remove(int index)
public boolean remove(Object o)
public void clear()
public boolean removeAll(Collection<?> c)
public boolean retainAll(Collection<?> c)
remove(int index)方法，删除指定位置的元素
public E remove(int index) {
rangeCheck(index);// 校验index向上是否越界，越界则抛出异常
modCount++;// 扩容的时候++，删除也++，记录操作次数
E oldValue = elementData(index);// 获取指定位置的元素
int numMoved = size - index - 1;
// elementData index后面的元素向前移动一位
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// --size，elementData尾部元素置为null，GC可以回收
elementData[--size] = null;
return oldValue;// 返回已删除的元素
}
remove(Object o)方法，删除数组中第一个为o的元素
public boolean remove(Object o) {
// 遍历数组，删除第一个为null的元素并返回
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 遍历数组，删除第一个为o的元素（用equals判断）并返回
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
// 遍历结束还没有找到o，则返回false，elementData中元素没做任何变动
return false;
}
// 私有方法，快速删除index所在的元素，跟上面的remove方法大致逻辑一下，不返回已删除元素
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
}
clear()方法，删除列表中所有的元素
public void clear() {
modCount++;// 记录操作次数
// 遍历列表，每个元素都置为null，GC进行回收
for (int i = 0; i < size; i++)
elementData[i] = null;
// 列表size置为0
size = 0;
}
removeAll方法，删除传入参数集合中的所有元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);// 判断c是否为null，null抛出NullPointerException
// 删除集合中所有元素，这些元素也在c中，取elementData和c的差集即 elementData - c
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
// 新建一个不可变引用,指向List的 elementData数组
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
// 根据complement参数判断是否保留elementData[r]元素
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// c.contains() 抛出异常处理
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
// 下标size-w后面的元素置为空，gc回收；w=size则表示没有元素变动
if (w != size) {
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;// 相当于执行了多次remove操作
size = w;
modified = true;
}
}
return modified;// 返回elementData是否有元素变更
}
retainAll方法，删除非传入参数集合中的所有元素
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);// 判断c是否为null，null抛出NullPointerException
return batchRemove(c, true);
}
4. 序列化与反序列化
ArrayList的序列化重写了writeObject和readObject方法；
transient不被序列化
writeObject
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();// 调用默认的序列化方法
// 写入数组实际长度
s.writeInt(size);
// 真正的序列化操作
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
readObject
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();
}
}
}
5. 获取元素索引值
indexOf
// 返回列表中第一个与o相同的元素所在的索引；如果列表不包含o，则返回-1
public int indexOf(Object o) {
// o为null，返回列表中第一个为null元素的下标
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
lastIndexOf
// 返回列表中最后一个与o相同的元素所在的索引；如果列表不包含o，则返回-1
public int lastIndexOf(Object o) {
// 倒序遍历
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
contains
// 返回列表是否包含o元素，index = -1则返回false
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
6. ArrayList转化为数组
Object[] toArray()
public Object[] toArray() {
// 调用Arrays数组copy
return Arrays.copyOf(elementData, size);
}
**<T> T[] toArray(T[] a) ** 泛型转化
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
7. 其他方法
// elementData扩容后会有多余的容量未使用；把elementData的容量减少到size（实际容量）
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
// 返回列表实际大小size
public int size() {
return size;
}
// 返回列表是否为空
public boolean isEmpty() {
return size == 0;
}
// ArrayList 浅copy
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
// elementData copy
v.elementData = Arrays.copyOf(elementData, size);
// modCount操作次数
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
// protect方法 列表数组移除元素（fromIndex到toIndex）
// list.sublist(fromIndex, toIndex).clear()这个方法底层调用
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
// 获取元素列表迭代器
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
// 返回一个列表迭代器，FastFail机制
public ListIterator<E> listIterator() {
return new ListItr(0);
}
// 返回一个迭代器，FastFail机制
public Iterator<E> iterator() {
return new Itr();
}
// 截取列表
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
@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();
}
}
/**
* Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
* and <em>fail-fast</em> {@link Spliterator} over the elements in this
* list.
*
* <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
* {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
* Overriding implementations should document the reporting of additional
* characteristic values.
*
* @return a {@code Spliterator} over the elements in this list
* @since 1.8
*/
@Override
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
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();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
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++;
}
// 列表排序
@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++;
}
五、参考资料
http://blog.csdn.net/jzhf2012/article/details/8540410
http://www.cnblogs.com/xujian2014/p/4625346.html