ArrayList 源码分析

用户头像
读钓
关注
发布于: 2020 年 05 月 24 日

本篇文章基于Java版本:1.8.0_91,代码中的注释不止是翻译,还带有一些自己的理解

点左侧目录按钮,可以查看本文目录

一、ArrayList类结构层次图





public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList继承AbstractList和实现了RandomAccess。对于支持随机访问的数据存储,可以继承AbstractList,而RandomAccess是一个标记接口,表名实现这个接口的集合,是支持快速随机访问的,官方还说,实现该接口的集合,使用for循环的方式获取数据for (int i=0, n=list.size(); i < n; i++)会优于用迭代器获取数据for (Iterator i=list.iterator(); i.hasNext();),该接口是Java集合框架的成员之一。

二、属性

/**
* 初始化默认容量。
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 指定该ArrayList容量为0时,返回该空数组。
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 当调用无参构造方法,返回的是该数组。刚创建一个ArrayList 时,其内数据量为0。
* 它与EMPTY_ELEMENTDATA的区别就是:该数组是默认返回的,而后者是在用户指定容量为0时返回。
*
* 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 = {};
/**
* 保存添加到ArrayList中的元素。
* ArrayList的容量就是该数组的长度。
* 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,当第一次添加元素进入ArrayList中时,数组将扩容值DEFAULT_CAPACITY。
*
* 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
/**
* ArrayList的实际大小(数组包含的元素个数)。
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;

需要注意的是elementData的访问权限是transient,ArrayList自定义了它的序列化(writeObject(java.io.ObjectOutputStream s))和反序列化(readObject(java.io.ObjectOutputStream s))方式。



三、构造方法

ArrayList(int initialCapacity)

/**
* 根据指定的初始化容量构造一个空列表
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list ArrayList的指定初始化容量
* @throws IllegalArgumentException if the specified initial capacity
* is negative 如果ArrayList的指定初始化容量为负。
*/
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);
}
}



ArrayList()

/**
* 构造一个初始容量为 10 的空列表。
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}



ArrayList(Collection<? extends E> c)

/**
* 构造一个包含指定 collection 的元素的列表,
* 这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
*
* 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
* 其元素将放置在此列表中的 collection
* @throws NullPointerException if the specified collection is null
* 如果指定的 collection 为空
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// c.toArray 返回类型不一定是Object[]
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}

使用Collection.toArray()方法,返回类型不一定是Object[],所以多加了一个判断,使用Arrays.copyOf(elementData, size, Object[].class)进行了转换。

四、核心方法

时间复杂度:O(1) 操作的数量为常数,与输入的数据的规模(n)无关。 O(n) 输入数据的规模(n)与操作的数量成正比。

4.1 get(int index)

/**
* 返回list中索引为index的元素
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* 需要返回的元素的索引
* @return the element at the specified position in this list
* list中索引为index的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
//越界检查
rangeCheck(index);
//返回索引为index的元素
return elementData(index);
}

越界检查:

/**
* 检查给出的索引index是否越界。
* 如果越界,抛出运行时异常。
* 这个方法并不检查index是否为负数:
* 如果下标为负数,它总是在访问数组之后立刻抛出 ArrayIndexOutOfBoundsException
*
* Checks if the given index is in range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 构造下标越界异常的详细信息。
* Constructs an IndexOutOfBoundsException detail message.
* Of the many possible refactorings of the error handling code,
* this "outlining" performs best with both server and client VMs.
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}

返回索引为index的元素

E elementData(int index) {
return (E) elementData[index];
}

4.2 add(E e)

/**
* 添加元素到list末尾。
* 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;
}

空间检查

//minCapacity 想要的最小容量
private void ensureCapacityInternal(int minCapacity) {
//当数组列表为空时
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//这里之所以用Math.max(),考虑到兼容addAll()方法
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
// 更改次数+1
modCount++;
// overflow-conscious code
// 这个判断是多余的,因为入参minCapacity总是大于elementData.length(见下图)
if (minCapacity - elementData.length > 0)
//扩容
grow(minCapacity);
}



扩容

/**
* 分派给arrays的最大容量
* 某些VM会在数组中保留一些头字。
* 尝试分配这个最大存储容量,可能会导致array容量大于VM的limit,最终导致OutOfMemoryError。
*
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 扩容,保证ArrayList至少能存储minCapacity个元素。
*
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
* 想要的最小容量
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
/**
* 扩容。第一次扩容为:在原有的容量基础上增加一半。
* 第一次扩容后,如果容量还是小于minCapacity,就将容量扩充为minCapacity。
* 如果扩容后的容量大于临界值,则进行大容量分配。
*/
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:
// 想要的最小容量(minCapacity)通常接近于数组列表的长度(见上图),所以下边的方式比较好
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 进行大容量分配:将容量扩大为Integer.MAX_VALUE
*/
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的最大元素个数为Integer.MAX_VALUE(2^31-1=2147483647);每次扩容时,使用Arrays.copyOf()方法,把旧数组copy到新数组里,所以使用ArrayList时,尽量避免数据的扩容。

4.3 add(int index, E element)

