ArrayList 源码解析

程序猿进阶 2024-09-18 10:35:01 阅读 54

<code>ArrayList是Java集合框架中的一个动态数组实现,提供了可变大小的数组功能。它继承自AbstractList并实现了List接口,是顺序容器,即元素存放的数据与放进去的顺序相同,允许放入null元素,底层通过数组实现。除该类未实现同步外,其余跟Vector大致相同。每个ArrayList都有一个容量capacity,表示底层数组的实际大小,容器内存储元素的个数不能多于当前容量。当向容器中添加元素时,如果容量不足,容器会自动增大底层数组的大小。

一、成员变量

在这里插入图片描述

<code>size(), isEmpty(), get(),set()方法均能在常数时间内完成,add()方法的时间开销跟插入位置有关,addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。为追求效率,ArrayList没有实现同步synchronized,如果需要多个线程并发访问,用户可以手动同步,也可使用Vector替代。

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

private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = { };

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };

transient Object[] elementData; // non-private to simplify nested class access

private int size;

}

【1】DEFAULT_CAPACITY:默认初始容量为10

【2】EMPTY_ELEMENTDATA:空数组实例,用于空实例。

【3】DEFAULTCAPACITY_EMPTY_ELEMENTDATA:默认容量为空数组实例。

【4】elementData:存储元素的数组。

【5】size:当前ArrayList中的元素数量。

二、构造方法

public ArrayList() {

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

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);

}

}

【1】无参构造方法:初始化elementData为默认容量的空数组。

【2】指定初始容量的构造方法:根据传入的初始容量创建数组。

三、添加元素

public boolean add(E e) {

ensureCapacityInternal(size + 1); // Increments modCount!!

elementData[size++] = e;

return true;

}

private void ensureCapacityInternal(int minCapacity) {

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

}

ensureExplicitCapacity(minCapacity);

}

private void ensureExplicitCapacity(int minCapacity) {

if (minCapacity - elementData.length > 0)

grow(minCapacity);

}

private void grow(int minCapacity) {

int oldCapacity = elementData.length;

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】add(E e):添加元素到ArrayList中。

【2】ensureCapacityInternal(size + 1):确保内部数组有足够的容量。

【3】elementData[size++] = e:将元素添加到数组中,并增加size

【4】ensureCapacityInternal(int minCapacity):检查并确保内部数组的容量。

【5】ensureExplicitCapacity(int minCapacity):如果需要,增加数组的容量。

【6】grow(int minCapacity):增加数组的容量,通常是原来容量的1.5倍。

四、获取元素

public E get(int index) {

rangeCheck(index);

return elementData(index);

}

private void rangeCheck(int index) {

if (index >= size)

throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

E elementData(int index) {

return (E) elementData[index];

}

【1】get(int index):获取指定索引处的元素。

【2】rangeCheck(index):检查索引是否越界。

【3】elementData(index):返回数组中指定位置的元素。

五、删除元素

public E remove(int index) {

rangeCheck(index);

modCount++;

E oldValue = elementData(index);

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

return oldValue;

}

【1】remove(int index):删除指定索引处的元素。

【2】rangeCheck(index):检查索引是否越界。

【3】System.arraycopy:将后续元素向前移动一位。

【4】elementData[--size] = null:将最后一个元素设为null,帮助垃圾回收。

六、大小调整

ArrayList的核心在于其动态调整大小的能力,通过grow方法来实现。当添加元素时,如果内部数组容量不足,就会创建一个更大的数组,并将旧数组中的元素复制到新数组中。

每当向数组中添加元素时,都要去检查添加后元素的个数是否会超出当前数组的长度,如果超出,数组将会进行扩容,以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前,我也可以使用ensureCapacity来手动增加ArrayList实例的容量,以减少递增式再分配的数量。数组进行扩容时,会将老数组中的元素重新拷贝一份到新的数组中,每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的,因此在实际使用时,我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时,要在构造ArrayList实例时,就指定其容量,以避免数组扩容的发生。或者根据实际需求,通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

/**

* Increases the capacity of this <tt>ArrayList</tt> instance, if

* necessary, to ensure that it can hold at least the number of elements

* specified by the minimum capacity argument.

*

* @param minCapacity the desired minimum capacity

*/

public void ensureCapacity(int minCapacity) {

int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)

// any size if not default element table

? 0

// larger than default for default empty table. It's already

// supposed to be at default size.

: DEFAULT_CAPACITY;

if (minCapacity > minExpand) {

ensureExplicitCapacity(minCapacity);

}

}

private void ensureCapacityInternal(int minCapacity) {

if (elementData == DEFAULTCAPACITY_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);

}

/**

* 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);

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;

}

在这里插入图片描述

七、总结

<code>Fail-Fast机制: ArrayList也采用了快速失败的机制,通过记录modCount参数来实现。在面对并发的修改时,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。