1、简介
ArrayList，它是List接口的一个实现类。底层是基于数组实现的，可以实现动态扩容，所以又称为动态数组。因为基于数组实现的，所以它继承了数组的优缺点。ArrayList是线程不安全的。
2、源码解析
1. 成员变量
//默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//指定ArrayList容量为0时，返回该空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//没指定ArrayList容量时，返回该空数组
DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//保存添加到ArrayList中的元素，当第一次添加时，数组扩容到DEFAULT_CAPACITY
transient Object[] elementData; // non-private to simplify nested class access
//ArrayList实际大小，长度（元素个数）
private int size;
2.构造器
定义ArrayList的方式
List<String> list = new ArrayList<>(10); //指定容量
List<String> list = new ArrayList<>(); //不指定容量
/**
* 含参构造器
* initialCapacity ：指定的ArrayList容量
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) { //指定容量为0，返回EMPTY_ELEMENTDATA数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 不含参构造器
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //返回DEFAULTCAPACITY_EMPTY_ELEMENTDATA
}
3、添加元素方法
与扩容有关的后面详说
3.1 add(E e)
/**
* 添加元素到ArrayList中，不指定位置，顺序添加
*/
public boolean add(E e) {
//扩容，先判断，需要就扩容，不需要就什么都不做
ensureCapacityInternal(size + 1); // Increments modCount!!
//添加元素
elementData[size++] = e;
return true;
}
3.1 add(int index, E e)
/**
* 在指定位置插入元素
* @param index 插入位置
* @param element 元素
*/
public void add(int index, E element) {
//检查插入位置是否越界，包含上越界和下越界，越界rangeCheckForAdd()方法抛异常
rangeCheckForAdd(index);
//扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//调用arraycopy，方法插入这是一个c/c++写的方法。
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//指定位置插入元素
elementData[index] = element;
size++;
}
4、移除元素
4.1 remove(int index)
/**
* 从列表中移除一个元素
*
* @param index 所要移除元素的位置
* @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;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将值设为null便于垃圾回收
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
5、获取元素
5.1 get(int index)
/**
* 根据索引获取元素
* @param 索引位置
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
//越界检查，只检查上越界
rangeCheck(index);
return elementData(index);
}
6、设置元素值
6.1 set(int index, E element)
/**
* 给指定位置设置元素值
* @param index 索引
* @param element 元素
* @return 该位置旧的值
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
//越界检查，只检查上越界
rangeCheck(index);
//获取旧值
E oldValue = elementData(index);
//设置新值
elementData[index] = element;
//返回旧值
return oldValue;
}
7、扩容
1.
在来看一下插入操作的代码。每次插入元素前都会进行扩容判断，那么就跟着ensureCapacityInternal(int minCapacity)这个方法来一步一步往下看ArrayList扩容原理
/**
* 添加元素到ArrayList中，不指定位置，顺序添加
*/
public boolean add(E e) {
//扩容，先判断，需要就扩容，不需要就什么都不做
ensureCapacityInternal(size + 1); // Increments modCount!!
//添加元素
elementData[size++] = e;
return true;
}
2、ensureCapacityInternal(int minCapacity)方法
传入ArrayList所需最小容量，调用ensureExplicitCapacity(int minCapacity)进行扩容
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
3.ensureExplicitCapacity(int minCapacity)
判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 最小容量大于数组长度，则执行扩容操作，否则什么都不做
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
4.calculateCapacity(Object[] elementData, int minCapacity)
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果创建ArrayList时为指定容量，则第一次添加时，判断最小扩容长度，避免浪费空间
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//不是第一次添加，返回最小容量
return minCapacity;
}
5.扩容操作
/**
* 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) {
// 获取原数组容量
int oldCapacity = elementData.length;
//获取扩容后数组容量，扩容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩容后数组容量不满足要求，将扩容后数组容量改为所需最小数组容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 扩容，调用Arrays.copyOf方法扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
6、扩容总结
1、判断ArrayList所需的最小容量。若是定义时为指定容量，则第一次扩容时，扩容量为10。
2、判断当前容量是否满足需求
3、当然容量满足需求时，不做任何操作。不满足需求时，按1.5倍扩容（此时还未扩容，只是计算出要扩容的量）。如果1.5倍仍不满足需求，则按所需最小容量扩容。
7、心得
- ArrayList是基于动态数组实现的，在增删时候，需要数组的拷贝复制。
- ArrayList的默认初始化扩容量是10，正常情况下每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍。
- 删除元素时不会减少容量，若希望减少容量则调用trimToSize()
- 它不是线程安全的。它能存放null值。
网友评论