ArrayList源码分析
[TOC]
1. 概述
为了弥补普通数组无法自动扩容的不足, Java提供了集合类, 其中ArrayList就对数组进行了封装, 使其可以自动的扩容或缩小长度.
因为是对数据进行了封装, 所以底层存储结构是数组结构. 可以想象的到, 数组长度的自动变化必须需要开辟新内存, 然后进行数组元素的拷贝.
因为数组, 所以ArrayList也就具有数组的一些性, 如支持随机访问.
2. 存储结构
第一节已经说了, 它是一种自动数组, 内部存储结构就是数组了.
Object[] elementData;
3. 构造方法
先从构造方法开始分析.
3-1. 无参构造方法
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}注释说, 构造一个容量为10的空的list.
但是这里我们并没有看到数组的容量变为10, 而是一个空的数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA.
那么什么时候会被初始化为10的数组呢？答案是有元素被加入时(add方法).
3-2. 带有初始化容量的构造方法
/**
* 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);
}
}这个就比无参构造方法清晰多了, 直接建立一个initialCapacity大小的数组.
3-3. 带有初始化元素的构造方法
/**
* 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;
}
}这里的意思传入一个集合类(Collection的子类即可), 转为list.
Collection有一个子抽象类, 默认实现了toArray();, 如果子类比较特殊需要, 进行重写即可.
4. 集合的操作
集合类的重要功能就是进行交互(元素的存储、修改、删除、遍历等).
4-1. 添加
内部有四种方式的添加:
- 直接添加
- 指定位置添加
- 添加全部
- 在指定位置添加全部
4-1-1. 普通添加(在尾端添加元素)
因为是动态数组, 所以元素添加时需要校验数组空间是否足够, 如果不足, 需要进行数组的扩容(关于扩容看第5节).
源码如下:
/**
* 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;
}4-1-2. 指定位置添加
在指定位置添加, 必然会影响到该位置的元素以及后续元素, 对于数组这种数据结构, 只能进行元素的后移了.
这就体现出数组这种数据结构的不足了: 对元素的修改不太擅长.
同普通添加元素一样, 需要校验数组容量数组足够, 不过在校验之前还要检查一下入参的元素位置(index)是否在范围内.
然后进行数组元素的移动.
源码如下:
/**
* 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++;
}4-1-3. 添加一个集合中的全部元素
与构造方法类似, 这里也使用了toArray();
只不过需要进行数组大小的校验扩容, 然后进行元素拷贝.
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;
}4-1-4. 在指定位置添加一个集合中的全部元素
通过上面的说明, 这个方法就很容易懂了.
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;
}4-2. 修改
修改操作比较简单, 就是给数组的某个下标重新赋值.
只有一个方法: E set(int index, E element)
将指定位置上的元素进行更新, 会对index进行越界检查.
4-3. 删除
删除操作也意味着数组中会有元素移动, 除非删除的是最后一个元素.
删除方法有一下几个:
- E remove(int index)
- boolean remove(Object o)
- boolean removeAll(Collection<?> c)
- boolean retainAll(Collection<?> c)
4-3-1. 通过下标进行删除
删除指定位置上的元素, 如果删除的不是最后一个元素, 则要进行元素的移动.
public E remove(int index) {
rangeCheck(index); // 检查下标是否越界
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1; // 最后 -1 是为了数组下标不越界
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}4-3-2. 通过对象进行删除
删除数组中的某个元素, 会分为两种情况: null OR !null.
找到元素之后会使用fastRemove(index)进行删除.
源码如下:
// 删除成功返回true, 失败false
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
}4-3-3. 删除集合中的所有元素
传入一个集合c, 如果集合c中包含本集合中的元素, 则对改元素进行处理, 这里利用了一个complement属性, 来决定含有的元素是删除还是保留.
简单说一下批量删除/保留操作, 把匹配的元素(c.contains(elementData[r]) == complement)进行保留.
然后对不需要保留的下标赋予null值.
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
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++)
// 如果complement为false, 则c集合包含本集合中的元素, 则不进行操作, 这就是保留不属于c集合中的所有元素.
// 这就是 4-3-4. boolean retainAll(Collection<?> c)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}4-4. 查找
这部分就不贴源码了, 很容易理解.
查找可以分为两种情况:
- 通过下标直接定位元素
- 通过元素进行定位下标
包含的方法:
- boolean contains(Object o)
- int indexOf(Object o)
- int lastIndexOf(Object o)
- E elementData(int index)
- E get(int index)
contains(Object o)方法使用了indexOf(Object o)作为底层实现, 我们需要了解indexOf(Object o)的底层实现.
indexOf(Object o)是从数组的头开始查找, 查找到相同元素时, 进行返回, 而lastIndexOf(Object o)正好相反, 从数组的尾开始查找, 查找到相同元素时进行返回.
可以使用indexOf和lastIndexOf进行返回值的比较, 如果相等, 说明该元素在数组中唯一(前提是返回非-1).
elementData(int index)则是内部方法, 获取指定下标处的元素.
而get(int index)内部调用了element(int index), 调用之前会进行下标越界的校验.
4-5. 遍历
遍历分为三种方式:
- 普通for
- foreach
- iterator
至于三种方式的性能, 自己测试吧, 哈哈哈
重点: 只有某种情况下的普通for和iterator可以在循环的同事进行元素的删除.
例如:
普通for
// 该情况下不会发生异常
for (int i = 0; i < list.size(); i++) {
String s = list.get(i);
// do something...
list.remove(i);
}
// 这种情况会出现越界问题
int size = list.size();
for (int i = 0; i < size; i++) {
String s = list.get(i);
// do something...
list.remove(i);
}第一种情况下, for循环的终止条件会随着数组元素的移除不断的变化.
第二种情况下, for循环的种植条件不会变化.
foreach
for (String s : list) {
// do something...
list.remove(s);
}这种方式会发生ConcurrentModificationException, 因为ArrayList内部有一个属性为modCount, 每当数组中的元素发生变化是, 该数值会增1, 而foreach形式的循环编译后会变为
Iterator var2 = list.iterator();
while(var2.hasNext()) {
String s = (String)var2.next();
list.remove(s);
}这种形式. 因为ArrayList内部的Iterator也维护了一个属性expectedModCount来标识数组元素的变化, 初始化为modCount, 如果modCount与expectedModCount不一致的话, 就会抛出这个异常.
iterator
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
// do something...
iterator.remove();
}foreach时我们直接调用了list.remove(s);方法, 该方法只会改变modCount的值, 并不会改变expectedModCount的值, 相反, 使用Iterator提供的remove方法则会对两个值一起修改.
5. 扩容方式
首先记住一点: 每次会扩容原数组的 1.5倍(正常情况下).
非正常情况当前是两端的情况:
- 初始化时第一次扩容会扩容到初始化容量(DEFAULT_CAPACITY)
- 当容量达到最大值时不会遵循这个规律
扩容方式: 在每次添加新元素时, 会调用扩容代码, 扩容方式还是比较简单的. 只是进行了一些防止溢出的判断.
// 进行扩容调用
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算是使用 DEFAULT_CAPACITY 还是传入的 minCapacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 当使用 new ArrayList() 创建实例时, 数组的默认容量为10就是在这里产生的.
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
// 进行一次modCount的修改, 表示数组元素发生了变动
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// 防止元素溢出
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 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;
/**
* 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; // 获取旧数组长度
int newCapacity = oldCapacity + (oldCapacity >> 1); // 计算出新数组长度 oldCapacity + oldCapacity / 2.
if (newCapacity - minCapacity < 0) // 如果计算出的长度比传入的长度小, 则使用传入的长度作为新数组长度.
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果新数组长度比MAX_ARRAY_SIZE, 进行溢出的校验
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 进行数组的拷贝
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 如果minCapacity比MAX_ARRAY_SIZE大, 就取Integer.MAX_VALUE的值作为新数组长度, 否则使用MAX_ARRAY_SIZE
// 也就是传入的长度, 而非通过原数组计算出来的长度.
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}6. 总结
- ArrayList就是一个动态数组.
- ArrayList的扩容操作必然会进行内存的申请以及数组元素的拷贝.
- 实例化时尽可能的确定好数组中元素的数量, 避免发生扩容.
- 使用
List<E> subList(int fromIndex, int toIndex)时, 返回的不是ArrayList对象, 是SubList(ArrayList的内部类)对象, 但是操作的元素还是ArrayList的元素.