/**
* 在列表中的指定位置插入元素。
* 当前位置的元素和index之后的元素向后移一位(下标加1)。
*
* 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!!
//对数组进行复制处理,目的就是空出index的位置插入element,并将index后的元素位移一个位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//将元素插入到index位置,并把实际容量+1
elementData[index] = element;
size++;
}

越界检查

/**
* 越界检查的另一个版本,用在add()和addAll()方法
* A version of rangeCheck used by add and addAll.
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

空间检查、扩容

4.2 add(E e) 中的空间检查、扩容方法一样。

数组复制:arraycopy

System.arraycopy(Object src,  int  srcPos, Object dest, int destPos, int length)

/**
* 该方法用于从指定源数组中进行拷贝操作,可以指定开始位置,拷贝指定长度的元素到指定目标数组中
*
* @param src the source array. 源数组(要复制到目标数组中)
* @param srcPos starting position in the source array. 源数组中的起始位置
* @param dest the destination array. 目标数组
* @param destPos starting position in the destination data. 目标数组中的起始位置
* @param length the number of array elements to be copied. 源数组中要复制的长度
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);

使用native关键词修饰的方法,称为Java Native Interface(Java本地接口)。

4.4 remove(int index)

/**
* 删除list中位置为指定索引index的元素。
* 索引之后的元素向左移一位
*
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* 被删除的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
//检查索引是否越界
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
//删除指定元素后,需要左移的元素个数
int numMoved = size - index - 1;
//2 如果有需要左移的元素,就移动(移动后,该删除的元素就已经被覆盖了)
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//3 为了让GC起作用,必须显式的为最后一个位置赋null值
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}

remove(int index)方法中,如果删除的元素不是最后一个元素,则进行copy,如下图:

4.5 set(int index, E element)

/**
* 替换指定索引的元素
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
//检查索引是否越界
rangeCheck(index);
//记录被替换的元素
E oldValue = elementData(index);
//替换元素
elementData[index] = element;
//返回被替换的元素
return oldValue;
}



五、其他方法

5.1 remove(Object o)

/**
* 删除list中第一次出现的指定元素(如果存在)。
* 如果不存在,则不改变该集合。
* 更正式的说,是移除索引最小的指定元素(如果存在)。
* 返回true:如果集合包含被移除的元素(或者相当于,集合被改变了)
*
* @param o 被移除的元素
* @return <tt>true</tt> 如果集合包含被移除的元素
*/
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);
//为了让GC起作用,必须显式的为最后一个位置赋null值
elementData[--size] = null; // clear to let GC do its work
}

删除的原理见上图

5.2 clear()

/**
* 移除集合中所有的元素,调用此方法后集合会被置空。
*/
public void clear() {
modCount++;
// clear to let GC do its work 为了让GC起作用
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}

使用for循环置空集合中的每个元素

5.3 addAll(Collection<? extends E> c)

/**
* 按照指定集合的迭代器返回元素的顺序,将指定集合中的所有元素追加到列表的末尾。
*
* @param c 被添加到列表中的集合
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
//返回包含此集合中所有元素的数组
Object[] a = c.toArray();
int numNew = a.length;
//空间检查、扩容
ensureCapacityInternal(size + numNew); // Increments modCount
//把指定集合转化后的数组复制到elementData中(追加到末尾)
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}

addAll()会把指定集合中的所有元素追加到列表的末尾。

5.4 addAll(int index, Collection<? extends E> c)

/**
* 从指定位置,按照指定集合的迭代器返回元素的顺序,
* 将指定集合中的所有元素追加到列表的末尾。
* @param index 集合中第一个元素 将插入到列表中的索引为index的位置
* @param c 被添加到列表中的集合
*/
public boolean addAll(int index, Collection<? extends E> c) {
//越界检查 size - index >= 0
rangeCheckForAdd(index);
//返回包含此集合中所有元素的数组
Object[] a = c.toArray();
int numNew = a.length;
//空间检查、扩容
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
//如果不是插入到末尾
if (numMoved > 0)
//把index到末尾的元素复制到index + numNew后
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}

5.5 retainAll(Collection<?> c)

/**
* 仅保留该列表中包含在指定集合中的元素。
* 换句话说,从这个列表中删除指定集合中不包含的所有元素。
* >>保留两个集合中的交集
*
* @param c 包含要保留在此列表中的元素的集合
* @return {@code true} 如果列表因调用此方法而改变,则返回true
*/
public boolean retainAll(Collection<?> c) {
//判断不为空
Objects.requireNonNull(c);
//批量移除
return batchRemove(c, true);
}

批量移除或保存batchRemove()

/**
* 私有方法。用来批量移除或保存
* @return 如果列表因调用此方法而改变,则返回true
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// 即使c.contains()异常时,也能保持与AbstractCollection行为的兼容。
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// 为了让GC起作用,手动置空
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}

c.contains()异常时,finally中把没来得及用contains比较的元素,与比较后elementData[w]的元素放一起,把剩余的空位置置空,让GC回收。

5.6 removeAll(Collection<?> c)

/**
* 从这个列表中删除指定集合中包含的所有元素。
*
* @param c 包含要从列表中删除的元素的集合
* @return {@code true} 如果列表因调用此方法而改变,则返回true
*/
public boolean removeAll(Collection<?> c) {
//判断不为空
Objects.requireNonNull(c);
//批量删除
return batchRemove(c, false);
}

batchRemove(c, false)见【5.5 批量移除或保存batchRemove()】,通过控制布尔值complement达到了删除或保存的功能,方法抽象的套路只能学习。



重温ArrayList源码,发现了之前没注意到的点。编程就像写文章一样,首先需要多读别人怎么写代码,然后思考消化,变成自己的。

站在巨人的肩膀上,走的更远,共勉!



可以留言说下你阅读源码的感受,你的评论、在看、转发,都能让我高兴好久。

发布于: 2020 年 05 月 24 日 阅读数: 13
用户头像

读钓

关注

Java开发,专心练剑 2017.11.10 加入

公众号:读钓的YY,欢迎关注

评论

发布
暂无评论
ArrayList 源码分析