- 一、概述
- 二、源码解析
一、概述
ArrayList是实现了List接口的一个顺序存储的容器,允许存放null元素,底层通过数组实现,类内部没有实现同步,其余与vector大致相同,底层capacity表示数组实际的大小,当数组添加元素时,容量不足会触发自动扩容机制
二、源码解析
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;
底层数据结构为数组结构,大部分情况下第一次扩容的默认容量为10,size用来记录底层数组中实际存放的元素的个数
构造函数
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);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection extends E> c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
1.当构造函数参数为大于0整形参数时,会在底层创建一个整形参数长度大小的空数组并使elementData指向该引用,如果为0则指向已经在类中定义好的容量为0的空数组,如果小于0则会抛出异常
2.当构造函数为无参构造调用时,elementData指向已经在类中定义好的容量为10的数组引用
3.当构造函数参数为Collection接口下的容器时,会将该容器中的元素都存于数组之中,数组中元素个数不为0时,如果该容器为ArrayList容器,使elementData指向数组的引用,倘若为其他容器,进行数组复制的操作,如果容器元素为0,则使elementData指向一个容量为0的空数组
自动扩容
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 static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
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;
}
每当向数组中添加元素时,都要去检查添加后元素的个数是否会超出当前数组的长度,如果超出,数组将会进行扩容。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。
数组进行扩容时会新建数组,并将旧数组中的元素通过Arrays.copyOf的方法拷贝到新数组中,数组每一次扩容大约为旧数组容量的1.5倍(数组扩容通过位运算,未必为1.5倍)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
判断是否需要扩容,将元素放入数组末尾
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++;
}
如果index>size或index<0抛出异常,触发扩容机制, 创建一个新数组,索引之后元素全部后移,将元素复制到当前索引位置
set
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
索引检索并修改指定索引位置的值
get
public E get(int index) {
rangeCheck(index);
return 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;
}
通过数组复制将索引之后的元素向前移动一位,最后一位显式赋null使gc起作用



